【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
  • ## 引言 最近發現自己喜歡用的 Todo 軟體總是差點意思,畢竟每個人的習慣和工作流不太一樣,我就想著自己寫一個小的[Todo 項目]( https://github.com/circler3/TodoTrack ),核心的功能是自動記錄 Todo 執行過程中消耗的時間(尤其面向程式員),按照自己 ...
  • ### 前言 當我們編寫 C# 代碼時,經常需要處理大量的數據集合。在傳統的方式中,我們往往需要先將整個數據集合載入到記憶體中,然後再進行操作。但是如果數據集合非常大,這種方式就會導致記憶體占用過高,甚至可能導致程式崩潰。 C# 中的`yield return`機制可以幫助我們解決這個問題。通過使用`y ...
  • 1. ADO.NET的前世今生 ADO.NET的名稱起源於ADO(ActiveX Data Objects),是一個COM組件庫,用於在以往的Microsoft技術中訪問數據。之所以使用ADO.NET名稱,是因為Microsoft希望表明,這是在NET編程環境中優先使用的數據訪問介面。 ADO.NE ...
  • 1. 為什麼需要單元測試 在我們之前,測試某些功能是否能夠正常運行時,我們都將代碼寫到Main方法中,當我們測試第二個功能時,我們只能選擇將之前的代碼清掉,重新編寫。此時,如果你還想重新測試你之前的功能時,這時你就顯得有些難為情了,因為代碼都被你清掉了。當然你完全可以把代碼寫到一個記事本中進行記錄, ...
  • 1. 透過現象看本質 反射被譽為是 c#中的黑科技 ,在很多領域中都有反射的身影,例如,我們經常使用的ORM框架,ABP框架 等。 反射指程式可以訪問、檢測和修改它本身狀態或行為的一種能力。. 程式集包含模塊,而模塊包含類型,類型又包含成員。. 反射則提供了封裝程式集、模塊和類型的對象。. 您可以使 ...
  • # Rust Web 全棧開發之 Web Service 中的錯誤處理 ## Web Service 中的統一錯誤處理 ### Actix Web Service 自定義錯誤類型 -> 自定義錯誤轉為 HTTP Response - 資料庫 - 資料庫錯誤 - 串列化 - serde 錯誤 - I/ ...
  • 在前面的幾篇文章中,詳細地給大家介紹了Java里的集合。但在介紹集合時,我們涉及到了泛型的概念卻並沒有詳細學習,所以今天我們要花點時間給大家專門講解什麼是泛型、泛型的作用、用法、特點等內容 ...
  • ###BIO:同步阻塞 主線程發起io請求後,需要等待當前io操作完成,才能繼續執行。 ###NIO:同步非阻塞 引入selector、channel、等概念,當主線程發起io請求後,輪詢的查看系統是否準備好執行io操作,沒有準備好則主線程不會阻塞會繼續執行,準備好主線程會阻塞等待io操作完成。 # ...
  • 摘要:在讀多寫少的環境中,有沒有一種比ReadWriteLock更快的鎖呢?有,那就是JDK1.8中新增的StampedLock! 本文分享自華為雲社區《【高併發】高併發場景下一種比讀寫鎖更快的鎖》,作者: 冰 河。 什麼是StampedLock? ReadWriteLock鎖允許多個線程同時讀取共 ...
  • ## 併發與並行😣 ### 併發與並行的概念和區別 並行:同一個時間段內多個任務同時在不同的CPU核心上執行。強調同一時刻多個任務之間的”**同時執行**“。 併發:同一個時間段內多個任務都在進展。強調多個任務間的”**交替執行**“。 ![](https://img2023.cnblogs.co ...