六大设计原则 (设计模式之禅读书笔记)

开闭原则（The Open Closed Principle）

软件应该通过扩展来实现变化，而不是通过修改已有的代码来实现变化。

单一职责原则（The Single Responsibility Principle）

定义：应该有且仅有一个原因引起类的变更。

迪米特原则 （The Least Knowledge Principle）

最少知道原则
核心观念是类间解耦，低耦合，只有弱耦合以后，类的复用率才可以提高。
缺点：产生中转或跳转类，系统复杂性提高，增加维护难度。
一个类只和朋友交流，不与陌生类交流。
朋友类：出现在成员变量或方法输入输出参数中的类称为成员朋友类而出现在方法体内部的类不属于朋友类。
类要做到高内聚低耦合，尽量减少public属性方法。
关于方法放到哪个类中的问题：
如果一个方法放到本类中，既不增加类间关系，也不对本类产生负面影响，那就放置在本类中。
系统中如果一个类跳转两次以上才能访问另一个类就需要进行重构。

里氏替换原则 (The Liskov Substitution Principle)

只要父类能出现的地方子类就可以出现，而且替换为子类也不会产生任何错误或异常。
在类中调用其它类时务必要使用父类或接口，如果不能使用父类或接口，则说明类的设计已经违背了lsp原则。
如果子类不能完整的实现父类的方法，或者父类的某些方法在子类中已经发生畸变，则建议断开父子继承关系，采用依赖，继承，组合等关系代替继承。
覆盖或实现父类的方法时输入参数可以被放大。
覆盖或实现父类的方法时输出参数可以被缩小。
采用里氏替换原则的目的就是增强程序的健壮性，版本升级时可以保持非常好的兼容性。即使增加子类，原有的子类还可以继续运行。在实际的项目中，每个子类对应不同的业务含义，使用父类作为参数，传递不同的子类完成不同的业务逻辑。

依赖倒置原则 (The Dependency Inversion Principle)

高层模块不应该依赖低层模块，两者都应该依赖其抽象。
抽象不应该依赖细节。
细节应该依赖抽象。
面向接口编程。
两个类之间有依赖关系，只要指定出两者的接口，就可以独立开发了。
测试驱动开发，适合研发类项目或者项目成员整体水平比较低的情况。
抽象是对实现的约束，对依赖者而言也是一种契约。
1 每个类尽量都有接口或者抽象类。
面向接口编程
编写程序需要的是对现实世界的事物进行抽象，抽象的结果就是有了抽象类和接口，然后我们根据系统设计的需要产生了抽象间的依赖，代替了人们传统中的事物间的依赖，倒置就是从这里产生的。

接口隔离原则 (The Interface Segregation Principle)

实例接口 class
类接口 interface
客户端不应该依赖它不需要的接口
类间的依赖关系应该建立在最小的接口上。
建立单一接口，不要建立臃肿庞大的接口。
根据接口隔离原则拆分接口时，首先必须满足单一职责原则。
通过业务逻辑压缩接口中的public方法，尽量让接口达到满身筋骨肉，而不是肥嘟嘟的一大堆方法。

交易中继协议Erlay

目前，当节点获得新交易时，它会向连接的所有节点广播该交易（除了之前发送该交易的节点）。这是一个非常简单有效的策略，但效率不高 - 节点收到的大多数交易都是已经从不同节点收到的交易，这种冗余浪费了大约44％的节点带宽（根据论文）。

本文试图使用Erlay协议来减少冗余，该协议将中继分为两个阶段：扇出阶段和协调阶段。

• 在扇出阶段，节点将仅从节点的出站节点中选择部分节点广播新交易，而不是向所有节点广播交易。

• 在协调阶段，节点将周期性地从每个出站节点请求所有新交易的短交易标识符（txid前8字节）的草图。草图使用minisketch算法创建，该算法实现了高效的集合协调算法。收到请求的草图后，节点本身还会生成所有新交易的草图。节点将本地草图与接收到的草图组合在一起，生成草图之间差异的列表。然后，节点可以请求缺少的任何交易，并继续查询该节点下一个节点的草图。每隔时间T重复一次，从而允许节点快速接收通过扇出通知未收到的任何交易。

集合协调算法

erlay使用的集合协调算法为Minisketch,使用该算法生成的集合草图具有以下特性:
•草图具有预定容量，当集合中的元素数量不超过容量时，始终可以通过解码草图从草图中恢复整个集合。 具有容量c的b位元素的草图可以以bc位存储。
•通过对这些集的草图的位表示进行异或运算，可以获得两个集之间的对称差异草图（即，出现在一个但不是两个集合中的所有元素）。

节点间协调流程
（1）Alice和Bob节点计算本地交易草图。
（2）Alice将草图发送给Bob。
（3）Bob计算两个草图的对称差异。
（4）Bob 获取自己缺少的交易。
（5）Bob向Alice发送alice缺少的交易。
对草图进行解码在计算上是昂贵的，并且计算量是差异的二次方。 因此，准确估计差异的大小并在集合差异变得过大之前进行协调是协议的重要目标。
重要的参数
D – 草图真正的差异大小。
d – D的估计值。
q – 计算d的参数。
准确估计D对于协调的成功至关重要。论文采用了一种简约的方法，根据当前的集合大小和之前的对帐轮次中观察到的差异来估计集合差异的大小。

1

d = abs(|A| − |B|) + q · min(|A|, |B|) + c

其中q是表征先前对帐的浮点系数（在下面导出），c是用于处理特殊情况的参数。

1

q=(D − abs(|A| − |B|)) / (min(|A|, |B|))

此更新的q将用于下一轮对帐。 我们以这种方式计算q，因为我们假设网络中的每个节点都具有一致的最优q。
协议具体流程

Minisketch 数学原理

集合草图

出于本说明的目的，草图可以被视为具有两个特殊属性的“集合校验和”：

• 草图具有预定的容量，并且当集合中的元素数量不高于容量时，minisketch将始终能从草图恢复整个集合。具有容量c的b位元素的草图可以以bc位存储。

