论文阅读: TAO：Facebook的社交图谱的分布式数据存储(一)开启掘金成长之旅！这是我参与「掘金日新计划 · 12

开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第15天，点击查看活动详情

论文阅读: TAO：Facebook的社交图谱的分布式数据存储(一)

社交网络服务需要一种全新的存储模型，例如下图中，Alice和Bob一起在金门大桥， Cathy发表评论，David喜欢了这条post。可以抽象出下图b的模型。本文比较难读，如何你没有之前看过Facebook此前的架构，memcached@Facebook,为此，下文我也补充描述了其Cache aside的模式。论文地址www.usenix.org/system/file…

在TAO之前，Facebook的网络服务器直接使用MySQL来读取或写入社交图，并积极使用memcache作为aside缓存。TAO直接实现了一个图的抽象，使其能够避免look-aside缓存架构的一些基本缺陷。TAO继续使用MySQL进行持久化存储，但对数据库的访问进行调解，并使用自己的图感知缓存。

如上图所示，Cache Aside 模式中，业务应用方对于写，是更新 DB 后，直接将 key 从 cache 中删除，然后由 DB 驱动缓存数据的更新；而对于读，是先读 cache，如果 cache 没有，则读 DB，同时将从 DB 中读取的数据回写到 cache。这也即是论文提到的，缓存不能良好感知数据变化，因为更新缓存的策略通常是：

业务端处理所有数据访问细节，同时利用 Lazy 计算的思想，更新 DB 后，直接删除 cache 并通过 DB 更新，确保数据以 DB 结果为准，则可以大幅降低 cache 和 DB 中数据不一致的概率。

Facebook一开始是使用memcached +mysql的Cache-Aside模式，现在，显然他们对缓存的一致性，特别是跨区（region）的一致性提出了更高的追求，也即是本文的TAO.

TAO作为一个单一的地理分布实例部署在Facebook。它有一个最小的API，并明确倾向于可用性和每台机器的效率，而不是强一致性；它的创新之处在于其Scale能力。TAO可以在一个多PB的变化数据集上维持每秒10亿次的读取。

本文有三个贡献。我们在（第2节）描述了工作动机，并描述了（第7节）一项具有挑战性的工作负载：对一个不断变化的图的高效和可用的最多读的访问。我们描述了objects和associations，一个数据模型和API，我们用它来访问图（第3节）。最后，我们详细介绍了TAO，一个实现这个API的地理分布式系统（第4-6节），并评估了它在我们的工作负载上的性能（第8节)。

2.背景介绍

一个单一的Facebook页面可以从社交图谱中聚集和过滤数百个项目。我们为每个用户提供为他们量身定做的内容，并通过考虑到当前浏览者的隐私检查来过滤每个项目。这种极端的定制化使得在创建内容时执行大多数聚合和过滤是不可行的；

每个user的读都是定制的，所以需要读扩散，而且在读的时候进行过滤。使用pull模式，而不是推模式。

相反，我们解决了数据的依赖性，并在每次查看内容时检查隐私。我们尽可能地拉社交图谱，而不是推送它。这种实施策略对图数据存储提出了极高的读取要求；它必须是高效的、高可用的，并能可扩展到高query率。

2.1 从Memcache提供图服务

Facebook最初是通过将社交图谱存储在MySQL中，从PHP中查询，并将结果缓存在memcache中。这种lookaside缓存架构很适合Facebook的快速迭代周期，因为所有的数据映射和缓存验证的计算都在频繁部署的客户端代码中。随着时间的推移，一个PHP抽象被开发出来，允许开发人员读写图中的objects（节点）和associations（边），对于适合该模型的数据类型，直接访问MySQL的方式被取消。

TAO是我们构建的一个服务，直接实现了objects和associations模型。我们的动机来自于PHP API中的封装失败，来自于从非PHP服务中轻松访问图的机会，以及来自于lookaside缓存架构的几个基本问题。

