写点什么

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:134180
用户头像

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

关注

评论

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

程序员常用的工具软件推荐

程序员小呆

Java c++ 程序员 架构师 Go 语言

Zookeeper 集群部署的那些事儿

牧小农

zookeeper

Android 资源溢出崩溃轻松解

字节跳动终端技术

字节跳动 移动开发 Mars 火山引擎 MARS-APMPlus

这还不够全?阿里P8架构师耗时八年时间才整理出来这“Java核心知识PDF(Java高岗)

Java 程序员 架构 面试 后端

EMQ X VS RabbitMQ:两大消息服务器 MQTT 性能对比全解(下)

EMQ映云科技

RabbitMQ 物联网 IoT mqtt emq

理论+实例,带你掌握Linux的页目录和页表

华为云开发者联盟

Linux 内存管理 寄存器 页目录 页表

马萨卡!阿里大佬珍之若宝的最强高并发pdf,竟然被上传GitHub开源

Java 架构 面试 编程语言

GitHub上首本IntelliJ IDEA操作手册,标星果然百万名不虚传

Java 架构 面试 程序人生 编程语言

我凭借这份pdf拿下了蚂蚁金服、字节跳动、小米等大厂的offer

Java 编程 程序员 架构

Kubernetes 中的应用参数配置案例详析

Zilliz

数据库 Kuber k8s Helm

极客架构营2期模块5作业

Ping

会声会影和剪映在音频处理功能上的比较

懒得勤快

J2PaaS 低代码平台,正式发布开源版!

J2PaaS低代码平台

低代码 零代码 低代码开发 低代码开发平台 无代码平台

JS的深浅复制,原来如此!

华为云开发者联盟

js 序列化 深复制 浅复制

2022年最新Java小白学习路线总结,从零基础跟着学习不掉队(PDF+视频分享篇)

Java 编程 程序员 计算机 java面试

保持高效学习的 7 个方法

Phoenix

学习方法

Qcon 免费报名 | 融云「实时通信技术专场」议题抢鲜看

融云 RongCloud

开发者 通信云 场景化

从简历被拒到收割8个大厂offer,我用了3个月成功破茧成蝶

收到请回复

Java 程序员 面试

惊!HUAWEI高工熬夜赶出这本20W字的图解计算机操作系统指南手册,竟被我偶然发现!

Java 架构 面试 程序人生 编程语言

封神总结!蚂蚁金服+滴滴+美团+拼多多+腾讯15万字Java面试题

收到请回复

Java 程序员 面试 微服务 大厂Offer

Java集合核心内容之葵花宝面,搞定90%以上的技术面!建议收藏

程序员小呆

Java 程序员 架构师

网易云信 NERTC 高清画质体验之 H.265的工程实践 | 体验共享技术专题

网易云信

Java 测试 音视频 视频

为什么网络 I/O 会被阻塞?

编程 架构 操作系统 计算机

阿里P8手抄本惨遭泄露,并出现病毒式传播,致28人斩获大厂offer

收到请回复

Java 面试 阿里 大厂Offer

网络安全产品之堡垒机应用于金融行业案例讲解

行云管家

云计算 网络安全 等保 堡垒机

从互联网“后来者”到“引领者”:这场IPv6大会上,我读懂了中国式创新

脑极体

相约 DTCC 2021 | Tapdata 受邀分享:如何打造面向 TP 业务的数据平台架构

tapdata

惊了!网易架构大牛熬夜手敲千页网络协议笔记,竟在Github上标星百万!

Java 架构 面试 程序人生 编程语言

2021金九银十阿里Java岗7轮技术面经历,险幸上岸

Java 程序员 架构 面试 计算机

手把手带你做LiteOS的树莓派移植

华为云开发者联盟

树莓派 系统 LiteOS arm 树莓派移植

英特尔举办第十四届物联网峰会,携手中国生态伙伴迈向融合边缘新时代

科技新消息

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