當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

单机 “5千万以上“ 工业级 LRU cache 实现

發布時間：2023/11/27 生活经验 36 豆豆

生活随笔收集整理的這篇文章主要介紹了单机 “5千万以上“ 工业级 LRU cache 实现小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

- 前言
- 工業級 LRU Cache
- - 1. 基本架構
  - 2. 基本操作
  - - 2.1 insert 操作
    - 2.2 高并發下 insert 的一致性/性能保證
    - 2.3 Lookup操作
    - 2.4 shard 對 cache Lookup 性能的影響
    - 2.4 Erase 操作
    - 2.5 內存維護
  - 3. 優化

前言

近期做了很多 Cache 優化相關的事情，因為對存儲引擎較為熟悉，所以深入研究了 Rocksdb 的Cache實現，可以說是樸實無華得展示了工業級Cache的細節，非常精彩。

欣賞實現的同時做了一些簡單的代碼驗證，同時將整個 Cache 的實現做了一番梳理，發現真實處處都是設計，基本的算法實現只是最基礎的能力，如何設計實現的每一個細節與我們的cpu cacheline 運行體系綁定，如何實現insert/lockup 鏈路中的無鎖，如何不影響性能的基礎上保持對Cache的內存控制，如何讓頻繁的內存分配和釋放不是cache的性能瓶頸… 等等都是需要非常多的設計。

本篇及下一篇將主體介紹兩種 Rocksdb 實現的高性能工業級 Cache中的LRUCache 和 ClockCache。
相關的Cache 實現代碼以及通用的cache_bench 工具已經單獨摘出來，并在其上補充了一些更好展示cache內部狀態的功能，代碼路徑：https://github.com/BaronStack/Cache_Bench。
編譯運行：

# 1. 編譯
sh build.sh ; 
# 2. 執行壓測
./cache_bench -threads=32 \
-lookup_percent=100 \
-erase_percent=0 \
-insert_percent=0 \
-num_shard_bits=10 \
-cache_size=2147483648 \
-use_clock_cache=false # 使用的是 LRU Cache# 3. 輸出
Number of threads   : 32
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 10
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 0%
Lookup percentage   : 100%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 0.670 s; QPS = 57348698

整體介紹整個 Cache 體系實現之前，我們先思考一下我們的生產環境對Cache 的功能/性能需求：

Cache的讀性能至關重要，Cache的存在大多數是為了彌補我們熱點低延時需求的場景下的高昂I/O代價，所以高性能的讀一定是必要的，良好的數據結構的選型是關鍵，且要優于從page-cache讀，不然我們干嘛需要單獨的cache，直接存在page-cache得了（不考慮內存占用問題）。
高并發場景下需要保證Cache的可靠性。比如，我們多線程下insert的時候需要保證cache數據結構更新的原子性。這里的更新包括insert/erase。所以在更新鏈路上可能需要加鎖，如何解決鎖引入的 CPU 上下文切換的代價？
友好的內存控制功能。我們的線上機器往往不是一個服務在運行，為了防止內存無止境的消耗引發操作系統的OOM或者其他服務的swap ，則需要對當前服務的Cache所占用的內存進行限制。這個時候，怎樣盡可能得保證可能得熱點長期存在于Cache之中，則需要我們重點關注。
一些邊緣功能的實現。更高效的分配器選型，cache的insert/erase 會涉及到非常頻繁的內存操作，如何保證在復雜的workload場景（key-value大小差異非常大，幾個byte 到幾 M；頻繁的插入和Erase）能夠對Cache拿到的內存有一個高效的管理，在對分配器底層有足夠了解的情況下選擇合適的分配器能夠起到加速cache使用的作用。

綜合來看，一個工業級高效Cache的實現是需要深入理解數據結構、操作系統的CPU子系統、內存子系統的實現才能保證最終的產出是高效合理滿足工業級需求的。

限于作者能力有限，希望能在有限的能力基礎上為大家展示更多的實現細節，一起品鑒，如有不足，麻煩一定指正。

工業級 LRU Cache

介紹 Rocksdb 對LRU cache的改造之前，先概覽一下 LRU cache，顧名思義，LRU（Least recently used），近期使用最少的緩存單元將會被優先淘汰。
關于LRU的基本算法實現，網上介紹的太多了，基礎的鏈表就能夠滿足針對LRU的插入/刪除/查找了，這里就不做過多的展開了。我們直接進入正題，也就是Rocksdb 的LRU Cache如何在滿足以上那幾個需求的過程中針對LRU 做了哪一些改造。

