[Cache] LRU已經落伍了，S3-FIFO更適合在大快取系統

發表於 | 分類於 | |  閱讀次數:
字數統計: 3k

什麼是 Cache？

在我們的電腦系統中，Cache（快取）扮演著至關重要的角色。快取是一種高效能的臨時儲存區域，用於儲存經常被訪問的資料，以加速資料讀取和寫入的速度。想像一下冰箱裡的食物，快取就像是你放在冰箱門邊的零食，方便隨時取用，而不是藏在冰箱深處的冷凍食品。

一個好的 Cache 應該具備哪些特性？

  1. 高命中率: 快取的主要目的是提高資料訪問速度，所以高命中率是衡量一個好快取的關鍵指標。這就像你想從冰箱裡拿出一瓶飲料，理想情況下，它應該總是放在你容易找到的位置。
  2. 低延遲: 快取應該能夠快速響應資料請求，減少讀寫延遲。這就像你想要吃東西時，食物應該馬上能夠取到，而不是還需要解凍和加熱。
  3. 高效資源利用: 快取應該能夠高效地利用有限的儲存資源，儘可能儲存更多的有用資料。這就像冰箱空間有限，你應該放進去的是經常吃的食物，而不是占空間卻不常吃的。

當然，快取的速度很快，相對應的缺點就是「貴」！

傳統的 LRU 策略

在快取策略中，LRU（Least Recently Used）是一種經典的演算法。LRU 的基本策略是當快取空間不足時，淘汰最久未被使用的資料。這就像在冰箱裡，定期清理那些已經很久沒吃過的食物，確保新的食物有地方放。

LRU 的資料結構

要實現 LRU，我們需要兩個主要的資料結構：

  1. 哈希表（HashMap）: 用來快速查找資料的位置。
  2. 雙向鏈表（Doubly Linked List）: 用來記錄資料的使用順序。
    雙向鏈表可以讓我們在常數時間內（O(1)）移動和刪除節點，哈希表則可以讓我們在常數時間內（O(1)）找到需要的節點。 下面一個簡單的 Python 範例，展示了 LRU 演算法：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    # 定義 Doubly Linked List
    class Node:
        def __init__(self, key, value):
            self.key = key     # 一個整數key，佔用 4 bytes
            self.value = value # 通常是一個pointer，佔用 8 bytes
            self.prev = None   # 前驅指標，佔用 8 bytes
            self.next = None   # 後繼指標，佔用 8 bytes

    class LRUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            # key:   int value
            # value: Node address
            self.cache = {}
            self.head = Node(0, 0)
            self.tail = Node(0, 0)
            self.head.next = self.tail
            self.tail.prev = self.head

        def get(self, key: int) -> int:
            if key in self.cache:
                node = self.cache[key]
                self._remove(node)
                self._add(node)
                return node.value
            return -1

        def put(self, key: int, value: int) -> None:
            if key in self.cache:
                self._remove(self.cache[key])
            node = Node(key, value)
            self._add(node)
            self.cache[key] = node
            if len(self.cache) > self.capacity:
                node_to_remove = self.head.next
                self._remove(node_to_remove)
                del self.cache[node_to_remove.key]

        def _remove(self, node):
            prev = node.prev
            next = node.next
            prev.next = next
            next.prev = prev

        def _add(self, node):
            prev = self.tail.prev
            prev.next = node
            node.prev = prev
            node.next = self.tail
            self.tail.prev = node
    記憶體用量

LRU 的記憶體用量主要來自兩部分：

  1. 資料儲存: 儲存實際的資料。
  2. 資料結構: 用來追蹤資料使用情況的雙向鏈表（一個節點28 bytes至少）和哈希表。

每個節點在雙向鏈表中需要儲存前驅（prev）和後繼（next）指標，這增加了記憶體消耗。隨著資料規模增大，這些額外的儲存開銷在系統變大所需快取增加後會變得非常顯著。

為何 LRU 在大記憶體下會使用更多的記憶體？

當快取規模增大時，雙向鏈表和哈希表的節點數量也會隨之增加。這意味著需要更多的記憶體來儲存這些額外的指標和哈希表條目。特別是在高併發環境下，管理這些資料結構會導致更多的記憶體碎片和開銷。隨著摩爾定律，現在的系統越來越大、資源越來越多，可用的Cache空間也是越來越大，那有沒有什麼演算法能同時達到LRU的cache命中率，並且隨著Cache增大還能減少記憶體的佔用呢？

S3-FIFO

