IPFS,P2P文件系统调研

IPFS - Content Addressed, Versioned, P2P File System
(DRAFT 3)
↑文章链接：https://ipfs.io/ipfs/QmR7GSQM93Cx5eAg6a6yRzNde1FQv7uL6X1o4k7zrJa3LX/ipfs.draft3.pdf

go实现版本：https://github.com/ipfs/go-ipfs
官网：https://ipfs.io/

Abstract：
Introduction:
Background
IPFS Design

Abstract：

IPFS是一个点对点(P2P)的分布式文件系统，它试图用相同的文件系统连接所有的计算设备。IPFS可以被视为一个单独的BitTorrent集群，它在一个Git存储库中交换对象。换句话说，IPFS提供了高吞吐量的内容寻址块存储模型，并具有内容寻址超链接。IPFS包括一个分布式哈希表，一个（an incentivized block exchange）去中心化块交换，一个自认证命名空间。IPFS没有单点故障，节点间不需要信任彼此。

这里关注分布式哈希，incentivized block exchange

Introduction:

对于全局分布式文件系统，学术界和工业界都由十分多的构建尝试。例如仍在使用的AFS（J. H. Howard, M. L. Kazar, S. G. Menees, D. A.
Nichols, M. Satyanarayanan, R. N. Sidebotham, and
M. J. West. Scale and performance in a distributed file
system. ACM Transactions on Computer Systems
(TOCS), 6(1):51{81, 1988）。在学术界外，有很多面向large media的P2P文件共享应用程序。例如Napster, KaZaA, and BitTorrent，利用这些技术构建了十分多的文件分发系统，用户也十分多。BT技术如今也在广泛使用之中。尽管这些应用使用广泛，但应用并不具有作为基础设施的能力（个人理解应该指的是类似的BT应用不能作为文件系统这样的部分来支持构建其他应用，只是能够做到文件分发、共享等功能）。目前没有通用的实现了全局、低延时、去中心化分布式文件系统。

HTTP技术与浏览器的强大功能，使得使用HTTP作为“文件分发”最成功的技术，成为事实上的“分布式文件系统”。不过，HTTP难以演化升级，也并未使用过去发展出来的各种文件分发技术。另一方面，从HTTP出现以来，也催生了很多新的协议，HTTP缺乏的是设计升级优化，可以从提高当前HTTP web性能，在不影响用户体验的情况下创建新功能等角度来考虑。

工业界长时间使用HTTP的愿意在于移动小文件的损耗相当小，即便对于一个有较多流量的小型组织也是如此。因为各种原因（大容量高要求实时性媒体流，大容量数据集，重要文件保存......），现在的数据分发技术遇到了很多挑战。在带宽和关键特性的压力下，我们已经在很多数据分发协议上放弃了HTTP技术，下一步是让这些技术成为Web的一部分。

分布式源代码版本控制系统——Git，开发了许多方法来对分布式数据操作进行建模和实现。Git工具链提供了大型文件分发系统严重缺乏的多功能版本控制功能。Git提到的使用Merkle DAG来进行数据建模，这产生了很多有用的文件分发策略。需要探索的是这种数据结构如何影响面向高吞吐量的文件系统的设计。

文章提出了IPFS，一种新颖的对等版本控制文件系统，来试图协调这些问题。IPFS综合了过去许多成功系统的经验。IPFS的核心原则是将所有数据建模为同一个Merkle DAG的一部分。

Background

分布式哈希表

分布式哈希表用于维护和协调P2P系统元数据。例如BT的 MainlineDHT 跟踪torrent集群中的peers。

Kademlia DHT
（P. Maymounkov and D. Mazieres. Kademlia: A
peer-to-peer information system based on the xor
metric. In Peer-to-Peer Systems, pages 53{65.
Springer, 2002）
提供了几点特性：

在大规模网络高效查找：查询平均需要联系log2(n)个节点。例如20 hops可以查询网络中10^6个节点。
低协调开销:优化了发送给其他节点的控制消息的数量。
通过选择long-lived的节点来抵抗各种攻击。
广泛应用于P2P应用，包括Gnutella和BitTorrent，形成了超过2000万个节点的网络。

Coral DSHT
（M. J. Freedman, E. Freudenthal, and D. Mazieres.
Democratizing content publication with coral. In
NSDI, volume 4, pages 18{18, 2004）
虽然一些点对点文件系统直接在dht中存储数据块，但这只会浪费存储空间和带宽，因为数据必须存储在不需要它的节点。Coral DSHT在三个特别重要的方面扩展了Kademlia:

Kademlia将数据存储在id距离最近(使用XOR-distance)的节点中，这没有考虑应用的数据局部性，忽略了距离远的节点也可能拥有数据，同时强迫距离近的节点存储数据，而不管他们是否需要该数据，这浪费了大量存储和带宽。改进地方在于：Coral DSHT存储了那些可以提供数据块的peer的地址。
Coral将DHT API从get_value(key)拓展为get_any_values(key)（DSHT的 “sloppy”）。即使Coral用户只需要一个peer节点，而不需要整个完整列表，这个API也能工作。Coral只能够分发值的子集到最近节点，避免了热点分发。(当一个键变得流行时，会重载到所有最近的节点)。

不理解点2的意思

Coral组织了一个独立的DSHT层次结构，其根据区域和大小被称为clusters。这使得节点可以首先查询其区域内的peer，从而查找附近的数据而不查询远处的节点，并且大大减少了查找的延迟。

S/Kademlia DHT
(I. Baumgart and S. Mies. S/kademlia: A practicable
approach towards secure key-based routing. In Parallel
and Distributed Systems, 2007 International
Conference on, volume 2, pages 1{8. IEEE, 2007)
S/Kademlia扩展了Kademlia，以两种特别重要的方式防止恶意攻击:

S/Kademlia提供了安全生成NodeId和防止Sybill攻击的scheme。它需要节点
先创建一个PKI密钥对，从密钥对中能够获得他们的身份信息，并向对方sign。一种scheme包括一个工作证明加密谜题，使得生成Sybills的成本很高。
S/Kademlia节点在不相交的路径上查找值，以确保在网络中有大量adversaries的情况下，honest节点能够连接到其他节点。即使adversaries的占比高达网络中的一半，S/Kademlia的成功率也能达到0.85。

BitTorrent技术——块交换

BitTorrent广泛用于P2P文件共享系统，其成功协调网络中大量不可信任节点来用于节点间的文件分发。IPFS设计中用到的BT关键特性包括：

BT数据交换协议使用“以牙还牙”（tit-for-tat）策略，奖励对其他节点作出贡献的节点，惩罚只索取资源的那些节点。
BT peers 跟踪文件碎片的可用性，优先使少见的碎片传递。这减轻了seed的负担，使non-seed peer能够相互交换。
BT标准“tit-for-tat”策略易受某些利用带宽共享策略的攻击。PropShare提出一种不同的peer带宽分配策略，它能更好地抵抗利用带宽攻击的策略，并提高集群的性能。

版本控制系统-Git

版本控制系统提供了基于时间的文件更改建模的工具，同时有效分发不同的版本。流行版本控制系统Git提供了有利的 Merkle DAG对象模型来捕捉文件系统树的改变。

不可变对象表示文件（blob），目录（tree），改变（commit）。
对象是内容定位的，通过内容进行密钥hash。
对其他对象的链接是内嵌的，用于产生Merkle DAG。
大部分版本元数据都是简单的指针引用，因此可以易于创建和更新。
版本控制只更新引用或者添加对象。
向其他用户分发版本更改只需要简单转换对象和更新远端引用。

自认证文件系统-SFS

SFS提出了两种重要的实现(a)分布式信任链，(b)平等共享的全局命名空间。SFS引入了一种用于构建自认证文件系统的技术:使用以下方案对远程文件系统进行寻址
/sfs/:
Location是服务器网络的地址，其中 HostID = hash(public_key || Location)
因此，SFS文件系统的name certify了它的服务器。用户可以验证服务器提供的公钥，协定共享密钥，并确保所有流量的安全。所有SFS实例共享一个全局命名空间，其中的名称分配是加密的，而不受任何中心化主体的限制。

IPFS Design

IPFS是一种分布式文件系统，它综合了以前点对点系统的成功思想，包括DHT、BitTorrent、Git和SFS。IPFS的贡献是简化、发展和将经过验证的技术连接到一个单一的内聚系统，而不是其各部分的总和。IPFS为编写和部署应用程序提供了一个新的平台，并为大数据的分发和版本控制提供了一个新的思路。IPFS甚至可以发展成为Web本身。
ipfs是对等的，没有节点存在特权。IPFS节点将IPFS对象存储在本地存储中。节点之间相互连接并传输对象。这些对象（object）可以表示文件和其他数据结构。IPFS协议被划分为负责不同功能的子协议栈:

Identities - 管理节点标识的生成和连接。
Network - 管理与其他对等体的连接，使用各种底层网络协议。
Routing - 维护定位特定对等体和对象的信息。响应本地和远程查询。默认使用DHT，但可切换。
Exchange - 一个全新的块交换协议(BitSwap)，它负责管理有效的块分配。以market为模型，对数据复制的激励很弱。
Objects - 一个Merkle DAG，链接是内容寻址的不可变对象。可用于表示任意的数据结构，例如文件层次结构和通信系统。
Files - 受Git启发的版本文件系统层次结构。
Naming - 一个自认证可变名称系统

Identities

节点由一个NodeId标识，NodeId由一个公钥的加密哈希生成，由S/Kademlia的静态加密puzzle创建。节点存储它们的公钥和私钥(使用密码短语加密)。用户可以在每次启动时自由地创建一个“新”节点标识，尽管这会损失已积累的网络利益。节点是去中心化的来保持不变。

Network

IPFS节点定期会与网络中的数百个其他节点通信，过程中还可能跨越广泛的互联网。IPFS网络stack特性:

传输:IPFS可以使用任意的传输层协议，并且最适配WebRTC 数据通道和uTP。
可靠性:如果底层网络不能提供可靠性，IPFS能够通过uTP或者SCTP来提供可靠性。
连通性:IPFS也使用ICE NAT穿越技术。
完整性:（可选地)使用哈希校验并检查消息的完整性。
真实性:可选地使用HMAC和发送方的公钥检查消息的真实性。

Routing

IPFS节点需要一个路径系统来指导寻址其他peer的网络地址，以及寻址对特定对象进行服务的peer。IPFS通过S/Kademlia和Coral分布式哈希表来寻址。IPFS DHT对不同size的value存储方式不同，小value(≤1KB)的直接存在DHT中；对于大value，DHT存储他们的引用，也就是可以为块服务的NodeId组。
一些API：

块交换-BitSwap协议

在IPFS中，数据分发是通过使用BitTorrent启发的协议-BitSwap协议来实现的块交换。和BitTorrent一样，BitSwap中的peer也在寻求收集一套想要的块的集合(want_list)，并提供另一组块作为交换(have_list)。不像BT, BitSwap
不限于在一个torrent的块。BitSwap作为一个持久化的市场运行，节点可以获取
它们需要的块，而不管这些块是属于哪个文件的一部分。这些区块可能来自完全不相关的文件系统中的文件。节点聚集在市场进行以物易物。

文章关于BitSwap协议有大量介绍，例如协议的规范数据结构，交换策略，信用保证机制等内容，帮助不大，若有需要可阅读原文。

对象 Merkle DAG

DHT和BitSwap允许IPFS形成一个大规模的点对点系统，用于快速存储和分发块。在这之上，IPFS建立一个Merkle DAG，一个有向无环图，其中对象之间的链接是嵌入在源中的目标的加密哈希。这是Git数据结构的一般化。Merkle DAG为IPFS提供了许多有用的属性，包括:

内容寻址:所有内容由其多哈希校验和唯一标识，包括链接links。
抗篡改性:所有内容用其校验和验证。如果数据被篡改或损坏，IPFS会
检测它。
重复数据删除:所有保存完全相同的内容的对象是相同的，并且只存储一次。这对于索引对象(例如git terees和 commits)或数据的公共部分尤其有用。
IPFS 对象格式：

IPFS Merkle DAG是一种非常灵活的数据存储方式。它唯一的前期就是对象引用需要是内容寻址的、以上述格式编码。IPFS授予应用程序对数据字段的完全控制;应用程序可以使用它们选择的任何自定义数据格式。

可以使用字符串路径API遍历IPFS对象。
路径的工作方式与传统UNIX文件系统和Web中的工作方式相同。Merkle DAG的link使遍历变得容易。
注意IPFS中的完整路径的形式是

/ipfs是前缀，允许这个路径挂载在以标准挂载点的方式mount到现有的系统下面，第一个路径元素是对象hash值。注意IPFS是没有全局root的，root难以处理数百万对象的分布式一致性任务。IPFS使用内容寻址的方式来模拟root，所有的对象都通过他们的hash值来访问。

希望确保特定对象存活的节点可以通过固定对象（pinning）来做到这一点。这可以确保对象保存在节点的本地存储中。pinning可以递归执行，也可以固定所有链接的后代对象。所有指向的对象都将存储在本地。这对于持久化文件(包括引用)特别有用。

DHT以及内容寻址机制允许发布对象使用一种公平、安全和分布式的方式。任何能够发布对象的节点只需要简单地将它的key添加到DHT中，添加自己为对等体peer，然后向其他用户发布对象所在的路径。注意对象是不可变对象。新的版本hash值不同，因而是不同的对象。

文件

IPFS还定义了一组对象，用于在Merkle DAG之上对版本化的文件系统建模。这个对象模型类似于Git:

block: 一个可变大小的数据block。
list: 一个block集合或其他列表。
tree: 一个block集合，列表或者其他树。
commit: 一个树的版本历史快照。

文件对象：blob

blob对象包含一个可寻址的数据单元，并表示一个文件。IPFS block类似于Git blob或文件系统数据块。它们存储用户的数据。注意，IPFS文件可以用lists和blobs表示。blob没有链接。

文件对象：list

list对象表示由几个连接在一起的IPFS blob组成的大型或非重复文件。lists包含blob或列表对象的有序序列。在某种意义上，IPFS列表的功能类似于带有indirect block的文件系统文件。因为lists可以包含其他列表，所以拓扑结构(包括链表和平衡树)是可行的。

文件对象：tree

IPFS tree对象和Git中相同，它代表一个目录，一个名称到哈希值的映射。哈希能够引用blobs、lists、其他树或commits。注意，传统的路径命名已经由Merkle DAG实现了。

文件对象：commit

文件中的commit对象表示任何对象的版本历史。它与Git类似，但是可以
引用任何类型的对象。它还链接到author对象。

关于路径查找性能提升

基于路径的访问遍历对象图。检索每个对象需要在DHT中查找它的键、连接对等体并检索它的块。这是相当大的开销，特别是在查找包含许多组件的路径时开销更大。以下是缓解这一问题的措施:

tree caching：由于所有对象都是hash寻址的，因此可以无限期地缓存它们。此外，树的大小往往较小，因此IPFS缓存tree的优先级高于blob。
flattened trees 平整树:对于任何给定的树，都有一种特殊的flattened tree可以构造出来并列出所有树上可达的对象。在flattened tree，name实际上是从原始树上以斜杠分离出来的路径。

小结：
IPFS对标的是HTTP协议，不过IPFS没有可能也没有必要取代HTTP，而是作为一种传输协议与HTTP共存，有其自身的使用场景。由于近些年挖矿项目Filecoin爆火，IPFS也被推上风口浪尖，被一些行业外人士认为是骗局。但从技术角度来讲，IPFS构建去中心化存储系统的思想是十分优秀的，可以借鉴和发散的。
IPFS将数据分为block，block根据自己的内容，通过公钥/私钥和加密方式生成hash值作为NodeId，通过DHT表维护NodeId，如果block内容足够小，那么把值直接放置在DHT中，如果block内容较大，那么把block对应的NodeId放在DHT中，从而通过DHT能够索引到block。为了作版本化控制，IPFS借用了Git中Merkle DAG的思想，通过构建不可变对象和可变链接（指针）来维护对象变换graph。这样和内容寻址的思想相辅相成，内容改变后，其NodeId也会改变，这将生成新的对象，DAG中就增加一个新节点，用DAG中的链接来表达转换关系。
可惜的是，关于IPFS如何使用DHT的内容，文章中描述得并不清楚，文章描述了3种DHT的实现，但关于如何更新、删除、插入DHT的具体过程并无描述，只论述了这些操作是可行的。后续我还需要找一些资料弄清楚去中心化存储的原理。
关于文件的分块机制，作者提到类似于使用Rabin Fingerprints在LBFS中那样来寻找合适block边界，但并无解释具体操作，但这个机制我比较关心。
与非P2P的形式的分布式文件系统相比，IPFS还是有众多不同的，比如没有单点故障，节点间需要进行数据交换，要有自认证系统等。
总的来说，这篇文章作为Draft还是可以窥见一些IPFS设计的核心理念的，很多我想看的东西文章里也没写清楚，可能这是其为什么没发表的原因之一吧。