• 可以通过（XOR）组合两组的草图以获得两组之间的对称差异（即，在一个但不是两个输入组中出现的所有元素）。

此概述说明了如何将集合转换为草图以及如何从草图中恢复集合。

从字段元素到草图

数据条目作为字段元素

范围 [1…2^b-1] 中的每个整数（具有字段大小b的Minisketch草图的可接受数据元素）可以映射到有限域 GF(2^b) 的非零字段元素。在这个有限域中，我们可以添加和相乘元素，并为这些操作提供自定义。字段元素的加法（和减法）对应于它们对应的整数的XOR运算，但乘法复杂一些。

集合幂级数

我们定义了一个函数S，它将元素m映射到下面形式的幂级数：

• S(m) = 1 + mx + m²x² + m³x³ + ….
  然后，我们通过将集合元素的函数结果相加来扩展此函数以对字段元素集进行操作。如果M={m1，m2，…}：
• S(M) = S({m₁,m₂,…}) = S(m₁) + S(m₂) + … = (1 + 1 + …) + (m₁ + m₂ + …)x + (m₁² + m₂² + …)x² + (m₁³ + …
  因为在我们的有限域,加法对应于XOR，所以对于每一个a是a + a = 0。如果把这个规则引入S函数，意味着对于每个a，S（a）+ S（a）= 0。这意味着这些幂级数的系数具有我们希望的草图的第二个属性，即存在组合两个草图的有效操作，使得结果是集合的对称差异的草图。它认为 S({m₁,m₂}) + S({m₂,m₃}) = S(m₁) + (S(m₂) + S(m₂)) + S(m₃) = S(m₁) + S(m₃) = S({m₁,m₃}}).

问题是我们是否也可以从其幂级数系数中有效地恢复元素。

无穷大的系数近似

为了更容易理解这些幂级数，请注意单个元素的系列实际上是几何级数。如果我们正在研究实数而不是有限域并且 |mx| < 1，它会收敛到 (1 - mx)^-1。

• (1 - mx) S(m) = 1
  这可以推广到多个集合元素的运算。对于我们有两个要素：

• (1 - m₁x) (1 - m₂x) S({m₁,m₂}) = (1 - m₁x) (1 - m₂x) (S(m₁) + S(m₂)) = (1 - m₂x) + (1 - m₁x)
  对于三个：

• (1 - m₁x) (1 - m₂x) (1 - m₃x) S({m₁,m₂,m₃}) = (1 - m₁x) (1 - m₂x) (1 - m₃x) (S(m₁) + S(m₂) + S(m₃)) = (1 - m₂x)(1 - m₃x) + (1 - m₁x)(1 - m₃x) + (1 - m₁x)(1 - m₂x)
  在每一种情况下，我们注意到，S(M)(1 - m_ix) 其中mi是集合M元素，得到一个n-1阶多项式。

解析集合元素

上面的函数让我们可以构建了一个求解器，它从幂级数的系数中提取集合元素。如果我们能找到一个多项式L由N个不同 (1 - m_ix) 因子组成，对于不同的m_i，使得 P = S(M)L 为 n-1 阶多项式，然后这些值mi是M的元素。

P的系数是集合元素本身的非平凡表达式。然而，我们可以只关注P中的n阶或更高阶的系数，其它系数都是0.让si做S（m）系数 ，Ii做L的系数，S(M) = s₀ + s₁x + s₂x² + s₃x³ + … 并且 L = l₀ + l₁x + l₂x² + l₃x³ + … + l_nxⁿ。注意 l₀ = 1，它是 (1 - m_ix) 因子中所有单一项的乘积。

以下是n+1到2n阶的 S(M)L 系数的等式：

• s_n+1 + s_n+0l₁ + s_n-1l₂ + s_n-2l₃ + … + s₁l_n = 0
• s_n+2 + s_n+1l₁ + s_n+0l₂ + s_n-1l₃ + … + s₂l_n = 0
• s_n+3 + s_n+2l₁ + s_n+1l₂ + s_n+0l₃ + … + s₃l_n = 0
• …
• s_2n + s_2n-1l₁ + s_2n-2l₂ + s_2n-3l₃ + … + s_nl_n = 0

这些是具有n个未知数n个线性方程，可以使用高斯消元法求解。在这样做之后，我们得到L的系数，然后可以将其分解为一阶因子 (1 - m_ix)。得到的m值是我们的集合元素。

算法结论

有趣的是，解决上述方程组只需要2n个S（M）系数。这意味着我们得到答案：1至2N的S(M)系数，或列表 [m₁ + m₂ + …, m₁² + m₂² + …, …, m₁²ⁿ + m₂²ⁿ + …] 用作草图，满足我们想要的两个属性：

• 通过简单地将列表元素相加组成的草图，可以用来计算其对称差异的草图。
• 使用2n个列表元素，我们可以有效地从草图中恢复n个元素。

结论

在描述了Erlay协议之后，使用60,000个节点的模拟网络（数量与当前比特币网络相似）和100个节点的实时集合分析了其性能，这些节点遍布多个数据中心。最值得注意的结果是，Erlay将用于宣布新交易存在的带宽量减少了84％。 但是，传输到网络中所有节点的交易确实需要大约80％（2.6秒）的时间。比特币交易仍然只能平均每十分钟确认一次，因此三秒减速似乎是一个合理的价格，可以为带宽的大幅减少付出代价。

考虑到比特币中继策略未来可能发生的变化，文中指出出站节点数量从8个增加到32个，广播新交易带宽使用Erlay协议增加了32%，而使用目前的广播协议需要增加300%。正如上面关于Erlay两个阶段的段落中所描述的那样，新的交易仍然只能通过直接传达给8个对等点，但是节点会与所有32个对等点进行集合协调。中继连接性能提高了四倍，提高了像LN这样的协议的时间敏感交易能够快速进入矿工节点的机会。

提高网络传输效率背景

• 目前节点间连接数量的主要限制因素是通信带宽，带宽随着连接数量的增加线性增加，所以只有减少节点间通信带宽才能连接更多节点，节点更高的连接性会带来更高的安全性。

