正式定档!QCon 北京站改期为2024年4月11-13日,地点:北京·国测国际会议会展中心 >>> 了解详情
写点什么

Facebook 的分布式图查询引擎:Dragon

  • 2016-03-27
  • 本文字数:3097 字

    阅读完需:约 10 分钟

当每次访问 Facebook 时,你会看到从社交图中获得的成百上千的关系信息:不仅仅可以收到你朋友的发帖、图片和私信,也能收到“赞”、评论等。并且,这些信息是不断的变化的、不能事先计算好的,每秒钟都有百万次的写入和亿万次的读取。对于每个人来说,他/她们的交互信息都是实时的。

社交图谱是由顶点和边或者对象和关系组成(这里对象和关系是 Facebook 公司的叫法,其实对象就代表顶点,关系就代表边),带有一系列的属性。典型的图关系查询始于一个顶点,并给出某类限定条件查询出所有的边信息。例如,把你自己作为一个点,查询你所有的朋友信息,并按成为朋友的时间来排序。

Facebook 查询社交图谱最早是基于 memcached 和 MySQL,后面自己开发了一个分布式数据库TAO (TAO 适合单跳(single hop)大批量查询)。自从Facebook 采用TAO 后,Facebook 的用户量显著的提升,而且许多内容的交互度(engagement)也非常高。Facebook 的发帖有的收到亿万次的点赞,尽管几分钟的直播视频也获得成百上千的评论,评论有各种语言的,这让显示跟每个人的相关信息有了很大的难度。大部分情况TAO 可以解决,但需要新增加对大批量多跳(multi hop)的优化,这时候Dragon 应运而生。

Dragon,一个分布式图谱查询引擎,是支撑 Facebook 巨规模社交图谱的坚固基础,擅长对复杂图的查询。Dragon 可以实时监控社交图谱模型(对象和关系)的更新,并创建索引来提高攫取、过滤和重排序数据的效率。使用 Dragon 可以减少网络数据的传输,低延迟和不抢占其它机器的 CPU。

索引技术

假设 Alice 有上千个 Facebook 好友,她说英语和西班牙语,在 Facebook 上关注夏奇拉(Shakira,著名歌手)。当 Alice 访问夏奇拉的 Facebook 主页,会显示一句话“您的朋友 Bob 和 Charlie,以及其他 1.04 亿人关注这个页面”。如果有一个页面有成百上千的评论,会在顶部显示 Alice 所会语言的评论。

分布式数据库 TAO 能一次攫取成千的关系数据,这对大部分情况下的查询都可以,但对大数据量的查询时会产生延迟。当 Alice 浏览夏奇拉的主页,Facebook 的并发系统会在 RAM 中缓存评论的子集,并以时间戳(ts)排序,过滤上千的评论区找到相关语言的评论并重排序

图 1:使用 Dragon 前的评论存储和使用 Dragon 的索引存储

使用 Dragon,会指定索引并通过感兴趣的属性进行过滤。当一个图谱第一次查询命中,Dragon 会回调 TAO 数据库设置初始值到 RocksDB (一个高效的嵌入式 Key/Value 持久数据库) 持久化存储。Dragon 会存储最近查询的数据或者频繁查询的数据,下推程序到存储层,这样查询到效率会更高。举例,当 Alice 浏览夏奇拉的主页,Facebook 会计算一个 key:并直接寻找感兴趣的发帖;也可以做更复杂的排序并持久化到 RocksDB,以减少查询到时间。

而另外一些 Facebook 上的人并不会出现一篇发帖有大数据量的评论,他 / 她们许多人会上传大量的图片。一个常规的图片上传到 Facebook 会存储 20 条边到 MySQL 里并通过 TAO 缓存到 RAM 中。这些边可能包含一些属性(比如,上传图片的人、上传图片的地点以及图片是否打标签等)信息,大部分情况是读取数据,因此可以在写入的同时进行读操作。边的数据需要持久化存储,并且数据大小六年增长了 20x 倍;大约有一大半的数据是存储边的属性数据,只有一小部分是描述两个实体之间的关系(比如,Alice -> [uploaded] -> PhotoID 和 PhotoID -> [uploaded by] -> Alice)的。

使用 Dragon,只需要写入主要的边关系,然后创建基于方向的索引。索引加速读取,但同时会减缓写入数据,因为在写入数据的同时得创建对应的索引数据,所以 Dragon 只创建有意义的索引。比如,一个只有 10 个评论的发帖不需要创建索引,因为其用分布式数据库 TAO 就很方便的扫描所有数据。结合部分索引技术和丰富的支持过滤、排序操作的查询语言可以索引一个 150x 倍数据量但 90% 的查询会在缓存中命中。

社会化倒排索引

人们一般经常查询朋友的基本信息(比如,姓名和生日);这些数据读的频率远大于写入。复制 Alice 的基本信息到所有主机,当查询朋友的名字时仅仅需要访问一台主机即可,这也得平衡数据的一致性和可用性。索引加速读取,同时也减慢写入。每次写入都得复制到所有的主机上,并且有可能写入失败。

倒排索引在信息检索方面是一个主流的技术。当 Alice 关注 Shakira,Facebook 存储在代表 Alice 的主机有两条边(Alice -> [likes] -> Shakira 和 Shakira -> [liked by] Alice)。我们得到的是一个分布式倒排索引,因为 Shakira 的关注者不限于一台主机。查询一个索引需要访问集群上所有的主机,这显然增加了延迟和查询的代价。

Dragon 的独特实现在于这些索引存储是基于查询模式的深度解析,而不是随机共享

图 2 :朋友关系和主页关注存储在分布式数据库 TAO。每个框代表一台主机

图 3:搜索引擎里常用的倒排索引。每台主机存储一部分对象 IDs,比如[n*100,n + 1 * 100]

