2024年7月

前面写了简单的API测试工具ApiTools,返回的json有时需要做很多转换,于是开发了这个工具。

功能包括

1、json字符串转为表格,可以直观的展示,也可以复制,并支持转换后的表格点击列头进行排序,比较方便地定位数据。

2、表格转为EXCEL,就是导出Excel文件,支持2003和2007格式,即xls和xlsx。

3、支持EXCEL转表格,即读入EXCEL文件,展示到表格中。

4、表格转为json,就是把导入的excel文件再转为json字符串

5、json转csv,就是把json字符串先转为内存中的datatable,再转为csv格式。

csv格式是tab分割。

希望这个工具能给大家带来方便,希望提出宝贵意见。

最后附上下载地址,本工具暂不开源。https://files.cnblogs.com/files/weipt/JsonTools.zip

一、报错信息

某项目最近在 SQL Loader 导数据时偶尔会报错,类似如下:

SQL loader ORA-01658 unable to creale INITIAL extent for segment in tablespace ADS5GP2P_1

这个报错的意思是,没有足够的连续空间为表或索引创建 INITIAL extent:

[oracle@node1:1 ~]$ oerr ora 1658
01658, 00000, "unable to create INITIAL extent for segment in tablespace %s"
// *Cause:  Failed to find sufficient contiguous space to allocate INITIAL
//          extent for segment being created.
// *Action: Use ALTER TABLESPACE ADD DATAFILE to add additional space to the
//          tablespace or retry with a smaller value for INITIAL

二、报错分析

数据库版本是 Oracle 11G,实际查看该表空间仍有2T多的剩余空间,根据以往经验,最大的可能是这2T多的剩余空间大多是碎片,在业务忙时无法提供足够可用的连续空间,以下做验证。
DBA_FREE_SPACE describes the free extents in all tablespaces in the database.
数据字典 DBA_FREE_SPACE 描述了所有的可用 extent 情况:

select trunc(bytes/1048576) mb, count(*)
  from dba_free_space
 where tablespace_name = 'ADS5GP2P_1'
 group by trunc(bytes/1048576)
 order by 1;
 0	2374933
 1	61526
 2	21622
 3	13995
 4	34797
 5	5133
 6	6851
 7	3687
 8	16463
 9	2883
10	1785
11	1348
12	5552
13	742
14	666
15	615
16	6029
17	326
18	300
19	398
20	2553
21	94
22	62
23	49
24	82
25	41
26	21
27	9
28	26
29	15
30	12
......

以上可见空闲的空间里有大量的碎片,可能的原因是频繁、长时间的修改、导入数据逐步导致的。这些碎片的大小达到了 2T,如下:

select tablespace_name, sum(bytes/1048576) mb
  from dba_free_space
 where trunc(bytes/1048576) < 1
 group by tablespace_name;
---
ADS5GP2P_1: 2162858.375

结论是:
虽然空闲空间很多,但是这些空闲空间大都是小于 1M 的小碎片,这些小碎片加起来达到了2T,导致可能有时没法及时分配 INITIAL extent 给应用使用,从而报错。
以下进一步确认这些碎片的具体大小:

select trunc(bytes/65536) k64, count(*)
  from dba_free_space
 where tablespace_name = 'ADS5GP2P_1'
 group by trunc(bytes/65536)
 order by 1;
 1	31756
 2	8567
 3	6803
 4	10116
 5	3230
 6	1748
 7	2027
 8	2492
 9	11143
10	4988
11	1183
12	1875
13	21457
14	43512
15	2228918
16	1251
17	151
18	152
19	230
20	177

以上可见 15*65536=960k 的 extent 达到了 2228918,合计 2T 多。
可见这些小碎片大多是 960k 的小碎片,理论上对于大多数 64k 的 INITIAL extent 是可用、不会报错的。

三、解决方案

因此最终的解决方案是,修改报错表和索引的 INITIAL extent,让他们小于多数碎片的大小,即小于 960k。这个只能在业务闲时操作,确保操作的表不要引起其他问题,比如先备份表。

之前自己写了一篇介绍TCP的一些常用的功能介绍和特征,并且用代码做了示例,最终开发了一个EasyTcp4Net的TCP工具库,其最大的特色就是使用了微软提供的高性能库中的一些数据结构来处理TCP数据。
最近辞职待业在家,也没啥事做,就利用自己写的TCP通讯库基础上开发了一个示例的聊天程序,功能包括,文本发送,图片发送,断线重连,消息发送成功确认,消息发送失败提示等。

