写点什么

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

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

关注

评论

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

第三届OpenHarmony技术大会编译器与编程语言分论坛成功

科技热闻

【IoTDB 线上小课 08】时序数据库融合 AI,带来的效果竟然是?

Apache IoTDB

上海交大开源超逼真声音克隆 TTS;微软探索音生图 AI 模型丨 RTE 开发者日报

声网

MatrixOne助力江铜集团打造炉前智慧作业AIoT大数据系统

MatrixOrigin

大数据 AIOT

跨境1688代采案例:探索提供1688代采集运系统的公司

代码忍者

pinduoduo API API 性能测试

使用 Rust(替代 C 语言)扩展 NGINX

NGINX开源社区

读书笔记 rust 编程语言

第三届 OpenHarmony 技术大会:创新成果丰硕,共筑开源生态新未来

科技热闻

淘宝API关键词搜索商品列表:优化商家数据分析与策略制定

代码忍者

pinduoduo API API 性能测试

这个Offer开不开门?

王磊

程序员失业没offer、空窗期长!掌握Java架构核心宝典就能逆袭!分布式+中间件+大数据与高并发+数据库+设计模式与实践+数据结构与算法!

程序员高级码农

Java 面试 Java’ 程序员‘ Java 面试题 #编程

PIRF 412   – Penny for your thoughts

Echo!!!

English

ComfyUI现已上线Neolink.AI,AI 绘画从此轻松驾驭!

MatrixOrigin

GPU算力 AI绘画

EMQX Platform 旗舰版:面向企业级 AI 和物联网应用的高级 MQTT 消息服务

新消费日报

Mac动作冒险游戏:侠盗猎车手:罪恶都市 for Mac 下载

你的猪会飞吗

Mac游戏下载 Mac游戏推荐 mac破解软件下载

第三届OpenHarmony技术大会教育与人才分论坛圆满举办

科技热闻

拍立淘API返回值中的商品列表与详细信息解析

技术冰糖葫芦

API 接口 API 文档 API 测试 API 性能测试

【MM2024】面向 StableDiffusion 的多目标图像编辑算法 VICTORIA

阿里云大数据AI技术

人工智能 算法 论文 图像编辑 MM2024

Sketch快捷键大全 附Sketch最新中文激活安装包

Rose

第二届OpenHarmony竞赛训练营颁奖 ——创新驱动,培育未来科技人才

科技热闻

第三届OpenHarmony技术大会开发框架分论坛成功举行

科技热闻

第三届OpenHarmony技术大会通信互联分论坛圆满举行

科技热闻

《使用Gin框架构建分布式应用》阅读笔记:p32-p51

codists

gin 编程人

第三届OpenHarmony技术大会OS原生智能分论坛圆满举办

科技热闻

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