Telehash (JSON + UDP + DHT = Freedom )

分布式哈希表(DHT)

普通的Hash方式

普通的Hash的特点:

• 创建哈希表(HashMap)需要先指定大小，即默认创建一个能够存储多少个元素的哈希表。

• 当不断地向HashMap中添加元素时，HashMap越来越满，当添加的元素达到了装载因子乘以表长时，就需要扩容了。扩容时，原来已经映射到哈希表中的某个位置(桶)的元素需要重新再哈希，然后再把原来的数据复制到新的哈希表中。

对于普通的哈希表而言，扩容的代价是很大的。

例子

普通的Hash计算地址方式如下：Hash(Key)%M，

假设哈希函数为 hash(x)=x ，哈希表的长度为5(有5个桶)。

1. key=6时，hash(6)%5 = 1，即Key为6的元素存储在第一个桶中
2. key=7时，hash(7)%5 = 2，即Key为7的元素存储在第二个桶中
3. Key=13时，hash(13)%5=3，即Key为13的元素存储在第三个桶中

假设现在hash表长度扩容成8，那么Key为6，7，13 的数据全都需要重新哈希。

1. key=6时，hash(6)%8 = 6，即Key为6的元素存储在第六个桶中
2. key=7时，hash(2)%8 = 7，即Key为7的元素存储在第七个桶中
3. Key=13时，hash(13)%8=5，即key为13的元素存储在第五个桶中

从上可以看出：扩容之后，元素的位置全变了。比如：Key为6的元素原来存储在第一个桶中，扩容之后需要存储到第6个桶中。

因此，这是普通哈希的一个不足：扩容可能会影响到所有元素的移动。这也是为什么：为了减少扩容时元素的移动，总是将哈希表扩容成原来大小的两倍的原因。因为，有数学证明，扩容成两倍大小，使得再哈希的元素个数最少。（？）

一致性哈希方式

在分布式系统中，节点的宕机、某个节点加入或者移出集群是常事。对于分布式存储而言，假设存储集群中有10台机子，如果采用Hash方式对数据分片(即将数据根据哈希函数映射到某台机器上存储)，哈希函数应该是这样的：hash(file) % 10。

根据上面的介绍，扩容是非常不利的，如果要添加一台机器，很多已经存储到机器上的文件都需要重新分配移动，如果文件很大，这种移动就造成网络的负载。

因此，就出现了一种一致性哈希的方式。一致性哈希，其实就是把哈希函数可映射的空间(相当于普通哈希中桶的数目是固定的)固定下来了，比如固定为: 2n−1，并组织成环的形状。

每个机器对应着一个n位的ID，并且映射到环中。每个查询键，也是一个 n 位的ID，节点的ID和查询键对应着相同的映射空间。

Each node choose a n-bit ID
// ID是随机的，所以所有的node是随机分布在环上
  Intention is that they be random Though probably a hash of some fixed info IDs are arranged in a ring
// key的哈希跟ID属于同一个域内，也是分布在同一个环上
Each lookup key is also a n-bit ID
   I.e., the hash of the real lookup key
   Node IDs and keys occupy the same space!

例子

如下图：有四台机器映射到固定大小为2n−1的哈希环中。四台机器一共将整个环分成了四部分：(A,B)、 (B,C)、 (C,D)、 (D,A)

机器A负责存储落在（D,A）范围内的数据，机器B负责存储落在（A,B）范围内的数据…..

也就是说，对数据进行Hash时，数据的地址会落在环上的某个点上，数据就存储 该点的 顺时针方向上的那台机器上。

相比于普通哈希方式，一致性哈希的好处就是：当添加新机器或者删除机器时，不会影响到全部数据的存储，而只是影响到这台机器上所存储的数据(落在这台机器所负责的环上的数据)。

比如，B机器被移除了，那落在（A,B）范围内的数据 全部需要由 C机器来存储，也就只影响到落在（A,B）这个范围内的数据。同时，扩容也很方便，比如在（C,D）这段环上再添加一台机器E，只需要将D上的一部分数据拷贝到机器E上即可。

那一致性哈希有没有缺点呢？当然是有的。

• 没有考虑到每台机器的异构性质，不能实现很好的负载均衡。举个例子：机器C的配置很高，性能很好，而机器D的配置很低。但是，可能 现实中 大部分数据由于某些特征 都哈希到（C,D）这段环上，直接就导致了机器D的存储压力很大。

• 一致性哈希还存在“热点”问题（hotspot）。比如说，由于机器D上存储了大量的数据，为了缓解下机器D的压力，在 环（C,D）段再添加一台机器E，就需要将机器D上的一部分数据拷贝到机器E上。而且只有一台机器：即机器D参与拷贝，这会引起机器D 与 机器 E之间的网络负载突然增大。机器D，就是我们所说的hotspot。

引入虚拟节点的一致性哈希方式