示例

发消息给自己

image

收到消息

image

发送图片

image

消息发送中

image

重连中

image

发送失败

image

数据包结构以及拆包

定义数据包结构

数据包结构定义了每次发送一个数据的完整的数据结构,我们将包体长度定义在包头中来解决粘包和断包的问题。
数据包我们采用了简单的序列化成byte数组的方式来发送。

[StructLayout(LayoutKind.Sequential)]
public class Message<TBody> : IMsssage<TBody> where TBody : Packet
{
    //数据包包体长度 4字节
    public int BodyLength { get; private set; }
    //消息类型 4字节
    public MessageType MessageType { get; set; }
    public TBody? Body { get; set; }
    private Message<TBody> Deserialize(byte[] bodyData)
    {
        var bodyStr = System.Text.Encoding.Default.GetString(bodyData);
        Body = JsonSerializer.Deserialize<TBody>(bodyStr);

        return this;
    }

    public static Message<TBody> FromBytes(ReadOnlyMemory<byte> data)
    {
        Message<TBody> packet = new Message<TBody>();
        packet.BodyLength = BinaryPrimitives.ReadInt32BigEndian(data.Slice(0, 4).Span);
        packet.MessageType = (MessageType)BinaryPrimitives.ReadInt32BigEndian(data.Slice(4, 4).Span);
        packet.Deserialize(data.Slice(8, packet.BodyLength).Span.ToArray());

        return packet;
    }

    public byte[] Serialize()
    {
        var Length = 4 + 4;
        var bodyArray = System.Text.Encoding.Default.GetBytes(JsonSerializer.Serialize(Body));
        BodyLength = bodyArray.Length;
        Length += bodyArray.Length;
        byte[] result = new byte[Length];
        result.AddInt32(0, bodyArray.Length);
        result.AddInt32(4, (int)MessageType);
        Buffer.BlockCopy(bodyArray, 0, result, 8, bodyArray.Length);

        return result;
    }

    public TBody GetBody()
    {
        return Body;
    }
}

public interface IMsssage <out TBody> where TBody : Packet
{
    public TBody GetBody();
}

我们在服务端和客户端根据我们定义的数据结构,来调用
EasyTcp4Net
提供的固定包头来解析数据包

_easyTcpClient.SetReceiveFilter(new FixedHeaderPackageFilter(8, 0, 4, false));

文本/图片发送

我们可以定义消息基类,再拓展两个消息类,一个文本消息,一个图片消息

public class SendMessagePacket : Packet
{
    public string MessageId { get; set; } = Guid.NewGuid().ToString();
    public string From { get; set; }
    public string To { get; set; }
}

图片消息

public class SendImageMessagePacket : SendMessagePacket
{
    public byte[] Data { get; set; }
    public string FileName { get; set; }
}

文本消息

public class SendTextMessagePacket : SendMessagePacket
{
    public string Text { get; set; }
}

我们还需要在界面中增加相关的文本和图片的ViewModel
发送消息的时候,发送者可以立刻将消息添加到聊天界面,然后等待收到自己发送的消息从服务端发来的时候,根据状态判断消息是否发送成功,等待的时候可以将消息设置发送中的界面状态显示,这种发送消息逻辑和微信基本一致。

断线处理

利用
EasyTcp4Net
提供的断线的事件,可以非常方便的在服务端知道客户端突然断开了,或者在客户端知道和服务端连接断开了。

客户端

_easyTcpClient.OnDisConnected += async (obj, e) =>
{
    Title = Title + _disConnectTip;
    await ReConnectAsync();
};

主要是触发了重连的机制。

服务端

 _easyTcpServer.OnClientConnectionChanged += (obj, e) =>
 {
     if (e.Status == ConnectsionStatus.DisConnected)
     {
         _accounts.TryRemove(e.ClientSession.SessionId, out var account);
     }
 };

主要是将该用户从在线列表中移除。

总结

总体来说做一个聊天软件需要考虑的细节比较多。
示例地址:
https://github.com/BruceQiu1996/EasyChat

SSL,https(HTTP over SSL), X.509, SSL 证书 ,证书申请 /导入/签发, 等名词,想必有一定工作经验的小伙伴,一定都会略有耳闻,或者至少也听神边大神念叨过。虽然司空见惯,但是能够比较系统理清其中关系,能够从整体到局部深入浅出讲解下的人,估计至少也是十里挑一。反正没人给我讲,我只好自己梳理下。(注意本文不涉及密码学原理以及SSL协议具体细节,但具备密码学基础,会有助于愉快阅读)