如果你看你好友的关系图谱以及他/她们自己的好友的图谱,你会发现一些清晰的规律。对大部分人来说,社交图谱包含对社交圈子包括家庭、合作者或者高中同学。并且那些有相同朋友圈的朋友高度的相似性。如果 Alice、Bob 和 Charlie 在一个公司工作,Bob 和 Charlie 也是朋友,并且有许多成年人朋友,Facebook 公司的算法会试图把他们归到一台主机上。

图 4: 社交化倒排索引。Alice 朋友圈在同一台主机上。

Facebook 完成这些算法是针对人,但也同样对图谱中其他类型的对象适用。早期的索引减少读取 30% 的设备块和约 7% 的 CPU 使用,早期版本的 Dragon 未使用倒排索引。

Dragon 主要有两个优点:图谱中一个对象有唯一的索引,并共享存储在类似 MySQL 和 TAO 的数据库;第二个优点是朋友关系边的查询,这步有一个聚合层和更新服务来处理数据重新分布,同时依赖于分布式日志和至少处理一次的语法。

朋友关系、关注和评论是 Facebook 社交图谱中最常见的边。通过离线图谱分解技术来提升数据的本地性,最初的做法主要是通过“ balanced partitioning of the social graph ”基于好友关系边来做离线计算,并且随着扇出优化技术的发展,可以达到低于 3x 的扇出,相对于随机共享服务技术减少了平均延迟,见图 5。

图 5: 延迟和扇出关系图

这个算法机遇和挑战并存,查询时间和好友数并不是线性关系,所以可以高效的查询大批量数据,但查询的总时间遵循“最短木桶”效应,取决于最慢的查询操作,所以如果有某一台机器查询时间超过 100ms,尽管其他机器的查询时间大约 10ms,那也被视为高延迟。通过采用多核机器,尽可能的让 CPU 并行处理查询,这样对大数据量的查询也可以限制在一个合理的延迟范围内。

原生的函数式编程。

Dragon 支持函数式编程,在图谱上过滤/排序某个边。

(->> (friends) (assoc $friends) (filter (> age 20)) (count))列 1: 计算 Alice 朋友的好友年龄大于 20 岁的数量

复制代码
(->> (groups)
(->> (assoc count $offset))

列 2: 计算所有我的关注的组,并按组成员数排序,显示指定的条数。 Dragon 支持使用 Lua/JavaScript 语言编写用户自定义函数(UDF),可实现对复杂的字符串操作和正则的支持。

总结

Dragon 是高吞吐量、Key/Value 存储、实时更新和持久化的社交图谱查询引擎,支持数据一致性和高可用性。它采用多项优化技术存储,提高数据本地性,执行查询时间在 1ms 或者 2ms 左右。

Dragon 可以让你的应用更多的去关注业务逻辑、信息安全、数据质量校验和有深度的数据排序优化,而不是耗费太多的时间在迭代计算图谱数据。


感谢杜小芳对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作,请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博( @InfoQ @丁晓昀),微信(微信号: InfoQChina )关注我们。

2016-03-27 22:133630
用户头像

发布了 43 篇内容, 共 27.5 次阅读, 收获喜欢 7 次。

关注

评论

发布
暂无评论
发现更多内容

原型模式

卢卡多多

28天写作 12月日更 原型模式

大系统中的线下团队

张老蔫

28天写作

模块二作业——微信朋友圈高性能复杂度分析

木几丶

「架构实战营」

模块三作业

Vincent

「架构实战营」

如何把新用户转化为活跃用户

石云升

AARRR 产品思维 28天写作 产品增长 12月日更

在线JSON转BigQuery工具

入门小站

工具

Volatile 初探和 Java 内存模型

悟空聊架构

SpringCloud 28天写作 passjava 悟空聊架构 12月日更

大神级插件ScriptRunner案例分享

跟YY哥学Jira

Jira automation ScriptRunner

49 K8S之Envoy代理程序

穿过生命散发芬芳

k8s 28天写作 12月日更

homework02

王欣欣

「架构实战营」

分析下微信朋友圈的高性能复杂度

Anlumina

#架构实战营

Java程序中如何正确的释放资源

李子捌

Java 28天写作 12月日更

Dubbo框架学习笔记六

风翱

dubbo 12月日更

设计模式:责任链模式学习笔记

Changing Lin

12月日更

PoE、PoE+、PoE++ 三款交换机如何选择?一文带你了解!

Ethereal

交换机 运维技术 PoE 弱电工程

=>符号使用场景

喵叔

28天写作 12月日更

架构训练营第四期-作业2

supermenG

架构师训练营 4 期

架构实战训练营 - 模块 3- 作业

温安适

「架构实战营」

18《重学JAVA》--JAVA异常(二)

杨鹏Geek

Java25周年 28天写作 12月日更

第二模块学习总结

Anlumina

#架构实战营

A 5G Odyssey :2021北京漫游

脑极体

读《思辨与立场》-06 思维的要素 -02

wood

28天写作 批判性思维 思辨与立场

模块2

Geek_59dec2

架构实战营

CSS之选择器(十一):focus-within

Augus

CSS 12月日更

模块九作业

bob

「架构实战营」

微信朋友圈高性能复杂度

阿门阿前一颗葡萄树๑

架构实战营 #架构实战营 「架构实战营」

equals方法通用约定

李子捌

Java 28天写作 12月日更

语音信号处理 4:语音的声学特征

轻口味

AI 28天写作 12月日更

架构实战模块2作业

holdzhu

「架构实战营」

作业:架构实战营模块 2

Poplar89

「架构实战营」

架构实战营模块二作业

Poplar

架构实战营

Facebook的分布式图查询引擎:Dragon_Meta_侠天_InfoQ精选文章