提高区块传输效率方式

当节点发送区块时会完整的发送区块头和区块中的所有交易。而区块中的交易对每个节点来说大概率都是已知的，因为交易也会在网络上进行广播。为了减少带宽，发送方应避免发送接收方已知的交易信息，而是让接收方到交易池中查找已知交易。

• 最简单的方式发送交易的32字节ID来代替整个交易。如果区块包含2000个交易，则总大小64000个字节。

• 32字节ID之间意外冲突的可能性几乎为零，所以可以使用交易ID的前8个字节来代替交易。如果区块包含2000个交易，则总大小降低到16000个字节。

• 使用Bloom过滤器，布隆过滤器是一种概率数据结构，用于确定项目是否是给定集合的成员。在这种情况下，所谓集合是发送者块中的所有交易ID,而项目是指接收方mempool中的交易ID，所有可以用来确定接收方mempool中的交易是否在区块中。 Bloom过滤器有两个特殊的特征。首先，它没有假阴性。也就是说，如果Bloom过滤器确定交易ID不在集合中，那么它肯定不在集合中。其次，Bloom过滤器确实存在误报。也就是说，如果Bloom过滤器确定交易ID在集合中，那么它可能不在集合中。可以将Bloom过滤器的误报率（FPR）设置任何值，但是有一个重要的权衡：如果FPR很低，而Bloom过滤器因此是准确的，那么它的字节数也会更大。如果我们不介意关于块中的事务ID的错误答案，则Bloom过滤器将很小。

• 使用可逆布隆查找表（IBLT），是另一种有用的概率数据结构，它可以发现两个集合之间的对称差异。例如，可以创建发送方区块中所有交易ID的IBLT，然后使用接收方的mempool中交易创建另一个IBLT。第二个IBLT减第一个IBLT将告诉我们mempool中的哪些交易不在块中。鉴于此功能，可以单独使用IBLT将块从发送方转发到接收方，但不幸的是，它不是一种有效的方法。 IBLT的字节大小随着从中恢复的差异的大小线性增加。 IBLT每个交易ID使用大约17个字节，这是对称差异的一部分，IBLT的开销（以字节为单位）约为140％（对于小的对称差异，此值可能会有很大差异，并且可以使用所描述的技术进行最佳设置在下面的恢复部分）。因此，如果mempool是大于块的1000个交易（即，对称差异是1000），则发送方的IBLT将是大约（1.4 1000） 17 = 23,800字节。

• 第五个也是最好的解决方案是布隆过滤器和可逆布隆查找表两种数据结构的组合。首先，发送者创建区块中交易的布隆过滤器来过滤接受者mempool中的交易，这个过程允许大量的误报，所以可以使用一个小的Bloom过滤器。然后用发送者区块中交易的IBLT清除Bloom过滤器所犯的任何错误。因为对称差异现在非常小：它等于我们的Bloom过滤器产生的误报数量和接收方交易池中缺少的交易。有一个权衡：可以使Bloom过滤器更大（更准确），从而产生更小的IBLT;或者可以使IBLT更大（能够纠正更多错误），从而产生更小的布隆过滤器。

Graphene 协议实现

Graphene使用两组协调数据结构来表示交易列表：布隆过滤器和可逆布隆查找表（IBLT）。 两个数据结构的组合比单独使用任何一个更有效的表达交易列表，并且它通常比从缩短的交易ID构造交易列表更有效。

协议流程

节点之间的同步步骤：

1.发送方使用inv消息通知接收方新的块可用。

2.如果接收方尚不知道该块，则她使用get_grblk消息进行响应。

3.发送方创建块中所有交易ID的布隆过滤器S以及仅包含每个交易ID的“廉价哈希”（哈希的前8个字节）的IBLT(I)。
此外，接收方可能遗漏的任何完整交易（例如块的coinbase）都会收集到其他交易清单V中。如果没有协议定义的交易排序，则发件人还会创建交易排序列表R，按ID按字典顺序列出，表示（每个ID的log（n）位）每个事务ID的预期顺序。发送方将S，I，V，R和块头组装成grblk消息，然后发送给接收方。

4.接收者首先将所有本地已知的交易ID聚合到集合T中，集合T由在V和她的mempool（加上孤儿池）中找到的集合组成。然后，她使用Bloom过滤器S从T中过滤交易ID。任何看似在S中的交易都会添加到她自己的IBLT中，I’。然后，她在I和I’上执行IBLT减法操作，以解码两组之间对称差异中的交易ID集。从该减法操作，可以知道错误地通过S的一组假阳性ID集合 F或者ID集在块中但是没有T中缺失的交易集合M。减法操作要么成功要么失败，如果失败需要采用后备方法：

（1）成功：IBLT减法成功，集合M为空。块中的所有交易接收方都拥有。

（2）成功：IBLT减法成功，集合M非空。必须请求丢失交易。接收器使用get_grblktx消息请求丢失的交易，发送方用包含M指示的完整交易的grblktx消息响应。

（3）IBLT解码失败：IBLT减法操作完全失败。在这种情况下，接收方无法确定块中的完整交易ID集。当接收方mempool中交易较少时容易发生此类错误，由于IBLT的概率性质，也可能偶尔发生（例如，1/240块）。接收方需要使用获取完整区块消息重新请求整个区块。

（4）IBLT校验和失败，当发送方grblktx消息返回的交易太少时被检测到：IBLT减法成功，但由于IBLT校验和错误而返回错误的交易ID。在这种情况下，接收方将针对错误的交易ID发出get_grblktx消息，发送方将不会返回该交易。当接收方检测到并非所有事务都已被发送时，她将假定已发生校验和错误并请求完整的区块。

5.如果IBLT减法成功（并且接收到丢失的交易），并且如果没有发生校验和错误，则接收器将留下块中的无序交易集。 （请注意，在此阶段，接收方肯定会拥有实际的交易，而不仅仅是其ID）。