低效的edge lists。 键值缓存对于edge lists来说不是一个很好的语义匹配；查询必须总是获取整个edge lists，而对单个edge的改变需要重新加载整个列表。LOOK-ASIDE缓存中的基本列表支持只能解决第一个问题；需要更复杂的东西来协调缓存列表的并发增量更新。

分布式控制逻辑。 在一个lookaside缓存结构中，控制逻辑是在客户机上运行的，而客户机之间并不互相通信。这就增加了故障模式的数量，并使其难以避免惊群效应。Nishtala等人对这些问题进行了深入的讨论，并提出了租约模式，一个通用的解决方案[21]。对于objects和associations，固定的API允许我们将控制逻辑移到缓存本身，在那里问题可以得到更有效的解决。

昂贵的先读后写一致性。 Facebook对MySQL使用异步的主/从复制，这给使用复制的数据中心的缓存带来了问题。写被转发到Master，但在它们反映到本地副本之前会经过一些时间。Nishtala等人的远程标记[21]跟踪已知过期的键，将这些键的读取转发给主区域。通过将数据模型限制为objects和associations，我们可以在写入时更新副本的缓存，然后使用图语义来解释来自并发更新的缓存维护信息。这就为所有共享缓存的客户提供了（在没有多重故障的情况下）读写一致性，而不需要区域间的通信。

像看连续剧一样，看懂上面的文章，我们需要先了解Facebook memcached架构。社交网络其实不需要强一致性读写，而是更需要写后读一致性。下文两张图是上文讨论的早期架构，在slave region 读时，写后读一致性丧失，这给用户带来了困扰（我刚发的post，刷新后居然没有？！）

2.2 TAO的目标

TAO提供对多个地区的数据中心中不断变化的图的节点和边的基本访问。它对读取进行了大量的优化，并明确倾向于效率和可用性而不是一致性。

像TAO这样的系统可能对任何需要从高度互联的数据中有效地生成细粒度的定制内容的应用域都很有用。该应用不应该期望数据是在普通情况下是陈旧的，但应该能够容忍陈旧的数据。许多社交网络（应用）都符合这个类型。

3 TAO数据模型和API

Facebook关注的是人、行动和关系。我们将这些实体和联系建模为图中的节点和边。这种表示方法非常灵活；它直接模拟现实生活中的objects，也可用于存储应用程序的内部特定实现数据。TAO的目标不是支持一套完整的图查询，而是提供足够的表达能力来满足大多数应用程序的需求，同时允许可扩展和高效的实现。

考虑一下图1a中的社交网络例子，在这个例子中，Alice用她的手机记录了她和Bob对一个著名地标的访问。她在金门大桥上'签到'，并'标记'了鲍勃，表示他和她在一起。凯西添加了一条评论，大卫已经'喜欢'。社交图谱包括用户（Alice、Bob、Cathy和David），他们的关系，他们的行为（签到、评论和喜欢），以及一个物理位置（金门大桥）。

Facebook的应用服务器将查询这个事件的底层节点和边，每次它都会被重新读取。细致的隐私控制意味着每个用户可能会看到不同的签到视图：编码活动的单个节点和边可以重复用于所有这些视图，但聚合的内容和隐私检查的结果不能。

3.1 objects和associations

TAO objects是类型化的节点，TAO associations是objects之间类型化的有向边。objects由一个64位的整数（id）来识别，该整数在所有objects中都是唯一的，与objects类型（type）无关。associations由源objects（id1）、associations类型（type）和目标objects（id2）识别。任何两个objects之间最多只能存在一个给定类型的associations。objects和associations都可以包含作为键值对的数据。每个类型的模式列出了可能的键、值类型和默认值。每个associations都有一个32位的时间字段，它在查询中起着核心作用。（时间字段实际上是一个通用的应用程序分配的整数。）

图1b显示了TAO对象和associations是如何编码这个例子的，为了清晰起见，省略了一些数据和时间。这个例子中的用户由objects表示，签到、地标和Cathy的评论也是如此。associations捕捉用户的友谊，签到和评论的作者，以及签到和其位置及评论之间的联系。

