Filecoin系列 - IPLD 技術分析

1. 用途

1.1 存儲數據

為了成功地將數據加到 Filecoin 網絡, 需要成功完成以下步驟:

客戶端導入數據生成CAR文件: 數據必須打包成 CAR file (內容可尋址檔案) - CAR是IPLD規范的序列化歸檔文件.
存儲交易: 存儲供應商和客戶之間的存儲交易必須由客戶發起, 并由存儲供應商接受。
傳輸CAR文件: 數據必須傳輸給存儲供應商。
存儲供應商必須將數據放在一個扇區(Sector)中，封包并提交證明給Filecoin網絡

存儲時的數據表示:

要存儲的文件 -> IPLD DAG -> 序列化為CAR文件(它的Payload就是IPLD DAG) -> 生成Piece(包含PayloadCID, Payload和Zero-Padding) -> 派生PieceCID(也叫CommP,是Payload+Zero-Padding的Merkle 根哈希) -> 若干個Piece 組成UnsealedSector -> CommD(Pieces的 Merkle 根) -> SealedSector(密封該扇區) -> CommRLast(sealedSector的Merkle 根) 和 CommC(lable的Merkle 根哈希) -> CommR(復制承諾) = Hash(CommC || CommRLast)

*PayloadCID*在 CAR’ed 和 un-CAR’ed 結構之間是通用的
CAR文件用于存儲和網絡傳輸 IPLD數據塊
生成的 .car 文件用額外的零位填充，以便文件生成二叉 Merkle 樹。要獲得干凈的二進制 Merkle 樹，.car 文件大小必須是二的某個冪 (^2) 。一個名為的填充過程Fr32 padding將每 256 位中的每 254 位添加2個零位應用于輸入文件。
*檢索交易是根據PayloadCID*協商的

? 該圖顯示了 Piece 及其證明樹的詳細組成，包括完整和帶寬優化的 Piece 數據結構。

1.2 檢索數據

檢索市場基于PayloadCID。PayloadCID代表文件UnixFS版本的 IPLD DAG根的哈希。在此階段，該文件是具有IPFS樣式表示形式的原始系統文件。為了使客戶能夠在檢索市場上請求一些數據，他們必須知道PayloadCID。

檢索時的數據表示:

要檢索的文件的PayloadCID -> 未密封文件(可能需要解封獲得) -> un-CAR’ed 文件 -> 按IPLD DAG傳輸 -> 得到目標文件

1.3 數據傳輸

JS GraphSync 是 JavaScript 中 GraphSync 協議的實現。當用戶想要在 Filecoin 網絡中存儲數據時，在數據傳輸過程中使用了 GraphSync。GraphSync 允許本地節點請求遠程節點以獲取遠程節點 IPLD 數據的結果。
Filecoin 可以使用 GraphSync 來同步區塊鏈并以去信任的方式傳輸 DAG 化的內容。對于網絡參與者來說，JS GraphSync的實現可以實現網頁上的點對點同步，使瀏覽器能夠完成IPFS數據同步。

2. IPLD原理

2.1 IPLD的協議組成

CID（Self-describing content-addressed identifiers for distributed systems）：基于內容尋址的自我描述標識
IPLD tree：基于 JSON、Protobuf和路徑導航的跨協議的數據模型
IPLD Resolvers: IPLD轉換器，可以添加新的協議到IPLD里面

2.2 IPLD對象由兩個部分組成

Data?— 大小 < 256 kB 的非結構化二進制數據塊。
Links?— 鏈接結構數組。這些是指向其他 IPFS 對象的鏈接。每個 IPLD 鏈接有 3 個部分：
- Name?— 鏈接的名稱
- Hash? — 鏈接的 IPFS 對象的哈希
- Size——鏈接的 IPFS 對象的累積大小，包括跟隨它的鏈接

2.3 Merkle DAG

IPLD使用 Merkle DAG(又名有向循環圖) 數據結構來鏈接數據塊

IPLD 是一組標準和實現，用于創建可普遍尋址和鏈接的去中心化數據結構。這些結構允許我們為數據做 URL, 就像超鏈接為 HTML 網頁所做的事情。

Merkle DAG 提供了一種實現重復數據刪除的直接方法，通過將冗余部分編碼為鏈接來有效地存儲數據。

外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳

Merkle DAG 是許多不同項目的基本構建塊：Git 等版本控制系統、以太坊等區塊鏈、IPFS 等去中心化網絡協議以及 Filecoin 等分布式存儲網絡都使用Merkle DAG 用于存儲和通信數據！