S3-FIFO（simple, scalable, space-efficient first in first out）是一種新穎的快取管理策略，旨在解決 LRU 記憶體用量大的缺點。S3-FIFO 使用三個隊列（Queue）：S快取、M快取、和G快取來管理資料。這些隊列的具體運作如下：
1. S快取：這個隊列用來儲存新插入的資料。當資料被訪問時，訪問計數會增加。如果S快取滿了，就會根據訪問計數決定是將資料移動到M快取還是G快取。
2. M快取：這個隊列用來儲存經常被訪問的資料。當M快取滿了時，最舊的資料會被移出。這些資料會根據訪問計數決定是否重新插入M快取或移至G快取。
3. G快取：這個隊列用來儲存那些在S快取和M快取中被淘汰的資料鍵值（不儲存實際資料和訪問計數）。它用來記錄哪些資料最近被淘汰，以防止頻繁的重複插入(重複的記憶體分配和釋放)。

運作例子

假設我們有一個 S3-FIFO 快取系統，S 容量為 3，M 容量為 5，G 容量為 2。以下是一個運作過程的例子：

  1. 插入資料 1, 2, 3 到小快取 S：
    • S: [1, 2, 3]
    • M: []
    • G: []
  2. 插入資料 4 到 S（S 滿了，1 被移除）：
    • 1 沒有被訪問過，移至 G
    • S: [2, 3, 4]
    • M: []
    • G: [1]
  3. 插入資料 5 到 S（S 滿了，2 被移除）：
    • 2 沒有被訪問過，移至 G
    • S: [3, 4, 5]
    • M: []
    • G: [1, 2]
  4. 插入資料 6 到 S（S 滿了，3 被移除）：
    • 3 沒有被訪問過，G 滿了，移除 G 最舊的 1
    • S: [4, 5, 6]
    • M: []
    • G: [2, 3]
  5. 訪問資料 4（增加 4 的訪問計數）：
    • S: [4(1), 5, 6]
    • M: []
    • G: [2, 3]
  6. 插入資料 7 到 S（S 滿了，4 被移除）：
    • 4 被訪問過，移至 M
    • S: [5, 6, 7]
    • M: [4(1)]
    • G: [2, 3]
  7. 插入資料 8 到 S（S 滿了，5 被移除）：
    • 5 沒有被訪問過，移至 G
    • S: [6, 7, 8]
    • M: [4(1)]
    • G: [3, 5]
  8. 插入資料 9 到 S（S 滿了，6 被移除）：
    • 6 沒有被訪問過，G 滿了，移除 G 最舊的 3
    • S: [7, 8, 9]
    • M: [4(1)]
    • G: [5, 6]
  9. 訪問資料 5：
  • G 裡的 5 移至 S，S 滿了，移除 S 最舊的7
    • S: [8, 9, 5]
    • M: [4(1)]
    • G: [6]

這個例子展示了 S3-FIFO 如何通過使用三個隊列來管理資料的插入和淘汰。S 隊列用於臨時儲存新插入的資料，M 隊列用於儲存經常訪問的資料，G 隊列用於記錄被淘汰的資料鍵值。這樣的設計不但確保了高效的快取管理和訪問，還減少了快取未命中的情況。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class CacheItem:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.access_count = 0

class S3FIFO:
    def __init__(self, capacity_s, capacity_m, capacity_g):
        self.capacity_s = capacity_s
        self.capacity_m = capacity_m
        self.capacity_g = capacity_g
        self.cache_s = []
        self.cache_m = []
        self.cache_g = {}

    def get(self, key):
        # 檢查 M 隊列
        for item in self.cache_m:
            if item.key == key:
                item.access_count += 1
                return item.value

        # 檢查 S 隊列
        for item in self.cache_s:
            if item.key == key:
                item.access_count += 1
                return item.value

        # 檢查 G 隊列
        if key in self.cache_g:
            item = self.cache_g.pop(key)
            self.cache_s.append(item)  # 重新插入 S 隊列
            if len(self.cache_s) > self.capacity_s:
                self.evict_s()
            return item.value

        return -1  # 如果 key 不在快取中，返回 -1

    def put(self, key, value):
        # 檢查 key 是否在 M 隊列中
        for item in self.cache_m:
            if item.key == key:
                item.value = value
                return

        # 檢查 key 是否在 S 隊列中並更新
        for item in self.cache_s:
            if item.key == key:
                item.value = value
                return

        # 檢查 key 是否在 G 隊列中
        if key in self.cache_g:
            item = self.cache_g.pop(key)
            item.value = value
            self.cache_s.append(item)  # 重新插入 S 隊列
            if len(self.cache_s) > self.capacity_s:
                self.evict_s()
            return

        # 如果 key 不在任何快取中，則插入到 S 隊列
        new_item = CacheItem(key, value)
        self.cache_s.append(new_item)
        if len(self.cache_s) > self.capacity_s:
            self.evict_s()

    def evict_s(self):
        item = self.cache_s.pop(0)
        if item.access_count > 0:
            self.cache_m.append(item)
            if len(self.cache_m) > self.capacity_m:
                self.evict_m()
        else:
            self.cache_g[item.key] = item
            if len(self.cache_g) > self.capacity_g:
                self.evict_g()

    def evict_m(self):
        while len(self.cache_m) > self.capacity_m:
            item = self.cache_m.pop(0)
            if item.access_count > 0:
                item.access_count -= 1
                self.cache_m.append(item)
            else:
                self.cache_g[item.key] = item
                if len(self.cache_g) > self.capacity_g:
                    self.evict_g()

    def evict_g(self):
        if self.cache_g:
            oldest_key = next(iter(self.cache_g))
            del self.cache_g[oldest_key]

