一种面向数据交易的可信处理方法与系统转让专利
申请号 : CN201911032663.0
文献号 : CN110971663B
文献日 : 2021-03-12
发明人 : 黄罡 , 蔡华谦 , 景翔 , 张颖 , 刘譞哲
申请人 : 北京大学
摘要 :
权利要求 :
1.一种面向数据交易的可信处理方法,其特征在于,应用于P2P网络系统,所述P2P网络系统包括多个节点,所述节点中包括积极列表Active List和消极列表Passive List,所述Active List分为活跃列表Eager List和惰性列表Lazy List;其中,所述Active List中的节点数量为固定值,所述Eager List中存放的是在P2P网络系统上和该节点建立TCP连接的节点,用于传递消息;所述Lazy List中存放的是所述Active List除Eager List中的剩余节点,用于传递消息的摘要或消息的ID,用于P2P网络系统的优化和容错;所述Passive List中存放的是随机节点,用于替换Active List中断开连接的节点,保证节点和所述P2P网络系统中网络的连接;所述方法包括存入方法和查询方法;
所述存入方法包括:
所述P2P网络系统中的发起交易节点在发起交易的过程中,从所述P2P网络系统中随机选择多个见证节点对该交易进行见证;
所述见证节点将见证该交易所产生的交易数据打包,生成区块;
所述见证节点从所述P2P网络系统中随机选择多个存储节点;
所述见证节点将所述区块发送给多个所述存储节点;
所述存储节点对所述区块进行存储;其中,针对一笔交易,所有见证节点和所有存储节点的所有区块构成有向无环图DAG结构;
所述查询方法包括:
在所述P2P网络系统中,第一节点获得其父节点广播的查询请求,所述第一节点为所述P2P网络系统中的任一节点;
所述第一节点通过树形维护程序将所述查询请求广播给自身的孩子节点;所述孩子节点用于利用所述P2P网络系统的树形结构,将所述查询请求再广播给自身相应的孩子节点,自身相应的孩子节点重复上述广播步骤,直至将所述查询请求广播至该P2P网络系统上的所有节点;每个节点在收到查询的请求后,检索本地数据库,并等待其孩子节点的结果返回,当收集完所有的孩子节点返回的数据后,做结算和去重操作,并将结果返回给其父节点;经过层层反馈,当接收到用户查询请求的根节点收到所有孩子节点的返回结果时,做最终的结算和去重操作,生成最终查询结果,并将最终查询结果返回给该用户;
所述树形维护程序包括可扩展维护程序和容错性维护程序;
针对所述可扩展维护程序,所述查询方法包括:所述第一节点在将所述查询请求广播给自身的孩子节点时,向自身的孩子节点中的第二节点发送IHAVE消息,所述IHAVE消息中包括消息ID;
所述第二节点检查自己是否已收到与所述消息ID对应的用于传递所述查询请求的NORMAL消息;
如果所述第二节点在超时时间内未收到与所述消息ID对应的NORMAL消息,则执行以下步骤:
所述第二节点生成用于修复所述P2P网络系统的GRAFT消息;所述GRAFT消息包括所述消息ID和接收所述IHAVE消息的请求;
所述第二节点将所述GRAFT消息发送给所述第一节点,并将所述第一节点从自身的Lazy List中移动到Eager List中,使所述第一节点对所述P2P网络系统进行修复;
如果所述第二节点在超时时间内已收到与所述消息ID对应的NORMAL消息,则执行以下步骤:
所述第二节点计算IHAVE消息的接收跳数与NORMAL消息的接收跳数差;
所述第二节点判断所述跳数差是否超过跳数阈值;
若所述跳数差超过跳数阈值,所述第二节点对所述P2P网络系统进行修复;
针对所述容错性维护程序,所述查询方法包括:当构成所述P2P网络系统的边的第一节点和第二节点之间的连接断开时,所述第一节点将所述第二节点从自身的Eager List中移除;
所述第一节点依次向其Passive List中的第一目标节点发起查询请求;所述查询请求包括检查第一目标节点是否在线的指令和查询第一目标节点的Lazy List的大小的指令;
所述第一节点接收各个第一目标节点针对查询请求返回的查询结果,根据所述查询结果中的延迟和各个第一目标节点的Lazy List的大小,从所述第一目标节点中选择一个Lazy List的大小最小且延迟最低的第二目标节点;
所述第一节点将第二目标节点加入自身的Lazy List中,并利用Lazy List中的节点作为替补边来对所述P2P网络系统进行修复。
2.根据权利要求1所述的方法,其特征在于,所述存入方法包括:在所述DAG结构中,每个区块有多个前序区块和多个后续区块。
3.根据权利要求2所述的方法,其特征在于,所述存入方法包括:所述区块包括区块头和区块体;所述区块头包括多个前序区块的ID,见证节点签名、时间戳、唯一标识Nonce、数链版本、区块数、Merkle Tree树根;其中,所述区块体包括所述交易数据。
4.根据权利要求1所述的方法,其特征在于,针对一笔交易,所述见证节点的数量为3个,每个见证节点选择的存储节点的数量为3个。
5.根据权利要求1所述的方法,其特征在于,所述P2P网络系统包括BroadcastTree、MsgTransferProt和PartialView这3个协议,所述BroadcastTree负责P2P网络系统的维护工作;所述MsgTransferProt负责查询消息的广播和查询结果的验证传递;所述PartialView负责管理每个节点的邻居节点,所述邻居节点包括父节点和孩子节点;其中,所述Active List和所述Passive List位于P2P网络系统的PartialView协议中;
所述每个节点中包括第一Map缓存、第二Map缓存以及第三Map缓存,第一Map缓存是ReceivedMsgMap,存放的是消息ID和消息的映射,用来缓存当前已经收到的消息,以便于响应其他尚未收到该消息的节点对该消息的请求;
第二Map缓存是NotReceivedMsgMap,缓存的是消息ID和发送该消息的节点的映射;当达到指定的时长时,仍未收到Eager List中的节点发送的该消息,触发Timer定时器,用于向发送该消息的节点请求该消息,并修复所述P2P网络系统;
第三Map缓存是TimingCacheMsgMap,负责缓存当前收到的消息,如果在指定的时间范围内收到Lazy List中的节点发送的消息,比较两者的跳数来决定是否优化所述P2P网络系统。
6.根据权利要求5所述的方法,其特征在于,所述查询方法包括:所述第二节点收到消息时,通过所述ReceivedMsgMap检查是否已经收到所述IHAVE消息或NORMAL消息;
如果收到所述IHAVE消息或NORMAL消息,则丢弃该消息;
如果未收到所述IHAVE消息或NORMAL消息,则查看是否收到所述IHAVE消息或NORMAL消息的ID;
如果未收到,则丢弃该消息;否则,将所述IHAVE消息的ID或所述NORMAL消息的ID加入到NotReceivedMsgMap中,并将所述IHAVE消息或NORMAL消息设置为超时事件。
7.根据权利要求1所述的方法,其特征在于,针对所述容错性维护程序,所述查询方法还包括:
当所述第一节点中的Passive List中的在线节点数量小于预设阈值时,所述第一节点生成一个固定的跳数TTL;
所述第一节点将带有该TTL的消息发送给其Eager List中的一个随机的第三目标节点;所述第三目标节点收到该消息后,把自己最新的Passive List中的节点ID发送给第一节点,并将所述TTL减1,再随机发送给所述第三目标节点EagerList中的随机节点,重复上述步骤,直到所述TTL为0;
所述第一节点将所有收到的节点ID做汇总,随机从收到的所有节点中选M个,将这个M个节点加入到Passive List中;其中,所述M=Passive List中可存储的最大节点数减去Passive List中当前存储的节点数。
8.根据权利要求1所述的方法,其特征在于,在所述第一节点加入所述P2P网络系统之前,所述方法包括:
所述第一节点获取所述P2P网络系统的部分拓扑信息,应用所述拓扑信息初始化自身的Eager List、Lazy List和Passive List;
当完成Eager List、Lazy List和Passive List的初始化后,所述第一节点与其Eager List中的节点分别建立TCP长连接,用来构成所述P2P网络系统的边;
所述第一节点利用Lazy List中的节点作为替补边来对所述P2P网络系统进行修复,仅留下一个传输速度相对较快且跳数最少的边,剩下的节点被最终移除到Lazy List中。
9.根据权利要求8所述的方法,其特征在于,所述拓扑信息包括随机分配的节点NodeID;所述第一节点获取所述P2P网络系统的部分拓扑信息,应用所述拓扑信息初始化自身的Eager List、Lazy List和Passive List的步骤包括:所述第一节点利用所述NodeID和KAD算法向P2P网络系统的网络发起请求,查找距离该NodeID最近的邻居节点;
所述第一节点从所述邻居节点中选择部分节点来初始化自身的Eager List、Lazy List和Passive List。
10.一种面向数据交易的可信处理系统,其特征在于,应用于P2P网络系统,所述P2P网络系统包括多个节点,所述节点中包括积极列表Active List和消极列表Passive List,所述Active List分为活跃列表Eager List和惰性列表Lazy List;其中,所述Active List中的节点数量为固定值,所述Eager List中存放的是在P2P网络系统上和该节点建立TCP连接的节点,用于传递消息;所述Lazy List中存放的是所述Active List除Eager List中的剩余节点,用于传递消息的摘要或消息的ID,用于P2P网络系统的优化和容错;所述Passive List中存放的是随机节点,用于替换Active List中断开连接的节点,保证节点和所述P2P网络系统中网络的连接;所述系统包括存入装置和查询装置;
所述存入装置包括:
见证节点选择模块,被配置在所述P2P网络系统中的发起交易节点中,用于在发起交易的过程中,从所述P2P网络系统中随机选择多个见证节点对该交易进行见证;
交易数据打包模块,被配置在所述见证节点中,用于将见证该交易所产生的交易数据打包,生成区块;
存储节点选择模块,被配置在所述见证节点中,用于从所述P2P网络系统中随机选择多个存储节点;
区块发送模块,被配置在所述见证节点中,用于将所述区块发送给多个所述存储节点;
区块存储模块,被配置在所述存储节点中,用于对所述区块进行存储;其中,针对一笔交易,所有见证节点和所有存储节点的所有区块构成有向无环图DAG结构;
所述查询装置包括:
查询请求获得模块,被配置在第一节点中,用于在所述P2P网络系统中,获得其父节点广播的查询请求,所述第一节点为所述P2P网络系统中的任一节点;
查询请求广播模块,被配置在所述第一节点中,用于通过树形维护程序将所述查询请求广播给自身的孩子节点;所述孩子节点用于利用所述P2P网络系统的树形结构,将所述查询请求再广播给自身相应的孩子节点,自身相应的孩子节点重复上述广播步骤,直至将所述查询请求广播至该P2P网络系统上的所有节点;每个节点在收到查询的请求后,检索本地数据库,并等待其孩子节点的结果返回,当收集完所有的孩子节点返回的数据后,做结算和去重操作,并将结果返回给其父节点;经过层层反馈,当接收到用户查询请求的根节点收到所有孩子节点的返回结果时,做最终的结算和去重操作,生成最终查询结果,并将最终查询结果返回给该用户;
所述树形维护程序包括可扩展维护程序和容错性维护程序;
针对所述可扩展维护程序,所述查询装置包括:IHAVE消息发送模块,被配置在所述第一节点中,用于在将所述查询请求广播给自身的孩子节点时,向自身的孩子节点中的第二节点发送IHAVE消息,所述IHAVE消息中包括消息ID;
NORMAL消息检查模块,被配置在所述第二节点中,用于检查自己是否已收到与所述消息ID对应的用于传递所述查询请求的NORMAL消息;
GRAFT消息生成模块,被配置在所述第二节点中,用于在超时时间内未收到与所述消息ID对应的NORMAL消息时,生成用于修复所述P2P网络系统的GRAFT消息;所述GRAFT消息包括所述消息ID和接收所述IHAVE消息的请求;
GRAFT消息发送模块,被配置在所述第二节点中,用于在超时时间内未收到与所述消息ID对应的NORMAL消息时,将所述GRAFT消息发送给所述第一节点,并将所述第一节点从自身的Lazy List中移动到Eager List中,使所述第一节点对所述P2P网络系统进行修复;
跳数差计算模块,被配置在所述第二节点中,用于在超时时间内已收到与所述消息ID对应的NORMAL消息时,计算IHAVE消息的接收跳数与NORMAL消息的接收跳数差;
跳数差判断模块,被配置在所述第二节点中,用于在超时时间内已收到与所述消息ID对应的NORMAL消息时,判断所述跳数差是否超过跳数阈值;
第一系统修复模块,被配置在所述第二节点中,用于在所述跳数差超过跳数阈值时,对所述P2P网络系统进行修复;
针对所述容错性维护程序,所述查询装置包括:第二节点移除模块,被配置在第一节点中,用于当构成所述P2P网络系统的边的第一节点和第二节点之间的连接断开时,将所述第二节点从自身的EagerList中移除;
查询请求发起模块,被配置在第一节点中,用于依次向其Passive List中的第一目标节点发起查询请求;所述查询请求包括检查第一目标节点是否在线的指令和查询第一目标节点的Lazy List的大小的指令;
查询结果接收模块,被配置在第一节点中,用于接收各个第一目标节点针对查询请求返回的查询结果,根据所述查询结果中的延迟和各个第一目标节点的Lazy List的大小,从所述第一目标节点中选择一个Lazy List的大小最小且延迟最低的第二目标节点;
第二系统修复模块,被配置在第一节点中,用于将第二目标节点加入自身的Lazy List中,并利用Lazy List中的节点作为替补边来对所述P2P网络系统进行修复。
说明书 :
一种面向数据交易的可信处理方法与系统
技术领域
背景技术
程中形成的庞大数据资源资产化,使之成为支撑数字经济崛起的“新石油”,是数字经济发
展的关键挑战。数据资产价值的发挥是一个让数据“动起来”的过程。高质量、高可用、高有
效数据资产的安全可信流动、加工融合是支撑大数据分析、流通与应用变现,从而推动数字
经济发展的重要基础。政府企事业等单位拥有大量高价值核心数据,有效保障数据资产安
全可信的共享流动和融合使用,防窃取、防滥用、防误用,是数据可信流通过程中关键问题。
易”为主,整个平台的设计以“避免双花”作为前提假设,采用链式结构账本,通过全网共识
机制同步维护全局统一的最长链,交易吞吐量低、交易费用高且不可扩展,使其不能应用于
对实时性要求较高和高吞吐量的场景中,如银行和交易所等。
秒钟的交易数量)增加的情况下,保证查询功能的可扩展性。3、在网络中节点的在线状态和
节点之间的链路连接状态动态变化的环境下,检索出所有节点的相关数据用来支持共识算
法,保证查询功能的容错性。
发明内容
列表Passive List,所述 Active List分为活跃列表Eager List和惰性列表Lazy List;其
中,所述Active List中的节点数量为固定值,所述Eager List中存放的是在P2P网络系统
上和该节点建立TCP连接的节点,用于传递消息;所述Lazy List中存放的是所述Active
List除Eager List中的剩余节点,用于传递消息的摘要或消息的 ID,用于P2P网络系统的
优化和容错;所述Passive List中存放的是随机节点,用于替换Active List 中断开连接
的节点,保证节点和所述P2P网络系统中网络的连接;所述方法包括存入方法和查询方法;
节点,自身相应的孩子节点重复上述广播步骤,直至将所述查询请求广播至该P2P网络系统
上的所有节点;每个节点在收到查询的请求后,检索本地数据库,并等待其孩子节点的结果
返回,当收集完所有的孩子节点返回的数据后,做结算和去重操作,并将结果返回给其父节
点;经过层层反馈,当接收到用户查询请求的根节点收到所有孩子节点的返回结果时,做最
终的结算和去重操作,生成最终查询结果,并将最终查询结果返回给该用户;
令;
个Lazy List的大小最小且延迟最低的第二目标节点;
极列表Passive List,所述 Active List分为活跃列表Eager List和惰性列表Lazy List;
其中,所述Active List中的节点数量为固定值,所述Eager List中存放的是在P2P网络系
统上和该节点建立TCP连接的节点,用于传递消息;所述Lazy List中存放的是所述Active
List除Eager List中的剩余节点,用于传递消息的摘要或消息的 ID,用于P2P网络系统的
优化和容错;所述Passive List中存放的是随机节点,用于替换Active List 中断开连接
的节点,保证节点和所述P2P网络系统中网络的连接;所述系统包括存入装置和查询装置;
述查询请求再广播给自身相应的孩子节点,自身相应的孩子节点重复上述广播步骤,直至
将所述查询请求广播至该P2P网络系统上的所有节点;每个节点在收到查询的请求后,检索
本地数据库,并等待其孩子节点的结果返回,当收集完所有的孩子节点返回的数据后,做结
算和去重操作,并将结果返回给其父节点;经过层层反馈,当接收到用户查询请求的根节点
收到所有孩子节点的返回结果时,做最终的结算和去重操作,生成最终查询结果,并将最终
查询结果返回给该用户;
消息ID;
包括所述消息ID和接收所述IHAVE消息的请求;
自身的Lazy List 中移动到Eager List中,使所述第一节点对所述P2P网络系统进行修复;
目标节点的Lazy List的大小的指令;
小,从所述第一目标节点中选择一个Lazy List的大小最小且延迟最低的第二目标节点;
块后再选择多个随机存储节点对区块进行备份存储;同时采用了有向无环图DAG结构,有向
无环图帐本结构配合nRW共识机制,不仅解决了大规模共享交换过程中的监管问题,还使得
本发明实施例的分布式账本的存证吞吐量随着节点数量的增加可以线性扩展。
P2P网络系统中的父节点,父节点将所有孩子节点返回的数据和本地的查询结果做去重和
结算,将处理后的结果返回给该节点的父节点,以层层汇总的方式将数据返回给根节点,以
此可降低代理节点的负载,保证低延迟。
P2P网络系统,从而把查询结果的处理运算均匀地分配到网络中的所有节点上,并根据节点
的计算能力动态调节出度的大小,可在保证负载均衡的前提下,不对查询的延迟产生较大
影响,保证了系统的可扩展性。
下,保证查询消息被下层节点接收,通过邻居管理协议,可动态地将离开网络的节点替换为
新的在线节点,从而保证整个网络的连通性。
附图说明
具体实施方式
法;
客盗取了价值约5000万美元的以太币(此时的以太币还不是现在的以太坊),当时以太专的
创始人Vitalik Buterin为了挽回大部分的人的损失,采取了硬分叉的策略,用新的长的链
来代替被攻击的链,这样黑客盗取的就没有价值。但是当时社区的部分支持者认为这是一
个去中心化的社区,不应该由一个人决定未来。所以坚定愿意抗下被黑客攻击后的损失,以
保证社区的去中心化。因此社区之间产生了矛盾,就出现了硬分叉之后的两条链:以太经典
(ETC)和现在的以太坊(ETH),每个链都有算力的维持,所以两条链现在都运行的很好。这个
事件实际上是以太专的创始人Vitalik Buterin通过自己的号召力,修改了(或可以说是篡
改了)全网节点的共识结果,使的已经发生的黑客的攻击行为无效。除此之外,采用POW共识
机制的区块链都会有所谓的51%攻击的问题。在比特币的白皮书中,有一段最接近对51%
攻击的定义的描述:“The system is secure as long as honest nodes collectively
control more CPU power than any cooperating group of attacker nodes.”。即,只要
诚实的计算节点在总体上比任何一个攻击群控制更多的计算能力,那么系统就是安全的。
从这句话可以推论一下,如果有一个人要篡改比特币的交易结果,一种可能的方式就是在
短时间之内控制比特币网络中的大量算力(51%),并且通过产生新的块的数量比原始数量
(从要篡改的区块至当前块的案号)多的方式使得全网接受这条更新的更条的链。
慢。且传统的区块链的全网共识机制要求每一个参与节点中都存储全量的数据。然而这种
全网共识机制实现的可信存证会遇到明显的吞吐量和存储开销的瓶颈。
易节点获得数据输入为“Hello!”,然后将“Hello!”加上目标地址,进行封装,向与目标地址
对应的节点封装后的数据,此为交易的过程。实际处理时,该交易可能包括多笔数据的存
入,也可称为多笔子交易,如输入完“Hello!”后,还可能包括“I’m Davy”“nice to meet
you”等等,上述“I’m Davy”和“nice to meet you”分别为一笔子交易。
包,生成区块。基于上述子交易的描述,所生成的区块可能包括多笔子交易。因此,在本发明
一优选实施例中,为了便于数据的传输,设定区块的存储量为1024字节。步骤S102的具体实
现方法包括:所述见证节点在见证该交易所产生的交易数据的数据量超过1024字节时,将
所述交易数据打包,生成区块。接下来见证节点再随机选择多个存储节点,将区块发送至存
储节点存储。
随机分散存储在多个第一存储节点中。
始发起交易(获得用户数据输入的节点)节点,然后第一见证节点也会另外随机选择多个第
二见证节点对该交易(生成区块并将区块发送至各个第一存储节点)的过程进行见证,生成
第二区块,并由第二见证节点再随机选择多个第二存储节点存储第二区块。
说应该是同一个方向,"无环"则指够不成闭环)。在本发明所述的DAG结构中,每个区块有多
个前序区块和多个后续区块。对于每个节点来说(如第二见证节点),上一个交易的过程的
区块(如第一区块)为其前序区块,下一个交易的过程产生的区块为其后续区块(如第二区
块)。每个节点维护自己的前序区块和后续区块,形成了可无限扩展的链式结构。
标识Nonce、数链版本、区块数、Merkle Tree树根;其中,所述区块体包括所述交易数据。
Merkle Tree树根即保存交易数据的元信息,包括生成时间、实际数据(即区块体)的Hash、
上一个区块的Hash值等等信息。
区块的实际数据算出自身的Hash值,才能实现对该区块的篡改。但是由于针对该笔交易,所
涉及的区块为指数增长的,因此,篡改者得在全网中找到针对该笔交易的所产生的所有区
块(包括第一区块、第二区块、第三区块…),并对所有区块进行篡改,就从实现上来说,这几
乎是不可能的,以此加大了交易过程中篡改的难度。参照图2.2,示出了本发明实施例的区
块组织结构图。
需求来说,所选择的见证节点为多个,各个见证节点之间进行随机存储的过程是独立的,并
不需要对交易之间的严格顺序达成共识,无需全网同步,以此保证了本发明的交易可信存
入的速度。
全文找到针对每笔交易的3个见证节点,然后针对每个区块,再找到随机选择的3个存储节
点。三三共识的设置方式更进一步加大了篡改者的篡改难度,且由于每个节点维护自身的
DAG,不需要进行全网DAG的同步,避免了针对交易调用的节点数过多,影响交易的可信存证
速度的问题,使得节点的存储开销随着节点数量与存证吞吐量的增长,保持随时间线性增
长,而不会爆炸式增长,达到存储开销与数据可靠性之间的平衡点。如图3所示,示出了本发
明实施例的见证-共识过程示意图。
所述区块头的节点将所述区块头加入到其自身的区块对应的多个前序区块和多个后序区
块中。基于上述区块内部的数据结构图,区块头包括多个前序区块的ID,见证节点签名、时
间戳、唯一标识Nonce、数链版本、区块数、 Merkle Tree树根,见证节点采用将每个区块的
区块头广播给其他节点的方式,进一步提高了篡改难度,篡改者在修改区块的同时,还得消
灭其他节点中记录的该区块的区块头记录,增加了本发明对交易数据存证的可靠性。
有区块构成有向无环图 DAG结构,因此,恶意篡改者要想篡改该笔交易,首先得找到随机存
储的见证节点和存储节点,其次,还得对记录有该交易的全部区块进行篡改,有向无环图帐
本结构配合nRW共识机制,不仅解决了大规模共享交换过程中的监管问题,还使得本发明实
施例的分布式账本的存证吞吐量随着节点数量的增加可以线性扩展。
可靠且高效的机制去检索分布式账本上的数据,如查询余额,查询交易历史以及交易的内
容。这种查询不仅仅是精确查询,还有可能是模糊查询、范围查询、多条件查询。而查询功能
不应该仅仅提供交易数据的检索,还应该在对交易数据发生分歧时,提供溯源和审计功能。
即如何处理用户的查询请求,并在分布式账本上查询满足条件的数据,将结果准确快速的
响应给用户,和数据存储同样重要。
区块链结构中。全网中的每个节点都包含有全部的交易数据,故每个节点都可以作为查询
请求的代理节点,通过对自身的数据库中检索满足条件的数据,进而响应查询请求。但比特
币从2009年的第一个创世区块至今已经产生了193GiB的数据,比特币网络上的每个全节点
都需要占用193GiB的磁盘空间,而且随着时间的推移,该数据量的大小还会不断增加。而新
型的分布式账本为了增加交易的吞吐量以及节省磁盘空间,摒弃了数据全网同步的方式,
而采用了交易数据部分随机存储的方式。即网络上的所有节点并不存放全量的数据,而只
随机存储部分交易数据。因为此种架构网络上的节点存储的并不是全量数据,所以就无法
应用比特币和以太坊的查询方法。
存放到自身的数据库中,并对外提供查询功能。但该方案只适用于节点数量比较少和TPS较
低的场景下,当节点数量和TPS 达到一定阈值后,交易的数据量就会超过代理节点的带宽
和计算能力,从而使得查询功能变得不可用,即该查询系统的架构是不可扩展的。而网络环
境和节点的在线状态又是复杂多变的,节点频繁的加入和离开不应该影响查询功能的使
用,故该查询系统应当具备一定的容错性。
询功能的使用。
可以包括以下步骤:
应的孩子节点,自身相应的孩子节点重复上述广播步骤,直至将所述查询请求广播至该P2P
网络系统上的所有节点;每个节点在收到查询的请求后,检索本地数据库,并等待其孩子节
点的结果返回,当收集完所有的孩子节点返回的数据后,做结算和去重操作,并将结果返回
给其父节点;经过层层反馈,当接收到用户查询请求的根节点收到所有孩子节点的返回结
果时,做最终的结算和去重操作,生成最终查询结果,并将最终查询结果返回给该用户。
建。而是当传递第一条消息时,随着该条消息的传播路径形成一棵P2P网络系统,再通过后
续消息的传播对该树进行优化和修复。在针对该P2P网络系统的查询方法中,本发明实施例
采用了邻居节点(邻居节点指某一节点的父节点或孩子节点)的查询请求方法,并通过树形
维护程序将该查询的请求广播给该节点的孩子节点,孩子节点再广播给自己相应的孩子节
点,重复上述步骤,利用该树形结构,广播查询的消息至网络上的所有节点。节点在收到查
询的请求后,检索本地数据库,并等待孩子节点的结果返回,在此过程中采用了“分治思
想”,将查询的所有结果的去重、验证和传输均匀地分配给网络上的所有节点。首先节点之
间构成树形结构,除根节点外,每个节点向其父节点传递查询结果,父节点接收到所有的孩
子节点返回的所有数据后,将查询结果做去重和验证,经过层层反馈,当接收到用户查询请
求的根节点收到所有孩子节点的返回结果时,做最终的结算和去重操作,生成最终查询结
果,并将最终查询结果返回给该用户。本发明实施例通过邻居节点的发散性查询方法,以及
将查询结果在返回的传输过程中进行去重和验证,可降低代理节点的负载,还能保证低延
迟,该树不仅仅能用来做查询结果回收,还可用来做查询请求的传递。
关的数据结构来存储网络上的部分节点的信息。全网上节点的所有信息被分散保存到了该
网络的所有节点上,即所有节点维护的部分信息反映了全网的拓扑结构。每个节点能根据
和其维护的节点之间的连接状态做动态的更新,来保证该节点和全网节点的连接。P2P网络
系统的构建依赖于上述的数据结构,而节点之间的连接状态和延迟是动态变化的,根据该
变化对P2P网络系统的树形结构做修复和优化,而修复和优化的过程需要定义一些额外的
数据结构。如缓存消息的相关数据结构,该数据结构可以根据消息到达的先后次序来动态
优化和修复该P2P网络系统。如何定义和使用上述数据结构来维护一棵全局的树变得+分关
键。首先,树的维护主要分为以下三个部分:
化和节点的出度优化。
开的情况下,修复该P2P网络系统,保证所有的节点能收到广播的消息并可以传递查询的结
果,并在后续的传播过程中对该树不断地修复。
的故障或连接的断开。
MsgTransferProt负责查询消息的广播和查询结果的验证传递;所述PartialView负责管理
每个节点的邻居节点,所述邻居节点包括父节点和孩子节点;其中,所述Active List和所
述Passive List位于P2P网络系统的PartialView协议中;每个节点中包括积极列表Active
List和消极列表Passive List,所述Active List分为活跃列表Eager List 和惰性列表
Lazy List;其中,所述Active List中的节点数量为固定值,所述Eager List中存放的是在
P2P网络系统上和该节点建立TCP连接的节点,用于传递消息;所述Lazy List中存放的是所
述Active List除Eager List中的剩余节点,用于传递消息的摘要或消息的ID,用于P2P网
络系统的优化和容错;所述Passive List中存放的是随机节点,用于替换Active List中断
开连接的节点,保证节点和所述P2P 网络系统中网络的连接;
响应其他尚未收到该消息的节点对该消息的请求;
器,用于向发送该消息的节点请求该消息,并修复所述P2P网络系统;
给该P2P网络系统提供新的优化的可能。
6。这些节点收到该消息后,首先检查是否已经收到了该消息,即查看ReceivedMsgMap中是
否存在当前消息。如果已经存在,将发送该消息的节点从Eager List移动到Lazy List中,
并向发送该消息的节点发送PRUNE消息。如果不存在,将该消息缓存到ReceivedMsgMap中,
并向Eager List中的所有节点发送该消息。参照图5.1,示出了P2P网络系统的第一次生成
示意图,在图5.1中,虚线表示是Lazy List中的节点,用于容错;实线表示P2P网络系统的
边,用于传递查询消息。第一次消息传输完成后的P2P网络系统如图5.2所示,一些节点的
Eager List中的节点被移除到了LazyList中,每个节点和其Eager List中节点的连接构成
该生成树的边。后续的消息只需要传给Eager List中的所有节点和发送消息的ID给Lazy
List中的所有节点。但此P2P网络系统的初始化是根据传输路径的传输速度来生成的,即传
输速度快的节点的子树节点的数量就可能比传输速度慢的节点的子树节点数要多,并没有
考虑树的平衡。
络系统的结构,影响查询的延迟和查询结果的去重和验证。其中Eager List和Lazy List实
则是和当前节点长连接的节点,Passive List 是这两个列表的候补列表,旨在随机获得网
络上的节点,从而防止网络的部分区域化,出现多个连通分量,节点之间不能通信的情况。
连接到联系节点,由联系节点将其的三个列表发送给欲加入的节点。但这样容易导致网络
的区域化,产生多个连通分量,导致所有的节点之间不能相互通信。所以,本发明实施例采
用了基于KAD(Kademlia)实现的节点加入算法,KAD算法是NewYorkUniversity的Petar
Maymounkov和David Mazieres在2002年提出的一种分布式Hash表的收敛算法。该算法通过
两个节点ID的异或距离来衡量两个节点之间关联度,通过对节点ID的有效分层,每个节点
仅需要保存网络上部分的节点信息,仅需要log(N)跳就可以找到相应的资源或定位到相应
的节点。若没有满足条件的资源和节点,也会找到和该资源或节点异或距离最近的几个资
源或节点。基于KAD的特性,本发明实施例利用KAD算法来初始化节点自己维护的邻居节点
组成的邻居节点列表。
分配一个Node ID,利用Node ID和KAD算法向该网络发起请求,查找距离该Node ID最近的
几个节点。随后,节点从这几个节点中选择部分节点来初始化自身的三个List列表。每次选
取离该节点最近的几个节点作为邻居节点,优选的,从其中选取延迟较低的节点作为
Active List,剩余节点作为PassiveList。
点加入到自身的Eager List中,以及根据自身的Passive List中的节点数n,从所述邻居节
点的Passive List中随机选择n个节点,并加入自身的Passive List中,同时对Lazy List
初始化为空,以完成初始化自身的三个List列表。进一步的,当从所述邻居节点的Eager
List中不能找到满足条件的m个节点时,所述第一节点从返回的所述邻居节点的Passive
List中选择延迟最低的d个节点,并将这d个节点加入到自身的Eager List 中。从而保证该
节点的Eager List和Passive List能初始化成指定大小的List。Lazy List初始化为空,后
续树的构建和优化的过程,会将Eager List中的节点转移到Lazy List中。
List中。
复;
经收到消息的消息 ID,通过和Lazy List中的节点建立的TCP长连接发送,告知可从该节点
获取该消息ID对应的消息; GRAFT消息是P2P网络系统的修复消息,用于向IHAVE消息的发
送节点请求尚未收到的消息,将 Lazy List的边替换为EagerList,修复该P2P网络系统;
PRUNE消息用于裁剪P2P网络系统上多余的边,防止广播风暴。
或NORMAL消息,则丢弃该消息;如果未收到所述IHAVE消息或NORMAL消息,则查看是否收到
所述IHAVE消息或NORMAL 消息的ID;如果未收到,则丢弃该消息;否则,将所述IHAVE消息的
ID或所述NORMAL消息的 ID加入到NotReceivedMsgMap中,并将所述IHAVE消息或NORMAL消
息设置为超时事件。因此,第二节点通过判断Timer超时事件,就可判断是否在超时时间内
收到其邻居节点中的第一节点发送的 IHAVE消息。超时判断时间可设置为0.1S。
则发送GRAFT消息给消息ID的发送者第一节点。目的有两个,一是向第一节点请求这个没有
收到的消息,二是将第一节点从Lazy List中移动到Eager List中,来修复该P2P网络系统。
第二节点发送了多次所述查询消息。为避免多次消息重复,占用节点内存,并影响树的平
衡,本发明实施例还提供了方法:所述第二节点在收到所述查询消息时,查看其
ReceivedMsgMap中是否存在该查询消息;当所述 ReceivedMsgMap中存在所述查询消息时,
所述第二节点将发送所述查询消息的第一节点从其Eager List中移动Lazy List中,并向
该第一节点发送删除PRUNE消息;当所述ReceivedMsgMap中不存在所述查询消息时,将所述
查询消息缓存到所述ReceivedMsgMap中,并向其Eager List中的所有节点发送所述查询消
息;所述第一节点接收所述第二节点发送的PRUNE消息,将第二节点从自己的Eager List中
删除,并把所述第二节点放入到自身的Lazy List中。
的跳数小于Eager跳数至某一个threshold时,才进行该树的修复。这样可以保证该树的稳
定性和平衡性,不会由于频繁的网络变化,导致树的结构不断变化,维护了该树的稳定性。
且不会只根据传输的延迟而不考虑跳数来对该树进行优化,维护了树的平衡性。所述第二
节点在收到所述第一节点发送的NORMAL消息时,将所述NotReceivedMsgMap中关于该
NORMAL消息的记录删除,并存储到ReceivedMsgMap中,以及时保证数据的准确性,用于后期
维护树的平衡。
List的大小的指令;
点中选择一个Lazy List的大小最小且延迟最低的第二目标节点;
成该P2P网络系统边的替补。当P2P网络系统上的连接断开或者节点不在线时,下次消息广
播会自动由Lazy List中的节点修复。为了保证Active List和Passive List节点之间的平
衡,需要从Passive List中选择相应的节点来替换Active List中的节点。从而保证整棵树
的连通性,增加容错率。
开时,第一节点首先将第二节点从自身的Eager List中移除。此时,第一节点的Active
List就少了一个元素,需要从Passive List中选择一个节点来代替当前的节点。第一节点
依次和其Passive List中的节点发起查询请求,该查询请求有两个目的,一是检查当前节
点是否在线,二是查询该节点的Lazy List的大小。最后,更新每个节点的最近访问时间,综
合延迟和该节点的Lazy List的大小综合选择一个节点。节点的Lazy List 大小较小,说明
其在P2P网络系统中的层数比较小,将其嫁接到该节点,并且选择延迟较低的节点,可以给
树的优化提供更多的可能。所以,Passive List节点选择策略就是选择Lazy List大小较
小,当最小Lazy List的节点有多个时,选择延迟最低的。HyparView原文中采用的是将
Passive List中的节点,更换成原来的Eager List中的节点,通过第一节点当前Eager
List的大小,向Passive List中的节点发送优先级不同的加入操作。原文中采用的是Eager
List和Lazy List是固定大小的策略,这样就导致了该修复的必要性。但由于本文采用的是
Eager List和Lazy List大小之和不变策略,即使第一节点当前的Eager List中仅仅包含
一个节点,那第一节点的Lazy List中的节点数目就是k-1(k是节点加入网络时,配置的出
度参数),即使当前的Eager List断开,最终也会由Lazy List中的节点修复该断掉的边。原
文中采用的方式,极大地增加了维护的成本和维护的复杂度,并不适用于本发明实施例现
在的场景。故在本发明实施例中,只需要替换Lazy List中的节点即可,即使唯一的连接断
开,也只需要等待后面几轮的懒修复即可。
供Active List节点的候补,每个节点利用Passive List来保证整个网络上的在线节点之
间是连通的。若Passive List的维护算法较差,则可能导致网络中出现多个连通分量,每个
节点只能和网络中的部分节点发起连接请求,从而导致全网上的所有节点并不能接收到查
询的消息。断开连接的节点不断地加入到Passive List中,而延迟较低和Lazy List大小较
小的节点又不断地从Passive List中移除并加入到Lazy List中,这样只能导致 Passive
List中可用的在线节点越来越少。故需要采取相应的策略来对Passive List进行相应的更
新操作。整个更新的过程遵循了HyparView原文中提出的思想,即随机化更新。但是采用的
更新策略和原文有很大的不同,采取了低代价和懒更新的策略,更加适用于本发明实施例
的维护场景。每个节点 Passive List中的节点是随机保存的当前网络上在线的节点。
HyparView原文中采用的是每隔固定的间隔,节点通过Eager List发送随机跳数(TTL)的
Shuffle消息,收到消息的节点和发送消息的节点,就Passive List中的节点做Shuffle操
作。从而保证了每个节点的Passive List中维护了全网上随机的节点。由于所有的节点在
固定的间隔都要做Shuffle操作,增加了网络上的负载,为了减少这一负载,本发明实施例
同样采用了懒加载(Lazy Load)的方式来随机获得网络上的节点。只有当Passive List 中
的在线节点数量小于某个特定的阈值时,才会发起更新操作。
节点,并将所述TTL减1,再随机发送给所述第三目标节点Eager List中的随机节点,重复上
述步骤,直到所述TTL为0;
去Passive List中当前存储的节点数。
将第二节点加入到自身的Passive List中。以此可进一步增加Passive List中的数量。
输;通过随机采样的方式维护 Passive List来为Eager List和Lazy List的更新提供支
持,可完成P2P网络系统的初始化、修复和优化算法。List列表维护的质量将影响该生成树
的稳定性、传输时延和容错率。在本发明实施例中,树的修复和优化是通过交换Active
List和Passive List数据结构中的变量来实现的。如将断开连接的节点放入Passive List
中,将延迟低、跳数少的Lazy List中的节点替换Eager List中的节点,将Passive List 中
的在线节点替换为ActiveList中断开连接的节点。如Eager List中的节点是根据接收消息
的延迟和跳数来替换成Lazy List中的节点的,这样就会导致P2P网络系统的顶层节点
Eager List尽可能满,最大化利用节点的出度,降低整棵树的高度。而底层的节点就有足够
的Lazy List来用于优化和容错。节点的Eager List是通过KAD算法随机获取的,而Lazy
List是Eager List中淘汰下来的,也是随机的,下层节点的Lazy List随机存放整棵树上的
节点,该随机性增加了整棵树的容错性。不会由于出现上层的边断裂导致下层的节点不能
收到广播消息的情况。由于控制消息是轻量的,树的优化和修复都是采用Lazy Repair的方
式,所以优化和修复过程并不会占用大量的网络带宽,整个维护的过程是低负载的。
是并不像HyparView原文中限定了Lazy List的大小,故Lazy List只是Eager List的候补。
Eager List是Lazy List用于P2P网络系统上的节点,并不需要引入单独的列表维护机制来
维护Lazy List。基于这种不同于原文HyparView 的设计方案,处于P2P网络系统上层数较
低的节点,Lazy List的大小几乎为0。而处于P2P网络系统上层数较高的节点,Lazy List的
大小相对较大。充分利用节点之间建立的TCP长连接进行消息的传输,节点的出度尽可能
大,降低了P2P网络系统的高度,保证了传输的低延迟。而处于P2P网络系统中层数较高的节
点,又有足够的Lazy List来指向P2P网络系统的其他节点,保证了该树的容错性。本发明实
施例提供的方案的容错性小于HyparView容错性,能保证故障节点的百分比是一定不会超
过 30%。
量,m为该笔交易所选择的存储节点的数量);每笔交易的存储开销也为n*m(n为该笔交易所
选择的见证节点的数量,m 为该笔交易所选择的存储节点的数量)。因此,随着节点数量的
增加,其存储能力增加、网络带宽也增加,整个系统的存证是可横向扩展的。而对于传统全
网同步的链式区块链系统,其存储开销取决于节点数量K,因此,随着节点数量的增加,存储
能力增加的同时存储开销也同步增加,这会导致随着节点数量的增加,其整体开销越来越
大,吞吐量会越来越低。
该笔交易的区块及后续区块的数量k。而在本发明实施例的图结构区块链中,对于任意给定
的篡改代价k(表示需要篡改的区块的数量),总有一个时间T,使得card(AU(UBi))>k。这表
明,本发明实施例所提的图结构区块链的防篡改能力与链式结构相当,但使用时间更少,速
度更快,且吞吐量更大。Libp2p是一个模块化的网络栈,通过将各种传输和P2P协议结合在
一起,使得开发人员很容易构建大型、健壮的P2P网络。基于libP2P,本发明实施例实现了一
个分布式的图式账本的示例。参照图8,示出了图式分布式账本系统的拓扑结构图,在每个
物理节点上,运行了一个本发明实施例的进程,具体包括:网络层逻辑:有p2p发现模块,可
以发现其他加入网络的节点;消息发送模块,可以实现节点之间的消息通讯;事件订阅模
块,可以实现节点之间的事件订阅。协议层:实现了见证过程和共识过程的见证模块和共识
模块,还有对应用层提供支撑的交易模块。应用层:以服务网关的形式对外提供记账(存证)
服务。
protobuf 3.x,基于Netty4.x+。GRPC与thrift、avro-rpc等其实在总体原理上并没有太大
的区别,简而言之GRPC并没有太多突破性的创新。)接口将需要存证的内容传到某一节点
中。在交易模块,会将相关的元信息,如发起者、接收者、发送时间、校验码等打包成一条交
易记录,并交给见证模块进行见证。见证过程如前文所述,随机寻找若干个节点,将交易记
录同步。当交易收集到一定程度的时候(如1024条交易),会进行打包产块并分发的共识过
程。
现,找到所有节点,对于某次见证或共识过程,使用随机算法,可以从所有节点中选取若干
个节点,进行见过或共识即可。当使用事件订阅机制实现时,见证过程和共识过程的随机性
会有所减弱。在发起交易前,可以用一个定时的策略进行事件订阅,如5分钟执行一次。具体
而言,可以定义两种事件,共识事件与见证事件。以见证事件为例,对于任意一个节点A,每5
分钟就会执行以下流程:1.随机选择若干节点,发送一个订阅请求给这些节点;2.这些节点
收到之后,主动向A节点订阅该节点为“见证事件”。
但是每个节点的事件订阅数量方式一是方差为0的固定节点数量;而这种方式则存在一定
的方差,方差大小取决于被订阅者的随机算法。在具体实现中,如果没有防恶意节点的需
求,只有防失效节点的话,则可采取这种策略,以提升整体系统的性能。
节点。若忽略查询结果在节点上的处理过程,那么整个查询过程是两次树的层次遍历的过
程,故查询的延迟和P2P网络系统上的最长路径有关。假设每个节点配置有相同的出度k,每
一层以pi(0
网上的所有节点并汇总所有节点返回的查询结果,故查询的时间复杂度是O(logkN)。
满足该查询条件的交易数量是n,P2P网络系统的根节点实际上接收到的交易数据量是m,则
数据的去重率为1-m/(12*n)。
进而减少P2P网络系统的根节点数据处理总量。假设每个节点的出度是k,所有的数据均匀
地分布在整个网络上,那么满足相应条件的查询数据就应该均匀地分布在P2P网络系统根
节点的所有孩子中,那么最终返回的数据量应该为k*n,故查询的去重率是1-k/12。
低。所以,应该根据不同的场景综合考虑,当查询节点的计算能力较弱时,就可以采用低出
度,损失查询延迟来降低根节点的负载。当节点的计算能力较高,且对查询延迟要求较高,
就可以采用高出度的方式,降低查询延迟从而占用根节点的部分计算能力。
服务架构来说,如搜索引擎,必须是可扩展的,来处理更多用户的查询请求以及对更多的资
源建立正确的索引。中心化的服务架构通常采用横向扩展的方式,以增加服务器的方式来
增加整体系统的处理能力。而网络的可扩展性和中心化服务器的可扩展性却有所不同,如
路由协议的可扩展性是用来应对网络规模的变化,假设网络中节点的数量是N,而路由协议
表的大小是O(log N)级别的,该路由协议就可被认为是可扩展的。如早期的P2P应用
Gnutella就存在不可扩展的问题,只能通过洪范广播的方式查找其他节点。分布式哈希表
的出现,解决了该路由协议的不可扩展问题。纯P2P系统没有任何中心化的结构,所以不需
要除了节点以外的任何其他资源,就可以无限的扩展。在时间复杂度分析中,分析出一次查
询仅仅需要log(n)跳,在P2P网络层面就可以认为该协议是可扩展的。而除了消息的路由,
仍然还有查询结果的传输和处理,在负载降低率的分析中,分析了本发明实施例的方案中,
节点的负载和节点的出度k成负相关。故可通过调节节点的出度大小,来动态降低和增加节
点的处理负载,对计算能力较高的节点可赋予较高的出度,对计算能力较低的节点赋予较
低的出度,这样可以进一步增加查询系统的可扩展性。除了上述提到的可扩展性,本发明实
施例所提供的方案还具备很强的功能可扩展性,为将来进一步实现功能更加强大的查询系
统提供了良好的基础,如更强的可扩展性和更小的开销等。
居节点中移除,并通过邻居节点选取策略来选定新的邻居节点。而新的邻居节点的选取采
用了随机化的思想,首先是请求消息跳数的随机化,其次是请求消息传输邻居节点的随机
化,再者是从passive list中选择返回结果的随机化。这里虽较难估计具体的容错比,但通
过这种随机化及时替补的方式,可较好地保证各个节点之间的连通性,避免出现孤立节点
的情况。HyparView原文中能达到80%的容错率,但是维护该结构的开销是较大的,且分布
式账本应用并没有必要牺牲大量带宽和计算能力来保证如此高的容错率。
作的平均跳数以及平均最大跳数和数据的去重率等。实验结果表明,该方案不仅仅是可扩
展的,且查询的延迟在log(N)跳数内。还具备较好的容错性,即使在节点故障率30%的情况
下,仍然能在较低的跳数下返回正确的查询结果。
证通常采用的是增加节点的数量来检验功能的可用性,故采用节点数量为参照变量,来验
证该查询系统的可扩展性。而通过节点故障率验证查询功能的可用性,可验证该查询系统
的容错性。以节点的出度作为参照量可以验证节点出度对节点的负载以及传输延迟的影
响,从而更好地优化参数来提高系统的可扩展性。
据去重率来表征,数据去重率越大,节点的负载越小,反之亦然,通过观测节点的负载可较
好地调整节点的出度,从而维持查询延迟和负载之间的平衡。由于P2P网络的异构性,节点
之间的延迟在不同的网络环境中不尽相同,为了更好地表征查询的延迟,本文使用的是查
询的跳数指标而非查询消耗的时间。而树的平衡性是保证负载均衡的关键,通过维护一棵
较为平衡的树,每个节点都可以均匀地负载查询结果的处理和传输,树的平衡性的表征是
通过叶子节点到根节点的跳数分布来进行的,如果叶子节点到根节点的跳数都集中在log
(N),则说明树是较为平衡的。
量级,最大平均跳数由于网络拓扑结构的随机性略比平均跳数大1到2跳。证明该P2P网络系
统最大限度的利用了每个节点的出度,充分降低了P2P网络系统的树高。如图9.2所示,显示
的是在不同节点数量的情况下, P2P网络系统上的叶子节点到根节点的路径长度。如节点
数量在10000的情况下,路径长度主要集中在5跳和6跳上。证明该树是较为平衡的,树的平
衡性直接决定了统计查询结果时,返回的结果信息能不能被均匀地负载。综上,验证了该方
案中的P2P网络系统的维护方案,确实是充分利用了每个节点的出度,构造了一棵最大跳数
很小的平衡树。从而保证了查询的延迟和均匀地负载接收到的查询结果。如图9.3所示,显
示了在每个节点的Active List大小为7情况下,P2P网络系统上根节点的数据去重率,可发
现随着节点数量的增加数据的去重率并没有明显的变化,在51%上下波动。这也间接证明
了数据的去重率和节点数量无关,只和P2P网络系统中节点的出度有关。通过上述实验验证
了在节点数量增加的情况下,查询的延迟(实验中用跳数来衡量)是指数增加的,保证了在
节点数量增加的情况下,查询功能的低延迟特性。通过叶子节点到根节点的跳数分布可验
证该P2P网络系统的平衡性,验证了该方案对查询请求的接收和查询结果的处理是负载均
衡的,故查询功能在节点数量增加的前提下,仍然是可用的,验证了该方案的可扩展性。
络系统的容错性。下面展示的结果是在10000个节点上,出度K的大小为7,故障率从0%-
30%情况下,平均最大跳数和平均跳数以及所有叶子节点跳数的分布。
请求广播的同时,一次性退出相应故障率的节点。因为采用此种方式,树的结构可能在前几
次修复后就完全稳定了,导致最终的实验结果过于理想,不贴近实际。故评测的指标采用修
复过程中的跳数评测,并不是稳定后的跳数评测,能最大程度的贴近真实的网络环境。
障的情况,修复过程仍然能保证该P2P网络系统较为稳定。而最大跳数的增加说明和其他节
点断开连接的节点,有一部分被嫁接到了其他的子树上,导致平均最大跳数的增加。如图
9.5所示,可以看出在故障修复的过程中,一部分到根节点只需要5跳的叶子节点和父节点
断开了连接,最终被嫁接到了其他5跳的叶子节点上,变成了6跳和极少部分的7跳节点。在
修复的过程中,叶子节点的跳数也是稳定的,主要集中在5、 6和7跳中,并没有出现跳数骤
增,导致查询延迟递增的过程。故验证了该方案的容错性,在故障率30%以下,即使在修复
的过程中,仍然具有较优的查询延迟和较平衡的树结构。如图9.6所示,根节点接收到数据
的去重率并没有随着故障率的变化而变化,仍然在51%上下波动。证明在数据均匀地分布
在网络上的情况下,数据去重率和节点的故障率无关。数据去重率反映了根节点要处理的
数据量的大小,决定了根节点的查询负载,需要根据根节点的计算能力动态地调整。
少的跳数内(5.87跳)将查询消息广播至全网,不仅查询的跳数没有明显的增加,而且跳数
的分布仍然较为均衡。验证了该方案在存在节点故障率的情况下,仍能保证查询功能的可
用性,且作为查询功能核心算法的P2P网络系统仅发生了微小的变化,验证了本方案的容错
性。
率0%,节点的出度大小为3-10的情况下,节点的出度对查询系统评测指标的影响。
度并不是P2P网络系统中所有节点的孩子节点数量,故P2P网络系统的树高稍稍高于logkN。
但是平均跳数在logkN范围内,保证该课树是较为平衡的。当节点的总出度为10时,仅仅需
要6跳就可以广播到全网,并从全网收集查询结果。当前网络环境中,每个节点和10个节点
保持长连接是非常容易实现的。假设两个节点之间的平均延迟是100ms,每个节点的TPS平
均为60t/s,节点数量是10000。那么从节点数量是10000,TPS为60万的北大数链上检索交易
数据,仅仅需要1.2s,完全在用户的接受范围内。
均最大跳数会减少,查询的延迟会降低。节点的出度越小,数据去重率越大,但是平均最大
跳数会增大,查询的延迟会增大。当节点的出度为3时,去重率高达75.19%,极大减少了根
节点的计算负载。但是相应地,传输的平均最大跳数竟有12跳之多。所以需要对二者做权
衡,当节点的计算能力较差时,可以选取小出度,虽然会增加查询过程的延迟,但会极大减
少节点的处理负载。当对查询的延迟要求较高时,且节点的计算能力较强,可以增加节点的
出度,进而降低查询的延迟。故节点的出度需要平衡节点的计算能力、查询的延迟要求和网
络环境的带宽等因素来综合决定,BDChain上的每一个节点都可以根据上述因素配置不同
的出度大小。
结果传递给根节点。所以,根节点的去重率应该只和根节点有关。如图9.9所示,实验的环境
是,网络上节点10000个,除根节点外所有节点的总出度为7,根节点的出度恒为3,节点的故
障率是0%,数据去重率和其他节点的总出度的关系。尽管除根节点之外的节点出度一直在
变化,但是数据去重率一直在75.20%上下波动,且变化幅度仅有0.01%。说明根节点的数
据去重率和其他节点的出度并无关系,仅仅和根节点的出度有关。所以根据节点的计算能
力来决定节点的总出度,可以增加和减少处理的负载。
点的出度可能会影响P2P 网络系统的结构,故需要验证在根节点固定,其他节点出度变化
的情况下,P2P网络系统的最大跳数和平均跳数。如图9.10所示,表示在上述条件下,P2P网
络系统的平均跳数和节点总出度的关系。可见,当根节点的出度固定时,P2P网络系统的平
均最大跳数和平均跳数与根节点的出度不固定时,相差甚微。故根据根节点的计算能力来
决定根节点的出度,并不会对P2P网络系统的特性造成较大的影响。通过上述实验,以节点
的出度大小作为变量,以根节点到叶子节点的跳数作为衡量查询延迟的指标并进行检测,
验证了节点的出度越大,P2P网络系统的高度越小,查询的延迟越低。但以数据去重率作为
根节点负载的指标并进行检测,验证了节点的出度越大,节点的负载也会越大。而通过变化
节点的出度和固定根节点的出度,可验证节点的负载大小只与自身的出度大小有关,与其
他节点的出度无关,故可以通过降低节点出度的方式来降低节点的负载。而就降低节点的
负载是否会影响查询的延迟,本示例做了如图9.10所代表的实验,可得出结论:变化根节点
的出度并不会大幅影响查询的延迟。所以,可以通过降低计算能力和带宽较小的节点的出
度,在不影响查询延迟的情况下,降低该节点的负载,对节点的计算能力动态地调整节点的
出度,可进一步提高本发明实施例的可扩展性,进一步验证了本发明实施例的可扩展性。
方便阐述,仅测试一个包括条件查询和范围查询的一个多条件查询请求的API。实现环境是
10台阿里云机器,节点之间的延迟在20ms至80ms之间,每个节点的最大出度是7,优化的跳
数设置为1,无节点故障。
data和signature分别是数据内容和数据签名的二进制表示,在接口返回数据时,通过
Base64编码生成了图中的内容,type是交易的类型,包括上传合约、启动合约、调用合约和
结束合约等。
2019-05-12 20:05:31 到2019-05-12 20:22:21、满足发起者的账户地址是7f18ee43-
f142-439c-527a-442171780b38,接收者的账户地址是79a3bd9f-81bc-4403-4271-
3d33e98b8ec0的所有交易。如图10.2所示,查询的延迟是66ms,满足查询条件的交易仅有1
条。
的。
询结果的数据量,仅仅是原数据量的49%。当根节点的出度为3时,仅仅是原数据量的25%,
通过将整个查询结果的处理过程均衡的负载到全网的所有节点上,极大地减少了根节点的
处理负载。在故障率对性能影响的分析实验中证明了在节点故障率30%,P2P网络系统在修
复的过程中,仍能保证全网的所有节点在平均5.87 跳就可以收到查询的消息并返回正确
的查询结果。在节点出度对性能影响的分析实验中证明了节点的出度对数据去重率的影
响,以及改变某个节点的出度并不会对该方案的评测指标有较大影响,故可以根据节点的
带宽和计算能力等综合指标来指定节点的总出度。这样既不会对查询的延迟有较大的影
响,还会降低查询过程的负载。故对节点的计算能力动态地调整节点的出度,可进一步提高
该系统的可扩展性,进一步验证了该方案的可扩展性。
示例完成了查询过程中的核心工作,即P2P网络系统的维护和查询结果的传输,为后续实现
更多类型的查询提供了可扩展的框架。
据本发明实施例,某些步骤可以采用其他顺序或者同时进行。其次,本领域技术人员也应该
知悉,说明书中所描述的实施例均属于优选实施例,所涉及的动作并不一定是本发明实施
例所必须的。
Active List和消极列表Passive List,所述Active List分为活跃列表Eager List和惰性
列表Lazy List;其中,所述Active List中的节点数量为固定值,所述Eager List中存放的
是在P2P网络系统上和该节点建立TCP连接的节点,用于传递消息;所述Lazy List中存放的
是所述Active List除Eager List中的剩余节点,用于传递消息的摘要或消息的ID,用于
P2P网络系统的优化和容错;所述Passive List中存放的是随机节点,用于替换Active
List中断开连接的节点,保证节点和所述P2P网络系统中网络的连接;所述系统包括存入装
置A和查询装置B;
将所述查询请求再广播给自身相应的孩子节点,自身相应的孩子节点重复上述广播步骤,
直至将所述查询请求广播至该P2P网络系统上的所有节点;每个节点在收到查询的请求后,
检索本地数据库,并等待其孩子节点的结果返回,当收集完所有的孩子节点返回的数据后,
做结算和去重操作,并将结果返回给其父节点;经过层层反馈,当接收到用户查询请求的根
节点收到所有孩子节点的返回结果时,做最终的结算和去重操作,生成最终查询结果,并将
最终查询结果返回给该用户;
包括消息ID;
GRAFT消息包括所述消息ID和接收所述IHAVE消息的请求;
节点从自身的Lazy List中移动到Eager List中,使所述第一节点对所述P2P网络系统进行
修复;
第一目标节点的Lazy List 的大小的指令;
的大小,从所述第一目标节点中选择一个Lazy List的大小最小且延迟最低的第二目标节
点;
行了阐述,以上实施例的说明只是用于帮助理解本发明的方法及其核心思想;同时,对于本
领域的一般技术人员,依据本发明的思想,在具体实施方式及应用范围上均会有改变之处,
综上所述,本说明书内容不应理解为对本发明的限制。