Trinity论文阅读笔记

基于云存储的分布式图像引擎

Introduction

图能很好地表示各实体之间的关系,因此,在各个领域得到了广泛的应用(a) 互联网领域的应用.随着信息技术和网络技术的发展,社交网络(如Facebook、人人网)、微博(如Twitter、新浪微博、腾讯微博)等新兴服务中建立了大量的在线社会网络关系,用图表示人与人之间的关系.在社交网络中,基于图研究社区发现等问题;在微博中,通过图研究信息传播与影响力最大化等问题.在搜索引擎中,计算一个网页的PageRank得分等.(b) 自然科学领域的应用.图可以用来在化学分子式中查找分子,在蛋白质网络中查找化合物,在DNA中查找特定序列等.(c) 交通领域的应用.图可用来在动态网络交通中查找最短路径。其他的应用,如疾病爆发路径的预测与科技文献的引用关系等.图数据虽然结构复杂,处理困难,但是它有很好的表现力,因此得到了各领域的广泛应用.随着图数据处理中所面临的各种挑战被不断地解决,图数据处理将有更好的应用前景.

（图算法的计算是数据驱动的，随机访问的速度要求高。尽管近年来disk技术不断突破，但是也无法满足图计算所需要的随机访问要求。）

对海量图形数据的处理有各种各样的需求，简单分为两类：1.在线查询处理：需要低延迟2.离线图行分析：需要高吞吐。比如，在社交网络中确定两个人是否有联系，属于第一类，但是计算pagerank属于第二类。此类问题有很多，他们都是需要在线查询和离线分析。

现有的代表性图形系统，Neo4j和HyperGraphDB重点支持的是图形数据的在线事务处理（OLPT），他们不处理图形分布式处理，对图形的大小有局限，并且单机器没有足够的计算能力，web-Scale的图形处理很难掌控。Mapreduce、Pregel、GraphLab，离线平台，具有高吞吐特性，可是不支持在线查询，他们都采用以顶点为中心的计算，尽管像Pagerank和最短路径查询以此解决可以，但是有相当一部分复杂的图形计算如multi-level图形划分不能以此很好解决。

（图计算有几个特性，数据访问到计算的高效（IO intensive）,随机数据访问的高需求，特别是在在线查询时（eg..）离线）

Trinity，是微软推出的一款建立在分布式云存储上的计算平台,可以提供高度并行查询处理、事务记录、一致性控制等功能.主要使用内存存储,磁盘仅作为备份存储.

作为一个存储基础设施，他组织多台机器的内存成为全局的分布式存储地址空间，以此支持大量图形。支持on、off啊，用户友好的图形模型，和面向数据的操作。

（实时查询应用：基于内存和存储器基础架构实现了一个快速图形探索的能力；离线分析平台：通过底层向外扩展的分布式架构实现并行性。）

Trinity系统由多个组件组成，通过网络通信。3个部分，slave：计算包括从其他部件收集信息和传递信息，可以存储数据并处理；proxy：只处理消息，不存储，是client和slave的中间层。例如，   client：用户与Trinity集群交互，与Trinity library链接。

Memory cloud 是分布式键值存储，由内存存储模块和信息传递框架支持。内存存储模块管理内存并提供并发控制的机制，网络通信模块提供有效、单边、机器对机器消息传递架构。TSL为图形建模和数据存储搭建连接。

2^p个memory trunk组成，存在一台机器里，比机器总数大，也就是说每台机器有多个memory trunk。划分为多个trunk的原因，1,是trunk级别并行性可以不需要任何locking的overhead；2.一个单一的庞大hash table的性能不理想，因为很可能hash冲突。同时，为了支持容错，这些trunk在TFS中备份。因为云存储是分布式的，我们不能通过物理地址定位键值对，Trinity用的是hashing机制，为了定位已给key的值，1.识别存储了键值对的机器是个哪个2.定位在trunk里。例如~

Data model

1）modeling graph：图由节点和边组成。图并不只是拓扑，因为边和节点的携带大量信息。而图形包括遍历，所以关系型数据库不适合处理图形数据。为了在键值存储上建立图形，我们用cell实现图中的节点，对于无向图，cell里面包含cellId表示邻居，对于有向图，cell有两套cellId，出入各一。其他和边相关的数据用cellID存储即可。

2）TSL：为了数据和网络通信模型。因为图有多种多样的特性，并且图上的分布式算法有各种通信模式，面对这些多样性，TSL极易用。1,2,3TQL

例子，cell struct 是模型最基本的元素，里面可以装有任意数量的原生数据类型、数据容器类型、其他用户自定义结构。simpleEdge（cellId表示），structEdge（独立的cell），hyperStruct（hyperEdges）。除了数据建模，还有网络通信建模，一方面图算法拥有各种网络通信模式（因为是数据驱动型，数据是分布式的），另一方面基于顶点计算和其他算法需要大量数据收和发，如果系统不自动打包好数据成一种简单的传递，那么两台机器间的传输代价会相当大，第三，图算法需要固定的消息传输机制，MPI框架在分布式图形应用中有缺陷：适合双边批量同步通信，需要改写成有效异步、细粒度的传输很麻烦。TSL提供了直观的表达方式。

3）Object-oriented cell manipulation：比较，blob更好。尽管blob存储很经济，不需要序列化反序列化的overhead，也可以让对象在全局中有可达地址便于查找，但是blob不够用户友好，我们并不知道面向对象的接口，也需要知道memory 的布局，编程带来困难。解决这个，Trinity引入了一个机制（cell accessor机制）。实际上是数据映射，把数据结构中的声明映射到blob具体位置，通过映射，没有拷贝的overhead。

 

