系統設計 - 基礎概念 CAP (Consistency, Availability, Partition Tolerance)

-

此篇文章大致上是翻譯一篇國外精彩的CAP介紹文，讀者在此篇文章可以透過有趣的小故事了解到甚麼是CAP。

我們先節錄Wiki介紹的CAP

  • Consistency - 一致性
    • 等同於所有節點訪問同一份最新的數據副本
  • Availability - 可用性
    • 每次請求都能獲取到非錯的響應——但是不保證獲取的數據為最新數據
  • Partition Tolerance - 分區容錯性
    • 以實際效果而言，分區相當於對通信的時限要求。系統如果不能在時限內達成數據一致性，就意味著發生了分區的情況，必須就當前操作在C和A之間做出選擇

看完是不是一頭霧水呢?沒關係我也是，接下來的主文我們會用個簡單的小故事來講解CAP到底是甚麼

wiki

主文

第一章 : “幫你記” 公司開張

在前一天晚上你的另一半非常開心你記住了他的生日，並且送了他曾經告訴過你他最喜歡的東西當作禮物，你突然想到大家常常忘東忘西的但是我的記憶力特別強，何不用這項能力當作我的第一項事業呢?於是幫你記公司成立了!

幫你記有限公司 - 別再忘記，也不用再記
你是否曾經非常失落自己又落東落西了呢? 不用擔心，只要一通電話讓你馬上回憶
如果你需要記住甚麼東西馬上撥打 555-55-5807 並且告訴我們你要記住甚麼東西
當你要回憶時，馬上再次撥打我們會讓你得到你要的答案
例如: 我今天要記住我老婆的生日，只要一通電話先在我們公司留下紀錄，下一次有不好的預感時馬上call我們，我們會馬上告訴你
收費 : 每次紀錄/詢問只要 1 塊錢

  • 所以你典型的一次成交對話會如下
    • 消費者 : 你好請問可以幫我記住鄰居的生日嗎?
    • 你 : 當然! 幾時?
    • 消費者 : 七月二號
    • 你 : (記錄在記事本之中) 以記錄，之後如果要查詢的話歡迎隨時撥打
    • 消費者 : 謝謝你
    • 你 : 沒問題的，這次記錄收取你1元的服務費哦

第二章 : 生意興隆

你的創業點子非常簡單而且實用，所以得到了創投的第一筆資金， 每天的消費者電話來到了一百多通，但是人不是鐵打的也需要休息，每一次休息都會讓你損失一整天的生意，況且會讓消費者們不滿意，所以你拉了自己老婆一起做生意，下面是你新的營運系統計畫

  • 你和老婆都有一隻分機
  • 客戶撥打一樣的電話會自動轉接到目前有空的人分機

第三章 : 你的第一個服務失敗案例

新營運系統上線第二天，你接到了一個忠實顧客的電話，以下是電話內容

  • 顧客: HI
  • 你: 很高興為你服務
  • 顧客: 我想知道我下一班飛機的時間
  • 你: 請等一下 (開始翻閱筆記本，發現沒有任何紀錄在此顧客的回憶錄中)
  • 你: 不好意思，你從來沒有告訴過我們你下一班飛機的時間
  • 顧客: 怎麼可能!我昨天才打給你們! (掛上電話)

大家有發現甚麼問題了嗎?是顧客在說謊嗎?還是顧客是打給你妻子做的紀錄呢?當然你打開妻子的筆記本上面果然有此筆資料，你們發現這套營運系統有個很致命的問題!

其實這一套新的營運系統已經變成一個分散式系統，但是重點你的分散式系統沒有做到資料一致性(你的筆記本跟老婆的筆記本資料是不同步的)，所以只要顧客打給你或你老婆做紀錄，但是打給另一個人做查詢就會讓整個服務失敗。

我們看到了第一個CAP中的C
Consistency - 一致性

第四章 : 修正營運系統中一致性的問題

