系统与数据库2015vldb.org编辑精选
一万亿条边：Facebook 规模的图处理
One trillion edges: graph processing at Facebook scale
进阶 · 约 45 分钟读完前置知识：分布式系统基础、图计算模型（如 Pregel/BSP）、PageRank 原理
导读
这篇 Facebook 的论文介绍了其大规模图处理系统（基于 Giraph）如何在超过一万亿条社交边的图上运行 PageRank、k-means 等计算，并分享了工程实践与优化经验。论文声称仅用 200 台机器即可在每轮不到 3 分钟内完成万亿边图上的 PageRank 迭代。
HN 关注点：超大规模图处理的工程实现，同时对其性能数字的真实性和这类论文的学术价值展开讨论。
后来怎么样
该工作是 Facebook 基于 Giraph 的大规模图处理实践总结，展示了万亿边社交图上的工程优化，但系统本身未成为行业标准，影响主要限于工业界图处理实践参考。
HN 评论精选
这几条评论里：质疑 2 补充 1
补充推荐最大的公开图数据集，并指出学术基准有缺陷：单机 Rust 实现可胜过集群
如果有人对大规模图处理感兴趣，最大的 Web Data Commons 超链接图（基于 Common Crawl 数据构建）有 35 亿网页和 1280 亿条超链接，据我所知这是最大的可免费获取的真实世界图数据集。许多图系统都能在单台强力机器上处理这个规模的数据，包括用 SSD 的 FlashGraph、Frank McSherry 在单台笔记本上用 Rust 写的实现，以及 Dato 的 GraphLab Create。正如 McSherry 指出的，图计算系统还有很大改进空间，尤其因为目前的学术评估是有问题的——所谓"有问题"是指一台笔记本上的单线程 Rust 图系统竟能击败高性能机器集群跑出的基准。
Smerity查看英文原文
If anyone is interested in graph processing at scale, the largest Web Data Commons Hyperlink Graph[1] (created from Common Crawl[2] data) is 3.5 billion web pages and 128 billion hyperlinks. To my knowledge, it's the largest freely available real world based graph dataset. Numerous graph systems have been made that can scale to this data, frequently on just a single powerful node, including FlashGraph[3] (using SSDs for high), Frank McSherry's single laptop Rust implementation[4], and Dato's GraphLab Create[5]. As Frank McSherry points out at [6], there's a lot of room to improve state of the art in graph computation systems, especially as the current academic evaluations are broken. (where "broken" means that a single threaded graph system written in Rust on a laptop can beat the benchmarks created by a cluster of high performance machines) [1]: http://webdatacommons.org/hyperlinkgraph/ [2]: http://commoncrawl.org/ [3]: https://github.com/icoming/FlashGraph [4]: http://www.frankmcsherry.org/graph/scalability/cost/2015/02/04/COST2.html [5]: https://twitter.com/CommonCrawl/status/623615774909857792 [6]: http://blog.commoncrawl.org/2015/04/evaluating-graph-computation-systems-performance-and-scale/
质疑质疑论文性能数字：每台机器每秒 2800 万条边似乎不现实
"我们仅用 200 台机器就能在超过一万亿条社交连接上运行 PageRank，每轮迭代不到 3 分钟"——我对此表示怀疑，这相当于每台机器每秒处理约 2800 万条边。
anotherangrydev查看英文原文
>we were able to execute PageRank on over a trillion social connections in less than 3 minutes per iteration with only 200 machines Colour me skeptical, that's around 28M edges per second per machine.
质疑批评论文只展示集群规模而缺乏可迁移的洞见，只有 k-means 部分有价值
我有点讨厌这类论文，只是炫耀集群化配置却不提供任何抽象层面的洞见。这并没有让我更好地理解图数据，只是让我准备好去安装一套价值数百万美元的机器和存储集群。关于 k-means 的部分有点意思，其余内容无聊且无关紧要。
logicrime查看英文原文
I kinda hate these papers that just humble-brag clusterized setups without providing any abstract insights. This doesn't bring me any closer to understanding graph data any better, but I'm now ready to begin installation of a multi-million-dollar cluster of machines and storage. The bit about k-means was interesting, but the rest was an irrelevant bore.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2015Hacker News 讨论帖201 分 · 25 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选