1. 基本架構

先看一下整體的LRU Cache的架構：

是不是看起來和基本的LRU 實現有很大的差異，先整體介紹一下整個架構中每一個組件的作用，后續將詳細介紹這幾個組件是為了解決需求中的什么問題而引入的：

shard。我們可以看到，整個LRU cahce 從外部來看是一個個分開的shard，每一個shard內部才是真正的lru cache的底層實現。上層的用戶請求在進入cache操作之前會先經過hash映射到預先創建好的一個個shard中，然后才是針對每個cache內部的操作。
HashTable。這個組件是為了加速shard內部 lru cache查找的，將要操作的key進行hash生成唯一的一個hash值，這個key的操作將落在某一個hash-bucket之中，通過單鏈表來解決hash沖突。每次針對hash表的鏈表插入都會采用頭插法，保證越新的key將采越靠近bucket頭部。
High pri pool / Low pri pool。高優先級緩存池和低優先級緩存池是主體的Cache部分，也就是 LRU 維護數據的主體部分。lru_是高優先級pool的head，也是整個cache的head，所有高優先級的entry的插入都先插入到lru頭部。low-pri 是低優先級pool的尾部，所有針對低優先級pool的更新也都會插入到low-pri的尾部。從上圖可以看到，高優先級pool的尾部和低優先級pool的尾部相接，這樣從整個lru_鏈表來看，lru的prev就是整個lru-cache的最新的元素，lrv的next就是lru-cache的最舊的元素。

2. 基本操作

針對Cache的幾個基本操作包括如下幾種：

 virtual bool Insert(const Slice& key, uint32_t hash, void* value,size_t charge,void (*deleter)(const Slice& key, void* value),Cache::Handle** handle,Cache::Priority priority) override;virtual Cache::Handle* Lookup(const Slice& key, uint32_t hash) override;virtual bool Ref(Cache::Handle* handle) override;virtual bool Release(Cache::Handle* handle,bool force_erase = false) override;virtual void Erase(const Slice& key, uint32_t hash) override;

更細粒度的一些數據結構的指標如下，能夠直接將Cache 擁有的內部結構暴漏出來：
每一個cache entry 維護了一個 LRUHandle，可以看作是用來標識一個key-value

struct LRUHandle {void* value; void (*deleter)(const Slice&, void* value);LRUHandle* next_hash;LRUHandle* next;LRUHandle* prev;size_t charge;  // TODO(opt): Only allow uint32_t?size_t key_length;// The hash of key(). Used for fast sharding and comparisons.uint32_t hash;// The number of external refs to this entry. The cache itself is not counted.uint32_t refs;enum Flags : uint8_t {// Whether this entry is referenced by the hash table.IN_CACHE = (1 << 0),// Whether this entry is high priority entry.IS_HIGH_PRI = (1 << 1),// Whether this entry is in high-pri pool.IN_HIGH_PRI_POOL = (1 << 2),// Wwhether this entry has had any lookups (hits).HAS_HIT = (1 << 3),};uint8_t flags;char key_data[1];

其中主體部分包括：

key_data: 實際插入的key數據部分
value: 實際的value數據
deleter ，是一個回調函數，用來清理ref=0, in-cache=false的key-value
next_hash，是hashtable 中解決hash沖突的單鏈表
next/prev: hpri, lrpi 中的雙向鏈表
charge，表示當前handle的大小
hash，當前key的hash值，主要被用做hash-table/ high/low pool 中的key的查找，用來標識唯一key
refs, key被引用的次數
flags, 其四個字節分別被枚舉類型 Flags 中的四個標識來用。這四個標識，將用來決定一個 LRUHandle 應該存儲于哪里。

前面提到我們的shard cache 為了加速查找性能，引入了 hashtable，基本的table 數據結構可以參考LRUHandleTable。

每一個 shard 則維護了這個 Cache 的內部信息，通過如下數據結構能夠更直觀得看到 Cache 的內部情況。

  // Initialized before use.size_t capacity_;......LRUHandle lru_;LRUHandle* lru_low_pri_;LRUHandleTable table_;size_t usage_;size_t lru_usage_;......
};

capacity。當前shard的初始容量，我們外部配置的LRU cache大小會被均分到多個cache shard中
lru_。高優先級pool的雙向循環鏈表的表頭，也是整個lru 鏈表的表頭。
lru_low_pri。低優先級pool，總是指向低優先級pool的鏈表頭。
table_。 hashtable 。
usage_。整個shard 當前的使用總容量，包含lru_usage_的容量。
lru_usage_。兩個pool中的鏈表使用容量。

