簡介

storj 是在 Kademlia 上構(gòu)建的。

加密與分片

文件應(yīng)該在分片前在客戶端被加密。
數(shù)據(jù)擁有者擁有加密的密鑰祟蚀。
碎片大小是一個(gè)可設(shè)置的參數(shù)敬锐。

Proofs of Retrievability

數(shù)據(jù)完整性通過proof of retrievability維持

可獲取證明，確保分片被正確存儲喇勋。

通過 challenge-response 交互，也稱為 audit, 或 heartbeat, 來驗(yàn)證文件是否可獲取。

data owner 隨機(jī)生成 n 個(gè) challenge salts 列表, s0, s1, ...sn?1, 并存儲 salts 列表.

pi 是 pre-leaf
pi = H(si + d)

li 是 merkle 樹的葉子
li = H(H(si + d))

如果葉節(jié)點(diǎn)的個(gè)數(shù)不是2的冪次揩页，增加空字符串的 hash 作為新葉子，知道葉節(jié)點(diǎn)的個(gè)數(shù)是2的冪次烹俗。

data owner 存儲 challenges(salts) 列表, merkle root, 和 merkle 樹的高度爆侣，然后把 merkle 樹的部分葉節(jié)點(diǎn)發(fā)給 farmer萍程。
farmer 存儲部分 merkle 葉節(jié)點(diǎn)和 shard。

data owner 會周期性地挑選出一個(gè) challenge(salt)累提，并發(fā)送給 farmer尘喝。challenge 不可以被重用。

data owner 用 challenge(salt)斋陪、shard朽褪、merkle 樹葉列表，生成 merkle proof 并發(fā)送給 data owner无虚。

merkle proof 總是包含 log₂(l) + 1 個(gè) hashes缔赠，data owner 使用 merkle root 和 merkle 樹高來驗(yàn)證 merkle proof 的有效性。

局部 audit

為了減小 IO 負(fù)擔(dān)而采取的一種方案友题。

發(fā)出 Audits

Storj 擴(kuò)展 Kademlia message嗤堰，增加來一個(gè)新消息類型: AUDIT.

數(shù)據(jù)存取流程

該合同系統(tǒng)擴(kuò)展 Kademlia message，增加來四個(gè)新消息類型: OFFER, CONSIGN, MIRROR, and RETRIEVE.

存文件

取文件

備份文件

付費(fèi)

使用 Strojcoin度宦，使用微支付管道踢匣。

在 audit 時(shí)支付費(fèi)用，最小化信任需求戈抄。

小額支付离唬，價(jià)格小于 $0.000001 per audit.

Quasar

p2p publish/subscribe system.

擴(kuò)展 Kademlia, 增加 3 個(gè)新消息類型: SUBSCRIBE、UPDATE划鸽、PUBLISH输莺。

每個(gè)節(jié)點(diǎn)保存 topic，以及訂閱那些 topic 的 節(jié)點(diǎn)裸诽，這些節(jié)點(diǎn)距離本節(jié)點(diǎn)最遠(yuǎn)距離為 3.

獲取其他節(jié)點(diǎn)的訂閱列表

傳播本節(jié)點(diǎn)的新訂閱

先 SUBSCRIBE 是為了了解鄰居的狀態(tài)嫂用，可能是為了做一些策略。

發(fā)布

PUBLISH 消息包含一個(gè) TTL 參數(shù)丈冬，防止無限傳播嘱函。
為了防止節(jié)點(diǎn)再次收到同樣的 PUBLISH 信息，節(jié)點(diǎn)收到 PUBLISH 后埂蕊，會將自己的 node id 加到過濾列表再轉(zhuǎn)發(fā)实夹，轉(zhuǎn)發(fā)時(shí)不會發(fā)送給過濾列表中存在的節(jié)點(diǎn)。

冗余方案

簡單副本策略

文件shard 存多個(gè)副本粒梦，shard副本 越多亮航，可靠性越高。

K-of-M 丟失文件還原

丟失文件還原算法講一個(gè)文件分成 k 個(gè) shard匀们，并創(chuàng)建 m 個(gè)等價(jià) shard缴淋，共 k + m = n 個(gè) shard。
n 個(gè) shard 中的任意 k 個(gè) shard，可以重建文件或任意一個(gè)丟失的 shard重抖。
data owner 可以容忍部分 shard 丟失露氮。