起因是公司最近在搞安全加固,想起了历史原因用了很久的FTP服务,这东西众所周知是明文的,裸奔的用户名密码,被监听是分分钟的事儿。于是寻思加个密吧,搜了下发现有个FTPS( FTP over SSL),很容易联想到一个更常用的https(http over。SSL), 展开一搜还有各种 XXXX - over -  SSL。 如SMTPS,POP3S, LDAPS等,于是问题来了,SSL到底是个啥东西,为啥可以被各种over。

  • SSL的由来


我们从大家比较熟悉的http协议角度说起,HTTP这个协议(就是header,body,post get这些)是在大概1991年附近发布,其设计初衷就是用来传输显示网页内容。这协议是明文的,明文的含义——就是你阅读的网页内容以及提交的,经过的每一个网络节点都可以知道传输的具体是啥内容。我猜早期的网页既不动态,也不私密,也没有个人相册:-),所以为了简单,http协议本身并没有考虑加密机制。

后来,WWW就火了,网络时代正式来临,页面功能越来越强大,支持动态化,可以为不同用户提供不同内容,已经可以发个悄悄话,照片啥的了。这时自然就产生了加密需求。于是1994年有一个叫网景(Netscape)的公司,做浏览器的,开始琢磨怎么加密http协议传输的网页内容。琢磨着,琢磨着,就琢磨出了
SSL协议
,后来历经完善,变成了标准,改了名字 目前叫TLS,至今广泛使用。

网景已乘黄鹤去,但对互联网的发展和安全起了重要贡献。

  • SSL 协议的制定

SSL协议的制定目标是解决http传输的安全问题,目前仍在广泛应用,可见网景制定的这个协议还是比较科学的。所谓天下文章一大抄,SSL也是借鉴了前人基础,融会贯通而成。

大约1976年,大洋彼岸的大壮,提出了非对称加密,数字证书的概念。1977年,同样远在彼岸的小明,发明了实用的非对称加密RSA算法,标志着公开密钥加密的诞生(就是现在常提的公钥,私钥,非对称啥的)。

有了天才的大壮和小明,数字证书以及非对称加密的相关理论已经完备,只待应用。于是在一些安全需求较高的专用内部网络(军事,金融,企业)中,一些系统开始根据大壮和小明提供的思路,实现基于数字证书和非对称加密算法的身份认证与通信加密功能。

凡事都是先发明,再应用,再有标准(参照电池,先发明,再使用,再规定5号 ,7号电池啥规格)。基于数字证书和RSA算法的加密机制,因为缺乏标准,导致出现各系统实现间的不兼容,证书互不认可等问题。

于是1988年诞生了一个叫做X.509的标准,定义了数字证书的字段内容,比如应该有持有者的名称、公钥、有效期、序列号以及证书颁发机构(CA)的签名等。这个标准的产生,也推动了CA的标准化和普及。

X.509 标准仅定义了证书的字段内容,而另外的一些文件格式标准,则具体定义了证书文件的存储格式。如.pem .der .p12 .p7b等,这些就是我们在系统中可见的证书和私钥的存在形式。

基于以上,网景公司定义了在互联网中,客户端和服务器进行网络通信时,类似 发送ABC 表示 请求证书,发DEF ,表示协商双方都支持的密码套件的,发XYZ,表示XXX。 这样一个网络协议,
将其命名为SSL/TLS。

  • XXX over ssl

SSL(Secure Sockets Layer )为啥可以被各种over,Layer 顾名思义,SSL协议的作用主要是加解密,与具体传输数据无关,应用把数据扔给 SSL层后,细节就不太需要关心了。他自然会帮你加密好,传送到目的地,解密好,再送达应用。所以所有的应用层协议,都是可以over SSL的。如http,FTP等。

通信的过程,大致都是先建立SSL通道,证书验证好,对称密钥交换好。这个建立SSL通道的过程,概念上称为——SSL协商握手。握手完成后,后续的通信内容就都是加密的了。你应用层需要传个 GET ,POST,Header,body 之类,还是按你应用层的协议来,该咋咋滴。所以你应用层是http 那就是 http over SSL. 如果是 ftp 就是FTP over ssl。