6.接收器将交易放在Merkle树中，该树根和块头中指定的根进行验证。 Merkle树中的交易顺序由网络的协议定义的规范排序或grblk中包含的特定排队信息R确定。

参数选择

使用Bloom过滤器中继块需要多少空间？例如，我们可以将布隆过滤器的FPR设置为f = 1 / m。在这种情况下，当接收者检查mempoool中的每个m个交易ID时，Bloom过滤器将错误地指出1个交易在块中。更糟糕的是，接受者不知道哪个交易是错误的;由于额外的交易，Merkle根将不会验证通过。我们可以尝试通过降低过滤器的FPR来解决这个问题。例如，如果我们将FPR设置为f = 1 /（144m），那么我们可以预期过滤器将仅允许每144个块中继一次的错误答案（即，每天仅约一次）。但请记住，这种准确性将花费我们的字节数。插入n个项目和假阳性率f = 1/144m的布隆过滤器的大小众所周知为-n ln（f）/ ln2（2）= n ln（1 /（144m））/ （8ln2（2））个字节。例如，对于具有n = 2000个交易的块和总共m = 6000个交易的mempool，Bloom过滤器将是大约7,113个字节。这比我们使用交易ID或8字节的廉价ID有所改进,但不是最优方案。

Graphene通过选取两个数据结构的参数，使得总和尺寸最小。例如，对于n = 2000和m = 6000，发送方计算可以通过设置恢复27项对称差异的IBLT和具有f = 0.00675的FPR的布隆过滤器来达到最小尺寸。在我们的测试实现中（再次假设IBLT开销为140％），这导致总共3,244字节，基于643字节的IBLT和2601字节的Bloom过滤器，大约是发送每笔交易发送8个字节交易ID的大小的1/5。如果协议未定义打包交易顺序，则还必须发送事务排序的信息，这会将总计增加2,750个字节到5,994个字节（这大约是每个交易发送8个字节交易ID的成本的38％）。
随着块尺寸的增加，石墨烯保持了这种尺寸优势。例如，对于n = 10,000个事务的块，列出每个事务ID的8个字节将是80,000个字节。使用m = 30,000个事务的mempool，Graphene的成本为14,482字节（或包括订购信息时为31,091字节）。

数据同步协议

比原链网络数据同步协议栈如下图所示。协议栈基于tcp/ip,Encryption完成数据的加密传输，Wire Protocol完成数据序列化，最上层为同步协议。

基于tcp/ip同步协议

数据同步首先会在节点之间建立连接MConnection，建立连接后会对连接进行加密处理，区块，交易数据序列化为二进制数据流通过加密通道传递给其它节点。

建立加密连接

建立多路复用连接

MConnection 是在单个tcp连接上支持多个独立流传输的多路复用连接，并且每个流提供了单独的服务质量保证。每个流称为Channel，每个Channel具有全局唯一的 byte id 。每个channel也具有决定服务质量的相对优先级。byte id 和每个Channel的相对优先级在初始化时配置。

MConnection支持三种数据包类型：

• Ping
• Pong
• Msg

Ping和Pong

ping和pong消息向连接写入单个字节;分别为0x1和0x2。

当我们在pingTimeout周期没有及时收到MConnection上的任何消息时，我们发送一条ping消息。
当在MConnection上收到ping消息时，会发送一个pong作为响应。如果在ping之后没有及时收到pong消息，则节点将断开连接。

Msg

通道中的消息被切割成较小的msgPacket 以进行多路复用。

1
2
3
4
5

type msgPacket struct {
    ChannelID byte
    EOF       byte // 1 means message ends here.
    Bytes     []byte
}

msgPacket
用go-wire进行序列化，并以0x3为前缀。接收到的一组数据包的“字节”被附加在一起直到收到带有EOF = 1 的数据包，然后完整的序列化消息由相应channel的onReceive函数处理。

多路复用

消息从sendRoutine 发送，它循环在select状态上并发送ping，pong或msg消息。该批数据消息可以包括来自多个channel的消息。消息字节排队等待在各自的通道中发送，每个通道一次取一个未发送的消息。从最近发送的字节与信道优先级的比最低的信道选择一个消息发送。

发送消息

发送消息有两种方法：

1
2

func (m MConnection) Send(chID byte, msg interface{}) bool {}
func (m MConnection) TrySend(chID byte, msg interface{}) bool {}

Send（chID，msg）是一个阻塞调用，等待msg成功排队到给定id字节chID的通道。消息msg被序列化使用wire子模块的WriteBinary()反射函数。

TrySend（chID，msg）是一个非阻塞调用，它将消息msg排入chID通道如果队列未满;否则立即回false。

Send（）和TrySend（）对每个Peer可见。

Peer

每个peer都有一个MConnection实例，并含有其他信息，例如是否是outbound(主动拨号其它节点)，关于节点的各种身份信息，以及reactor使用的其他更高级别的线程安全数据。

Switch/Reactor

Switch 控制peer连接，以在Reactor上接收传入消息。每个Reactor负责处理一个或多个channel传入的信息。因此，通常通过peer发送消息，在Reactor上接收传入的消息。

新添加peer后，给定reactor的传入消息将通过该reactor的Receive方法处理，并且输出消息由每个节点的Reactor直接发送。 reactor使用节点之间的go-routing来处理这些。

连接加密及身份确认

在节点拨号成功后，执行两次握手：第一次进行通道加密、身份验证，第二次进行版本、网络类型验证。

Peer Identity

节点每次启动都会随机产生一个public key作为节点的id。当尝试连接到peer时，我们使用PeerURL：<ID> @ <IP>：<PORT>。我们将尝试连接IP：PORT上的节点，并验证身份，通过经过身份id的签名，只有拥有相应私钥的节点可以建立连接。这可以防止对节点的中间人攻击。

通信加密、身份验证

节点建立加密连接时使用Diffie-Helman密钥交换协议生成共享秘钥，使用NACL SecretBox对通信数据进行对称加密。
工作流程如下：