Graph computation paradigm

1）遍历：用index搜索：检查3跳之内的邻居中有没有叫david的，但是网络规模这个规模太大；Trinity利用基于memory图搜索的特性解决这个问题。比如，部署八台机器的集群，图由8亿节点，1040亿条边，平均每个节点有130条边，研究发现搜索节点中3跳的邻居平均需100毫秒，也即是说130+130^2+130^3=220万节点，需要零点几秒。

2）在线查询的新范例

3）顶点为中心的离线查询

跟pregel一样，Trinity提供顶点为中心的计算模型。而pregel在每个superstep中，一个点接受任何点，也发送给任何点；Trinity只接受和发送给固定的一些点。为什么这样？1.许多算法值需要与邻居节点打交道，2.提供优化机会，因为交流范围是固定的一些点，通信模式可通过反复实验预测并优化。据了解，亿节点图形划分在一般的图平台上还未解决，Trinity 在memory cloud上部署图，不受计算模型的限制使用任何图算法、计算模型。

4）message passing optimization

基于顶点计算中，在job上的顶点工作前，需要收到所有他需要的消息，一种简单方法是等着所有消息到，那么本地机器需要从远程顶点清掉所有消息？但是消息量太大，需要把他buffer到硬盘上，在硬盘上再随机读，这样代价很大。另一种方法，把job直接放在本地顶点上运行，当本地顶点准备运行job，我们获得顶点的远程消息后立即运行，但是系统没有那么多空间，需要丢掉一部分，比如x上的job要运行，我们需要u，v的信息，后来y也要u，v，重复多次发送，网络容量的浪费。Trinity中，在本地机器上，把远程顶点划分2类，一是包含hub顶点，也就度数大的点并且与大部分本地顶点有联系，剩下的是一类。

5）离线分析的心范例

可以在单一的机器上进行图计算然后再收集结果，提取出整个图结果，或者可以推测出整个图结果？这个新范例有突破网络通信瓶颈的潜力，如果一个图划分到10台机器，每台机器10%的节点和边的信息，如果一个图随机划分那我们就推测结果。试验中，找到landmark点，由他们在大图中找两点最短路径，X轴表示我们使用的landmark顶点总数，Y轴表示估算准确度。最好的方法是用global betw最高的点，最差的是简单用有最多度的点，我们用的本地最多的，因为找到global这些点就需要比我们的方法更高的代价。

 

Implementation

1）环形内存管理

有限空间内管理上亿的不同大小的键值对是个挑战，以前的方法用mem bucket很浪费，因为键值对间有mem gap。Trinity采用环形内存管理机制避免大量键值对的mem gap，当我们初始化一个mem trunk，我们保留2GB的虚存地址空间，新的键值对顺序的添加到commitied memory区域后面， append head指针指向下一个空闲的mem byte？内存空间就被committed tail 和append head间的占满。当我们需要新增一个键值对，在commited mem没有满的情况下，我们从append head后面分配一个区域，如果满了，我们分配新的mem pages和增长commited head。这样，就有效率多了，通常我们只advance append head。

收缩或者扩大键值对size可能会产生mem gap，采用反碎化程序，他扫描commited mem区域，把键值对搬向append head。所有的就搬到trunk 头部，一直这样搬直到空间占满。

对于键值对长度一直变化，导致overhead大，我们采取短生命的内存保留机制，比如，现在这个键值对需要16byte，我们就分配32byte，但是这样利于率比较低，两段

没有被用的保存的内存在下次反碎化后释放，一方面我们减少了内存的变动，另一方面通过反碎化，未被用的内存是不是被清理减小运行的内存的overhead。

Fault tolerance

1）共享地址表维护

Trinity在主机器上维护一份地址表，给TFS上复制一份，采用心跳信息主动监测机器fail，还有，如果一个机器A读取B数据失败，A告知主机器，A等待地址表更新完成后，再次读。如果确认一个机器fail，主机器启动恢复，重新加载失败的机器数据给到其他机器上，更新地址表后再广播。如果主机器fail，重新选举。

2）故障修复

对于基于BSP同步计算，在每个超步上设检查点，同时这些检查点也写在系统文件里为了以后的故障恢复；对于异步计算，因为异步模式下检查点不能简单产生，用“定期中断”的机制产生快照。

 

Evaluation

图形遍历

对比：Facebook在开发图谱搜索(Graph Search)服务时，选择采用了Giraph

 

Trinity有以下4个特点.

(a) 数据模型是超图:超图中,一条边可以连接任意数目的图顶点.此模型中图的边称为超边.基于这种特点,超图比简单图的适用性更强,保留的信息更多;

(b) 并发性:Trinity可以配置在一台或上百台计算机上.Trinity提供了一个图分割机制,由一个64位的唯一标识UID确定各结点的位置,利用散列方式映射到相应的机器上,以尽量减少延迟,如图 8所示.Trinity可以并发执行PageRank、最短路径查询、频繁子图挖掘以及随机游走等操作;

(c) 具有数据库的一些特点:Trinity是一个基于内存的图数据库,有丰富的数据库特点,如:在线高度并行查询处理、ACI交易支持、并发控制以及一致性维护等;

(d) 支持批处理:Trinity支持大型在线查询和离线批处理,并且支持同步和不同步批处理计算.相比之下,Pregel只支持在线查询处理,批处理必须是严格的同步计算.