本文主要是介绍IDK（自己瞎想的一种共识算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-------------------------------2020-05-02更新---------------------------------
很久没有正式发博客了。
去年加了几个云原生和区块链的社区和技术群，有问题基本都在社区/群里解决了，再加上用印象笔记越来越多，基本上有什么想法都会随手写在印象笔记上；而且CSDN上抄袭太严重了，像这篇博客费那么大劲写出来，别人Ctrl+C-->Ctrl+V几秒钟就完事，太心寒了，这些原因导致现在CSDN用的越来越少了；中间写过6/7篇博客，每次想到花了那么多心思完善出来的博客，有可能又被人Copy走了，所以最后也都删掉了。
过几个月再来看吧。
（后来对这篇文章有很多改动，但是没有放上来，都在印象笔记上，有需要的留言，不过最近有事，可能不能及时看到留言。）
-------------------------------2020-05-02更新---------------------------------
1 相关概念
1.1 Region：根据地理位置进行分区，比如可以按照省份进行划分，该地区的节点同属一个region。
全局来看，Region是进行共识时的最小单位。
1.2 Genesis Node：初始节点，它只负责在收集申请加入网络的节点的信息，在达到一定条件后就根据申请加入网络的节点划分出若干region，这个条件根据网络是否是第一次启动而有所不同：
1）网络重启：在网络重启前我们将整个世界分为100个region，每个region都有若干数量的节点，在网络重启时，Genesis Node在收集到某个region中2/3个相关节点的注册信息或者超过超时设置后，从这个region中选出这个leader，然后从leader中选出新的Consensus Node，这些被选出的新Consensus Node会先复制区块数据并进行测试，这个跟区块的复制和测试的过程是相同的。选出Consensus Node并测试之后，Genesis Node的职责已经执行完毕。以后执行交易过程，Genesis Node不负责参与，他们只是跟着记录区块数据及请求，目的是做备份。
2）网络第一次启动：如果是第一次启动整个网络，在收集到初始个数—N（比如N可以是100）个节点的请求，或者达到超时设置后（比如我们可以设置超时时间为1天，或者1小时），就把当前申请的节点根据IP分为不同的region，然后继续执行后续过程。
在划分完成后，Genesis Node会通知所有被划分的节点。
1.3 Leader Node：因为Region是进行共识的最小单位，所以region产生后需要选举出一个可以代表该region的节点，该节点即为leader-node。所有region各有一个leader，所以本来是对全网络所有节点进行共识的工作，现在就转化为了对所有leader的共识。
1.4 Consensus Node：共识节点。Consensus Node对leader进行共识。
1）Consensus Node的产生：Consensus Node是从leader中选举得到的：当所有region选举leader结束时，Genesis Node会从所有的leader中选择出若干（3~5）个Consensus Node，那些被选择成为Consensus Node的leader节点，会再次通知整个region的所有节点进行第二次leader的选举，第二次选举选出的节点作为leader代表region进行共识。
2）Consensus Node的工作原理：Genesis Node选举出Consensus Node后，需要选择一种交易序号生成策略，将该策略所生成的交易序号等差分发配给各个Consensus Node。每个leader发送给多个Consensus Node交易请求，每次发送请求时都会附带一个RegionID_LeaderID_Timestamp，多个Consensus Node收到的请求可能有重复的，此时Consensus Node经过剔重处理后，确保每个Consensus Node上的RegionID_LeaderID_Timestamp不会出现在其他Consensus Node上，接下来，Consensus Node会为所有的交易分配交易序号，分配完毕后，Consensus Node将自身处理的交易发送给所有leader和其他Consensus Node，Consensus Node和leader在收集到所有Consensus Node发送的信息后，都会对接收到的信息按照交易序号进行排序，然后执行交易，对于不成立的交易直接丢弃。每个leader执行完所有的交易后，生成一个区块，然后leader将该区块的hash值发送给Consensus Node，所有Consensus Node比较所有leader发送来的hash值及所有Consensus Node得到的hash值，如果都相同，则向所有leader发送commit请求。至于hash不相同的情况，后面会给出相应解决方案。
交易序号生成策略：交易序号不是随机生成的，也不是顺序下来的，而是经过一定的策略生成的。所有peer可以根据策略得到在这个策略下的初始序号值(也就是这个策略下的第一个值。比如我们现在使用的策略是奇数策略，那么第一个值就是1。)，而且可以根据自己收到的最后一个交易提交请求的序号值计算得知下一个序号值是多少，比如我们使用的是奇数策略，当前序号值是5，那么下一个来的查询请求的序号值就应该是7，
系统应该提供一些默认的策略，比如整数顺序排下去，或者奇数、偶数排下去。这个策略也可以由开发者自定义。不管指定什么样的策略，这个算法都应该保证：
1、所有人根据该策略可以得到有且只有一个初始序号值。
2、所有人可以根据当前序号值得到有且只有一个下一个序号值。
3、原则上不建议出现循环，如果出现循环，则需要保证单次循环之间至少包含一千万个数（具体多少应根据tps来决定）。
比如，如果我们采用的是奇数策略，现在有三个Consensus Node，则第一个Consensus Node分到1，7,13,19,25,31……，第二个Consensus Node分到3,9,15,21,27,33……，第三个Consensus Node分到5,11,17,23,29,35……。
开发者可以同时指定多种策略，这些策略被称为策略集合，简称策略集。系统启动后，由Consensus Node从策略集中随机选择一个策略作为接下来要使用的策略，根据策略的不同来设置不同的过期时间。比如在选定策略时可以同时生成一个long型随机数，该随机数是该策略在系统中被使用的时间，时间一到，Consensus Node再从除当前策略之外的策略集中随机选择一个。如果被选择的策略以编码的形式显示指定了到哪个随机数是到期，则以策略中指定的为准(比如现在使用的是奇数策略，策略中有一个方法叫endNumber()，该方法返回了7，超时时间为10000000000000，则序号值到7后或者过了超时时间10000000000000后，该策略失效，如果未指定到期序号，则使用超时时间作为结束标志。)
1.5 Secondary creation block：次创世块。如果系统中区块数量不多，此时复制的工作量比较小，可以很快完成。但是随着系统运行时间的不断延长，系统中的区块数量可能会非常多，此时分发到每个正常节点的区块链的长度会非常长，从而导致复制的时间会非常长，此时可以考虑将某区块前面的所有区块存储起来，并标记该区块的位置，新加入的节点在复制区块时可以不复制前面的部分，而是从被标记区块处开始复制，这样可以缩短复制时间。
Region、Leader Node和Consensus Node是动态变化的，每隔一段时间都会有所改变。
2 启动网络
2.1、Genesis Node划分region
网络第一次启动时，所有想加入网络的节点都向Genesis Node发起注册请求，Genesis Node收集这些请求，在收集到项目发起方制定的初始节点数N或者达到超时设置后，Genesis Node自动对已收集到的节点划分region，在划分完成后，Genesis Node会通知所有被划分的节点。
2.2、各region内部选举leader
各个节点接收到Genesis Node的通知后，立即进行leader选举。现有很多成熟的选举leader的方案，只要具有随机性、能选举出一个leader即可。被选举出的leader将代表整个region中的所有节点进行共识。
2.3、交易。
2.4、测试。
测试在区块链网络的整个生命周期中都存在，即每隔一段时间就会进行一次验证。
3 新节点的加入：
3.1 前置验证
当有节点想加入到网络中时，该节点需要先连接Consensus Node，Consensus Node会将其分配至某一个region中，接下来节点还需要先经过前置验证，这些验证暂时包括：
- 网络节点数保护：
在知道集群当前正常节点个数的前提下，如果有节点想加入集群，可以允许其参加网络，但是同一时间/时期，最多允许该节点加入的region中节点总数的(n-1)/2个新的node加入，比如，现在节点即将加入的region中有9个正常节点，此时如果节点想加入网络，只要节点个数小于等于4，就可以允许其加入。
2、代码保护机制：
项目启动后对项目代码和所运行的二进制代码进行实时的监测，一旦hash与预期的不同，这说明当前运行的代码可能存在危险。
3.2 区块的复制
区块的复制根据之前是否加入过网络有不同的策略：
1）节点重新连接至网络。某个已经参与到网络中的节点，因为某些原因（长时间断网或者断电）导致该节点有一段时间没有参与交易，如果这个时间超过了设置的超时时间，则该节点再想加入到网络中，就相当于新加入网络；如果没有超过超时时间，此时可能出现这样两种情况：
i:数据延迟。很有可能在该节点不参与交易时发生了大量交易，产生了很多区块，此时该节点上的数据实际是有延迟的，我们将这种节点称为延迟节点。延迟节点在加入网络前需要先同步数据：peer先检测本地区块数据，再与现有的完整区块做对比，然后region的Consensus Node再根据区块数量的差值分发复制任务。比如：现在有1000个区块，一个节点请求加入网络，将其分配给了某个region（该region原先有10个节点），该region通知该节点自检，查看该节点本地有多少区块，该节点自检发现本地有500个区块，节点所在region的Consensus Node计算出需要复制的区块数量=1000-500=500，然后500/10=50，所以原先在该region的10个节点分别需要负责50个区块的复制任务。
区块数据同步完成后，接下来就是数据验证（测试），具体步骤见前文。
ii:如果数据未发生延迟，此时对网络进行简单的测试（通过加密手段对数据测试）后直接允许节点进行交易。
2）节点新加入网络。第一件事是将该节点根据IP和地区位置分配给某个region。接下来Consensus Node会通知相应region的leader和该节点，紧接着是复制区块数据。此时区块复制涉及复制和验证两个阶段。
a)复制：该过程发生的主体是处于区块复制队列的节点，有两种复制方式：
i：一种是直接复制区块数据以及所有的请求；
ii：另一种是仅仅复制所有的请求，peer根据初始数据来执行复制的请求，一条一条请求的执行，生成一个个的区块，最终直到执行完所有的请求。
数据复制阶段：不管是直接复制所有区块及其请求，还是仅复制请求，都涉及数据的复制。如果所有数据都由同一个节点负责复制，会出现两个问题：
1、如果该节点中的数据有误，会导致无法通过验证阶段，白复制了。
2、所有数据都从同一个节点复制，会导致该节点压力过大。
为了避免出现以上问题，在复制时采用分段复制，即每个正常节点负责一段区块链的复制，比如现在集群中有932个区块、即将加入的region中有10个正常节点，此时可以让每个正常节点负责100个区块的复制工作，不足100的则按照实际数量进行复制。
b）验证：验证请求由Consensus Node发起，验证时只验证各个区块的hash值。只要各个区块的hash值相同，则认为复制阶段没有出现错误。（除了只验证hash外，系统还需要提供一种或多种基于智能合约的验证：该智能合约可以根据输入的数据进行计算，然后得出一个值。Consensus Node对该算法进行加密后，发送给待验证node， node根据该加密算法进行计算，然后将计算结果返回给Consensus Node。）
*attention 1：即便是第一次加入网络，有时为了缩短复制时间，节点可能从其他地方复制了已知的区块数据，此时的解决方案跟发生数据延迟时的解决方案一样，在数据复制、测试完成后，可以允许节点加入进网络。
*attention 2：前面说，将请求加入网络的节点分给某个region后，Consensus Node会通知相应region的leader和该节点，但是有可能该节点和相应的leader节点都没有收到Consensus Node发送的信息，这个问题，后面会给出解决方案。
3.3 测试阶段
4 测试
不管是第一次启动网络还是有节点加入网络，都涉及到测试，这里统一说一下：
针对节点的不同测试目的也有所不同：
1、测试待加入网络的节点 目的：为了验证其是否具有恶意性。
2、测试正常节点 目的：为了测试其是否具有恶意性，同时验证该节点链上的数据是否正常（正常是指复制阶段未出错。虽然验证阶段会对复制的区块进行验证，但是实际上，如果node在验证时使用正常的区块链，而通过验证后、真正参与到网络中时，不再使用正常的区块链，而是改用自己修改后的恶意区块链，如果这种恶意节点数量过多，数据就有可能会被篡改，所以仍然需要随时进行测试）。
测试是否具有恶意性可以通过先执行一个请求、然后再执行相反请求的方式来进行测试（加密货币的话可以设置两个系统账号，A先向B转N个代币，然后再执行B向A转N个代币；其他应用场景的话，可以是先执行一个操作，增删改都可以，然后再声明该操作无效）。
1）测试带加入网络的节点。有新的node加入集群，并且新加入的node已经完成了区块的复制，此时node进入测试阶段，只有通过测试，节点才正式加入网络。
测试时会有测试不通过的情况，不通过有可能是被测试node返回的结果是错误的（此时该node有可能是恶意节点，只是有可能，因为出错了有可能是内存泄漏，导致程序运行出错，也有可能是网络数据包被篡改），也有可能是没有收到被测试node返回的结果（此时可能是网络出现了问题），这时需要进行一定的容错处理：
a）一次测试不通过，则继续测试。
b）两次测试不通过的节点，被标注为临时无效节点，并继续进行测试。如果第三次测试通过了，则从步骤一重新开始测试。
c）三次测试不通过的节点，直接将IP拉入黑名单，一段时间内禁止该IP注册新的node。如果第三次测试通过了，则从步骤一重新开始测试。
d）我们以F来代表测试失败，以T来代表测试成功。有时测试会出现FFTFTFFTFTFTFFT这种情况，根据1）2）3）条规定，这时会无限重复下去，为了防止此种情况的发生，我们给每个节点设置两个变量—tolerantFaultTimes和tolerantLostTimes，tolerantFaultTimes记录节点处于被测试阶段时测试失败的次数，每次测试失败，tolerantFaultTimes都做++操作，只要该变量的值超过了我们预设的值（比如我们可以预设为2），则立即拉黑该节点。tolerantLostTimes用于记录测试时未收到node返回值的次数（此时认为返回信息丢失），只要在超时时间内未返回结果，tolerantLostTimes就做++操作。如果tolerantLostTimes超过了我们预设的值（比如我们可以预设tolerantLostTimes为2），此时并不会拉黑该node的IP，仅仅是从节点列表里剔除该节点（因为超过了tolerantLostTimes的预设值仍然没有连续错两次，说明其可能真的只是网络条件不好导致结果无法被正常接收）并通知node剔除的原因，待该节点排查完原因后，可再次请求加入。
*attention 1：Consensus Node内部维护有若干队列，如正常节点队列、测试中队列、复制区块中队列、验证队列和IP黑名单队列……Consensus Node在测试节点的过程中，并不是只发给处于测试阶段的node，而是对全网所有的node都进行，只不过是处理逻辑不同：
对于处于测试阶段的节点，按照上述处理方式来处理。
对于已经存在于正常节点队列中的节点来说，如果出现测试结果错误的情况，则立即将其从正常节点队列中剔除，并将其加到测试中队列，并按照上述过程进行测试；或者是如果出现收不到测试结果的情况，累计达到三次，则认为其网络异常，则将其从正常节点队列中剔除，并将其加到测试中队列，并按照上述过程进行测试。
*attention 2：经过若干次测试后，如果测试中节点没有问题的话，则将其加入到复制区块中队列，同时将其从测试中队列里面删除。
除了以上看上去与正常交易请求没有任何区别的测试手段外，系统还应提供一种或几种基于智能合约的测试：该智能合约可以根据输入的数据进行计算，然后得出值。Consensus Node对该算法进行加密后，发送给待测试节点，节点根据该加密算法进行计算，然后将计算结果返回给Consensus Node。算法需要提供多种，由Consensus Node随机选中某一种。Consensus Node在发送这种测试请求时，通过数字证书将使用的加密算法的具体内容发送给节点，然后节点根据传递过来的算法进行计算。
5 数据共识失败，集群宕机与重启
5.1 共识失败与宕机【2019-05-09补充：可以不必宕机，只需要暂停对外服务，重新选举leader节点跟Consensus Node即可】
恶意节点集中式爆发导致集群共识失败：
其实大部分的共识算法保证的是本次传递的数据可以被集群中大部分的节点认同，但是如果恶意节点数量超过了正常节点的数量，共识算法是无法保证共识的结果跟正常节点占多数情况下所得出的结果是一致的。比如pbft算法：假设此时集群中有4个node，三个正常节点，另一个节点是组织A混进来的异常节点，但是这个异常节点并没有表现出恶意，而是作为一个正常节点正常工作。组织A紧接着又向集群中依次添加了6个这种节点，这时集群中有10个节点，其中有3个是正常node，7个异常节点，这时如果这7个节点如果突然爆发恶意，将本来是x的结果恶意改为y，这是因为得出y的节点数量为7，满足pbft的条件，所以此时集群数据就会被篡改，这时从算法的角度来看，确实是共识成功，但是从数据角度来看，其实共识是失败的。另外，如果某个人或组织控制了大部分的节点，因而此时多数region的leader节点可能都受他控制，此时他可以通过修改网络数据包的方式来篡改共识数据，因为此时他是控制大多数节点的，所以也有可能会出现这种情况。
为了防止此种情况的发生，需要Consensus Node充当中间层，用于验证：在对各个node进行共识之前，Consensus Node集群需要先达成共识。
下面补充介绍Consensus Node的部分功能：Consensus Node本身并不参与数据的共识，但是它们在发送请求的同时，也会在本地执行计算过程。Consensus Node集群在对各个节点返回的结果进行共识前，需要在它们本身的集群（Consensus Node集群）中先达成共识（此处的共识不必采用专门的共识算法，只需要简单的对比即可），如果可以成功达成共识，则对其他node返回的结果进行共识。既然可能达成共识，相应的，也有可能存在共识失败的情况。比如，某次请求过来后，正常执行的结果是X，Consensus Node也会得出一个结果，如果都是X，则Consensus Node集群会对各个节点的计算结果进行共识；如果Consensus Node集群得出的结果不是X，可能会有三种情况：
i：第一种是只有名为a的 Consensus Node跟其他Consensus Node不同，这时需要再次执行本次请求，如果还是只有a跟其他不同，则重新选举一个Consensus Node，然后再执行本次请求。
ii：第二种情况是出现了多种结果，此时Consensus Node集群停止对外服务，Consensus Node之间互相发送信息，找出时间上最近的、大家都认同的区块及其结果，找到后，全网广播找到的这个区块，然后整个集群宕机（这是第一种宕机的情况）；
iii：第三种情况就是有的Consensus Node节点没有任何返回结果。此时的处理方式参照情况一。
这样就将各个节点之间复杂度较高的共识分成了相对来说较为简单的两个共识阶段，阶段一是leader之间的共识，阶段二是单个leader对其所负责的节点进行共识。
第一阶段：各个region的leader节点在请求转发中心的帮助下完成共识。上面已经给出了具体介绍。但是也会有共识白的情况：
a）Consensus Node集群共识出的结果跟大部分leader共识出的结果不相同，或者leader得出了很多中结果，切没有一个结果的数量超过半数，此时Consensus Node集群停止对外服务，Consensus Node之间互相发送信息，找出时间上最近的、大家都认同的区块及其结果，找到后，全网广播找到的这个区块，然后整个集群宕机（这是第二种宕机的情况）；
b）多数leader共识结果跟Consensus Node共识结果相同，只有个别leader不同，此时该leader所在的region宕机。（这是第三种宕机的情况）；
第二阶段：Consensus Node在达成共识后，接下来才是各个leader向各自负责的region中的节点发送请求（其本身也执行），并收集各个节点返回的结果，然后对其负责的各个节点返回的结果进行共识操作：如果该regin的多数节点的返回结果跟Consensus Node集群得出的结果相同，则认为该regin成功完成了共识。如果所有的regin都完成了共识，然后Consensus Node节点向其所在的regin集群发送提交命令。
而对于那些没有返回正确结果的节点，默默记录下其本次未计算出正确结果，跟复制、验证时一样，达到一定次数即将该节点剔除。
如果某个节点只记错了一次，还未达到剔除的次数，那么就将该节点从正常节点队列中剔除，并纳入可能出错队列中，接下来共识时不会将该节点的返回结果考虑在内，但是会记录该节点每次返回的结果跟当前region中大部分节点的返回结果是否相同，如果累计若干次都相同，则认为该节点是一个正常节点，此时将该节点从可能出错队列中剔除，并重新纳入正常节点队列。另外，只要某个peer节点有计算不正确结果的记录，则在选择Consensus Node时，不会将该节点考虑在内。
如果leader集群达成了共识，而且绝大部分的region共识的结果跟Consensus Node集群共识的结果是相同的，但是极个别的region中的节点得出的结果并非Consensus Node集群的结果，此时可以让这几个极个别的region临时宕机。Consensus Node记录相关信息后准备重启事宜。
5.2 重启
网络重启是一个自动的过程，在Consensus Node通知全网宕机后，所有节点停止对外服务，并立即重新启动，重启后需要重新向Genesis Node注册，并再次选举leader。选举出leader后，需要对宕机前的区块数据进行共识：
所有节点上报本地区块的hash给leader，leader在region内部达成共识后上报给Consensus Node，Consensus Node对所有leader上报的数据进行共识，共识成功后开始对外服务。
6 其他：
6.1 维护一致性状态
来看这么一种情况：某个leader在给它管理的节点发送交易请求时，若干节点的网络临时出现了波动，导致丢失了一些交易请求（因为region是根据地区划分的，所以可能会出现多节点同时出故障的情况），导致这些节点并没有收到交易提交请求，所以这些节点上的数据并不是最新的（虽然会有对正常节点的测试，但是测试并不能完全解决问题，因为为了保证系统的TPS，对于正常节点的测试不会太频繁，所以会有一小段时间存在数据不同步的情况），如果此时查询请求被分发到这些节点上，查询得到的结果可能还是不是最新的，要过一段时间才能查到最新的结果，这种情况可能会让用户有很不好的使用体验。这种情况就是区块复制处提到的数据延迟。
我们需要一个策略来保证各个节点之间的数据能够快速的同步，或者说缩短两次一致性状态之间的时差：
交易过程中需要给每个账单一个序号（一份账单上可能包含若干交易，比如，交易A，交易B，交易C被Consensus Node组成了账单—FirstOrder，我们这里讨论的交易提交序号就是指这个FirstOrder），每个查询请求在查询时需要附带最新的账本序号，当节点发现请求附带的账本序号比自己当前的账本序号大的话，就将本次查询请求通过leader转发给其他节点并立即停止各项服务，然后向leader发起数据同步请求。
6.2信息同步
因为leader跟Consensus Node之间交互较多，为了确保Consensus Node中的信息跟leader中信息的一致性：可以让leader节点定期与Consensus Node进行交互，核查本region中的全部节点是否跟Consensus Node中所对应region的信息相同，例如：假设leader中记录的某个region的节点比Consensus Node中记录的多，则剔除多出来的；如果leader节点中的节点比Consensus Node中对应region中节点的数量少，则通知Consensus Node将多出的节点分给该leader节点。如果同一个节点在多个leader中出现，则随机剔除只保留一个leader中的节点。整个过程可以通过心跳机制来确保节点没有下线，达到一定心跳次数后，就同步一次信息。
这篇关于IDK（自己瞎想的一种共识算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