可以解析 IPLD 數據和 CID 的系統可以引用來自其他系統的內容：例如，我們可以有一個引用 IPFS 中數據 blob 的 Filecoin 交易，或者一個引用特定 Git 提交的基于區塊鏈的智能合約！CID 使我們能夠為每條數據提供唯一的全球地址；Merkle DAG 和 IPLD 為我們提供了一種遍歷和理解數據結構的方法。它們共同構成了一個由相互關聯和相互理解的數據生態系統組成的全球網絡的基礎。

3. 支持鏈接類型

參考: 深入理解IPFS（2/6）：什么是星際關聯數據（IPLD）？

3.1 鏈接數據

IPLD 允許我們將所有散列鏈接的數據結構視為統一信息空間的子集，將所有通過散列鏈接數據的數據模型統一為 IPLD 的實例。這意味著可以從全局命名空間中完全不同的數據結構鏈接和引用數據。在 Filecoin 中被廣泛使用:

所有系統數據結構都使用 DAG-CBOR（IPLD 編解碼器）存儲。
存儲在 Filecoin 網絡上的文件和數據也使用各種 IPLD 編解碼器（不一定是 DAG-CBOR）存儲。

因為 IPLD 是為內容尋址數據設計的，所以它還在其數據模型中包含一個“鏈接”原語。實際上，鏈接使用 CID規范。IPLD 數據被組織成“塊”，其中一個塊由原始編碼數據及其內容地址或 CID 表示。每個內容可尋址的數據塊都可以表示為一個塊，這些塊一起可以形成一個連貫的圖或 Merkle DAG。

3.2 IPLD 選擇器

IPLD 選擇器還可用于尋址鏈接數據結構中的特定節點。

–> 3.3 已能鏈接的異構數據

通過 IPLD，*可以跨協議遍歷鏈接，讓您可以探索數據，而無需考慮底層協議*。

Git
Bitcoin
Ethereum
IPFS

4. 支持可驗證性

可通過CID來驗證一棵 Merkle DAG 樹

通過 Ipld 數據結構持久化這種狀態以及通過使用檢查狀態并可能糾正錯誤的初始化例程來實現的。

所有系統數據結構都使用 DAG-CBOR（IPLD 編解碼器）存儲。DAG-CBOR 是 CBOR 的一個更嚴格的子集，具有預定義的標記方案，專為哈希鏈接數據 DAG 的存儲、檢索和遍歷而設計。與 CBOR 相比，DAG-CBOR 可以保證確定性。

5. 不支持錯誤恢復-糾刪碼(Erasure Code)

參考: EC糾刪碼原理

什么是Erasure Code ?
Erasure Code（EC），即糾刪碼，是一種前向錯誤糾正技術（Forward Error Correction，FEC，說明見后附錄），主要應用在網絡傳輸中避免包的丟失，存儲系統利用它來提高存儲可靠性。相比多副本復制而言，糾刪碼能夠以更小的數據冗余度獲得更高數據可靠性，但編碼方式較復雜，需要大量計算。糾刪碼只能容忍數據丟失，無法容忍數據篡改，糾刪碼正是得名與此。

EC的定義

Erasure Code是一種編碼技術，它可以將n份原始數據，增加m份數據，并能通過n+m份中的任意n份數據，還原為原始數據。即如果有任意小于等于m份的數據失效，仍然能通過剩下的數據還原出來。

EC的分類