举一反三: 如果你自己写了个聊天客户端和服务器,是否可以用你的自定义聊天协议来 LAOWANG over SSL 呢?

  • 实践

如何实践应用 XXX over SSL。

1. 向CA申请服务器端ssl证书(x.509证书)——通过上面我门可以知道,x.509证书适用于,各种的 https ftps pop3s laowangs . 以及其他依赖于x509证书的领域,如电子签章。
注意,我门有时候会说 https 证书,ssl证书,ftps证书,本质都是x509证书,习惯称为ssl证书,不要混淆。

2. 在服务器端将申请到的证书及对应私钥放置好,并配置启动SSL支持——这是ssl协议通信的基础。证书虽然都是x.509证书,但具体的证书文件可能需要格式转换,nginx倾向于使用PEM文件格式的证书(.pem)和私钥。

3. 申请客户端证书(可选)——我也是刚知道不久,原来
ssl协议是支持双向认证的
。Web浏览器模式使用的是单向认证,但在一些安全需求较高的应用,可能会需要进行双向认证,服务器可以验证客户端的证书是否有效,并且根据证书信息如持有人,决定是否可以进行连接。

4.客户端对应使用支持SSL的客户端进行通信。

ok
,写到这里拜了个拜~
*关于密码学基础,在我的其他网络安全相关文章中,有简要介绍,欢迎参考

Pregel论文

《Pregel: A System for Large-Scale Graph Processing》

上次向大家分享了论文图谱项目Awesome-Graphs的介绍文章
《论文图谱当如是:Awesome-Graphs用200篇图系统论文打个样》
,这次我们就拿图计算系统的奠基文章Pregel开篇,沿着论文图谱的主线,对图计算系统的论文内容进行解读,下篇预报Differential dataflow。

对图计算技术感兴趣的同学可以多做了解,也非常欢迎大家关注和参与论文图谱的开源项目:

提前感谢给项目点Star的小伙伴,接下来我们直接进入正文!

摘要

使用Pregel计算模型编写的程序,包含一系列的迭代。在每个迭代中,图的点可以接收上一个迭代发送的消息,也可以给其他的点发送消息,同时可以更新自身和出边的状态,甚至可以修改图的拓扑结构。这种以点为中心的计算方式可以灵活的表示大量的图算法。

1. 介绍

大规模图处理面临的挑战:

  • 图算法的内存访问局部性较差。
  • 单个点上的计算量较少。
  • 执行过程中并行度改变带来的问题。
  • 分布式计算过程的机器故障问题。

大规模图算法的常见实现方式:

  • 为特定的图定制的分布式实现【通用型差】
  • 基于现有的分布式计算平台【如MR,性能、易用性不足】
  • 使用单机图算法库【如BGL、LEDA、NetworkX、JDSL、GraphBase、FGL,限制了图的规模】
  • 使用已有的图计算系统【如Parallel BGL、CGMgraph,缺少容错机制】

Pregel计算系统的设计灵感来源于Valiant的BSP模型:

  • 计算是由一系列的迭代组成,这些迭代被称为超步(Superstep)。
  • 每次超步框架都会并行地在点上执行用户的UDF,描述了点V在超步S的行为。
  • UDF内可以读取S-1超步发送给点V的消息,并将新的消息发送给S+1超步的点。
  • UDF内可以修改点V以及其出边的状态。
  • 通常消息是沿着点的出边方向进行发送的,但也可以发送给指定ID对应的点。

2. 模型

输入

Pregel计算模型的输入是一个有向图:

  • 点使用string类型的ID进行区分,并有一个可修改的用户自定义类型value。
  • 有向边与源点关联,包含可修改的用户自定义类型value和目标点ID。

计算

Pregel计算模型运行一系列超步直到计算结束,超步之间通过全部同步点(Barrier)进行分割。每个超步中点上的计算都是并行的,当所有的点都是inactive状态且没有消息传递时,计算终止。

输出

Pregel计算模型的输出是所有点输出值的集合,通常是和输入图同构的有向图。但这不是绝对的,因为计算过程中可以对点/边进行新增和删除操作。

讨论

Pregel使用消息传递模型,而非远程读取或者其他类似共享内存的方案:

  • 消息传递具备足够的表达能力,而不必非要使用远程读取的方式。
  • 远程读取的延迟很高,使用异步+批量的消息传递方式,可以降低这个延迟。(蕴含push语义)

