(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...
閱讀完整內容

設計模式 - 工廠模式 (Creational Patterns - Factory Pattern)

-
圖片
前言 這篇文章會介紹三個最常使用的工廠模式方法，分別是 Simple Factory (簡單工廠) Abstract Factory (抽象工廠) Factory Method (工廠方法) 其中最容易讓人搞混的是，Abstract Factory和Factory Method，不過對我來說何必太過糾結於這兩個的概念，工廠模式最主要的核心原理就是將你創造物件的邏輯隱藏起來，不向客戶端顯示，我覺得只要知道這個概念就夠了，接下來會介紹這三個種類的工廠模式。 Factory Pattern 工廠模式 Simple Factory 簡單工廠 簡單工廠是工廠模式的第一步，也是工廠模式最基本的核心概念實踐，主要解決的問題是 將創建物件邏輯抽離 解偶Class的複雜度 Class Diagram 將封裝物件邏輯抽出寫成Simple Factory 產出父類別物件的物件 範例 在這個範例我們希望將戰士與魔法師遊戲創造英雄的邏輯抽出並且寫成靜態工廠，戰士與魔法師都是英雄並且’目前’只能進行攻擊，程式碼如下 Interface Hero public interface Hero { void attack(); } Magician.class public class Magician implements Hero { @Override public void attack() { System.out.println("Use magic to attack"); } } Warrior.class public class Warrior implements Hero { @Override public void attack() { System.out.println("Use sword to attack"); } } HeroFactory.class public class HeroFactory { public Hero makeHero(HeroType heroType) { if (heroType.equals(HeroType.MA...
閱讀完整內容