• 生成一个临时的ED25519密钥对
• 将临时的公钥发送给对等方
• 等待接收对等方的临时公钥
• 使用对方临时公钥和我们的临时私钥计算Diffie-Hellman共享密钥
• 生成两个用于加密（发送和接收）的随机数，流程如下：
  • 按升序对临时的公钥进行排序并将它们连接起来
  • 进行RIPEMD160运算
  • 附加4个空字节（将散列扩展为24个字节）
  • 结果是nonce1
  • 翻转nonce1的最后一位以获得nonce2
  • 如果我们有一个较小的临时pubkey，使用nonce1接收，nonce2发送;否则相反
• 从现在开始的所有通信都使用共享密钥和随机数进行加密，其中每个随机数每次使用时增加2
• 我们现在有一个加密通道，但仍需要进行身份验证
• 签名共同挑战：
  • 对排序和连接的短暂pubkey进行SHA256运算
• 使用我们的持久私钥签署共同挑战
• 将go-wire编码的持久性pubkey和签名发送给节点
• 等待从节点接收持久公钥和签名
• 使用节点的持久公钥验证消息签名

如果这是一个outgoing连接（主动连接其它节点）并且使用了节点ID，然后最后验证节点的持久公钥是否与我们拨号的节点ID相对应，即。 peer.PubKey.Address() == <ID>。

现在连接现已通过身份验证，并且所有流量都已加密。

注意：只有拨号节点可以验证节点的身份，但这是我们关心的，因为当我们加入网络时我们希望确保已经连接了目标节点（而不是被中间人攻击）。

版本确认

版本确认允许节点交换其NodeInfo：

1
2
3
4
5
6
7
8

type NodeInfo struct {
  PubKey     crypto.PubKeyEd25519
  ListenAddr string
  Network    string
  Version    string
  Moniker    string
  Other      []string
}

如果出现以下情况则断开连接：

• peer.NodeInfo.Version 未格式化为X-X-X，其中X是称为Major，Minor和Revision的整数。
• peer.NodeInfo.Version 主版本号与我们的不一样。
• peer.NodeInfo.Network 网络类型与我们的不一样。

此时，如果没有断开连接，则节点有效。它通过AddPeer方法添加到switch中，因此被添加到所有reactor中。

数据序列化协议

支持的类型

• 原始类型
  • uint8 (aka byte), uint16, uint32, uint64
  • int8, int16, int32, int64
  • uint, int: variable length (un)signed integers
  • string, []byte
  • time
• 派生类型
  • structs
  • 特定类型的变长数组
  • 特定类型的固定长度数组
  • interfaces：注册的联合类型，前面是type byte
  • 指针

二进制编码

固定长度基本类型 用1,2,3或4个大端字节编码。

• uint8（又名byte），uint16，uint32，uint64：分别占用1,2,3和4个字节
• int8，int16，int32，int64：分别占用1,2,3和4个字节
• time：int64 表示自纪元以来的纳秒

可变长度整数 用一个前导字节编码，表示后续大端字节的长度。对于有符号的负整数，前导字节的最高有效位为1。

• uint：1字节长度前缀可变大小（0~255字节）无符号整数
• int：1字节长度前缀变量大小（0~127字节）有符号整数

注意：虽然数字0（零）用单个字节x00编码，但数字1用两个字节表示：x0101。这不是最高效的表示，但规则更容易记住。

Structures 通过按声明顺序对字段值进行编码来编码。

1
2
3
4
5
6
7
8
9
10
11

type Foo struct {
    MyString string
    MyUint32 uint32
}
var foo = Foo {“626172”，math.MaxUint32}

 foo的二进制表示：
 0103626172FFFFFFFF
 0103：`int`编码的字符串长度，这里是3
     626172：3个字节的字符串“bar”
           FFFFFFFF：uint32 MaxUint32的4个字节

可变长度数组 用前导“int”编码，表示数组的长度，后跟项目的二进制表示。 固定长度数组 类似，但前面没有前导int。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

foos：= [] Foo {foo，foo}

foos的二进制表示：
 01020103626172FFFFFFFF0103626172FFFFFFFF
 0102：`int`编码的数组长度，这里2
     0103626172FFFFFFFF：第一个`foo`
                       0103626172FFFFFFFF：第二个`foo`


foos：= [2] Foo {foo，foo} //固定长度数组

foos的二进制表示：
 0103626172FFFFFFFF0103626172FFFFFFFF
 0103626172FFFFFFFF：第一个`foo`
                   0103626172FFFFFFFF：第二个`foo`

接口 可以代表任意数量的具体类型之一。必须首先使用相应的type byte声明接口的具体类型。然后使用前导“类型字节”对接口进行编码，然后对底层具体类型进行二进制编码。

注意：字节x00保留用于nil接口值和nil指针值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

type Animal interface{}
type Dog uint32
type Cat string

RegisterInterface（
  struct{ Animal }{},          // Convenience for referencing the 'Animal' interface
  ConcreteType{Dog(0),  0x01}, // Register the byte 0x01 to denote a Dog
  ConcreteType{Cat(""), 0x02}, // Register the byte 0x02 to denote a Cat
）

var animal Animal = Dog（02）

 The binary representation of animal:
 010102
 01:     the type byte for a `Dog`
   0102: the bytes of Dog(02)

指针 用一个前导字节x00编码为nil指针，否则用前导字节x01编码，然后是指向的值的二进制编码。

注意：将指针类型转换为接口类型很容易，因为type byte x00总是nil。

JSON编码

JSON编解码器与[binary]（#binary）编解码器兼容，如果您已经熟悉golang的JSON编码，则相当直观。下面提到了一些特殊规定：

• 可变长度和固定长度字节编码为大写十六进制字符串
• 接口值被编码为两个项的数组：[type_byte，concrete_value]
• 次数被编码为rfc2822字符串

同步协议

bytom 目前支持普通同步模式，快速同步模式，SPV Proof。

节点协议握手

节点协议握手首先会向对方发送状态信息，同时通过状态信息获取对方当前状态，同步协议在获取状态之后。

StatusRequestMessage

