【golang】分散式緩存 - lru演算法實現

来源:https://www.cnblogs.com/freeyw/archive/2022/08/05/16554128.html
-Advertisement-
Play Games

前言 最近複習操作系統,看到了lru演算法,就去網上搜索下,因此發現了GeeCache,順手寫了一遍。研究下lru演算法的實現。 正文: lru使用map+鏈表實現。map裡面存儲了key以及其對應的鏈表節點。當我們根據某個key訪問緩存值的時候,可以經過map快速定位到該鏈表節點。從而獲取值 下麵我們 ...


前言

  最近複習操作系統,看到了lru演算法,就去網上搜索下,因此發現了GeeCache,順手寫了一遍。研究下lru演算法的實現。

正文:

  lru使用map+鏈表實現。map裡面存儲了key以及其對應的鏈表節點。當我們根據某個key訪問緩存值的時候,可以經過map快速定位到該鏈表節點。從而獲取值

下麵我們來看下它的具體實現:

首先,我們可以考慮下lru的結構:

  1.map

  2.鏈表

  3.占用的記憶體大小

  4.最大記憶體

type Cache struct {
	maxBytes  int64
	nbytes    int64
	ll     *list.List
	cache  map[string]*list.Element
}

添加key:

lru演算法的思想是經常訪問的元素移動到隊頭,不常訪問的元素移動到隊尾。從而進行淘汰隊尾元素。

當我們添加的key已經存在的時候,我們只需要更新其對應的值即可。

不存在的時候,需要插入鏈表和map

如果記憶體已經不夠,我們需要開啟淘汰演算法

