基于机器学习的可扩展HCGraph算法

文章正文
发布时间:2024-08-09 00:50

HCGraph 是Leviatom网络的核心算法。在前面的文章中,我们介绍过该算法利用Gossip 协议族构建全网信任模型。HCGraph利用类似于HashGraph的Gossip以及Gossip about Gossip协议来实现高效的信任关系传递。利用该协议,我们可以在获得一个比较完整的全局网络互信关系。

但是,在未来真实系统里百万节点级别的分布式环境中,因为受限于网络负载,就有可能会引发网络热点负载过重。如果受限于网络负载,就会影响节点达成共识的速度。

因此,我们设计了一个基于机器学习的网络链接预测的算法,来解决这个问题。此外,我们还设计了一个基于分布式的系统架构来实现它。接下来,我们详细介绍一下:

假设我们需要预测节点u到v之间的证实关系,而u到v并没有直接发起过证实。我们可以收集两个类型的图计算信息。

第一个类型,我们共收集七个维度的信息,这些信息仅与这两个节点本身与整个网络世界的关系。这其中包括,u 证实的可信节点;u 证实的不可信节点;u证实的所有节点;证实v为可信的节点;证实v为不可信的节点;所有证实v的节点;u和v的共同邻接节点的数量。

第二个类型,我们共收集16个维度的信息,这些信息取决于共识节点u和v之间的交互。根据两节点间证实关系的方向、信任关系,一共有(2*2)*(2*2)=16种关系。

结合两个类型的信息,或者仅使用其中一个类型的信息,采用机器学习的算法对部分数据进行训练,而对另一部分数据进行交互测试。

共识节点之间的证实关系是实时地存储在共识节点本地的数据结构中的,那么要实现此算法就涉及到两个问题:

1)如何获取到所有周期性的证实信息来训练机器学习模型;

2)当需要预测u和v之间的信任关系时,如何抓取到u和v的实时证实信息来进行预测。

在这里,第一个问题是批处理的计算问题,第二个问题则是在分布式系统中的实时计算问题。针对这两个问题,以及共识节点本地化存储、证实的需求,我们抽象出了三个模块:

实时异构共识图

共识节点本身及其之间的通信所组成,主要的功能便是建立起共识节点之间的证实关系,并将这些关系存储在本地的可持久化的数据结构中。

批处理机器学习

由一个Hadoop生态搭建起来的ETL系统加上构建在其上的机器学习组件组成,其采用pull模型来从各个组件中周期性的同步出共识节点的证实信息,并且以分片的方式来训练出机器学习的模型,来供后续预测的需要。

ETL :将业务系统的数据经过抽取、清洗、转换之后加载到数据仓库的过程。目的是将企业中的分散、零散、标准不统一的数据整合到一起。

弹性拉伸

一个基于Paxos的状态注册模块,当新的共识节点加入或者旧的共识节点退出的时候,会在Paxos机上注册自己的服务,这样当客户端需要进行服务的时候便能够从Paxos机中寻找到正确的路由信息来进行实时的信息获取和预测。Paxos机是整个Leviatom生态的核心基础,需要保证高可用、高性能和高一致性。

首页
评论
分享
Top