StatusResponseMessage

在握手后会进行交易池同步，交易池同步会把当前池中的交易打包发给对方，发送交易使用TransactionMessage。

TransactionMessage

同步协议

目前支持普通同步和快速同步两种模式，区块同步程序定时检查所有连接的节点状态，判断是否需要同步，当需要同步时，判断节点满足快速同步条件时则进行快速同步，否则进行普通同步。为了使挖矿区块能快速同步到全网，当收到挖矿区块时会触发同步流程，使新区块快速上链，并及时更新挖矿区块高度，从而减少孤儿块产生的概率。

MineBlockMessage

普通同步模式

普通同步模式下，节点按高度获取高度并进行全区块验证。使用GetBlockMessage和BlockMessage消息。
GetBlockMessage

BlockMessage

快速同步模式

快速同步模式下，通过在代码中加入checkpoint(已确认的区块的hash)，这样同步时只需要比较某些高度区块hash是否和checkpoint区块hash一致，即可判断区块头正确性。通过计算区块中交易merkle树roothash是否和区块头中roothash一致，即可判断区块中的交易正确性。快速同步模式下批量获取区块头以及区块，可以极大提高同步速度。

GetHeadersMessage

HeadersMessage

GetBlocksMessage

BlocksMessage

SPV Proof

简单支付验证（SPV）是Satoshi Nakamoto的论文中描述的一种技术。 SPV允许轻量级客户端验证区块链中是否包含交易，而无需下载整个区块链。 SPV客户端只需要下载块头，这些块头比完整块小得多。 为了验证交易是否在块中，SPV客户端以Merkle block的形式请求包含交易证明。
SPV提供了两个关键要素：a）它确保您的交易处于一个区块中; b）它提供了区块被添加到链中的确认（工作证明）。

SPV 轻客户端首先连接全节点，当与全节点成功建立连接后。轻客户端向全节点注册地址过滤器，过滤器是一个地址集合，包含SPV节点账户的地址。全节点使用地址过滤器对交易进行过滤，并将相关交易发送给轻客户端。轻客户端使用GetMerkleBlockMessage命令向全节点获取MerkleBlockMessage消息。

FilterLoadMessage

FilterAddMessage

FilterClearMessage

GetMerkleBlockMessage

MerkleBlockMessage

本文分析golang中的timer实现原理、工作流程、及正确使用方法。

timer造成资源泄露

在项目中发现随着系统运行时间增加，系统资源cpu/memory消耗逐渐增加，使用pprof打印系统资源占用。发现siftdownTimer、timerproc在占用系统资源。

1
2

9.73s 30.36% 66.55%     10.10s 31.51%  runtime.siftdownTimer
0.13s  0.41% 95.48%     16.48s 51.42%  runtime.timerproc

很显然，这是错误使用timer造成系统资源泄露，为了解决这个问题需要知道runtime 层timer是如何实现的。

timer 工作原理

runtime中定义了timers变量用来存储系统中所有的timer。timers长度为64，每个含有一个存储timer的timersBucket。CacheLineSize 是CPU假定的cache line 大小。pad用来填充timersBucket到chace line的间距，以避免在不同的 P 之间发生 false sharing，提高多核运行时内存操作效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// timers contains "per-P" timer heaps.
//
// Timers are queued into timersBucket associated with the current P,
// so each P may work with its own timers independently of other P instances.
//
// Each timersBucket may be associated with multiple P
// if GOMAXPROCS > timersLen.
var timers [timersLen]struct {
	timersBucket

	// The padding should eliminate false sharing
	// between timersBucket values.
	pad [sys.CacheLineSize - unsafe.Sizeof(timersBucket{})%sys.CacheLineSize]byte
}

timer操作函数调用流程如下图所示。

主要分析一下以下两个问题。
1、是如何将timer加入堆栈。
2、如何进行多timer调度并定时唤醒timer。

将timer加入到timersbucket中的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

func addtimer(t *timer) {
    tb := t.assignBucket() //分配bucket
    lock(&tb.lock)
    tb.addtimerLocked(t)
    unlock(&tb.lock)
}

// 对g.m.p 的 id 模 64 求余，并分配相应的bucket
func (t *timer) assignBucket() *timersBucket {
    id := uint8(getg().m.p.ptr().id) % timersLen
    t.tb = &timers[id].timersBucket
    return t.tb
}

// 向时间堆中添加一个 timer，如果时间堆第一次被初始化或者当前的 timer 比之前所有的 timers 都要早，那么就启动(首次初始化)或唤醒(最早的 timer) timerproc
// 函数内假设外部已经对 timers 数组加锁了
func (tb *timersBucket) addtimerLocked(t *timer) {
    // when 必须大于 0，否则会在计算 delta 的时候溢出并导致其它的 runtime timer 永远没法过期
    if t.when < 0 {
        t.when = 1<<63 - 1
    }
		//timer加入末端
    t.i = len(tb.t)
    tb.t = append(tb.t, t)
		//向上调整timer在堆中排序
    siftupTimer(tb.t, t.i)
    if t.i == 0 {
        // 新插入的 timer 比之前所有的都要早
        if tb.sleeping {
            // 修改 timerBucket 的 sleep 状态
            tb.sleeping = false
            // 唤醒 timerproc
            // 使 timerproc 中的 for 循环不再阻塞在 notesleepg 上
            notewakeup(&tb.waitnote)
        }
        // 同一个 P 上的所有 timers 如果都在 timerproc 中被弹出了
        // 该 rescheduling 会被标记为 true
        if tb.rescheduling {
            // 该标记会在这里和 timejumpLocked 中被设置为 false
            tb.rescheduling = false
            goready(tb.gp, 0)
        }
    }
    // 如果 timerBucket 是第一次创建，需要启动一个 goroutine
    // 来循环弹出时间堆，内部会根据需要最早触发的 timer
    // 并进行相应时间的 sleep
    if !tb.created {
        tb.created = true
        go timerproc(tb)
    }
}

timerproc是定时器调度goruntine。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

