分布式存儲
以電影為例子，那么有很多電影表制，分布式節(jié)點是不是都要把所有的電影完整存儲在本地節(jié)點上健爬，還是分開存儲，如果一旦分散存儲么介，節(jié)點加入和退出會不會影響到整個存儲電影的數(shù)據(jù)娜遵。
一致性哈希
一致性哈希算法在1997年由麻省理工學(xué)院提出的一種分布式哈希（DHT）實現(xiàn)算法，設(shè)計目標(biāo)是為了解決因特網(wǎng)中的熱點(Hot spot)問題壤短，初衷和CARP十分類似设拟。一致性哈希修正了CARP使用的簡 單哈希算法帶來的問題慨仿，使得分布式哈希（DHT）可以在P2P環(huán)境中真正得到應(yīng)用。?
一致性hash算法提出了在動態(tài)變化的Cache環(huán)境中纳胧，判定哈希算法好壞的四個定義：
平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去镰吆，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件跑慕。
單調(diào)性(Monotonicity)：單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中万皿，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去核行，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)牢硅。
分散性(Spread)：在分布式環(huán)境中，終端有可能看不到所有的緩沖芝雪，而是只能看到其中的一部分减余。當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同绵脯，從而導(dǎo)致哈希的結(jié)果不一致佳励，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應(yīng)該避免的蛆挫，因為它導(dǎo)致相同內(nèi)容被存儲到不同緩沖中去赃承，降低了系統(tǒng)存儲的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度悴侵。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生瞧剖，也就是盡量降低分散性。
負(fù)載(Load)：負(fù)載問題實際上是從另一個角度看待分散性問題可免。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中抓于，那么對于一個特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同 的內(nèi)容浇借。與分散性一樣捉撮，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷妇垢。(摘自百度百科-一致性哈希)
一致性哈希（Consistent Hashing）：結(jié)合上面的例子說明巾遭，使用一組不同的hash函數(shù)，根據(jù)電影的文件名movie-name分別計算出一組h1（x）計算hash值闯估。根據(jù)hash函數(shù)h（x）再結(jié)合分布式網(wǎng)絡(luò)中每個節(jié)點n的唯一名稱或者標(biāo)簽灼舍，再計算一組h2（x）計算hash值。針對某一個電影來說涨薪，那么h1（x）≈h2（x）骑素。那么講其一個副本存儲在該網(wǎng)絡(luò)節(jié)點上。計算公式：|h1（x）-h2（x）|=min{|h1（x）-h2（x）|}刚夺。這個針對每一個任意節(jié)點來計算献丑。
那么我們假設(shè)有m部電影末捣、網(wǎng)絡(luò)中有n個節(jié)點、有k個hash函數(shù)创橄，根據(jù)節(jié)點的hash值和電影hash最為接近的原則塔粒，得到一個存放電影的期望值km/n。
那么問題來了筐摘，節(jié)點如果不能保證長期在線正常的工作，這個時候就需要考慮節(jié)點的加入和退出帶來的影響船老。在這個環(huán)境中咖熟，網(wǎng)絡(luò)中的節(jié)點無法直接知道那個節(jié)點具體存放了那個電影，在搜索的時候會不斷詢問周邊節(jié)點柳畔，周邊節(jié)點再詢問周邊馍管，直到找到所需要的信息。簡單理解分布式系統(tǒng)內(nèi)部有一個虛擬網(wǎng)絡(luò)薪韩，稱為覆蓋網(wǎng)絡(luò)（Overlay Network）确沸。
一致性哈希算法設(shè)計原理
針對節(jié)點的加入和退出，一致性hash算法原則：?
環(huán)形Hash空間?
按照常用的hash算法來將對應(yīng)的key哈希到一個具有2^32次方個桶的空間中俘陷，即0~(2^32)-1的數(shù)字空間中÷奚樱現(xiàn)在我們可以將這些數(shù)字頭尾相連，想象成一個閉合的環(huán)形拉盾。?
把數(shù)據(jù)通過一定的hash算法處理后映射到環(huán)上桨菜，每個對象通過特定的Hash函數(shù)計算出對應(yīng)的key值，然后散列到Hash環(huán)上捉偏。?
節(jié)點機(jī)器通過hash算法映射到環(huán)上?
在采用一致性哈希算法的分布式集群中將新的機(jī)器加入倒得，其原理是通過使用與對象存儲一樣的Hash算法將機(jī)器也映射到環(huán)中，然后以順時針的方向計算夭禽，將所有對象存儲到離自己最近的機(jī)器中霞掺。這樣的部署環(huán)境中，hash環(huán)是不會變更的讹躯，因此菩彬，通過算出對象的hash值就能快速的定位到對應(yīng)的機(jī)器中，這樣就能找到對象真正的存儲位置了蜀撑。?
機(jī)器的刪除?
節(jié)點（機(jī)器）的刪除挤巡，如果任意出現(xiàn)故障被刪除了，那么按照順時針遷移的方法酷麦，對象將會被遷移到下一個節(jié)點中矿卑，這樣僅僅是對象的映射位置發(fā)生了變化，其它的對象沒有任何的改動沃饶。?
機(jī)器的增加?
節(jié)點（機(jī)器）的添加母廷，如果往集群中添加一個新的節(jié)點轻黑，通過對應(yīng)的哈希算法得到KEY4，并映射到環(huán)中琴昆。?
按順時針遷移的規(guī)則氓鄙，那么對象被遷移到了下一個節(jié)點中，其它對象還保持這原有的存儲位置业舍。通過對節(jié)點的添加和刪除的分析抖拦，一致性哈希算法在保持了單調(diào)性的同時，還是數(shù)據(jù)的遷移達(dá)到了最小舷暮，這樣的算法對分布式集群來說是非常合適的态罪，避免了大量數(shù)據(jù)遷移，減小了服務(wù)器的的壓力下面。?
平衡性處理?
一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性复颈，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由，因為還缺少了平衡性沥割。引入“虛擬節(jié)點”（ virtual node ）是實際節(jié)點（機(jī)器）在 hash 空間的復(fù)制品（ replica ）耗啦，一實際個節(jié)點（機(jī)器）對應(yīng)了若干個“虛擬節(jié)點”，這個對應(yīng)個數(shù)也成為“復(fù)制個數(shù)”机杜，“虛擬節(jié)點”在 hash 空間中以hash值排列帜讲。
參考：https://blog.csdn.net/cywosp/article/details/23397179/?有興趣可以看看全文，文章圖片和文字都有詳細(xì)說明叉庐。
IPFS
星際文件系統(tǒng)IPFS（InterPlanetary File System）是一個面向全球的舒帮、點對點的分布式版本文件系統(tǒng)，目標(biāo)是為了補(bǔ)充（甚至是取代）目前統(tǒng)治互聯(lián)網(wǎng)的超文本傳輸協(xié)議（HTTP）陡叠，將所有具有相同文件系統(tǒng)的計算設(shè)備連接在一起玩郊。原理用基于內(nèi)容的地址替代基于域名的地址，也就是用戶尋找的不是某個地址而是儲存在某個地方的內(nèi)容枉阵，不需要驗證發(fā)送者的身份译红，而只需要驗證內(nèi)容的哈希，通過這樣可以讓網(wǎng)頁的速度更快兴溜、更安全侦厚、更健壯、更持久拙徽。
IPFS的存儲與讀取
接下來先基礎(chǔ)地介紹下IPFS是怎么進(jìn)行存儲和讀取的刨沦。IPFS文件的存儲和讀取與BitTorrent上傳下載原理相似。?
IPFS采用的索引結(jié)構(gòu)是DHT（分布式哈希表）膘怕，數(shù)據(jù)結(jié)構(gòu)是Merkle DAG（Merkle 有向無環(huán)圖）想诅。?
單文件存儲?
研究過文件系統(tǒng)的人都知道索引和扇區(qū)這兩個概念，如：NTFS一個扇區(qū)通常是4K，真正的文件數(shù)據(jù)都是保存在扇區(qū)里面的来破，找到這些扇區(qū)的方式就是建立索引（確切的說是高效的索引）篮灼，IPFS也是一個文件系統(tǒng)，不同的是徘禁，IPFS是沒有存儲上限的诅诱，且不存在空間回收的功能。IPFS存儲文件時送朱，如圖(沒天賦娘荡，略丑)，會經(jīng)歷以下幾個步驟：?
1. 把單個文件拆分成若干個256KB大小的塊（ block驶沼，這個就可以理解成扇區(qū) ）它改；?
2. 逐塊(block)計算block hash，hashn = hash ( blockn )商乎；?
3. 把所有的block hash拼湊成一個數(shù)組，再計算一次hash祭阀，便得到了文件最終的hash鹉戚，hash ( file ) = hash ( hash1……n )，并將這個 hash（file） 和block hash數(shù)組“捆綁”起來专控，組成一個對象抹凳，把這個對象當(dāng)做一個索引結(jié)構(gòu)；?
4. 把block伦腐、索引結(jié)構(gòu)全部上傳給IPFS節(jié)點（這里先不介紹細(xì)節(jié)）赢底，文件便同步到了IPFS網(wǎng)絡(luò)了；?
5. 把 Hash（file）打印出來柏蘑，讀的時候用幸冻；?
PS: 這里可以看出IPFS計算文件得到的hash，其實和我們平時計算hash的方式不一樣咳焚，而且最終的結(jié)果也不一樣洽损！?
這里還漏掉了一個小文件的處理邏輯，和NTFS等文件系統(tǒng)類似革半，小文件（小于 1KB） 的文件碑定，IPFS會把數(shù)據(jù)內(nèi)容直接和Hash（索引）放在一起上傳給IPFS節(jié)點，不會再額外的占用一個block的大小又官。?
現(xiàn)在延刘，已經(jīng)把文件的原始數(shù)據(jù)和文件的索引（即hash）上傳到IPFS網(wǎng)絡(luò)了。前面已經(jīng)講過六敬，IPFS是不支持空間回收的碘赖，文件一旦同步到IPFS，將永久的存在⊙掳蹋看起來這樣會招來一個嚴(yán)重的后果就是秘车，如果頻繁的編輯大文件，每編輯一次就要重新同步劫哼，豈不是會過度浪費(fèi)空間６Ｅ俊？舉個例子：?
本地有一個1G的大文件File1权烧，已經(jīng)同步到IPFS了眯亦，后面在這個文件File1后面追加了1K的內(nèi)容，現(xiàn)在需要重新同步這個文件般码，算下來需要花費(fèi)的空間應(yīng)該是：1G+1G+1K妻率；?
然而，事實并非如此板祝。IPFS在儲存數(shù)據(jù)的時候宫静，同一份數(shù)據(jù)只存儲一次，文件是分塊（block）存儲的券时，hash相同的block孤里，只會存儲一次，也就說橘洞，前面1G的內(nèi)容沒有發(fā)生改變捌袜，其實IPFS并不會為這些數(shù)據(jù)分配新的空間，只會為最后1K的數(shù)據(jù)分配一個新的block炸枣，再重新上傳hash虏等，實際占用的空間是： 1G + 1K ;?
不同的文件有很多數(shù)據(jù)是存在重復(fù)的，如不同語言字幕的電影适肠，影音部分相同的霍衫，只有字幕部分不一樣，當(dāng)兩個不同國家的人都在上傳同一部電影的時候侯养，這些文件在分塊（block）的時候慕淡，很有可能有大部分block的hash是一致的，這些block在IPFS上也只會存儲一份沸毁，這樣一來就可能會有很多文件的索引指向同一個block峰髓，這里就構(gòu)成了前面提到的一個數(shù)據(jù)結(jié)構(gòu)——Merkle DAG（Merkle 有向無環(huán)圖）。?
因為所有的索引上都保存了hash息尺，所以Merkle DAG具有以下特點（從白皮書上扒下來的）：?
1. 內(nèi)容可尋址：所有內(nèi)容都是被多重hash校驗和來唯一識別的携兵，包括links。?
2. 無法篡改：所有的內(nèi)容都用它的校驗和來驗證搂誉。如果數(shù)據(jù)被篡改或損壞徐紧，IPFS會檢測到。?
3. 重復(fù)數(shù)據(jù)刪除：重復(fù)內(nèi)容并只存儲一次。
文件樹存儲
IPFS支持目錄結(jié)構(gòu)并级，存儲目錄的方式很簡單：
先把目錄下所有的文件同步到IPFS網(wǎng)絡(luò)中去拂檩，為所有的文件hash建立一個別名，這個別名其實就是本地文件名嘲碧，把hash和別名“捆綁”在一起組建成一個名為 IPFSLink 的對象稻励；?
把該目錄下所有的 IPFSLink 對象組成一個數(shù)組，對該數(shù)組計算一個目錄hash愈涩，并將數(shù)組和目錄hash拼成一個結(jié)構(gòu)體望抽，同步到IPFS網(wǎng)絡(luò)；?
如果上層還有目錄結(jié)構(gòu)履婉，則為目錄hash建立一個別名（就是目錄名）煤篙，把目錄hash和別名“捆綁”在一起組建成一個 IPFSLink 的對象，重復(fù)從步驟2開始執(zhí)行毁腿；?
把目錄hash打印出來辑奈，讀取的時候用；?
由上可以看出已烤，對于IPFS而言身害，存儲目錄和文件其實是一樣的處理方式，IPFS甚至根本沒有關(guān)心節(jié)點想要存儲的是一個目錄還是一個文件草戈。
單文件讀取
IPFS取文件的方式，就比較簡單了侍瑟，就是存儲方式的一個逆推過程：?
根據(jù)hash搜索該hash的索引結(jié)構(gòu)唐片，即找到該文件hash 的 block hash數(shù)組（這一步由IPFS網(wǎng)絡(luò)完成，是曠工該干的事情）涨颜，下載下來费韭；此時已經(jīng)得到了 block 的索引，根據(jù)block hash庭瑰，搜索block所在的節(jié)點位置星持，下載下來；本地拼裝block：根據(jù)block hash數(shù)組的順序弹灭，把文件拼湊好督暂。block的下載是IPFS的核心，這中間涉及到很多復(fù)雜的技術(shù)細(xì)節(jié)穷吮，因為個人能力有限逻翁，這里沒有展開討論，只是先一筆帶過捡鱼。希望不會誤導(dǎo)新入門的讀者八回，以為IPFS就只干了這么點事情！
文件樹讀取
目錄的讀取也是目錄存儲過程的逆推：?
根據(jù)hash搜索該hash的索引結(jié)構(gòu)，找到該目錄的 IPFSLink 對象數(shù)組缠诅，即目錄下的子列表溶浴；?
遍歷數(shù)組，如果IPFSLink對象是文件管引，則取出文件的hash下載該文件士败；?
如果IPFSLink對象是目錄，取出目錄hash汉匙，重新從步驟1開始執(zhí)行拱烁。
大致介紹IPFS文件存儲于讀取，磨鏈社區(qū)-陳狍子噩翠，原文鏈接：http://mochain.info/wordpress/index.php/2018/03/12/qian_xi_ipfs_de_cun_chu_yu_du_qu/
