# Data Partitioning and Replication ###### tags: `System Design` ## Limitation of a single server * Limitation of a single server * Storage space * 單台主機擴充儲存空間的難度會越來越高 * Computing resources * 單台主機提升運算能力的難度會越來越高 * Network bandwidth * 單台主機所能支撐的網路流量有上限 * Geography * 主機靠近使用者能帶來效能、延遲的優點 ## Partition Strategies * Horizontal partitioning （sharding) * 每個 partition 保存部分的 rows (有相同的 schema) ![](https://i.imgur.com/bh8kIVq.png) * 優點 * 將負載分散到多台主機 * 提升效能表現 * 但此策略在 sharding key 的選擇上很重要 * 當系統上線後，很難對 key 作出調整 * 要能確保負載是均勻分散在各個 shard 之間的 (e.g. hash function) * 盡量漸少未來需要將過大個 shard 分裂，或是合併兩個過小的 shard 的可能性 * 非常耗時，且可能需要 shard 離線來執行操作 * 或是 shard 有做複寫，則可能達到某寫 shard 繼續提供服務而另一份複寫進行分裂/合併，但也衍生出不一致的問題需要處理。 * Vertical partitioning * 每個 partition 保存部分的 columns ![](https://i.imgur.com/7ORIotL.png) * 優點 * 可以減少高頻被查詢的 item 大小，且不太變動的資料可以使用 cache 以增進效能 * 增加敏感資料的安全性 (e.g. 信用卡卡號) * Fucntional partitioning * 每個 partition 保存功能接近的 table ![](https://i.imgur.com/NhRvPPx.png) ## Target of Partition * Consideration for Scalability * 分析資料存取的模式 * 每次 query 資料的大小、query 的頻率、處理操作所需的運算資源 * 確定現在跟未來所需要的 scalability 目標所需的處理的資料大小與負載，然後規劃 partition 將其能夠均勻分散到各個節點。 * 確保每個節點硬體上的限制足夠應對此設計下所需要的資料大小與負載。 * 如果規劃的 scalability 下所需要運算資源或儲存資源會超過節點的硬體限制，則需要考慮在切分更細一點。 * 定期監控是否資料如預期般分散到各個 partition 中 * 當負載與預期不符時，需調整設計來達到平衡 * Consideration for Query Performance * 分析資料存取的模式 * 找出處理很慢的 query * 找出強烈需要處理夠快的 query * 針對處理很慢的 query，可以考慮 * 減少每個 partition 的資料量大小 * 如為 horizontal partitioning，可以嘗試設計 shard key 使得每次 query 不需要跨 partition 都查詢 * 讓資料所在的 partition 地理上靠近主要的使用者以減少 latency * 針對要求速度的 query * 嘗試利用 functional partition 將不同功能的 table 存放於不同的 partition * 如 functional partition 後仍未達到要求，則進一步考慮 horizontal partition * 也可考慮 parallel query 同時查詢多個 partition * Consideration for Availability * 將 partition 設計成可以個別管理跟維護 * 當某個 partition 出現問題時，可以單獨的修復而不會影響到其他 partition 正常提供服務 * 根據資料是否重要存放於 partition * 可根據不同 partition 的重要程度提供不同等級的監控規則或備份頻率 * 也可考慮將有高度 availability 需求的資料複寫到多個 partition 中同時存在，然而這也會有衍生的一致性問題。 ## Sharding Strategy * The Lookup Strategy * 需要維護一個 mapping 將 query 導到該資料所屬的 partition * 此 mapping 可以直接將 shard key 對應到實體的 partition * 但也可以多一層 virtual partitioning 的概念，shard key 先對應到 virtual partitioning，而 vritual partitioning 在對應到數量較少的實體 partition，此做法有利於未來再平衡的需要。 * The Range Strategy * 當 shard key 具有順序性，且應用有 range query 的需求時，可以考慮根據 range 作為 partition * 例如根據月份切分 partition，當同個月的資料會常常同時被存取時，將其放置於相同 partition 可提供幫助 * The Hash Strategy * 所選的 hash function 需要能將 data 均勻分散到各個 partition 中 * 假設近期新增的資料相比就資料更 active，則 hash strategy 比 range startegy 更能減少 hotspots 的發生 * 優點與缺點 * Lookup Strategy * 透過人為定義好的 mapping 更好掌握每一份資料會導倒哪個 partition * 使用 virtual shard 的概念可以讓再平衡更容易 * 須考量 mapping 所額外需要花的工 * Range Strategy * 當有 range query 需求時可以考慮 * 更容易維護 (e.g. 考慮以時區劃分的情形，相同時區的 user 都位於同一 partition) * 在 partition 之間的平衡可能表現不佳 * Hash Strategy * 最可能平均分散資料量與負載 * 需要再平衡時可能會是個問題 * 須考量 hash 運算所額外需要花的工 ## 分區再平衡 / 新增節點 * 為什麼不建議直接取模來分區 * 考慮 10 個節點變成 11 個節點的情形，多數資料都需要搬移 * 固定數量的分區 * 起初直接設置一個足夠大的分區數，每個節點負責一定數量的分區 * 當有新節點加入時，直接從每個節點上取走一些分區，使得整體每個節點的負載是均衡的 * 動態分區 * 預先設定一個臨界值，當分區上的資料量超過時，該分區發生分裂，一半的資料轉移到其他節點上的新的分區。 * 按節點比例分區 * 每個節點具有故定數量的分區 * 當新節點加入時，選擇固定數量的現有分區進行分裂，拿走這些分區的一半數據量作為新節點上的。 ## 請求路由 * 客戶端可連接任意節點，如節點剛好有 query 要的資料則回傳，如沒有，節點會幫忙轉發給另一個合適的節點。 * 所有客戶端的 query 統一發送給一個路由層，路由層決定該把 query 發送到哪個節點 * 客戶端擁有分區跟節點的分配關係，自己知道要連到哪一個目標節點 ## Reference * https://docs.microsoft.com/zh-tw/azure/architecture/patterns/sharding * https://docs.microsoft.com/en-us/previous-versions/msp-n-p/dn589795(v=pandp.10)#designing-partitions-for-availability * Kleppmann, Martin. Designing data-intensive applications: The big ideas behind reliable, scalable, and maintainable systems. " O'Reilly Media, Inc.", 2017.