// timerproc 负责处理时间驱动的事件
// 在堆中的下一个事件需要触发之前，会一直保持 sleep 状态
// 如果 addtimer 插入了一个更早的事件，会提前唤醒 timerproc
func timerproc(tb *timersBucket) {
    tb.gp = getg()
    for {
        // timerBucket 的局部大锁
        lock(&tb.lock)
        // 被唤醒，所以修改 sleeping 状态为 false
        tb.sleeping = false
        // 计时
        now := nanotime()
        delta := int64(-1)
        // 在处理完到期的 timer 之前，一直循环
        for {
            // 如果 timer 已经都弹出了
            // 那么不用循环了，跳出后接着睡觉
            if len(tb.t) == 0 {
                delta = -1
                break
            }
            // 取小顶堆顶部元素
            // 即最近会被触发的 timer
            t := tb.t[0]
            delta = t.when - now // 还差多长时间才需要触发最近的 timer
            if delta > 0 {
                // 大于 0 说明这个 timer 还没到需要触发的时间
                // 跳出循环去睡觉
                break
            }
            if t.period > 0 {
                // 这个 timer 还会留在堆里
                // 不过要调整它的下次触发时间
                t.when += t.period * (1 + -delta/t.period)
                siftdownTimer(tb.t, 0)
            } else {
                // 从堆中移除这个 timer
                // 用最后一个 timer 覆盖第 0 个 timer
                // 然后向下调整堆
                last := len(tb.t) - 1
                if last > 0 {
                    tb.t[0] = tb.t[last]
                    tb.t[0].i = 0
                }
                tb.t[last] = nil
                tb.t = tb.t[:last]
                if last > 0 {
                    siftdownTimer(tb.t, 0)
                }
                t.i = -1 // 标记 timer 在堆中的位置已经没有了
            }
            // timer 触发时需要调用的函数
            f := t.f
            arg := t.arg
            seq := t.seq
            unlock(&tb.lock)
            // 调用需触发的函数
            f(arg, seq)
            // 把锁加回来，如果下次 break 了内层的 for 循环
            // 能保证 timeBucket 是被锁住的
            // 然后在下面的 goparkunlock 中被解锁
            lock(&tb.lock)
        }
        if delta < 0 || faketime > 0 {
            // 说明时间堆里已经没有 timer 了
            // 让 goroutine 挂起，去睡觉，通过调用goready(gp)将gorouting转换成runnable状态。
            tb.rescheduling = true
            goparkunlock(&tb.lock, "timer goroutine (idle)", traceEvGoBlock, 1)
            continue
        }
        // 说明堆里至少还有一个以上的 timer
        // 睡到最近的 timer 时间
        tb.sleeping = true
        tb.sleepUntil = now + delta
        noteclear(&tb.waitnote)
        unlock(&tb.lock)
        // 内部是 futex sleep
        // 时间睡到了会自动醒
        // 或者 addtimer 的时候，发现新的 timer 更早，会提前唤醒
        notetsleepg(&tb.waitnote, delta)
    }
}

以上就是timer加入heap及timerproc定期弹出timer的流程。

siftupTimer，siftdownTimer用于调整timer在heap中的顺序。timer在TimersBucket中的存储结构为四叉堆。四叉堆多数是以数组作为它们底层元素的存储，根节点在数组中的索引是0，存储在第n个位置的父节点它的子节点在数组中的存储位置为4n与4n+1,4n+2,4n+3。对于一个节点的要求只有和其父节点以及子节点之间的大小关系。相邻节点之间没有任何关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

向上调整
func siftupTimer(t []*timer, i int) {
    // 先暂存当前刚插入到数组尾部的节点
    when := t[i].when
    tmp := t[i]

    // 从当前插入节点的父节点开始
    // 如果最新插入的那个节点的触发时间要比父节点的触发时间更早
    // 那么就把这个父节点下移
    for i > 0 {
        p := (i - 1) / 4 // parent
        if when >= t[p].when {
            break
        }
        t[i] = t[p]
        t[i].i = i
        i = p
    }

    // 如果发生过移动，用最新插入的节点
    // 覆盖掉最后一个下移的父节点
    if tmp != t[i] {
        t[i] = tmp
        t[i].i = i
    }
}

向下调整
func siftdownTimer(t []*timer, i int) {
    n := len(t)
    when := t[i].when
    tmp := t[i]
    for {
        c := i*4 + 1 // 最左孩子节点
        c3 := c + 2  // 第三个孩子节点
        if c >= n {
            break
        }
        w := t[c].when
        if c+1 < n && t[c+1].when < w {
            w = t[c+1].when
            c++
        }
        if c3 < n {
            w3 := t[c3].when
            if c3+1 < n && t[c3+1].when < w3 {
                w3 = t[c3+1].when
                c3++
            }
            if w3 < w {
                w = w3
                c = c3
            }
        }
        if w >= when {
            break
        }
        t[i] = t[c]
        t[i].i = i
        i = c
    }
    if tmp != t[i] {
        t[i] = tmp
        t[i].i = i
    }
}

timer使用方式及常见问题

常用的是 time.After() 和 time.NewTicker()。两者都会新建一个timer，time.After 和 time.Tick 不同，区别是After是一次性的定时器，Ticker是周期性的。After触发后 timer 本身会从时间堆中删除。

当系统中启动timer数量过多，需要存储的空间及调度的成本会越来越多。所以在使用timer时需要注意:

1、当使用NewTicker新建一个ticker的时候，一定要用Stop函数将其关闭。

2、不要用以下这种方式使用timer。第一段代码，如果<-ch 这个 case 每次执行的时间都很短，每次进入 select，time.After 都会分配一个新的 timer。因此会在短时间内创建大量的无用 timer，虽然没用的 timer 在触发后会消失，但这种写法会造成无意义的 cpu 资源浪费。

1
2
3
4
5
6
7

for {
		select {
		case <-time.After(time.Second):
				println("time out, and end")
		case <-ch:
		}
}

而是应该在循环外定义timer。

1
2
3
4
5
6
7
8