發現問題後你徹夜難眠，直到突然腦中有個新想法並且叫醒你的妻子與他分享

  • 當接到紀錄電話時，我們在掛斷客戶電話前打給對方(你或是妻子)同步更新資料
  • 這樣我們雙方都有最新的資料了

不過這方法有個小小問題，如果我們為了要增加一致性會導致整個記錄過程延長(接到電話並且記錄，在中間還要打給另一半同步資料，在掛斷電話)，這樣會讓整個過程阻塞住，不過還好依照目前的紀錄看來我們真正紀錄回憶錄的次數遠小於詢問回憶的次數。

你老婆聽到了這個新的方法覺得非常棒，但是深思了一下發現，如果我們兩個其中一個休息的話這套方法不就完蛋了嗎?因為有一方休息他的筆記本就無法同路另一方的紀錄狀態，因為不能同步對方更新回憶錄狀態那我們整個記錄過程就無法結束，這時候我們來到了CAP中的A

  • Availability - 可用性
    • 雖然上面得故事有點牽強，不過我覺得換成軟體與系統面還是得過去的
    • 當你的服務其中一個環節掛掉了，那可能會造成整個服務無法使用，這就是可用性問題

第五章 : 最好的辦法

你苦惱了幾天，一值在思考這個一致性©與可使用性(A)之間的問題，最後又給你找到方法了，跟第四章節的方法相似不過加了一點小細節

  • 當接到紀錄電話時，我們在掛斷客戶電話前打給對方(你或是妻子)同步更新資料
  • 但是如果有一方今天請假或者不方便，則今天值班的那一方就在下班前整理今日新增/更新的回憶錄內容到對方的Email中
  • 請假一方回來上班，第一時間先將Email中的內容更新到自己的筆記本上

真是個天才，這樣馬上就解決了C與A的問題，看來"幫你記"公司準備要大賺特賺上市上櫃了

第六章 : 老婆7噗噗

當這套兼容C與A的營運系統開始使用後，即使你們其中一人沒上班，服務照樣穩定運行，公司果然穩定開始起飛，但是問題來了，常常說道朋友與家人最好不要一起開公司，容易私事影響公事，公事影響私事，前一天晚上你們因為小孩教育問題大吵特吵，隔天上班時老婆根本不跩你的系統，不想跟你同步資料也不想在下班後記Email給你整合，這時候我們看到了CAP中的P，

  • Partition Tolerant - 分區容錯姓

這時候的你可以決定，好好和你的老婆和解後再重新開張，而這代表了你選擇了CAP中的P而拋棄了A，因為和老婆和解釋必須要關門一陣子，你的服務也失去了可使用性
或是不管你老婆繼續做你的事情，那這樣你就失去了CAP中的C(一致性)

第七章 : 總結

根據CAP理論中，如果你在設計分散式系統的話，你只能從CAP中選取兩個特性

  • Consistency(一致性): 當客戶紀錄回憶後，他可以透過電話得到正確的答案(不管他多快打回來給你)
  • Availability(可使用性): 只要你或你老婆其中有一人有上班，就可以提供服務
  • Partition Tolerance(分區容錯性):即使你和你老婆吵架，不爽在溝通，你們的服務照樣可以運轉

個人想法

CAP中根據我搜尋網路中的資料，大致上都認為P是不可能不避免的要素，就如同上面的故事你和老婆吵架，而機器也一樣，誰都不知道哪天誰會踢到店員陷害機器關機(QQ)，所以大部分的人都是從C或是A選一個做徹底執行，如果選C的話，因為需要同步多台分散式機器，而在同步的過程中就會喪失了A可使用性，若是要選A的話，因為同步需要時間那可能在還沒同步完成的時候客戶就又來索取一次資料，這樣資料可能不一致

參考資源

http://ksat.me/a-plain-english-introduction-to-cap-theorem

留言

張貼留言

這個網誌中的熱門文章

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

(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的寫入是依靠硬碟的而快取是依靠記憶體，有基本計算機常識的話就可以知道
閱讀完整內容

設計模式 - 享元模式 (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 "
閱讀完整內容