糾刪碼技術在[分布式存儲](http://www.chinabyte.com/keyword/分布式存儲/ //t _blank) 系統中的應用主要有三類: 陣列糾刪碼（Array Code: RAID5、RAID6等）、RS(Reed-Solomon)里德-所羅門類糾刪碼和LDPC(LowDensity Parity Check Code)低密度奇偶校驗糾刪碼。

磁盤陣列存儲（RAID 5、RAID 6）
云存儲（RS）: 涉及到矩陣求逆，采用高斯消元法
LDPC碼目前主要用于通信、視頻和音頻編碼等領域。與RS編碼相比，LDPC編碼效率要略低，但編碼和解碼性能要優于RS碼以及其他的糾刪碼，主要得益于編解碼采用的相對較少并且簡單的異或操作。

RS Code

編碼：給定n個數據塊（Data block）D1、D2……Dn，和一個正整數m，RS根據n個數據塊生成m個編碼塊（Code block），C1、C2……Cm。

上圖最左邊是編碼矩陣(柯西矩陣)，編碼矩陣需要滿足任意n * n子矩陣可逆。編碼矩陣上部是單位陣（n行n列），下部是m行n列矩陣。下部矩陣可以選擇范德蒙德矩陣或柯西矩陣。
解碼：對于任意的n和m，從n個原始數據塊和m個編碼塊中任取n塊就能解碼出原始數據，即RS最多容忍m個數據塊或者編碼塊同時丟失。
1. 假設D1、D4、C2丟失，從編碼矩陣中刪掉丟失的數據塊/編碼塊對應的行。
2. 由于B’ 是可逆的，記B’的逆矩陣為 (B’^-1)，則B’ * (B’^-1) = I 單位矩陣。兩邊左乘B’ 逆矩陣。
3. 恢復原始數據D, 對D重新編碼，可得到丟失的編碼碼

EC vs RAID

正如許多分布式存儲那樣，三副本的容量利利用率始終是個問題，特別是對于海量?結構化數據和冷存儲這些在意性價比的應用來說。相比之下，糾刪碼(Erasure Code)能夠提供接近于本地 RAID 5/6 的有效磁盤空間，代價是犧牲了性能。糾刪碼在隨機寫?，特別是改寫和重構(Rebuild)時產生的 I/O 懲罰較大，對應的集群網絡流量比副本保護模式要大。

結論

IPLD支持鏈接類型, 所以它的塊數據可以是要鏈接的CID (即要鏈接的數據可以不在本地), 所以才叫內容可尋址數據結構
IPLD已支持的異構數據: Git, Bitcoin,Ethereum,IPFS. 不確定支不支持filecoin上的sector數據
IPLD本身不包含糾刪碼技術, 得自己在存儲底層實現. (如采用22+2的糾刪碼技術，將空間利用率提升到了90%以上，相較于3副本策略，硬件成本縮減超過50%)

截屏2020-12-03 下午2.10.37

附錄

名詞解釋

`CID`

IPFS 使用的內容標識符. CID 是一個散列摘要，其前綴是其散列函數和編解碼器的標識符。這意味著您可以僅使用此標識符來驗證和解碼數據。

`IPLD`

IPLD (InterPlanetary Linked Data ), IPLD 是為內容尋址數據設計的，所以它還在其數據模型中包含一個“鏈接”原語。實際上，鏈接使用 CID規范。IPLD 數據被組織成“塊”，其中一個塊由原始編碼數據及其內容地址或 CID 表示。每個內容可尋址的數據塊都可以表示為一個塊，塊一起可以形成一個連貫的圖，或 Merkle DAG。

IPFS 使用IPLD 來管理和鏈接所有數據塊**。**
Filecoin 節點的 IPLD 存儲是哈希鏈接數據的本地存儲

`UnixFS`

建立在 IPLD Merkle-Dags 之上的文件格式

`DAG-CBOR`

Filecoin 系統數據結構都使用 DAG-CBOR（一種 IPLD 編解碼器）存儲, 具有預定義的標記方案，專為哈希鏈接數據 DAG 的存儲、檢索和遍歷而設計。

Filecoin上, IPLD DAG 經 DAG-CBOR 序列化到 CAR文件

`DAG-PB`

IPFS中 IPLD 序列化為CAR文件的編解碼器

`CAR`

CAR格式（Content Addressable aRchives）可用于將IPLD塊數據形式的內容可尋址對象存儲為字節序列；通常在具有.car文件擴展名的文件中。

`Piece`

Piece是用戶想要存儲在 Filecoin 上的數據的主要記賬單位和協商單位。 Piece不是一個存儲單元，它沒有特定的大小，而是以Sector的大小為上限。一個 Filecoin Piece 可以是任何大小，但如果一個 Piece 大于礦工支持的 Sector 的大小，則必須將它分成更多的 Pieces，以便每個 Piece 適合一個 Sector。

每個 Filecoin Piece 是一個 CAR 文件，包含一個IPLD DAG，有對應的數據CID和piece CID。

`Bitswap`

IPFS 中的數據傳輸算法

`GraphSync`

Filecoin 中的數據傳輸算法, 使用 GraphSync 來同步區塊。

數據可用性

數據可用性（Data Availability）是指發生了各種物理上的故障，系統仍然可用，數據不會丟失，一般通過RAID、副本、糾刪碼等技術實現。IPFS本身是不對可用性做保障的。因為添加的文件，默認只會放到本地節點。其他節點訪問了相關的文件，才會在自己的機器上面存一份。但對于企業應用來說，數據一經寫入，一般來說就需要有冗余，以防止各種意外情況導致數據損壞。從白皮書來看，Filecoin會使用副本或者糾刪碼來實現相關的功能。其他基于存儲的區塊鏈項目，也或多或少要涉及到這塊才有價值。如果使用原生IPFS，那基于ipfs-cluster可以實現數據的自動冗余，但每個節點都存一份數據開銷的確非常大。因此，基于IPFS提高數據可靠性方面的努力，是反映IPFS方案廠商技術實力的重要方面。

Filecoin的糾刪碼技術沒找到