action 可以被编码为objects或associations。Cathy的评论和David的 "喜欢 "都代表了用户采取的action，但只有评论会产生一个新objects。associations自然地模拟那些最多只能发生一次或记录状态转换的动作，如接受事件邀请，而可重复的动作最好表示为objects。

尽管associations是有方向的，但associations与逆向边紧密相连是很常见的。在这个例子中，所有的associations都有一个逆边，除了COMMENT类型的链接。这里不需要逆向边，因为应用程序不需要从评论到CHECKIN对象的跟踪。一旦知道checkin的id，呈现图1a只需要重新遍历出站associations。然而，发现checkin对象需要入站边，或者一个id被存储在另一个Facebook系统中。

objects和associations类型的模式只描述实例中包含的数据。它们没有对可以连接到特定节点类型的边缘类型或可以终止一个边缘类型的节点类型施加任何限制。例如，在图1中，相同的a类型被用来表示check-in对象和评论objects的authorship。允许自边缘。

3.2 对象API

TAO的对象API提供了分配新objects和ID的操作，以及检索、更新或删除与ID相关的objects的操作。一个值得注意的遗漏是比较和设置功能，TAO的最终一致性语义大大降低了它的效用。更新操作可以应用于字段的一个子集。

3.3 Association API

社交图中的许多边是双向的，例如对称的，如例子中的朋友关系，或不对称的，如AUTHORED和AU-THORED BY。双向的边被建模为两个独立的associations。TAO通过允许将associations类型与逆类型配置在一起，提供了对保持associations与逆类型同步的支持。对于这样的associations，创建、更新和删除都会自动与反向associations的操作相联系。对称的双向类型是它们自己的逆类型。associations的写入操作是：

3.4 Association查询API

任何TAO关联查询的起点都是一个起始objects和一个associations类型。这是搜索关于特定objects的特定类型信息的自然结果。考虑图1中的例子。为了显示CHECKIN对象，应用程序需要列举所有标记的用户和最近添加的评论。

社交图的一个特点是，大部分数据都是旧的，但许多查询是针对最新的子集。每当一个应用程序专注于最近的项目时，就会出现这种创建时间的局部性。如果图1中的Alice是一个著名的名人，那么她的签到可能有成千上万的评论，但默认情况下，只有最近的评论会被呈现。

TAO的associations查询是围绕associations列表组织的。我们将associations列表定义为具有特定id1和type的所有associations的列表，按照时间域降序排列。

例如，列表(i, COMMENT)中有该例子关于i的评论的边缘，最新的在前。TAO对association 的查询，

TAO对用于associations查询的实际限制强制执行每个类型的上限（通常是6000）。为了列举一个较长的associations列表的元素，客户必须发出多个查询，使用pos或high来指定一个起始点。

对于图1所示的例子，我们可以将一些可能的查询映射到TAO API上，如下所示：

"关于爱丽丝签到的50条最新评论" =>assoc_range(632, COMMENT, 0, 50) "在GG桥有多少人check-in？" =>assoc_count (534, CHECKIN)

网址：论文阅读: TAO：Facebook的社交图谱的分布式数据存储(一)开启掘金成长之旅！这是我参与「掘金日新计划 · 12 https://mxgxt.com/news/view/214703

相关内容

基于数据挖掘的社交网络分析与研究
网络社交媒体数据挖掘与情感分析
[参考]基于数据挖掘的校园社交网络用户行为分析
基于社交媒体地理数据挖掘的游客时空行为特征分析
社交网络分析：数据挖掘的新方向1.背景介绍 社交网络分析（Social Network Analysis，SNA）是一种
微博社交网络数据挖掘和用户权重分析.doc
移动互联网行业APP四月数据分析：泛娱乐类增长迅猛，头条系社交之路坎坷.docx
Facebook数据挖掘：探索社交网络的深度
星环科技知识图谱落地实践 助力金融行业业务创新
百度天量数据挖掘明星关系，极客都是好娱记

随便看看