大體的shard 以及 shard內部數據結構就介紹這么多，下來我們從一些基礎的操作來看看整個 shard 內部的狀態。

2.1 insert 操作

了解LRU Cache最直接的辦法就是從Insert 中來看，insert 會涉及針對每一個組件的操作，同時會夾雜著cache 滿之后的數據淘汰過程，這也是Cache的算法基礎體現。

最開始的Cache中沒有任何數據，我們初始化cache的一些配置如下：

ps: 這里的capacity實際是當前shard cache的大小，單位是bytes, 這里的5 是為了后續說明整個插入過程而用一種有歧義的方式來表示，可以看作是當前shard中能夠保存多少個key-value的entry個數。

那么初始化之后的cache 情況如下：

hashtable 只有在有key的時候才會動態初始化填充。
high pri pool 根據初始時設置的cache 比例，將會初始化為capacity 為 4，且對雙向循環鏈表進行初始化。
low pri pool 則直接取 high 剩下的容量。

當我們插入一條enry的時候，經過對key的hash 可以知道這個key將落在哪一個shard，后續的操作都將針對這個shard來進行，接下來我們看看一條 key 在shard cache內部的數據流：
第一次插入的時候需會同步在hashtable 和 high-pool和之中，同時設置count 為0.

high pool 有充足的容量之前的插入都會先插入到highpool之中，如果high pool滿了，會將high pool中最舊的數據淘汰到low pool之中。

則在shard cache中的插入過程如下：

key在選擇指定shard 操作之前會做一次hash, 帶著這個hash值操作接下來的shard。

首先是更新hashtable，拿著這個hash值通過 hash & (length_ - 1) 選擇對應的hash-bucket，并采用頭插法插入到這個bucket后的單鏈表中。
其次更新high pool 或者 low pool。判斷初始參數設置的high pool的比例是否大于0，以及當前pool 是否未滿，如果是則優先更新high pool，否則更新low pool。所以會先采用頭插法，插入到lru_頭部（高優先級 pool）。

第二次的插入也是類似的。

后續的插入針對hash-table 的更新以及 lru_ 鏈表的更新都是采用頭插法。
當high pool 插滿之后，則需要將high pool最舊的元素插入到 low pool之中，這個時候就需要將low_pri的指針放在high pool的末尾了。

Ban 這個字符串需要插入到high pool的時候發現滿了，插入還是會先插入到high pool的頭部，但是low-pri指針需要需要向后移動一次，low-pri的next 直接指向的是high pool的末尾元素。
此時，在high-pool之中，頭指針的lru_.prev指向的是最新的key，lru_.next指向的是最舊的key。

此時我們可以看到當前的shard-cache已經滿了，那后續的insert將是什么樣的行為呢，再插入一條key看看。

主體主要是兩個步驟：

嘗試插入新的key Ted之前，會先檢測插入后的容量是否超過capacity。這里顯然是超過了，會出發cache evict，即從cache中移除最舊的一條key，顯然就是lru.next指向的 abc了。現將abc 從hashtable 中移除，同時在其ref count為0的時候從lru-list中移除。
將新的keyTed按照之前的方式插入到 hash-table 和 lru-list之中，并將high pool的最舊的key hsd放在low-pool之中。

到此，基本的插入過程就已經很清晰了，我們能夠看到high-pool的頭插法 + low-pool 的尾插法是能夠完整的維護LRU Cache的特性。
可以看到，高低優先級 pool的功能，是為了盡可能得讓熱點key在cache中駐留的時間最長。而hashtable 的能力則是一個cache-key的全集，能夠在需要lookup的時候以最快的速度找到目標key。

2.2 高并發下 insert 的一致性/性能保證

這個時候，我們再回頭看看我們的工業級需求。
可以看到Insert的過程涉及大量的指針更新（針對high/low/hashtable），所以針對同一個shard-cache的更新，如果我們不想出現指針指向的丟失或者指向錯誤，那就需要保證每一次更新的原子性了，那就需要引入鎖機制了。
但是這個鎖不應該影響整個shard的其他讀取/更新操作，只需要保證當前handle的更新是一個排他鎖，所以LRU-Cache的更新鎖粒度是 key。鎖的范圍是從 key 在 hashtable 中的更新到 key在lru-list 中的更新。

這把鎖鎖住了當前CPU 多次訪存操作，而在高并發的cahce更新場景性能將非常難看，使用我們的cache-bench 做如下幾個測試。