func (c *Cache) Add(key string,value Value)  {
	if v,ok := c.cache[key]; ok{
	//	 移動到常用元素 --> 隊頭
		c.ll.MoveToFront(v)
	//   獲取舊值
		kv := v.Value.(*entry)
		c.nbytes += int64(value.Len()) - int64(kv.value.Len())
	// 更新值
		kv.value = value
	}else{
		ele := c.ll.PushFront(&entry{key,value})
		c.cache[key] = ele
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	if c.maxBytes != 0 || c.maxBytes < c.nbytes{
    //  淘汰演算法
		c.RemoveOldest()
	}
}

  下麵我們來看淘汰演算法:

    在鏈表中移除隊尾的元素,刪除map中相應的key

func (c *Cache) RemoveOldest()  {
    ele := c.ll.Back()
    if ele != nil {
        c.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(c.cache,kv.key)
        c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
    }
}

根據key獲取緩存中元素就簡單了,根據map定位到鏈表元素即可:

func (c *Cache) Get(key string)(value Value,ok bool)  {
	if ele,ok := c.cache[key];ok {
		c.ll.PushFront(ele)
		kv := ele.Value.(entry)
		return kv.value,true
	}
	return
}

  

lru演算法在GeeCache中的實現還是挺好理解的。記錄下~

 

| 不驕不躁,保持學習




您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 前言 之前也瞭解到過一致性哈希演算法,但是沒有用go實現過,剛好最近看GeeCache,動手實現下一致性哈希演算法 正文: 我們先來想下一致性哈希演算法的數據結構含有哪些內容: 1.map 用來存儲虛擬節點對應的真實節點,是一個映射表 2.hash 哈希函數 3.key 哈希環,存儲所有虛擬節點 4.re ...
  • 前言 最近在學習C++的類如何構造,在W3Cschool上看到關於拷貝構造函數的一個例子,記錄一下。 案例背景 這篇文章大致是構造瞭如下的一個Line類: class Line{ public: int getLength(void); Line(int len); // 簡單構造函數 Line(c ...
  • JPA是Java Persistence API的簡稱,中文名Java持久層API,是JDK 5.0註解或XML描述對象-關係表的映射關係,並將運行期的實體對象持久化到資料庫中。 ...
  • 用Python來繪製自己的個人足跡地圖, 精確到市級別。 首先我們需要安裝以下Python的第三方模塊: echarts-china-cities-pypkg==0.0.9 echarts-china-provinces-pypkg==0.0.3 pyecharts==1.6.2 PyYAML==5 ...
  • 問題背景 大家看看這個頁面,有沒有發現什麼問題? 主頁:http://www.javastack.cn/ 是的,頁面 CSS 樣式全丟失了,導致頁面混亂。。 這個頁面是我人為刪除了樣式(為了演示),真正出現問題是另外一個頁面,最近棧長髮現有個頁面時不時就會出現樣式錯亂的問題,很詭異!! 於是這篇就記 ...
  • JProfiler 是一個功能強大的工具,您可以使用它以動態方式分析基於 Java 的應用程式,並使您能夠分析它們以優化性能。當您配置文件時,您需要最強大的工具。同時,您不想花時間學習如何使用該工具。JProfiler 就是這樣:既簡單又強大。 Mac版詳情:JProfiler 13 for Mac ...
  • 雙向鏈表與數據結構 引言 在上小節中 我們分析了ArrayList的底層實現, 知道了ArrayList底層是基於數組實現的,因此具有查找修改快而插入、刪除慢的特點 本章我們介紹的LinkedList是List介面的另一種實現 它的底層是基於雙向鏈表實現的 因此它具有插入、刪除快而查找修改慢的特點 ...
  • 大家好,我是Mic,一個工作了14年的Java程式員。 最近很多小伙伴私信我,讓我說一些線程池相關的問題。 線程池這個方向考察的點還挺多的,如果只是靠刷面試題 面試官很容易就能識別出來,我隨便舉幾個。 線程池是如何實現線程的回收的 核心線程是否能夠回收 當調用線程池的shutdown方法,會發生什麼 ...
一周排行
    -Advertisement-
    Play Games
  • 前言 JSON Web Token(JWT)是一個非常輕巧的規範。這個規範允許我們使用 JWT 在用戶和伺服器之間傳遞安全可靠的信息。一個 JWT 實際上就是一個字元串,它由三部分組成,頭部、載荷與簽名。前兩部分需要經過 Base64 編碼,後一部分通過前兩部分 Base64 編碼後再加密而成。針對 ...
  • 一:背景 1. 講故事 今天本來想寫一篇 非托管泄露 的生產事故分析,但想著昨天就上了一篇非托管文章,連著寫也沒什麼意思,換個口味吧,剛好前些天有位朋友也找到我,說他們的拍攝監控軟體卡死了,讓我幫忙分析下為什麼會卡死,聽到這種軟體,讓我不禁想起了前些天 在程式員桌子上安裝監控 的新聞,參考如下: 我 ...
  • 文章目錄 介紹 ABP的依賴註入系統是基於Microsoft的依賴註入擴展庫(Microsoft.Extensions.DependencyInjection nuget包)開發的。所以我們採用dotnet自帶的註入方式也是支持的。 由於ABP是一個模塊化框架,因此每個模塊都定義它自己的服務併在它自 ...
  • 前言 外觀模式,英文名稱是:Facade Pattern。我們先從名字上來理解一下“外觀模式”。我看到了“外觀”這個詞語,就想到了“外表”這個詞語,兩者有著很相近的意思。就拿談戀愛來說,“外表”很重要,如果第一眼看著很舒服、有眼緣,那就有交往下去的可能。如果長的“三寸釘、枯樹皮”,估計就夠嗆了。在這 ...
  • 模擬.NET實際應用場景,綜合應用三個主要知識點:一是使用dnSpy反編譯第三庫及調試,二是使用Lib.Harmony庫實現第三庫攔截、偽造,三是實現同一個庫支持多版本同時引用。 ...
  • 通過strimzi部署的kafka集群,如何部署prometheus+grafana去監控呢?官方文檔信息量太大,即便照著做也可能失敗,這裡有一份詳細的保姆級操作指南,助您成功部署監控服務 ...
  • 在工具類中封裝getBean,使用哪個介面來實現 實事上,在工具類中,實現BeanFactoryPostProcessor和ApplicationContextAware介面後,使用它們構造方法里的對象ConfigurableListableBeanFactory和ApplicationContex ...
  • 1章:系統基礎信息模塊詳解 通過第三方模塊獲取伺服器的基本性能、塊設備、網卡介面、網路地址庫等信息。 1.1 系統性能模塊psutil:獲取系統性能信息、記憶體信息、磁碟信息、網路信息、用戶信息等。 1.2 IP地址處理模塊IPy: 處理IP地址,網段等。 1.3 DNS處理模塊dnspython: ...
  • EasyExcel動態表頭導出(支持多級表頭) 在很多業務場景中,都會應用到動態表頭的導出,也會涉及到多級表頭的導出,如下圖所示 通過EasyExcel,我們可以快速實現這一需求,具體代碼如下 DynamicHeader import java.util.List; /** *@Author: <a ...
  • 基於java線上婚紗定製系統設計與實現,可適用於線上婚紗攝影預定系統,基於web的婚紗影樓管理系統設計,基於web的婚紗影樓管理系統設計,婚紗攝影網系統,婚紗攝影網站系統,婚紗攝影網站系統,婚紗系統,婚紗管理系統等等; ...