为了解决一致性哈希的一些不足，又引入了虚拟节点的概念。引入虚拟节点，可以有效地防止物理节点(机器)映射到哈希环中出现不均匀的情况。比如上图中的机器A、B、C都映射在环的右半边上。

一般，虚拟节点会比物理节点多很多，并可均衡分布在环上，从而可以提高负载均衡的能力。

• 如果虚拟机器与物理机器映射得好，某一台物理机器宕机后，其上的数据可由其他若干台物理机器共同分担（不需要顺时针方向的机器把宕机机器的数据都承担了）。
• 如果新添加一台机器，它可以对应多个不相邻 环段 上的虚拟节点，从而使得hash的数据存储得更分散。

分布式哈希的路由算法

上面提及的都是分布式哈希逻辑上怎么存储数据，但是怎么路由到相应逻辑上的虚拟结点并没有说，这里有两个最简单最直接的法子：

1. 每个结点维护所有结点的一个路由表，根据哈希运算得到应该发送的机器id，然后根据id找到路由表中相应的ip进行转发。这种查询方法，每个结点都要维护一个全局的路由表。
2. 当某台机器接受到查询请求时，先待查找的数据是否在本地，如果不在本地，则将查询请求转发到顺时针方向的下一个节点上。这种查询方式最坏情况下，查询的时间复杂度为O(N)。如下图所示，
   

Chord算法

为了权衡方法1和方法2的利弊，每个结点选择存储部分路由信息，这样即做到低存储(logn)&少量转发(logn)的要求。那实际系统中的路由信息是如何维护的呢？Chord中实现的查询算法大致如下：

A node’s finger table contains the IP address of a node halfway around the ID space from it, a quarter-of-the-way , and so forth in powers of two.

A node forwards a query for key k to the node in its finger table with the highest ID less than k. 

The power-of-two structure of the finger table ensures that the node can always forward the query at least half of the remaining ID-space distance to k. 

As a result Chord lookups use O(log N ) messages.

在Chord中，用到一个叫做“Finger Table”的机制：Entry i in the finger table of node n is the first node that succeeds or equals n+2i

机器n的id就是n。succ表示下一台机器(路由表中存的实际上是succ的ip地址)。比如机器1上的路由表如下：

i	n+2i	succ
0	1+2^0=2	2
1	1+2^1=3	6
2	1+2^2=5	6

它指出了 items 为2，3，5 所对应的数据分别在 机器2、机器6、机器6上。

查询方式

机器1本地存储着 items为1的数据；机器2本地存储着 items为2的数据；机器6本地存储着 items为3, 4, 5, 6的数据；机器0本地存储着items为0, 7 的数据。

与此同时，机器1上，还存储着items 为2, 3, 5 的数据 所在的机器地址。比如，机器1知道，items为5的数据存储在机器6上面。

比如，当机器1接收到 查询 items为7的数据在哪台机器上时，它发现 items=7 最接近它路由表中的items5，于是将查询请求转发到 items=5所对应的机器6上。

机器6上的路由表指出：items=7的数据在机器0上，于是就找到了items=7的数据 在机器0上了。

对于每步的查询而言，目标就是：尽可能地将查询key发送到离存储这个key最近的那台机器上。比如，上面的机器1接收到 key 为 items7 的查询，机器1上存储着 key为 2,3,5的数据，但是由于items 7 比items 2，3，5都要大，因此它判断出存储 items=5 的那台机器 距离 存储items=7的机器 更近，故把查询请求转发给 items=5 所在的那台机器（机器6）

通过在每台机器上保存路由信息，上面的方式可以做到O(logN)的查询时间复杂度。可以通过下图，想明白时间复杂度为什么是O(logN)

另外，比如Amazon Dynamo论文中所说的：Dynamo通过在每台机子上保存足够多路由信息，从而做到O(1)时间的查询。

Dynamo can be characterized as a zero-hop DHT,where each node maintains enough routing information locally to route a request to the appropriate node directly

更多1
更多2
更多3

分布式哈希表对BT下载的影响

在传统的BT下载里，所有的种子文件都必须指定一个或多个种子服务器，即通常所说的Tracker或Announce地址，种子文件和连接信息都存储在种子服务器上，而引入了DHT网络之后，这些连接信息则可以保存在根据一定的算法挑选出的DHT网络参与者（即DHT节点）之间，也就是说，一旦你加入公有DHT网络，你就会有一个ID（该ID只是程序生成的、虚拟的、完全随机的ID，与你的实际个人信息没有任何联系，请完全放心）。

而根据一定的规则，你需要负责维护一部分种子文件的连接信息，相当于你同时也是一个超轻量级种子服务器。这样，下载者只要接入了DHT网络，并且找到了一些连接（或者说节点），就能获得连接信息，而不需要再依赖于tracker服务器。
　　
这样，加入DHT网络解决了传统BT下载中的两个问题：