# 單shard 單線程的 純 insert./cache_bench -threads=1 -lookup_percent=0 -erase_percent=0 -insert_percent=100 -num_shard_bits=0 -cache_size=2147483648 -use_clock_cache=false
Number of threads   : 1
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 0
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 100%
Lookup percentage   : 0%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 0.919 s; QPS = 1306012# 單shard 16線程的 純 insert
./cache_bench -threads=16 -lookup_percent=0 -erase_percent=0 -insert_percent=100 -num_shard_bits=0 -cache_size=2147483648 -use_clock_cache=false                                                                                                       
Number of threads   : 16
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 0
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 100%
Lookup percentage   : 0%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 38.139 s; QPS = 503421

可以看到如果我們只維護一個整體的cache，那在這種高并發場景下的性能將巨差，從單線程的130w 降到 16線程的 50w，因為針對一個cache - shard 的原子更新讓多核場景的cpu根本無法發揮用處，性能顯然會很差。

雖然鎖保證了多線程下的Cache一致性，但是高并發場景的性能是用戶所不能接受的。而為了提升多核硬件中高并發下的性能，cache的分shard策略是必然的。
如下測試，多shard的多線程顯然比單shard 好很多，而這一點在cache的lookup heavy場景體現的更加明顯，后面有詳細的測試數據。

./cache_bench -threads=16 -lookup_percent=0 -erase_percent=0 -insert_percent=100 -num_shard_bits=5 -cache_size=2147483648 -use_clock_cache=false
Number of threads   : 16
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 5
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 100%
Lookup percentage   : 0%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 7.874 s; QPS = 2438406

2.3 Lookup操作

那我們繼續。
接下來看看 LRU 的查找操作，查找很簡單。
查找的大體過程如下：

先從hashtable 中查找，如果找不到直接返回。
找到了，拿著找到的handle 返回即可。
同時，為了提升lookup 命中cache的key的熱度，會標記當前key為命中。再次insert 當前key時，則會直接放在高優先級的pool中。
判斷其ref是否為0，如果是會將其從lru鏈表中移除，但因為它被查找過，所以還會在hashtable中保留一份它的key-handle。

如果ref count 為0 時，對于Cache來說再次進行操作就可以進行清理了，因為目的是為了讓熱點key長期駐留在cache中。而lookup則表明這個key是一個熱點key，所以會將其保留在HashTable中，因為之前的ref count 為0，則會從LRU 中移除，但是會標記hit，在后續的insert 操作則會再次添加到lru-cache的high-pool中。

所以，Lookup操作也會有指針的更新，也就需要鎖的保護了。

