【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
  • 通過WPF的按鈕、文本輸入框實現了一個簡單的SpinBox數字輸入用戶組件並可以通過數據綁定數值和步長。本文中介紹了通過Xaml代碼實現自定義組件的佈局,依賴屬性的定義和使用等知識點。 ...
  • 以前,我看到一個朋友在對一個系統做初始化的時候,通過一組魔幻般的按鍵,調出來一個隱藏的系統設置界面,這個界面在常規的菜單或者工具欄是看不到的,因為它是一個後臺設置的關鍵界面,不公開,同時避免常規用戶的誤操作,它是作為一個超級管理員的入口功能,這個是很不錯的思路。其實Winform做這樣的處理也是很容... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他的程式每次關閉時就會自動崩潰,一直找不到原因讓我幫忙看一下怎麼回事,這位朋友應該是第二次找我了,分析了下 dump 還是挺經典的,拿出來給大家分享一下吧。 二:WinDbg 分析 1. 為什麼會崩潰 找崩潰原因比較簡單,用 !analyze -v 命 ...
  • 在一些報表模塊中,需要我們根據用戶操作的名稱,來動態根據人員姓名,更新報表的簽名圖片,也就是電子手寫簽名效果,本篇隨筆介紹一下使用FastReport報表動態更新人員簽名圖片。 ...
  • 最新內容優先發佈於個人博客:小虎技術分享站,隨後逐步搬運到博客園。 創作不易,如果覺得有用請在Github上為博主點亮一顆小星星吧! 博主開始學習編程於11年前,年少時還只會使用cin 和cout ,給單片機點點燈。那時候,類似async/await 和future/promise 模型的認知還不是 ...
  • 之前在阿裡雲ECS 99元/年的活動實例上搭建了一個測試用的MINIO服務,以前都是直接當基礎設施來使用的,這次準備自己學一下S3相容API相關的對象存儲開發,因此有了這個小工具。目前僅包含上傳功能,後續計劃開發一個類似圖床的對象存儲應用。 ...
  • 目錄簡介快速入門安裝 NuGet 包實體類User資料庫類DbFactory增刪改查InsertSelectUpdateDelete總結 簡介 NPoco 是 PetaPoco 的一個分支,具有一些額外的功能,截至現在 github 星數 839。NPoco 中文資料沒多少,我是被博客園群友推薦的, ...
  • 前言 前面使用 Admin.Core 的代碼生成器生成了通用代碼生成器的基礎模塊 分組,模板,項目,項目模型,項目欄位的基礎功能,本篇繼續完善,實現最核心的模板生成功能,並提供生成預覽及代碼文件壓縮下載 準備 首先清楚幾個模塊的關係,如何使用,簡單畫一個流程圖 前面完成了基礎的模板組,模板管理,項目 ...
  • 假設需要實現一個圖標和文本結合的按鈕 ,普通做法是 直接重寫該按鈕的模板; 如果想作為通用的呢? 兩種做法: 附加屬性 自定義控制項 推薦使用附加屬性的形式 第一種:附加屬性 創建Button的附加屬性 ButtonExtensions 1 public static class ButtonExte ...
  • 在C#中,委托是一種引用類型的數據類型,允許我們封裝方法的引用。通過使用委托,我們可以將方法作為參數傳遞給其他方法,或者將多個方法組合在一起,從而實現更靈活的編程模式。委托類似於函數指針,但提供了類型安全和垃圾回收等現代語言特性。 基本概念 定義委托 定義委托需要指定它所代表的方法的原型,包括返回類 ...