Open levy5307 opened 2 years ago
https://levy5307.github.io/blog/kv-storage-engine/
Key-value存储支持key-valueAPI，以及管理key-value pairs，其应用十分广泛。
KEY-VALUE STORAGE ENGINES, AND APPLICATIONS
Storage Engine Design
KV存储的核心是实现一个存储key-value pairs的数据结构，每个数据结构的设计都实现了读取、更新和内存放大的特定trade-off。例如，读放大被定义为读取一个特定的key时，需要读取的数据。实际上，读、更新和内存放大进一步细分为更细粒度的指标，如点读、范围读、更新、删除、插入和缓存所需的内存。核心数据结构的设计影响着每一个性能指标以及系统的每一个特性和属性。例如：
为了支持time-travel查询，需要决定如何存储timestamp信息。 为了加速对最近访问数据的查询，我们需要在缓存和其他结构之间平衡可用内存，这些结构需要加速对基本数据的处理，例如，内存bloom过滤器，fence pointers。 为了支持高效的并发读写请求，存储引擎可能必须将数据布局从“in-place”更改为“out-of-place”。
Rapidly Changing System Requirements
今天我们比以往任何时候都更希望快速构建、更改和调整数据系统，以便能够跟上不断变化的应用程序和硬件的需求。使用新workload patterns的新应用程序或现有应用程序中的新特性经常出现，单个系统无法有效地支持不同的workload。这一问题有几个日益紧迫的原因：
首先，出现了新的应用程序，其中许多应用程序引入了以前非典型的新workload pattern。 其次，现有的应用程序不断重新定义它们的服务和特性，这将直接影响它们的workload pattern，并且在许多情况下使现有的底层存储决策不是最优的，甚至是糟糕的。 第三，硬件不断变化，影响CPU/带宽/延迟平衡;
最大化性能要求底层存储设计更改，这些问题归结为：one size does not fit all problem，这适用于整个系统设计和存储层。特别是，在当今基于云计算的世界中，即使是略低于最优水平的设计，也会导致能源利用以及成本方面的巨大损失。
There is no Perfect Design
不存在完美的数据结构可以最小化所有性能trade-off。
例如，如果我们添加一个日志来支持高效的out-of-place写，我们就会牺牲内存/空间成本，因为我们可能有重复的条目，并牺牲读取成本，因为将来的查询必须同时搜索核心数据结构和日志。反过来，这意味着不存在能够满足不同性能需求的完美KV存储。每一个设计都是一种妥协。但是，我们如何知道哪种设计最适合应用程序？我们是否有足够的设计和系统来满足新兴和不断变化的数据驱动应用程序的需求？特别是在数据科学和机器学习的新机遇推动下，应用程序越来越多样化和庞大的今天，在系统内核适当设计以匹配目标应用程序的需求是非常关键的。
Tutorial Structure
本论文由三部分组成：
第一部分回顾了本节中描述的整个问题设置，1)定义键值存储系统，2)描述跨数据科学领域的传统和新兴应用程序，3)给出关键的开放挑战，特别是针对不同的workload和动态应用程序场景。 第二部分讨论了过去几年的主要研究和行业趋势，这些趋势已经形成了键值存储引擎的最先进水平。具体来说，我们将讨论1)读优化的存储引擎，2)写优化的存储引擎，3)系统组件之间分配内存的设计选项和注意事项，4)如何存储时间戳，5)如何存储大value。 在第三部分，我们提出了一个统一的框架，它封装了所有最先进的设计，并允许我们推理存储引擎的可能设计空间。我们还讨论了如何描述和交流存储引擎设计，以及为什么这是一个关键问题 最后，我们提出了self-designed的KV存储引擎的挑战。我们解释了1)与过去的解决方案相比，它们带来了新的机会，2)它们如何能够被用于解决跨许多类型的数据密集型应用的实际问题，3)它们与过去的工作相融合而产生的新的研究机会。self-designed系统知道关键组件（如data storage）可能的设计选择及其组合，并能在截然不同的选择中选择最合适的设计
STATE-OF-THE-ART ENGINE DESIGN
The Big Three
KV存储主要使用三种数据结构来管理数据。为了了解它们提供的不同设计目标和性能平衡，我们简要介绍它们的核心设计特征。
第一个是B+树。
https://levy5307.github.io/blog/kv-storage-engine/
Key-value存储支持key-valueAPI，以及管理key-value pairs，其应用十分广泛。
KEY-VALUE STORAGE ENGINES, AND APPLICATIONS
Storage Engine Design
KV存储的核心是实现一个存储key-value pairs的数据结构，每个数据结构的设计都实现了读取、更新和内存放大的特定trade-off。例如，读放大被定义为读取一个特定的key时，需要读取的数据。实际上，读、更新和内存放大进一步细分为更细粒度的指标，如点读、范围读、更新、删除、插入和缓存所需的内存。核心数据结构的设计影响着每一个性能指标以及系统的每一个特性和属性。例如：
Rapidly Changing System Requirements
今天我们比以往任何时候都更希望快速构建、更改和调整数据系统，以便能够跟上不断变化的应用程序和硬件的需求。使用新workload patterns的新应用程序或现有应用程序中的新特性经常出现，单个系统无法有效地支持不同的workload。这一问题有几个日益紧迫的原因：
最大化性能要求底层存储设计更改，这些问题归结为：one size does not fit all problem，这适用于整个系统设计和存储层。特别是，在当今基于云计算的世界中，即使是略低于最优水平的设计，也会导致能源利用以及成本方面的巨大损失。
There is no Perfect Design
不存在完美的数据结构可以最小化所有性能trade-off。
例如，如果我们添加一个日志来支持高效的out-of-place写，我们就会牺牲内存/空间成本，因为我们可能有重复的条目，并牺牲读取成本，因为将来的查询必须同时搜索核心数据结构和日志。反过来，这意味着不存在能够满足不同性能需求的完美KV存储。每一个设计都是一种妥协。但是，我们如何知道哪种设计最适合应用程序？我们是否有足够的设计和系统来满足新兴和不断变化的数据驱动应用程序的需求？特别是在数据科学和机器学习的新机遇推动下，应用程序越来越多样化和庞大的今天，在系统内核适当设计以匹配目标应用程序的需求是非常关键的。
Tutorial Structure
本论文由三部分组成：
STATE-OF-THE-ART ENGINE DESIGN
The Big Three
KV存储主要使用三种数据结构来管理数据。为了了解它们提供的不同设计目标和性能平衡，我们简要介绍它们的核心设计特征。
第一个是B+树。