Cache::Handle* LRUCacheShard::Lookup(const Slice& key, uint32_t hash) {MutexLock l(&mutex_);LRUHandle* e = table_.Lookup(key, hash);if (e != nullptr) {assert(e->InCache());if (!e->HasRefs()) {// The entry is in LRU since it's in hash and has no external references// LRU 雙向鏈表中的移除操作。LRU_Remove(e);}e->Ref();e->SetHit();}return reinterpret_cast<Cache::Handle*>(e);
}

所以，因為工業級cache對一致性的需求引入了鎖，那我們想要提升性能，分shard仍然有很大的需求了，對于shard來說無非引入了一點內存管理的代價而已，性能上key的按hash映射是位運算，可能就幾個ns，根本沒有什么消耗。

2.4 shard 對 cache Lookup 性能的影響

我們來測試一下Lookup性能，保持80% 的lookup和20% 的insert，分別看一下單shard下單線程和多線程的性能已經多shard下的多線程性能。

# 單線程 單sharda
./cache_bench -threads=1 -lookup_percent=80 -erase_percent=0 -insert_percent=20 -num_shard_bits=0 -cache_size=2147483648 -use_clock_cache=false
Number of threads   : 1
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 0
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 20%
Lookup percentage   : 80%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 0.273 s; QPS = 4398988# 多線程 單shard
./cache_bench -threads=16 -lookup_percent=80 -erase_percent=0 -insert_percent=20 -num_shard_bits=0 -cache_size=2147483648 -use_clock_cache=false
Number of threads   : 16
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 0
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 20%
Lookup percentage   : 80%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 18.037 s; QPS = 1064451

可以看到，單shard下的單線程有440w /s 的吞吐，而多線程僅有106w。
再跑一下多shard的場景，我們跑了1024個shard，可以看到性能能夠達到 1950w/s （在lookup 比例更高一些的場景，隨著shard個數的增加，性能甚至能夠達到線性，當然實際shard個數大于2^20 的時候性能就開始退化了）。

./cache_bench -threads=16 -lookup_percent=80 -erase_percent=0 -insert_percent=20 -num_shard_bits=10 -cache_size=2147483648 -use_clock_cache=false
Number of threads   : 16
Ops per thread      : 1200000
Cache size          : 2147483648
Num shard bits      : 10
Max key             : 1073741824
Populate cache      : 0
Insert percentage   : 20%
Lookup percentage   : 80%
Erase percentage    : 0%
Test count          : 1
----------------------------
1 Test: complete in 0.984 s; QPS = 19504108

所以LRU cache 之上的shard 封裝，真的可以說是工業級高并發cache上設計層面的一個必備能力了。

2.4 Erase 操作

后面的 Erase操作這里便不再多說了，和lookup的操作時類似的。優先從hashtable中清理，如果key-handle的引用計數為0，則會從 high/low pool中的cache中移除，同樣因為設計cache的更新，所以還是有鎖的參與來原子更新cache的雙向鏈表。

void LRUCacheShard::Erase(const Slice& key, uint32_t hash) {LRUHandle* e;bool last_reference = false;{MutexLock l(&mutex_);e = table_.Remove(key, hash);if (e != nullptr) {assert(e->InCache());e->SetInCache(false);if (!e->HasRefs()) {// The entry is in LRU since it's in hash and has no external referencesLRU_Remove(e);usage_ -= e->charge;last_reference = true;}}}// Free the entry here outside of mutex for performance reasons// last_reference will only be true if e != nullptrif (last_reference) {e->Free();}
}

2.5 內存維護

外部設置的Cache大小會被均分給設置的多個shard。

LRUCache::LRUCache(size_t capacity, int num_shard_bits,bool strict_capacity_limit, double high_pri_pool_ratio,std::shared_ptr<MemoryAllocator> allocator,bool use_adaptive_mutex)
: ShardedCache(capacity, num_shard_bits, strict_capacity_limit,std::move(allocator)) {// 2^num_shard_bits 個 shardnum_shards_ = 1 << num_shard_bits;shards_ = reinterpret_cast<LRUCacheShard*>(port::cacheline_aligned_alloc(sizeof(LRUCacheShard) * num_shards_));// 均分的總cache大小size_t per_shard = (capacity + (num_shards_ - 1)) / num_shards_;for (int i = 0; i < num_shards_; i++) {new (&shards_[i])LRUCacheShard(per_shard, strict_capacity_limit, high_pri_pool_ratio,use_adaptive_mutex);}
}

每個Cache內部，Lru high/low pool的總內存大小 lru_usge_ 是包含在 hashtable 的內存占用總大小usage之內的。
hashtable的usage 是每一個handle 都要進行更新的，insert/erase 都需要操作hashtable。

如果想要看到更細粒度的cache內部狀態，則可以通過如下命令
編譯運行的話進入到cd example; make test即可，會詳細得打印每個shard cache內部hashtable , lru 雙向鏈表的狀態。

3. 優化

通過以上的一些實現架構和細節上的描述，我們能夠總結出 rocksdb 的工業級lru cache 相比于傳統lru-cache 的優化點：

多次提到過的并且在性能測試中性能突出的分shard能力。
為了保證Cache一致性的操作鎖。
為了提升Cache 讀性能的hashtable 以及高低優先級pool，hash table用來加速key的查找，并且盡可能得保證熱點key保存在了內存中。
支持指定不同的分配器來作為LRUCache的默認分配器。（本篇沒有對不同分配器的性能進行測試，直接使用的是操作系統默認的malloc/free）
內存控制管理能力，超過限制，則按照LRU策略從優先從low pool中淘汰數據（其本身也是整個LRU Cache中較舊的數據，其頭部則是整個lru 雙向鏈表最舊的數據）。

相關代碼和 benchmark 工具：https://github.com/BaronStack/Cache_Bench

這個LRU Cache是作為Rocksdb的默認cache，同時Rocksdb還提供了另外一種可選的Cache : ClockCache。因為它選用了tbb:concurrent_hash_map 作為索引，底層選擇deque 作為clock algorighm的實現。因為TBB 庫本身的無鎖操作，從而在Cache的并發操作上有了不小的提升。

限于篇幅原因，ClockCache的介紹會單獨進行，包括基本的架構設計以及 tbb 的無鎖化(并發erase) 實現細節。

總結

以上是生活随笔為你收集整理的单机 “5千万以上“ 工业级 LRU cache 实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。