新软件Minisketch可降低分布式系统节点带宽要求

最近Blockstream团队成员Pieter Wuille和Gleb Naumenko以及前同事Greg Maxwell共同揭晓了Minisketch，这个软件库将能够减少在分布式系统中同步数据时所需的带宽。

Minisketch原本是一个项目中的组成部分，这个项目旨在研究如何利用配置对账(set reconciliation)来在比特币节点之间传递交易信息，即“配置对账中继”(Set Reconciliation Relay，简称SRR)。SRR的目标就是要大幅度降低运行比特币全节点的带宽要求。

开发团队决定将Minisketch从SRR项目中拿出来单独发布，是因为这项技术在比特币以及其他行业都有十分广阔的应用前景。

为什么选择Minisketch?

所有分布式系统一直都面临着在不同节点之间同步数据的困难，如果是一个中心化的系统的话，只需要中心下令哪些数据应该保存、哪些数据应该删除即可。

例如，在去中心化网络上进行数据同步的一个方法是Invertible Bloom Lookup Tables (IBLT)。IBLT对CPU的要求比较低，但这是以较高的带宽要求为代价换取的，特别是当差异数量很小时。Minisketch使用的则是更加节省带宽要求的算法PinSketch。

和其他宽带利用效率较高的配置对账算法，如CPISync和Pinsketch最初的配置相比，Minisketch将占用更少计算资源，比PinSketch快20到100倍，有时候比CPISync快上1000倍。

如何实现改进?

由Minisketch实现的配置对账可以更加高效地利用带宽，不是简单地将所有的数据列都发送过去，而是让节点自己产生数据列的“素描(sketch)”。节点接着把这个“素描”发给其他节点进行对比。这个“素描”的大小只与节点之间差异数量期望有关，而与整个数据组的大小无关。尽管如此，节点仍然能够确定他们从其他节点需要哪些数据。

“假设只有一个差别，这样就很好理解了：我有一个数列{3,5,7,11}，你有一个数列{3,5,7,9,11}，我和你的差别就是{9}。我们都对这个数列里的数字进行求和，那么我会得到3+5+7+11=26，而你会得到3+5+7+9+11=35。我把我的求和结果26发给你，你用你的求和结果35相减之差为9。这个原理只有在差别数量为1时才能求出差别。Minisketch推广了这个原理，发送数据的不同种类的“求和”，有N个不同的求和结果，也就能够找到N中差别… 只要不同数据组差别的数量不大于发送的求和结果数量，Minisketch就一定能成功地找到所有的差别。”