AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

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

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

关注

评论

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

AI大模型入门(二):不微调的大模型能用吗?

测试人

人工智能

用友签约招商局集团人力资源智慧系统(二期)

用友BIP

悦达集团与用友战略签约,共启数智发展新纪元!

用友BIP

从人工智能到业务落地,低代码搭建智能工作流

天津汇柏科技有限公司

人工智能 低代码

【AI聊天机器人】轻松上手,快速配置实战指南

JEECG低代码

AI大模型 AI应用 AIGC AI聊天

Nexpose 8.6.0 for Linux & Windows - 漏洞扫描

sysin

用友携手中展集团,打造会展行业首个AI智能体集群

用友BIP

Head First LLM-开篇

好名字可以让你的朋友更容易记住你

#大模型

数智焕新| 4月招商局集团、悦达集团等选择用友BIP

用友BIP

从 SQL Server 到 TiDB:恺恩泰助力 40 + 医院数据平台升级的技术实践

TiDB 社区干货传送门

PET口语APP的开发流程

北京木奇移动技术有限公司

软件外包公司 AI口语学习 PET考试

苏州企业等保快速通关小秘诀看这里!

行云管家

等保 等保测评

迭代器失效:99%的C++程序员都会踩的坑 !

电子尖叫食人鱼

c++

Dell OpenManage Enterprise 4.4 - Dell 服务器、存储和网络设备集中管理软件

sysin

dell

JEB Pro v5.29 (macOS, Linux, Windows) - 逆向工程平台

sysin

JEB

签约!杭州金投选择用友BIP推进业财一体化,加强精益化管理

用友BIP

「摩根士丹利」最新人形机器人研报:5万亿美元全球市场和最佳商业模式分析(附报告)

机器人头条

科技 大模型 人形机器人 具身智能

PET口语练习APP的技术框架

北京木奇移动技术有限公司

软件外包公司 AI口语练习 PET考试

区块链ETF软件的核心功能

北京木奇移动技术有限公司

区块链技术 软件外包公司 区块链ETF

AI+高等教育,和鲸Heywhale上线从通识到“学科+AI”的解决方案2.0

ModelWhale

人工智能 数字化教育 智慧教育

Elasticsearch Enterprise 8.18 (macOS, Linux, Windows) - 分布式搜索和分析引擎

sysin

elasticsearch

Elasticsearch Enterprise 9.0 (macOS, Linux, Windows) - 分布式搜索和分析引擎

sysin

elasticsearch

区块链ETF软件的功能模块

北京木奇移动技术有限公司

区块链开发 软件外包公司 区块链ETF

启动!华润五丰携手用友推进数智化渠道协同管理

用友BIP

AI重构人力价值链:从“人效管理”到“智效革命”

用友BIP

白鳝:国产化替换浪潮进行时,信创数据库该如何选型?

TiDB 社区干货传送门

GreatSQL Hash Join 条件列长度对执行计划的影响

GreatSQL

香港人工智能营销技术研究院正式揭牌成立

东信营销科技

用友BIP再发新品,开启「人+智能体+群」业务协同新模式

用友BIP

国内远程控制安全性天花板?ToDesk、向日葵、UU远程、RayLink深度对比

小喵子

远控工具 向日葵 远控软件 ToDesk

数智焕新进行时,用友BIP助力企业跨越周期、迈向高质量发展

用友BIP

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