返回主题:存储常用数据结构

知识卡片

普通读书笔记卡

读取/更新/内存放大:键值存储设计的三角权衡

理解等级:未标注

评价一个键值存储引擎”好不好”,不能只看查询快不快,因为快本身 往往是拿别的代价换来的。读取放大衡量的是”为了访问某一个键, 实际上要多读多少数据”——比如LSM-tree的点查询要从内存到磁盘、 从新到旧逐层查找,即便最终只找到一条记录,中途读取的数据量 也远超这一条记录本身。更新放大和空间放大衡量的分别是”一次更新 实际引发多少额外写入”(LSM-tree的合并操作就是典型代表)和”存下 同样的数据要占用多少额外空间”。三者的关系不是各自独立可以同时 最优,而是互相牵制的权衡:哈希表牺牲有序性、放弃范围查询,换来 读写都接近最优;B+树维持有序结构支持范围查询,代价是要多维护 一套树形索引占用额外空间;LSM-tree把随机写攒成顺序写换来极致 的写入吞吐,代价是读取和空间都要为这份”延迟整理”的债买单 (体现为读放大和写放大)。理解这个三角权衡的意义在于:任何号称 “读写都快、还省空间”的存储引擎宣传,本质上都是在某个具体负载 形态下把权衡点选在了对该场景有利的位置,而不是真的同时消灭了 三者的代价——评估一个存储引擎是否适合自己的场景,本质就是要 看它把这个三角的权衡点选在了哪,是否和自己的负载特征匹配。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:《新型数据库系统:原理、架构与实践》第4章"键值数据库 技术"4.1节"键值数据库技术概述"(源文件: _epub-src/EPUB/xhtml/Section0001_0006.xhtml) - 结论依据:原文明确"每个数据结构的设计都要在读取、更新和内存 放大的基本权衡方面实现特定的平衡……读取放大被定义为'在访问 这个特定的键的基础上,要为每个键多读取多少数据'……核心数据 结构的设计影响着这些性能属性中的每一个",说明存储引擎设计 本质是在这几项指标间做取舍而非同时最优。 - 原始内容:每个数据结构的设计都要在读取、更新和内存放大的 基本权衡方面实现特定的平衡。例如,读取放大被定义为"在访问 这个特定的键的基础上,要为每个键多读取多少数据"。