timer := time.NewTimer(time.Second)
for {
		select {
		case <-timer.C:
				println("time out, and end")
		case <-ch:
		}
}

交易映射

交易验证时需要首先将inputs、outputs描述的TxData转换成Entriy描述的的bc.Tx。
Entry 是区块链中很多组件都实现的一个接口。比如交易中实现了此接口的组件包括Spend,Issuance,Coinbase,
Output,Retirement，TxHeader 等。验证前需要将TxData中的元素转换成对应的Entry组件，
实现相同接口后方便对各个部分进行统一验证。

1
2
3
4
5
6
7
8

// TxData encodes a transaction in the blockchain.
type TxData struct {
	Version        uint64
	SerializedSize uint64
	TimeRange      uint64
	Inputs         []*TxInput
	Outputs        []*TxOutput
}

1
2
3
4
5
6
7
8
9

//验证交易结构
type Tx struct {
	*TxHeader           //header 指针
	ID       Hash				//header entryID
	Entries  map[Hash]Entry  //交易组件对应的entries
	InputIDs []Hash // TxData.Inputs的 entryID
	SpentOutputIDs []Hash  //SpendInput的Output entryID
	GasInputIDs    []Hash  //btm spend 和 coinbase 的entryID
}

对于inputs
IssuanceInput 转化成 bc.Issuance。
SpendInput 转换成两个组件一个bc.Output，一个bc.Spend。
CoinbaseInput 转化成 bc.Coinbase。

对于outpus
TxOutput根据ControlProgram是否可以spend被转换为Retirement(不可花费)和Output(可花费)。

每个交易还会添加一个TxHeader 和 一个 Mux。TxHeader中的ResultIds记录了所有交易输出组件的entryID，
是交易验证的入口。Mux用来连接输入和输出。
具体映射关系如下图：

交易验证

从header开始，沿着上面的图从右侧向左对各组件进行依次验证，每一种组件有单独的验证规则，具体验证规则见上图。

由于各组件都实现了Entry接口，所以可以使用同一个函数对所有的组件进行验证。

1
2

验证各组件的函数入口
func checkValid(vs *validationState, e bc.Entry) (err error)

节点发现

节点连接主要负责发现P2P网络中的其它节点。Bytom实现了类Kademlia的DHT存储有关网络中Bytom节点的信息。协议维护了节点路由表，节点路由表依据距离把网络中节点信息存储到表中不同的bucket中。

节点发现协议

节点ID及距离

网络中每个节点都有一个唯一ID，节点每次启动时都会产生ED25519公私钥对，其中公钥作为节点的ID，长度32byte。

两个节点之间的距离是以下公式计算而来，所以节点之间的距离代表逻辑距离，而不是节点间的真实物理距离。

1

distance(n₁, n₂) = keccak256(n₁) XOR keccak256(n₂)

节点路由表

根据Kademilia协议节点需要保留其邻居节点的信息。邻居节点存储在由“k-buckets”组成的路由表中。对于每个bucket[i] 0≤i<256，存储距离自己“2^i”和“2^(i + 1)”之间的距离节点。

协议使用“k = 16”，即每个k-bucket最多存储16个节点。bucket中节点按上次查看的时间排序 - 最近看到的节点位于bucket头部，最先看到的在bucket尾部。

每当遇到新节点N1时，它就可以插入相应的桶中。如果桶中包含少于“k”的节点，则可以简单地将N1添加到桶头部。如果该桶已经包含k个节点，则取桶中最先看到的节点N2，需要通过发送ping数据包重新验证节点是否在线。如果没有从N2收到答复，那就是被认为是无效的，N2被移除bucket并且N1被添加到桶的前面。
否则将N2加入cache中，如果cache也满了，则把最先放入cache中的节点N3删除。当有节点掉线时则会把cache中的最新节点放入bucket中。

路由表刷新

节点通过定期迭代查找距离targetID距离近的节点来更新路由表。工作过程如下：

a. 随机生成目标节点Id，记为TargetId，从1开始记录发现次数和刷新时间。

b. 在当前节点的K桶里查找与目标节点最近的16个节点

c. 向b中得到的每个节点发送findnode命令,接收到每个节点传回的neighbours节点

d. 对c返回的每个节点进行ping-pong测试然后更新到本地k桶

如果一轮FindNode查询无法返回比已知最近的节点更近的节点，启动器将FindNode重新发送到k个最近节点中未查找过得节点。

协议消息及编码

协议实现了Kademlia协议的两组命令：

ping<------------->pong

findnode <---------->neighbors

节点发现消息作为UDP数据报发送。数据包的最大大小为1280字节。

1

packet = packet-header || packet-data

每个数据包都以header开头：

1
2
3

packet-header = hash ||nodeID ||signature||packet-type
hash = sha3（nodeID || signature || packet-type || packet-data）
signature = sign（packet-type || packet-data）

hash 字段使在同一个UDP端口上运行多个协议时可识别。

packet-type 是定义消息类型。

Ping Packet（0x01）

1
2
3

packet-data = [version，from，to，expiration]
from = [sender-ip，sender-udp-port，sender-tcp-port]
to = [recipient-ip，recipient-udp-port，0]

expiration 字段是绝对的UNIX时间戳。包含过去时间戳的数据包会因为过期而无法处理。
收到ping数据包后，收件人应使用pong数据包进行回复。

Pong Packet（0x02）

1

packet-data = [to，ping-hash，expiration]

Pong是对ping的回复。

ping-hash 应该等于相应ping包的hash。应该忽略没有包含最新ping-hash的pong数据包，因为不是对最新ping消息做出的响应。

FindNode Packet（0x03）

1

packet-data = [target，expiration]

FindNode 数据包请求接近target的节点的信息。收到FindNode后，收件人应回复Neighbors数据包，在其本地表中找到最接近target的16个节点并返回。

Neighbors Packet（0x04）

1
2

packet-data = [node，expiration]
nodes = [[ip，udp-port，tcp-port，node-id]，...]

Neighbors是对FindNode的回复。