摘要
kv存储引擎近些年越来越受欢迎，因为它可以弹性地扩缩容，对于get/put可以维持高吞吐量，有更低的延迟。这些得益于它的简单，然而简单也带来一定的代价：目前的kv存储系统不能很好的支持scan性能， 所以它不适用于处理复杂、分析型的query。分析型的query要求更好的数据局部性，然而get/put的高吞吐要求离散的索引。这篇paper展示了一种折中的方式可以兼具两者。讲述了分布式kv存储系统TellStore，对于kv、分析型和混合场景都表现了不错的性能。在论文最后的章节中展示了benchmark的测试结果。
1. 介绍
相比于传统关系型数据库，kv store由于它的弹性、可扩展性、部署和管理简单而受到欢迎。而且它的性能也是可预期的：每条get/put请求花费确切的常量级时间。这些特性使得一些应用可以建立在kvs之上。
近期的一些工作展示了kvs可以以高效可扩展的方式run oltp的负载。这些工作采用了一种"SQL-over-NoSQL"的方式：数据持久化存储在kvs（NoSQL）,应用逻辑(with SQL support)放在一个分隔的处理层。在这个工作中我们要提出的一个重要问题是这样一个"SQL-overNoSQL"的架构使用相同的kvs能否同时满足OLAP和OLTP的负载？
这个问题是有价值的，因为oltp和olap的请求访问方式是不同的。大多数kvs的get/put层是为oltp型负载所设计的，但对于分析型的请求并不是可行的，往往要涉及读全部的数据或者大范围的数据。分析型的系统提供适用于它们的访问方式：允许一次性访问到所有的数据(full table scan)，下推select条件或者join条件到存储层。大多数kvs是不具备这样的能力的，所以对于scan的性能是不可接受的。
为了说明目前kvs不适合分析型的应用，table1展示了简单的查询5000wkv对数据的时间，返回了特定字段(YCSB# Query 1 in Section 7.2.1)的最大值(？最大值是什么意思？)。对于这个实验，论文中用了四种机型(在7.1章节中展示了配置)。因为rocksdb是一个单机存储引擎，测试它只用了1/4的数据量。Cassandra花费了大约19m处理这个简单的查询。RAMCloud和HBase需要大约半分钟。对于这三种kvs，使用服务端聚集数据，因为传输数据在客户端聚集会使得性能更差(???)。即使将这些数据集全部放在内存中，性能也是不可接受的。在这个实验中可以接受的系统是rocksdb，memsql和kudu。rocksdb是一个适用于oltp系统的开源数据库存储引擎，被facebook所使用。MemSQL是分布式的、内存关系型数据库系统，经过很好的优化(相比与其它的有很快表达式编译？？)。kudu 是一种基于列存的kvs，适用于混合负载(分析型和get/put)。但是如果有实时的延迟的要求，这7种系统都还远达不到要求。这篇论文将提出TellStore的不同变种，可以实现更低的延迟，更快的响应时间。
kudu的性能表现说明了即使为这种查询做了特定优化的系统也不容易在kvs实现快速查询。这里的问题在于同时支持get/put和scan操作是一个矛盾的目标。有效的scan要求很好的数据局部性，而get/put要求离散的索引。多版本和回收机制的实现也会很大的影响性能，是需要考虑的点。这篇论文展示了一种折中的方式，说明在相同kvs上支持混合负载是可能的。
这篇论文主要贡献了以下几个点：
第一，论文提到了Sql-over-NoSql架构，展示了它如何处理混合负载的。
第二，论文提出了开发一个同时支持点查和范围查询的kvs的存储格式设计(列存/行存等)。
第三，论文介绍了TellStore，一个分布式的内存kvs和两种不同kvs的实现（Sections 4 to 6）。
最后，论文给出了用扩展的YCSB benchmark测试的实验性能和工业界（the telecommuni- cations industry ）使用变体实现kvs支持有效查询的负载。
这个工作的主要思想是构建一个支持混合型负载的kvs是可能的，而且性能是可接受的。相比于从文献中简单提出概念，从整体上考虑和罗列这些设计问题是比较重要的。
REQUIREMENTS
2.1 SQL-over-NoSQL架构
Figure 1 描述了在kvs之上支持OLTP/OLAP混合负载的SQL-OVER-NOSQL架构。在这种架构中，数据持久化在分布式的包含get/put和scan接口的kvs中，事务和查询的逻辑在单独的处理层。处理层也需要处理并发的查询和事务。在整个过程中，我们使用SI(Snapshot Isolation)作为隔离级别，使用Figure 1 中展示的Commit Manager来实现。SI(或者多版本并发控制的其它形式)被作为是默认的隔离级别实现，尤其是在分布式系统和数据库混合负载的场景下，因为oltp事务从来不会阻塞或者干扰olap的查询。在SI隔离级别下，Commit Manager 简化设计了事务的时间戳，保留了对活跃、已提交和回滚事务的追踪，因此几乎不会成为系统的瓶颈。
SQL-Over-NoSQL架构的一个主要优势是elastic(弹性)。机器可以独立的增加到存储层或者处理层(计算层)。比如，可以新增OLAP节点放在处理层来处理复杂的分析型查询。当query完成时，这些节点可以关闭或者更改属性来处理其它任务。这种结构也能有效地支持混合型的事务/分析型的负载:两种负载都可以并发的跑在单独的数据副本上。
为了高效地实现SQL-OverNoSQL架构，分布式kvs必须满足以下的要求：
Scans
除了get/put请求，kvs还必须支持高效地scan操作。为了减少网络传输的代价，kvs应该支持selections、projections和简单的聚合，以实现只有相关的数据从存储层传输到处理层。另外，支持sharded scan对于许多应用来讲是一大优势。
Versioning
为了支持多版本的并发控制，kvs必须要每条记录的不同版本，根据事务的时间戳来返回正确的数据版本。Versioning需要有旧版本回收来释放旧版本数据占用的空间。
Batching and Asynchronous Communication
为了实现高oltp性能，oltp处理节点将多个请求打包发给存储层是关键的。使用这种方式，从处理层到存储层传输信息的往返代价就被分摊到了多个并发事务中。而且，这种打包请求的方式需要异步执行，使得处理层在等待前一次请求被kvs处理完成之前可以收集下一轮的请求。
2.2 实现的难点
实现这三个需求的最大难点在于它们是矛盾的。这也是为什么今天大多数kvs只支持get/put(例如Cassandra 和 HBase)，有的实现了多版本（例如RAMCloud 和 HBase），有些实现了异步传输。所有的这些特征都能很好的支持离散的数据结构，为get/put操作而设计。当查找一行特定版本的记录时，是否它是紧凑的存储是不重要的。然而对于scan，要求很高的数据局部性和数据紧密的存储使得每一次存储层的访问能够返回尽可能多的相关数据。数据局部性对于磁盘和内存中的scan都很重要。而且，加入scan的特征也带来如下的矛盾点：
Scan vs. Get/Put
大多数的分析型系统使用列向存储层来增加数据的局部性。然而，kvs，不需要物化数据，典型的使用行向存储来处理get/put请求。
Scan vs. Versioning
不想关的多版本记录会减少数据的局部性而降低scan的性能。而且，scan过程中check记录的版本相关，也会花费高昂的代价。
Scan vs. Batching
像get/put请求那样打包scan请求并不是有利的。OLTP的负载要求常量级的返回时间和对get/put请求可预期的返回时间。相反，scan会带来返回时间的多变性，取决于谓词的选择性和需要处理的复杂query涉及的字段数量。
幸运地，如我们所描述的，这些矛盾点是可以以一种折中的方式来解决的。这篇论文的目的是去研究kvs的存储结构设计和通过实验证明哪种方式最有效。
3. DESIGN SPACE
这部分给出了一个整体的概括，关于构建一个支持bulk操作和scan的kvs的大多数重要的设计问题。
3.1 Where to Put Updates?
这里有三种可能的设计方式来实现updates(put, delete和insert)：update-in-place, log-structured, and delta-main。
update-in-place是大多数关系型数据库系统所采用的方式。新的记录(insert)存储在已存在的空闲页上，更新已有记录(puts or deletes)通过在原有记录的地方进行覆盖写来实现。如果记录是fixed，这种方式是很好的，因为这样几乎就不会有碎片产生。然而，这种方式对于多版本维护是tricker的。如果多版本数据是在原地进行维护，则会引起明显的存储空间碎片和失去局部性。这种方式的另一个问题是限制来并发：为了创建一条记录的新版本，整个page都要被latched（与锁的区别？？）（a latch是lock-term的锁，一旦page被更新完就可以释放）。
Log-structured的存储设计第一次被提出是在文件系统的应用中【40】。这种方式被一些kvs所使用，例如RAMCloud。主要想法是通过追加写的方式实现所有的update操作。 Log-structured的存储有两个重要的优势：(1) 不会有空间碎片产生。(2)不会有并发问题，因为追加写可以以一种不阻塞的方式实现【29】。一个主要的缺点是如果没有做优化的话，对于scan是很费的，scan需要读旧版本的数据。而且，如果一个记录很少被更新，是很难去做旧版本回收的。一个被称为LSM-Tree的数据结构被用在LevelDB [23], RocksDB [16], and Kudu [19]中。这种变体会定期重组数据来提升读的性能。
第三种方式delta-main，是被SAP Hana所提出的【17】，也被用在几个research 工作中，例如AIM【10】。这种方式以一种写优化的数据结构来收集所有的update请求(called delta)，并且以一种读优化的数据结构来维护大部分的数据(called main)。这两种数据结构会定期的进行merge，这种方式尝试将log-structed的优点(fast get/put)和update-in-place(fast scan)的优点结合起来。
3.2 How to Arrange Records?
最流行的两种设计方式是row-major和column-major。row-major以连续的字节流方式将数据存储在页中[24]，这种布局通常对于get/put在整条记录上很有效。column-major将数据垂直分区，将表的整列存储为连续的字节流。这种column-major组织方式对于分析型的query是有益的，这种query经常会涉及到scan列的一个子集[25, 3, 2, 45, 9, 8]。另外，column-major支持向量操作(SIMD)来加速批量操作和在现代硬件上的scan [47, 49]。一种column-major的变体称作PAX[5]，在每个page中存储多条记录，而在页内，所有的记录以一种column-major的方式存储。PAX是一个在纯列向设计和行向设计之间很好的折中。
Column-major在定长的value上表现比较好。这就是state-of-the-art系统避免使用变长值的原因，要么简单的不允许使用它们(as AIM[10)，要么使用在堆上分配内存，存储对应指针的方式(as in MonetDB [8] and HyPer [33])，或者用一个字典并存储固定大小的字典代码(as e.g. in SAP/HANA [18] and DB2/BLU [39]))。
3.3 How to Handle Versions?
如第二部分所描述的，我们需要支持记录的多版本来实现多版本并发控制。这里有两种主要的实现方式：(a) 存储一条记录的所有版本在相同的位置 (b) 将记录的多个版本使用链表链起来。第一种变体通常与update-in-place结合使用，用这种方式创建新版本的成本更低，但是合并页面做垃圾回收时会花费高昂的代价。第二种变体更适合log-structured的存储，clustering versions in an append-only data structure would require a costly copy of all previous versions to the head.
链接记录的指针会消耗空间，遍历链表会涉及到很多cache miss也会花费很大的代价。好的一方面，第二种方式简化了垃圾回收，因为它可以以一种旧版本数据日志流截断的方式来实现。而且可以减少空间的碎片化。
3.4 When to do Garbage Collection?
回收旧版本数据的方式有两种：(a) 使用单独的线程做周期的回收。(b) scan的过程中做piggy-back回收。方法b增加了scan的时间，但是也换回了垃圾回收的收益：相比其它table，scan频繁从垃圾回收中受益的table会更频繁的做垃圾回收。piggy-back回收的另一个优点是数据处理过程中随时随地做回收，也避免了拿取数据引起的cache miss。
3.5 Summary
table 2给出了在存储效率(碎片)、并发、实现多版本和垃圾回收的花费和scan、get/put操作的效率的前三个纬度之间权衡的方式。第四个纬度垃圾回收正是实现这些性能特征的基础。一个kvs的性能是由这些技术的组合所决定的。总而言之，构建一个kvs总共有24种不同的方式：
(update-in-place vs. log-structured vs. delta-main)
×(row-major vs. column-major / PAX)
×(clustered-versions vs. chained-versions)
×(periodic vs. piggy-backed garbage collection)
另外，还有混合的方式，例如periodic和piggy-backed回收方式可以组合实现。幸运的是，仅仅只有几种变体方式是有意义的：Log-structured方式的updates 和 列向的存储结构设计是没有意义的，因为明显“delta-main & column-major”的组合方式更有效。另外“log-structured & chained-version”的方式明显比"log-structured & clustered-versions"更优。
这其中最有的两个组合方式是log- structured with chained-versions in a row-major的方式和使用delta-main的数据结构with clustered-versions in a column-major的格式。接下来的两个章节将会描述我们使用这两种方式在TellStore上的实现，叫做TellStore-Log 和 TellStore-Col。 第六章给出了TellStore的实现细节，对于所有的TellStore的变体都是很重要的。第七章包含了通过比较不同变体之间的权衡得出的性能评估，使用已存在的一些kvs作为baseline。出了tellstore-log和tellstore-col，第七章节包含了第三种变体的结果，tellstore-row，与tellstore-col是相似的，但是使用row-major的存储格式可以更好的研究对于混合oltp/olap的负载权衡行存和列存。
4. TELLSTORE-LOG
TellStore-Log的实现由RAMCloud所启发，并加入了新的修改以支持有效的scan。
Where to Put Updates?
Figure 2描述了TellStore-Log的主要数据结构：详细描述了记录的布局(kv对)以及使用hashtable来索引日志中的记录。日志本身是被分为多个片段使用链表链起来的多个pages来存储所有的kv对。
日志是使用追加写的数据结构：内存分配以一种无锁的方式自动增加到page的头部。一旦记录追加到日志中，将变为不可变的。这个属性使得恢复和复制日志变得简单，因为复制过程只需要监视头部。因为无锁的特性，相同key的记录可以并发的追加到日志中。哈希表始终是同步点，一条记录只有等指向它的指针成功地插入或者更新到哈希表中才认为生效。以防冲突，数据变为immutable之前在日志中是无效的状态。delete以一种特殊标记的没有数据的update的形式被写入。
hashtable使用锁实现会变成性能点。并发无锁的hashtable设计对于特定的路径是一种常用的优化手段。尤其，在实现扩容时面临点查和update性能的权衡。TellStore预先分配一个定长大小的hashtable，为所有在存储节点上的表共同使用。实现上采用线性探测的开放寻址算法以解决数据冲突的问题。不利的是，开放寻址在高负载下往往表现不佳。为了节省内存以使得可以使用较小的内存保存更大的表，哈希表只记录表的id、记录的key和指向记录的指针。
How to Arrange Records?
追加写的方式本质上与行向存储结构相关联。为了支持有效的scan，日志中的记录必须是完全独立的。我们尤其想要避免去哈希表中查找来确定一条记录是否有效(没有被delete或者覆盖写)。这个约束对版本控制有一些影响，将在下一节中提到。
TellStore-Log在存储节点上为每个表分配一段单独的log。这使得scan可以只处理相关的pages，提高了数据的局部性。sca对有效的记录的数量是敏感的，这对局部性的要求有影响，4.4节将会提到。
4.3 How to Handle Versions?
日志的不可变性使得一条记录的新版本只能追加到日志的头部。为了能够定位到旧版本的数据，我们在每个记录旁边存储指向前一个版本的指针来形成多版本链。另外事务为每条记录分配一个时间戳保存在元信息中，多版本的链表总是根据snapshot由新到旧严格排序的，哈希表总是指向最新的记录。给定一个snapshot，get请求会沿着链表查找直到遇到第一个满足条件的记录。遍历链表涉及到cache miss的代价，与fast put是一种权衡。
这种设计看起来是与所有数据都必须独立的要求是矛盾的：当scan日中中记录时，只有记录的时间戳可以拿到，不能判断是否数据是过期了的。为了避免哈希表的查找，我们为每条记录在元信息中增加了过期的时间戳((valid-to)作为不可变字段。一条记录被成功写之后，旧版本的记录的valid-to将会更新（lazily updated）为新版本的valid-to。给定一个snapshot, scan 可以通过比较两个时间戳来确定记录是否满足条件。
哈希表仍然是唯一的同步点，始终指向最新的元素。更新哈希表和设置valid to字段之间没有竞争条件，TellStore的SI实现不能确保在线事务的可见性(???)。
When to do Garbage Collection?
scan的性能被不再被任何活跃事务所看见的过期数据的数量所影响。为了更频繁合并那些经常被scan的table，垃圾回收放在正常scan的一部分中。扫描一个页面时，其运行状况按照页面中有效记录的数量与总记录数量的比率来计算，一旦该值降到某个阀值以下，页面将会被标记为垃圾回收。被标记的页面将在下一次scan时将剩余有效数据copy到log的头部并将回收后的页面放入空闲页面的池子中。一条记录被copy到日志头部之后，该键的多版本链的指针需要重新调整。为此，我们需要查找哈希表，沿着版本链找到正确的位置。这个操作由于很差的缓存局部性而成本高昂。为了从非频繁扫描的表中回收空间，由后台线程定期去扫描回收。
Summary
尽管Ramcloud是日志结构kvs的典型实现，但其scan性能较差。同时构建一个支持快速get/put请求、版本控制和scan的log-structed kvs是可能的。主要的要点是日志中多版本的仔细组织、有效的垃圾回收策略、延迟的元信息/时间戳实现来使得记录独立，无锁算法和良好的工程设计。
TELLSTORE-COL
TellStore-Col采用delta-main方式的核心理念，维护两种数据结构：main for read, delta for update。如Figure3所示，我们的实现实际涉及到4种数据结构：page list用来维护主要的数据，两个log存储delta(一个for insert, 一个for update)和一个哈希表来索引数据。
5.1 Where to Put Updates?
除了查询元信息字段，在main中的数据只用于read，所有update都被写入一个追加写的存储中。与TellStore-Log不同，delta被分成两个独立的log:update已存在的记录被写到update-log中，update不存在的记录被写到insert-log中。如第5.4节所示，这种分离使得从delta构建main更容易。索引中保留了一个标志位来标示指针指向delta或者main。除了这个标志位，索引表使用与TellStore-Log相同的哈希表。