1. 一旦该种子服务器当机或由于其它原因无法访问，BT用户很可能就无法继续获得连接信息（当然，已经有比特精灵等一些客户端通过连接共享等功能一定程度解决了这个问题）；
2. 在传统BT下载中，如果有两个完全相同的种子文件，但是由于指定了不同的Tracker，那么不同Tracker的用户之间将无法进行下载与上传，从而不能充分体现BT的下载/上传效率。

UDP（User Data Protocol，用户数据报协议）

1. UDP是一个非连接的协议，传输数据之前源端和终端不建立连接，当它想传送时就简单地去抓取来自应用程序的数据，并尽可能快地把它扔到网络上。在发送端，UDP传送数据的速度仅仅是受应用程序生成数据的速度、计算机的能力和传输带宽的限制；在接收端，UDP把每个消息段放在队列中，应用程序每次从队列中读一个消息段。
2. 由于传输数据不建立连接，因此也就不需要维护连接状态，包括收发状态等，因此一台服务机可同时向多个客户机传输相同的消息。
3. UDP信息包的标题很短，只有8个字节，相对于TCP的20个字节信息包的额外开销很小。
4. 吞吐量不受拥挤控制算法的调节，只受应用软件生成数据的速率、传输带宽、源端和终端主机性能的限制。TCP堵塞控制
5. UDP使用尽最大努力交付，即不保证可靠交付，因此主机不需要维持复杂的链接状态表（这里面有许多参数）。
6. UDP是面向报文的。发送方的UDP对应用程序交下来的报文，在添加首部后就向下交付给IP层。既不拆分，也不合并，而是保留这些报文的边界，因此，应用程序需要选择合适的报文大小。

UDP场景

我们经常使用“ping”命令来测试两台主机之间TCP/IP通信是否正常，其实“ping”命令的原理就是向对方主机发送UDP数据包，然后对方主机确认收到数据包，如果数据包是否到达的消息及时反馈回来，那么网络就是通的。

UDP的包头

UDP的包头结构：

• 源端口 16位
• 目的端口 16位
• 长度 16位
• 校验和 16位

TCP与UDP的区别

1. 基于连接与无连接；
2. 对系统资源的要求（TCP较多，UDP少）；
3. UDP程序结构较简单；
4. 流模式与数据报模式 ；
5. TCP保证数据正确性，UDP可能丢包，TCP保证数据顺序，UDP不保证。

JSON

Telehash

A lightweight interoperable protocol with strong encryption to enable mesh networking across multiple transports and platforms.

Each endpoint generates its own unique public-key based address (a hashname) to send and receive small encrypted packets of JSON (with optional binary payloads) to other trusted endpoints.

An endpoint may also provide routing assistance to others for bridging across different transports and to help negotiate direct peer-to-peer links.

Design Principles

1. full end-to-end encryption, all the time
2. strict privacy: no content, identity, or metadata is ever revealed to third parties
3. maximum app/device compatibility: suitable for embedded, mobile, and web usage
4. making privacy the easy choice for developers
5. flexible transport protocols, for compatibility with existing layers
6. native implementations for the widest possible variety of languages/platforms

Protocol

The protocol stack is separated into two main areas, a lower level end-to-end encrypted exchange (E3X) that handles all of the security primitives and encrypted messages, and higher application-level definitions for managing a mesh of links that support standard channels, transports, and URIs.

E3X - End-to-End Encrypted Exchange

E3X is a flexible end-to-end encrypted wire protocol, a specification for applications to route interoperable packetized content over any transport while protecting the privacy of those communications from network monitoring.

It is designed to be used as a low-level software library that can be embedded in any app. It exposes all trust decisions to the app layer; zero information or metadata is revealed to any network or endpoint without explicit instructions from the app.

All of the cryptographic primitives used in E3X are defined as a Cipher Set, allowing for applications to select for different resource or security requirements as needed.

E3X defines asynchronous messages and synchronous channels managed using an exchange. Each exchange has mutual session state established through explicit handshakes.

An exchange is created by combining keys for the local endpoint (one or more, depending on what Cipher Sets it supports) and has another endpoint’s public key(s). Once created, the exchange can then be used to create encrypted messages and generate handshakes in both directions.

Once the handshakes have been received and verified, encrypted channels can stream reliable or unreliable data between the two connected endpoints. All data is encoded as packets both before (application layer) and after encryption (wire transport layer).

The current v3 protocol has these high-level properties

1. each endpoint has verifiable unique fingerprint (a hashname), a secure universal MAC address
2. provides native tunneling of TCP/UDP sockets, HTTP, object streams, and more
3. facilitates asynchronous and synchronous messaging and eventing
4. supports an automatic peer discovery mode when available on local transports
5. specifies a URI format for initiating new links out-of-band
6. supports bridging and routing privately by default and optionally via a public DHT (draft)
7. integrates native support for JSON Object Signing and Encryption (JOSE) and OpenID Connect