使用链式MR实现图算法的性能问题:

  • Pregel将点/边保存在执行计算的机器上,仅使用网络传递信息。MR的实现方式需要将图状态从一个stage转换到另一个stage,提高了通信和序列化的开销。
  • 一连串的MR作业的协调增加了图计算任务的复杂度,而使用Pregel的超步可以避免该问题。

3. API

template <typename VertexValue, typename EdgeValue, typename MessageValue>
class Vertex {
  public:
    virtual void Compute(MessageIterator* msgs) = 0;
    
    const string& vertex_id() const;
    int64 superstep() const;
    
    const VertexValue& GetValue();
    VertexValue* MutableValue();
    OutEdgeIterator GetOutEdgeIterator();
    
    void SendMessageTo(const string& dest_vertex, const MessageValue& message);
    void VoteToHalt();
};
  • Vertex:Pregel程序继承于Vertex类,模版参数对应点值、边值和消息的类型。
  • Compute:每次超步在每个点上执行的UDF。
  • GetValue:获取点的值。
  • MutableValue:修改点的值。
  • GetOutEdgeIterator:获取出边的迭代器,可以对出边的值进行读取和修改。
  • 点的值和出边是跨超步持久化的。

3.1 消息传递

  • 点可以发送任意多的消息。
  • 所有在超步S发送给点V的消息,可以在超步S+1时使用迭代器获取。
  • 消息顺序不做保证,但能保证一点会被传输且不会去重。
  • 接收消息的点不一定是邻居点,即消息不一定沿着出边发送。

3.2 连接器(Combiner)

当给点发送消息,尤其是目标点在其他的机器上时,会产生一定的开销,通过用户层面自定义Combiner可以降低这样的开销。比如发送给同一个点的消息的合并逻辑是求和,那么系统在发送消息给目标点之前就预先求和,将多个消息合并为一个消息,降低网络的和内存的开销。

3.3 聚合器(Aggregator)

Pregel的聚合器提供了一种全局通信的机制:

  • 每个超步S中的点都可以提供一个值。
  • 系统使用reduce算子将所有的值规约为一个全局值,如max、min、sum。
  • 这个全局值对超步S+1中的所有点可见。
  • 聚合器可以提供跨超步的聚合能力。

使用场景:

  • 统计特征:对点的出度求和可以计算图的边数。
  • 全局协调:超步中等待所有的点满足一定条件再继续计算;算法中选举一个点作为特殊角色。
  • 跨超步聚合:根据超步中对边的新增/删除自动维护全局边数量;Δ-stepping最短路径算法。

3.4 修改拓扑

修改冲突解决策略:

  1. 删除边优先于删除点。
  2. 删除操作优先于新增操作。
  3. 新增点优先于新增边。
  4. 用户自定义冲突策略。
  5. 最后执行compute函数。

3.5 输入输出

  • 构图与图计算分离。
  • 自定义Reader/Writer。

4. 实现

4.1 基本架构

Pregel程序执行流程:

  • 用户程序被拷贝到master和worker节点上。master用于协调worker节点,worker节点通过名字服务向master注册信息。
  • master决定图的分区,默认hash(点ID)%分区数。worker负责维护图分区的状态、执行compute函数、收发其他worker的消息。
  • master为worker分配用户输入,输入的划分和图切分是独立的。如果输入和图分片刚好在一个worker上则立即更新对应数据结构,否则shuffle到其他worker。输入加载完成后,点被初始化为active状态。
  • master指导worker执行超步,worker为每个分区启动一个线程,在active状态的点上执行compute函数,接收上个超步传递的消息。worker执行结束后,会向master汇报下次超步active的点数。
  • 超步会不断的执行,直到没有active的点以及消息为止。计算结束后,master通知worker保存图分片上的计算结果。

4.2 错误容忍

容错机制通过checkpoint方式实现:

  • 超步开始之前,master通知woker将图状态保存到持久化存储。
  • 图状态包含:点值、边值、输入消息,以及master上的aggregator的值。
  • master通过ping消息检测worker的状态,一旦失联worker计算终止,master将worker标记为failed状态。
  • master将失败的worker上对应的分区分配到其他存活的worker,其他worker从checkpoint加载图状态。
  • checkpoint可能比出错时的上次超步领先多个超步(不一定每次超步都会checkpoint)。
  • Confined Recovery会将发出的消息持久化,以节省恢复时的计算资源,但要求计算是确定的。