比如 20-of-40 組合，可以容忍 5 個(gè) shard丟失钟沛，因?yàn)樵賮G失 16 個(gè) shard 的概率很低畔规。

KFS

本地文件存儲，使用 LevelDB恨统。
LevelDB存儲超過100GB叁扫，會影響性能，所以需要多個(gè) LevelDB 實(shí)例畜埋。

基本原理

多個(gè) LevelDB實(shí)例緩解了操作壓力莫绣，提升每個(gè)實(shí)例的操作速度。
多個(gè) LevelDB悠鞍，每個(gè) LevelDB 存的范圍小对室，鎖的范圍更小，并發(fā)數(shù)更大咖祭，阻塞時(shí)間也更短掩宜。

S-Buckets 與路由

KFS 存儲分片在 B 個(gè) 大小限制的 LevelDB 實(shí)例，稱為 S-Buckets.
S-Buckets 存儲最大的字節(jié)大小為 S么翰。
因此 KFS 最大存儲大小為 S*B bytes牺汤。
Stroj 目前使用 S = 32 GB，B = 256 個(gè)實(shí)例硬鞍。總大小為 8 TB戴已。

KFS 有一個(gè)隨機(jī)的 R bits id固该，要求 R >= log₂(B)。
即 256 個(gè)實(shí)例糖儡，至少需要 8 bit伐坏。

1、 g = log₂(B)
2握联、 h 為 KFS id 的前 g bits
3桦沉、 i 為 shard hash 的前 g bits
4、 n = h 異或 i
5金闽、 存儲 shard 在第 n 個(gè)LevelDB 實(shí)例

如果一個(gè) KFS 實(shí)例滿了纯露，第二個(gè)實(shí)例會被創(chuàng)建。

存儲細(xì)節(jié)

數(shù)據(jù)被分塊存儲代芜，每塊 C 字節(jié)埠褪。默認(rèn) C = 128 KB。
每個(gè)塊的 key 為 數(shù)據(jù)全部內(nèi)容的 hash + “ ” + 數(shù)字索引
這是為了確保 kv對 較小，同時(shí)能夠從 S-Bucket 中順序讀寫钞速。
數(shù)字索引字符長度為：l = log₁₀(LevelDB存儲容量/塊大小)
比如 l = 6,則第 3753 個(gè)塊的數(shù)字索引為 ‘003753’

NAT 穿透與反向 HTTP 打開通道

Storj 擴(kuò)展 Kademlia贷掖，增加 3 個(gè)額外類型：PROBE、FIND_TUNNEL渴语、OPEN_TUNNEL苹威。

檢查自己是否是公網(wǎng)地址

本節(jié)點(diǎn)不是公網(wǎng)IP，反向打開通道

Bridge

Bridge 是管理節(jié)點(diǎn)驾凶。負(fù)責(zé)文件存取協(xié)商牙甫、校驗(yàn)文件可獲取、支付狭郑、文件狀態(tài)腹暖。被設(shè)計(jì)為只存儲云數(shù)據(jù)。

Client 負(fù)責(zé)加密翰萨、文件預(yù)處理脏答、文件密鑰管理。

Bridge 必須是可靠的亩鬼，Client可以不可靠殖告。

上傳操作

1. Client 收集并預(yù)處理。
2. Client 通知 Bridge 等待上傳數(shù)據(jù)雳锋。
3. Bridge 與網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)商(上傳)
4. Bridge 返回節(jié)點(diǎn)和 token 列表給 Client
5. Client 根據(jù)節(jié)點(diǎn)IP 和 token 上傳數(shù)據(jù)
6. Client 把 AUDIT 信息給 Bridge黄绩，委托管理
7. Bridge 驗(yàn)證文件可獲取
8. Bridge 承擔(dān) AUDIT、支付玷过、管理文件狀態(tài)的責(zé)任
9. Bridge 通過 API 顯示文件的 metadata

下載操作

1. Client 傳遞標(biāo)記文件的標(biāo)識符爽丹，并請求文件
2. Bridge 校驗(yàn)請求，提供 farmer IP + token 的列表
3. Client 根據(jù) IP 和 token 取得文件
4. 文件在客戶端組裝并解碼

參考

stroj 白皮書