(InterviewBit) System Design - Design Cache System

-

前言

這是InterviewBit中Storage Scalabiliy第一題，設計一個快取系統。

我希望可以透過InterviewBit中的文章與題目，打開自己系統設計的視野，並且重裡面中得到關鍵詞彙，透過這些關鍵詞彙補足自己知識的不足。

其中會參考許多jyt0532神的許多文章

題目

替Twitter或是google設計快取系統，概念圖如下:

分析步驟

  • 列出需求情境
  • 估算
  • 立定設計目標
  • 深入探討設計方法

需求情境

  • 需要多大的快取
  • 我們的快取清除策略要如何
    • 因為快取大小所以必須將舊資料刪掉
  • 快取的寫入策略
    • Write through cache
      • 當資料寫入時，同時寫入DB和Cache中
      • 寫入因為需要寫入兩個系統(DB/Cache)所以有較高的延遲
    • Write around cache
      • 當資料寫入時先寫入DB，當快取被讀取發現遺失資料時，再將資料從DB同步到快取中
      • 因為讀取是從快取中讀取，但是在讀取時判斷到有新增資料沒進入快取，會有較高的讀延遲。
      • 但寫和重複讀不會有特別的延遲
    • Write back cache
      • 直接將資料寫入到快取中，在同步到資料庫裡
      • 風險 - 畢竟快取是in-memory會有遺失風險
      • 優點 - 高寫入效率(寫得快可附合的流量大)
      • 可以透過replica快取降低memory消失的風險

評估

預先知識

  • QPS - Queries Per Second
  • TPS - Transactions Per Second
  • UV - Unique Visitor
  • RPS - Requests Per Secornd

獲取設計前條件

目前得知的條件

  • 快取大小會是30TB
  • QPS會是10M(每秒一千萬)

估算機器數量

假設我們每台機器都有72G的記憶體，則要存入30TB的資料則需要
30TB / 72G = 420(大約)，而這是剛剛好的數目，有可能需要增加，因為我們每秒要附和10M的搜尋流量。

設計目標

設計目標三巨頭

  • Latency(延遲)
  • Consistency(一致性)
  • Availability(可使用性)

快取系統的設計目標

快取的用意就在於降低延遲，DB的寫入是依靠硬碟的而快取是依靠記憶體，有基本計算機常識的話就可以知道記憶體的存取速度>>硬碟。所以快取系統顧名思義就是要降低延遲。

根據CAP理論，C和A我們只能偏重其一。

如何選擇

根據google和Twitter的業務性質，一致性並不會造成太大的影響(一時的不一致)，因為在使用者觀看訊息時或許沒辦法看到最新的，但她依然可以看其他舊的訊息。
而可使用性就非常重要了，當快取系統不可用時也代表整個系統需要依靠DB去運作，整個搜尋或寫入的延遲就會非常的嚴重，造成使用者感受快速下降。

所以在C和A中我們取A為首先考慮要素。

深入探討設計細節

預先知識

快取策略 Wiki

  • FIFO
    • 最近進入Cache先淘汰，先進先出如同Queue，不過對於快取設計的概念，最近被使用也容易代表他還會持續被使用，所以FIFO出非特別業務不然不參考
  • LFU
    • 最近最少使用的快取先被淘汰
    • 但是像是google搜尋引擎提示自，最近開始大家都搜尋這個關鍵字但是他在這個月是最少使用的，還是會被淘汰，所以還是需要依照業務邏輯
  • LRU
    • 最符合快取設計的策略
    • (最久)沒有存取的資料淘汰
    • (最久)沒有存取很大機率代表之後也不會存取
  • NMRU
    • 在最近沒有使用的資料隨機淘汰

快取最常使用的LRU如何設計

  • 如果永遠不需要刪除過期的資料
    • 我們可以直接使用一個Map or HashMap
  • 若需要刪除最久沒被使用的資料
    • Linkedlist會是個非常好的選擇
    • 在每次Read資料時，接節點移到head
      • 資料如此會自動根據使用調節順序
    • 在快取超出最大容量時，刪除最後的節點
  • Java LRU原始碼

在單執行緒時我們可以簡單地用上方的Java LRU實踐快取機制，但是當多個執行序至多台Server時該如何處理呢?

  • 為何要討論多執行緒處理快取?
    • 單執行緒時可以假設只是一台機器，而多執行緒放大後也可以想成分佈式系統
    • 多執行緒牽涉到要如何設計鎖，讀和寫操作需要分離並且設計非同步的刷新方法
  • 設計LinkedList與HashMap為基礎的快取資料結構
    • LinkedList用於更新快取資訊(插入的順序性淘汰最末位)
    • HashMap用於拿取(O(1)的速度提升快取的效率)