4.3 Worker实现

  • worker维护了图分片上每个点的状态,状态包含:当前点值、出边列表(边值+目标点)、输入消息队列、active标记。
  • 考虑性能,点active标记和输入消息队列独立存储。
  • 点/边的值只有一份,点active标记和输入消息队列有两份(当前超步和下一超步)。
  • 发送给其他worker点上的消息先buffer再异步发送,发给本地的点的消息直接存放到目标点的输入消息队列。
  • 消息被加入到输出队列或者到达输入队列时,会执行combiner函数。后一种情况并不会节省网络开销,但是会节省用于消息存储的空间(compute内蕴含combine语义)。

4.4 Master实现

  • 协调worker,在worker注册到master分配id。保存worker的id、存活状态、地址信息、分区信息等。
  • master的操作包括输入、输出、计算、保存/恢复checkpoint。
  • 维护计算过程中的统计数据和图的状态数据,如图大小、出度分布、active点数、超步的耗时和消息传输量、aggregator值等。

4.5 聚合器

  • worker先进行分片的部分聚合。
  • 全局聚合使用tree方式规约,而不是pipeline方式,提高CPU并行效率。
  • 全局聚合值在下个超步被发送给所有worker。

5. 应用

5.1 PageRank

class PageRankVertex : public Vertex<double, void, double> {
  public:
    virtual void Compute(MessageIterator* msgs) {
      if (superstep() >= 1) {
        double sum = 0;
        for (; !msgs->Done(); msgs->Next())
        sum += msgs->Value();
        *MutableValue() = 0.15 / NumVertices() + 0.85 * sum;
    }
    if (superstep() < 30) {
      const int64 n = GetOutEdgeIterator().size();
      SendMessageToAllNeighbors(GetValue() / n);
    } else {
      VoteToHalt();
    }
  }
};

5.2 最短路径

class ShortestPathVertex: public Vertex<int, int, int> {
  void Compute(MessageIterator* msgs) {
    int mindist = IsSource(vertex_id()) ? 0 : INF;
    for (; !msgs->Done(); msgs->Next())
      mindist = min(mindist, msgs->Value());
      if (mindist < GetValue()) {
        *MutableValue() = mindist;
        OutEdgeIterator iter = GetOutEdgeIterator();
        for (; !iter.Done(); iter.Next())
          SendMessageTo(iter.Target(), mindist + iter.GetValue());
    }
    VoteToHalt();
  }
};

class MinIntCombiner : public Combiner<int> {
  virtual void Combine(MessageIterator* msgs) {
    int mindist = INF;
    for (; !msgs->Done(); msgs->Next())
      mindist = min(mindist, msgs->Value());
    Output("combined_source", mindist);
  }
};

5.3 二分图匹配

计算流程:

  • 阶段0:左边集合中那些还未被匹配的顶点会发送消息给它的每个邻居请求匹配,然后会无条件的VoteToHalt。如果它没有发送消息(可能是因为它已经找到了匹配,或者没有出边),或者是所有的消息接收者都已经被匹配,该顶点就不会再变为active状态。
  • 阶段1:右边集合中那些还未被匹配的顶点随机选择它接收到的消息中的其中一个,并发送消息表示接受该请求,然后给其他请求者发送拒绝消息。然后,它也无条件的VoteToHalt。
  • 阶段2:左边集合中那些还未被匹配的顶点选择它所收到右边集合发送过来的接受请求中的其中一个,并发送一个确认消息。左边集合中那些已经匹配好的顶点永远都不会执行这个阶段,因为它们不会在阶段0发送消息。
  • 阶段3:右边集合中还未被匹配的顶点最多会收到一个确认消息。它会通知匹配顶点,然后无条件的VoteToHalt,它的工作已经完成。
  • 重复以上过程,直到所有的节点匹配完成。

5.4 半聚类


【算法实现要补充一下资料】

6. 实验

使用最短路径算法测试:

  • 点/边规模10亿:worker数50-800,计算时间174s-17.3s,16x worker加速10x。
  • worker数800:点/边规模10亿-500亿,计算时间17.3s-702s,计算时间线性增长。


总结

  • Pregel受BSP计算模型启发,采用了“think like a vertex”方式的编程API。
  • Pregel可以满足10亿规模的图计算的性能、扩展性和容错能力。
  • Pregel被设计于稀疏图上的计算,通信主要发生在边上,稠密图中的热点会导致性能问题。