報告摘要：

報告摘要：

報告摘要：

報告摘要：

分片是源自數據庫的擴容技術，可用於提高區塊鏈系統的可擴展性，基本思想是將網絡中的節點分成不同的碎片，各分片可以並行處理不同交易，這樣可以並行處理相互之間未建立連接的交易，以提高網絡並發量。它的特點是隨著節點數目的增加，網絡吞吐量也隨之增加。核心難點在於數據分片的關鍵特徵值確定，以及元數據在片區之間通信的延遲造成的不一致性問題，頻繁的跨碎片之間的通信會使得區塊鍊網絡性能大大降低。由於每個片區裡的數據是分開更新的，在設計應用邏輯時必須確保信息的成功更新，同時也需要預留出一定的魯棒性來應對一個達成最終一致性過程中可能出現的不一致性。

在區塊鏈中的分片根據對象分為交易分片、網絡分片和狀態分片，其中值得注意的是，在區塊鏈中採用網絡分片技術，也就是將礦工分成幾個子網絡分別負責驗證該碎片上的交易，需要保證惡意節點的數目足夠小，也因此在分配礦工的規則上需要注意保證隨機性。在區塊鏈中應用分片技術，還需要考慮的問題是對各種攻擊如女巫攻擊，DDOS攻擊、雙花攻擊的防禦，需要在權衡效率的同時，保證每個分片內的總節點數目足夠多，並且誠實的節點佔大多數，分片技術對安全性要求極高，同時，區塊鏈系統中的節點數目比傳統數據庫中的可能要多，並且面臨帶寬的限制，需要充分考慮到延遲帶來的不一致性導致的性能和安全性問題，因此鮮少有落地的相關項目。需要在大規模的網絡中進行長時間的測試驗證，並結合嚴謹的理論方案證明，才能令人信服。

無論在區塊鏈領域或數據庫領域，分片時要進行的第一步工作都是提取數據的關鍵特徵值，並將關鍵特徵值按照一定的規則來劃分給不同的碎片來處理。關鍵特徵值的選擇非常重要，它關係著數據的表示唯一性保障以及分片的效果。關於特徵值的選取方法，一個言簡意賅的標準：based on what you think the primary access pattern will be（以你所認為的基本數據模式為標準）。因此我們在區塊鏈項目中經常可以看到分片的依據是用戶的私鑰/賬戶地址等等，因為這些值是唯一性且不隨時間改變的，分片時邏輯比較清晰。

1. 哈希方式，直接取模：1. 哈希方式，直接取模：

2. 一致性哈希：例如有3個碎片，就將數據經過哈希運算後用3求模，根據結果分配至特定的碎片，此種策略的目的是減少碎片負載不均衡的發生，因為哈希函數計算出來的結果毫無規律，也就打破了因為一些關鍵特徵值和負載的量相關的情況，因此數據更有可能均勻分散於各個碎片之間。一個反例則是，如果數據的關鍵特徵值是註冊時間順序的話，剛註冊的數據更為活躍，則有可能會把它們都分到某一個碎片裡。但是這一方法的缺點在於如果有新的碎片加入，重新平衡分片比較困難；其優點則在於不需要額外維護狀態信息。

3. Range based：2. 一致性哈希：

無虛擬節點的一致性哈希方式是指數據按照特徵值映射到首尾相連的哈希環上，同時也將節點按照一定規則映射上去，數據順時針找到的第一個節點為其所存儲的節點。有虛擬節點的一致性哈希和此類似，不過是將虛擬節點映射到哈希環上，也因此一個實際的物理節點可以佔據哈希環上的多個範圍。此種方法需要維護狀態信息，也就是數據具體被分到哪個節點了，但是優點在於如果碎片的數目需要增加，則重新平衡分片更為容易。但是分片狀態信息的維護需要考慮一致性問題，較為複雜。按照關鍵特徵值劃分成不同區間，每個節點對應一個或多個區間，類似一致性哈希的方式，也需要維護狀態信息。

在區塊鏈系統中，需要有機制來知道哪個節點實現了哪個分片，在傳統數據庫系統中分片信息（即元數據，指哪些數據劃分到了哪個碎片內）一般需要專門的服務器存儲，有時為了減輕元數據服務器的壓力，分佈式系統中，會在其他節點緩存元數據。

在區塊鏈中的思路也大體一致，需要保證在節點之間緩存的元數據的一致性，或者引入一個類似的主服務器來保證性能，但都帶來了一致性的挑戰。

多個副本的一致性、可用性是CAP理論討論的範疇，主要有兩種可用的方案。

第一種是主從同步，首先選出主服務器，只有主服務器提供對外服務，主服務器將元數據的更新信息以日誌的方式存至某個共享的存儲空間，然後從服務器從共享存儲空間讀取日誌並應用，達到與主服務器一致的狀態，如果主服務器被檢測到故障（比如通過心跳），那麼會重新選出新的主服務器。在網絡分割的情況下，有可能出現大家認為原來的主服務器已經宕機了，就選舉出新的主服務器，但是實時上原來的主服務器還在繼續提供服務，這就導致出現了“雙主”現象，為了解決這種問題，需要想辦法把舊的主服務器隔離，使其不能正常對外提供服務。為了保證元數據的強一致性，在進行準備切換的時候，新的主服務器必須要在確認元數據完全同步之後才能繼續對外提供服務。為了達到這個目的，一種方式是當元數據變化時立即通知所有的緩存服務器，並鎖定數據，例如如果系統要完成的任務需要多個碎片裡同時對狀態進行更新，那麼在更新完成之前，訪問將被拒絕。另一種在高度可擴展的NoSQL數據庫中經常實現的複制數據之間保持高度一致性的方法是使用讀寫仲裁和版本控制。這種方法避免了鎖定數據，代價是讀取和寫入數據的過程中會帶來額外的複雜度。

區塊鏈的網絡分片指將礦工劃分成幾個組，同時驗證交易，提高系統並行處理交易的能力，進而可提高TPS。通常可以通過定期以隨機數生成來決定選取達成共識的節點，只要將其映射到已經編好號的碎片中問題也就變的好處理多了。但是如果有節點宕機，重新分配節點時，就需要在碎片之間形成一致性共識。值得注意的是，在區塊鏈中採用網絡分片技術，也就是將礦工分成幾個子網絡分別負責驗證該碎片上的交易，需要保證惡意節點的數目足夠小，也因此在分配礦工的規則上需要注意保證隨機性。

參考文獻：

參考文獻：

參考文獻：https://www.cnblogs.com/xybaby/p/7076731.html

參考文獻：http://www.8btc.com/sharding-blockchain-scalability

3. 《sharding》，https://docs.mongodb.com/manual/sharding/

4. 《Sharding pattern》，https://docs.microsoft.com/en-us/azure/architecture/patterns/sharding

5. 《Database sharding explained in plain English》，https://www.citusdata.com/blog/2018/01/10/sharding-in-plain-english/

1. 《帶著問題學習分佈式系統之數據分片》，https://www.odaily.com/post/5132394

2. 《分片技術（sharding）——區塊鏈擴容問題的良方》，http://8btc.com/article-4660-1.html