QPS的深入解析

現在我們每個機台都有自己的Cache方法了，重Memory層面來看完全沒問題!72G 420台機器，但是如果從QPS層面來看問題就大了，這個系統的QPS為10M，代表每台機器會附和到23000QPS，這可是不小的問題，我們該如何調整這個很吃緊的QPS呢?

計算每台機器QPS

通常情況Sever為四核心那代表我每台機器處理這個23000 QPS他的延遲最多只能
410001000/23000 = 174us，這包含了我們從記憶體新增修改的時間，還包含了伺服器接收request和回傳response的時間，明顯要我們在這時間內處理72G的記憶體快取是非常困難的。

所以我們可以讓機器只擁有16G記憶體但是數量擴增到4倍，這樣每台機器需要負責的QPS數也可以降到大約5500QPS，運算的數度也比較合理。

預先知識，了解每個硬體的儲存延遲

https://gist.github.com/jboner/2841832

總結

  • 我們在設計過程中，分析了只從30T去分配機器數量會造成每台負荷QPS過高的問題
    • 將每台記憶體下調，但是增加機器數量(增加運算能力)
  • 我們思考了快取如何設計
    • LinkedList + HashMap，實作直接使用java.util.LinkedListHashMap處理
  • 快取的特性我們選擇了A不選擇C
    • 快取重要性在於不要讓使用者直接碰觸到我們的DB(硬碟搜尋延遲>>>記憶體搜尋延遲)，所以可使用性>一致性
  • 這裡為何一致性權重會小於可使用性能?
    • 因為系統特性，我們要設計的快取系統是給像是Twiter/google使用
    • 其中的使用者操作會更注重於現在使否有資料回饋，而資料的一致性則可以等使用者看完手邊資料後刷新再補進去。

參考資源

jyt0532 - 系統設計 - Design cache
interviewBit

留言

張貼留言

這個網誌中的熱門文章

Java Lambda Map篇

-
目的 主要介紹Map中的新方法，包含如下 forEach() getOrDefault() putIfAbsent() remove() replace() replaceAll() merge() 有些是Lambda有些則是我覺得比以前使用Map更方便而介紹 forEach Map的forEach方法與List不大依樣，因為Map主要的迭代方法是以Entry為主，所以需要Key-Value Pair去迭代 原始碼解說 可以看到forEach的傳入參數BiConsumer介面，必須傳入Key與Val，裡面的實作就如同我們使用Java8版本以前的寫法，需要使用for迴圈去迭代抓出每個Value 原始碼 default void forEach(BiConsumer<? super K, ? super V> action) { Objects.requireNonNull(action); for (Map.Entry<K, V> entry : entrySet()) { K k; V v; try { k = entry.getKey(); v = entry.getValue(); } catch(IllegalStateException ise) { // this usually means the entry is no longer in the map. throw new ConcurrentModificationException(ise); } action.accept(k, v); } } 範例 private void forEachExample() { Map<Integer, String> map = new HashMap<>(); map.put(1, "test1"); map.put(2, "test2"); m
閱讀完整內容

設計模式 - 享元模式 (Structural Patterns - Flyweight Design Pattern)

-
圖片
前言 甚麼是Flyweight Pattern? 幫助你節省記憶體開銷 透過共享物件的方式 最常見的例子 String : 每次新增一個String的時候，都會將String丟進String pool，再讓物件指向這個String memory。 String str1 = "test"; String str2 = "test"; System.out.println(str1 == str2) // true 實踐方式 撰寫Flyweight介面與物件 撰寫Flyweight工廠(主要節省記憶體邏輯在此)，負責管理和創建Flyweight 類別圖 範例 我們可以思考一下，在英雄遊戲中有那些東西可以使用享元模式。 重複製造 同物件的性質一樣 我想武器添加物系統可以使用享元模式，因為武器中插的寶石不管插在哪種類的武器裡，他們的功效都是一樣的，而如果為每把武器都創建新的寶石物件，那太消耗記憶體了。 程式行為 為武器加上寶石 若是已經存在的寶石則不在new 物件 透過DiamondFactory去控制要不要new新物件的邏輯 import java.util.ArrayList; import java.util.HashMap; import java.util.Map; abstract class Weapon { ArrayList<Diamond> diamonds = new ArrayList<>(); public void addDiamond(Diamond diamond) { diamonds.add(diamond); } abstract void attack(); } class Sword extends Weapon { @Override void attack() { System.out.println("Sword attack"); diamonds.forEach((x) -> { System.out.println("Use "
閱讀完整內容