if __name__ == '__main__':
    cache = S3FIFO(capacity_s=3, capacity_m=5, capacity_g=2)
    cache.put(1, 'A')
    cache.put(2, 'B')
    cache.put(3, 'C')
    print(cache.get(1))  # 輸出: 'A'（增加訪問次數）
    cache.put(4, 'D')
    cache.put(5, 'E')
    cache.put(6, 'F')
    print(cache.get(2))  # 輸出: 'B'（資料 2 仍在 M 隊列中）
    print(cache.get(3))  # 輸出: None（資料 3 被移到 G 隊列後再次插入 S 隊列）

    # 更新資料
    cache.put(1, 'AA')
    print(cache.get(1))  # 輸出: 'AA'（更新後的值）

S3-FIFO 相比 LRU，雖然有其優勢，但也存在一些缺點和潛在的限制：

  1. 過度淘汰新資料：
    • S3-FIFO 在快速淘汰一次性使用的資料時，可能會過度淘汰一些潛在有價值的新資料，尤其是在資料訪問模式變化較大的情況下。
    • 比如，某些資料可能在短時間內只被訪問一次，但稍後會被頻繁訪問。這些資料可能會被 S3-FIFO 過早淘汰，導致更多的快取未命中。
  2. G快取的大小限制：
    • G快取的大小是有限的，一旦達到容量限制，最舊的資料會被移除，這可能會導致一些資料被頻繁重複插入和移除，增加了快取管理的開銷。
    • LRU 不存在這個問題，因為 LRU 的設計不需要額外的鬼快取來管理淘汰的資料。
  3. 對工作負載模式的敏感性：
    • S3-FIFO 的性能依賴於工作負載的模式，對於高度局部性和頻繁重訪問的工作負載可能效果很好，但對於那些有較多新資料插入的工作負載可能表現不如 LRU。
    • LRU 在處理不同工作負載模式方面更具通用性，因為它總是保留最近訪問的資料。
  4. 實現和調整的複雜性：
    • 雖然 S3-FIFO 在理論上較為簡單，但在實際實現中，需要仔細調整 S、M 和 G 三個隊列的容量，以達到最佳性能。
    • LRU 的實現和調整相對簡單，只需管理一個雙向鏈表或類似的結構。
  5. 記憶體消耗：
    • S3-FIFO 雖然能有效利用記憶體資源，但由於需要管理三個隊列，可能會在某些情況下消耗更多的記憶體，特別是在鬼快取 (G) 需要儲存大量資料鍵值時。
    • LRU 只需要管理一個主要隊列，記憶體消耗相對較低。

舉例說明

假設我們有一個快取系統，需要處理一系列訪問模式變化較大的資料：

  1. S3-FIFO 的情況：
    • 在初期插入大量新資料時，由於 S 隊列容量有限，很多新資料會被快速淘汰，進入 G 隊列。
    • 如果這些新資料在後續被頻繁訪問，會導致大量快取未命中，因為這些資料已被移出 S 隊列。
  2. LRU 的情況：
    • 在初期插入大量新資料時，LRU 會保留最近訪問的資料，並逐步淘汰最久未被訪問的資料。
    • 這樣的設計能夠更好地適應訪問模式變化，確保最近被訪問的資料能夠保留在快取中，減少cache miss。

總結

S3-FIFO 以其簡單、高效和低資源消耗的特點，為快取管理提供了一個優秀的選擇。相比LRU，S3-FIFO更適合在大Cache的環境，但是針對訪問模式變化較大的資料或是系統，還是可以考慮原有的LRU快取策略。