系统与数据库2020reports-archive.adm.cs.cmu.edu
数据库管理系统的内存高效搜索树
Memory-Efficient Search Trees for Database Management Systems
专业 · 约 180 分钟读完前置知识：数据库索引基础、B树/前缀树、CPU 缓存层次
导读
这篇论文研究数据库管理系统中的内存高效搜索树，重点是在索引结构中采用压缩/紧凑表示来降低内存占用并提升缓存效率。评论认为其缓存优化思路可信且潜力大，但也指出压缩会让内部块更满，从而在插入时带来级联重平衡和长尾延迟，更适合读多写少场景。
HN 关注点：数据库索引的内存/缓存效率，以及论文方案与工业界已有紧凑索引实践、插入性能权衡之间的差距。
后来怎么样
论文系统化提出的 ART 等紧凑索引结构后来被多款内存数据库和索引库采用，成为主内存索引设计的重要参考；其缓存友好与压缩索引思路也影响了后续 DBMS 索引研究。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
补充数据库仍有大量低效可优化，压缩可惠及列/行，并列举系统调用批处理、异步 IO 等未被采用的改进机会。
内容很多，需要慢慢消化。论文里的压缩方案大概不只适用于键，也普遍适用于列，会正面影响行大小，进而提升整体性能？可以拿来比较的短字符串压缩库是 smaz，作者是 Redis 的作者 Antirez。过去十年 TokuDB 和后来的 MyRocks 展示了如何为大到放不进传统 RDBMS 的数据做快速存储引擎：多级结构、页级压缩等。但仍有大量容易获得的收益。总体而言数据库非常低效，低垂果实很多；如果 MyRocks 团队能翻倍，并同时审视服务器和存储引擎的低效之处，情况可能会变。我脑子里有一串数据库其实没做的很有希望的想法：Linux 没有系统调用批处理机制，如果有，上下文切换会大幅减少；2010 年的研究证明了这一点，受益的不只是数据库，而如今上下文切换比以往更贵。数据库引擎都使用阻塞 IO；io_uring 终于提供了可用的异步 IO，会极大有益于数据库存储引擎。
willvarfar查看英文原文
A lot to digest. Presumably the compression schemes outlined in the paper would benefit columns generally, and not just keys, and would have a positive impact on row-size which would in turn benefit general performance? One short-string-compression-library to compare with might be https://github.com/antirez/smaz by the Antirez, the author of redis. In the last decade Tokudb and then MyRocks showed how to do a fast storage engine for data too big to fit in traditional RDBMS. They are multi-level, they do page-level compression etc. And yet there is still so many easy wins yet to be had. Generally, databases are completely inefficient and there is just so much low-hanging fruit; if the team size working on e.g. myrocks could be doubled, and tasked with looking at the inefficiencies in the server as well as the storage engine, things might change. I have a list in my head of the various really-promising-ideas that databases don't actually do: * linux doesn't have a syscall batching system, but if it did, the number of context switches would be cut down dramatically. Research in 2010 https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Soares.pdf proved this and it wouldn't just be databases that benefit. These days context switching is more expensive than ever. * database engines all use blocking io. Finally io_uring offers workable async io and that would benefit database storage engines immensely. See https://fosdem.org/2020/schedule/event/rust_techniques_sled/ * tokudb showed that simply not tracking the affected row count could speed things up massively (tokudb called it NOAR) * query engines often don't handle things that a few more lines of code would handle efficiently. I've got some tables with big compound keys and often do prefix searches in them, and why isn't mysql evaluating constraints that it can against the other columns in the key before dereferencing the row? Arrgh. Dumb dumb dumb. Etc.
补充建议把 DBMS 做成 unikernel/ring-0 服务，以消除上下文切换开销并细粒度控制资源。
我一直纳闷为什么没见过把 DBMS 做成 unikernel。DBMS 本身已经是数据的“托管运行时”，有自己的内存分配器、调度器、某种意义上的文件系统等。而且为了可预测性，你几乎总是希望把 DBMS 工作负载跑在专用硬件/VM 上。那为什么不把这套 DBMS 服务放进 ring-0，从而不需要上下文切换开销、能细粒度控制自己对内核资源的排队，并且可以一路从网络到磁盘再回来都按引用传递数据结构？Linux 里已经有 Open-iSCSI：控制面在用户态，数据面完全是内核服务，因而获得这些优势。这个架构在那里运行得很好；我不清楚为什么其他提供高层“数据管理方案”、有同样高吞吐/低延迟需求的人没有照搬。
derefr查看英文原文
I've always wondered why I haven't seen a DBMS built as a unikernel. A DBMS is already a "managed runtime" for data, with its own memory allocator, scheduler, filesystem (in some sense), etc. And you're almost always going to want to run a DBMS "workload" on its own dedicated hardware/VM, anyway, for predictability. So why not just take that set of DBMS services and put them in ring-0, where they won't need any context-switch overhead, will have fine-grained control over their own queuing for kernel resources, and where they can pass data structures by reference all the way from the network to the disk and back? In Linux, we already have Open-iSCSI, which just has the control plane in userspace, while the data plane is entirely a Linux kernel service, gaining it all these advantages. This architecture works very well there; I'm unclear on why others attempting to provide the higher-level "data-management solutions", with the same high-throughput/low-latency requirements, haven't copied it.
亲历论文方向正确但落后工业实践；工业界已长期使用自适应紧凑索引，缓存效率可带来巨大性能提升。
这是一篇好论文，我欣赏它对缓存效率的整体关注——相比许多常见实现，这个领域常常能轻松获得多个数量级的性能提升。但它也凸显了学术文献与数据库引擎设计前沿之间的差距。例如，自适应紧凑索引结构在闭源数据库中至少已用了十年；类似论文中的想法早已在真实系统中落地。上个月我又交付了一个数据库引擎，与最好的开源同类产品做了基准对比，大致具体地说明了这个差距：设计的内存:存储比是 1:1000，比论文中称为激进的 1:100 还高一个数量级。公平地说，我之前的系统设计更接近 1:100，并用新的计算机科学研究显著扩展了比例而没有明显牺牲性能。对于索引需求相当复杂的数据模型，插入性能是最好的开源同类产品的 100 倍以上。很大一部分性能来自缓存效率的显著提升，而这些提升甚至并不特别新颖；论文中归因于缓存效率的收益是可信的。上述系统中的数据与索引比约为一百万比一，小到足以让许多 T… 进入 CPU 缓存。
jandrewrogers查看英文原文
This is a good paper and I appreciate the holistic focus on cache efficiency, an area where multiple orders of magnitude of performance improvement are often easily attainable compared to many common implementations. However, it also highlights the gap between academic literature and the state-of-the-art in database engine design. For example, adaptive succinct indexing structures have been used for at least a decade in closed source databases. Structures similar to the ideas presented in the paper have been reduced to practice in real systems for a long time. Last month I delivered yet another database engine, benchmarked against the best open source comparables, which provides a rough but concrete example of the gap: The designed memory:storage ratio was 1:1000, an order of magnitude higher than even the 1:100 ratio mentioned as aggressive in the paper. In fairness, my prior systems were designed much closer to 1:100 ratio and it used new CS research to significantly extend the ratio without materially sacrificing performance. For data models with fairly complex indexing requirements, insertion performance was >100x(!) the best open source comparables. A large part of this performance is due to dramatic improvements in cache efficiency that are not even particularly novel -- the gains attributable to improved cache efficiency in the paper are eminently believable. The data-to-index ratio in the above is around a million-to-one, small enough to fit in CPU cache for many TB scale data models. The high data-to-index ratio is largely attributable to using search structures that forego total order and balancing, which enables dramatic improvements in succinctness with minimal reductions in selectivity. The other major contributor to performance is scheduler design, which wasn't really touched on in the paper and is largely ignored entirely in open source databases. tl;dr: current open source database engine designs leave a massive amount of performance on the table due to very poor cache efficiency, and this paper correctly touches on some of the ways this is materially improved in closed source database engines.
质疑压缩本质是提高块填充率；读多写少场景收益好，但插入可能引发级联重平衡和长尾延迟。
他们说的压缩，是指让内部块保持得更满。这看起来是一篇不错的学位论文，导师也很有声望。但这有代价：块越满，插入就越容易触发级联效应。批量插入有帮助，但一旦要应用这一批，重平衡可能耗时很长，甚至可能涉及整棵树。这会给插入时间增加肥尾。不过在許多读多写少的场景下，这是个好权衡。
alecco查看英文原文
Note by compression they mean keeping internal blocks closer to full. It looks like a good thesis and advisors are reputable. But this comes with a trade-off. As blocks are full, inserts trigger more often a cascade effect. Batching inserts helps but once you need to apply the batch that could take a long time to rebalance potentially the whole tree. This adds a fat tail to insert times. But in many read-heavy scenarios it is a good trade-off.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2020Hacker News 讨论帖251 分 · 59 评
同领域还值得读
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 分钟编辑精选