标题：一个针对基于LSM的NoSQL数据库上的辅助性索引的比较性研究
本文是对NoSQL辅助索引技术的一个综述文章。
ABSTRACT
NoSQL数据库在大数据领域得以广泛应用，主要是因为其高写吞吐，和快速的主键查询。
然而对于非主键的查询也有需求，诞生了很多辅助索引，但是各种辅助索引之间没有直接的比较，比如空间和吞吐量。
作者把目前的辅助索引分成两类，一类是嵌入式的，就是在表里面补充一个轻量级的filter；另一类是独立型的，有独立的数据结构。
作者比较后发现，各种索引有不同的优势，没有绝对的dominating index。
嵌入式的优势在于写吞吐量高，空间占用小；独立式的优势在于查询相应速度快。
1 INTRODUCTION
- 定义：与时间相关的属性：属性的值和数据的插入时间有比较强的关系。
- 定义：Top-K query：指定一个属性值，满足这个属性值，lookup前K条记录，按照插入时间排序。
NoSQL主要完成的方法如下图，前三个关于primary key非常基本，后面两个是辅助索引中的Top-K问题。
- 实验方法论：作者基于开源的，毫无辅助索引的NoSql DB- Level DB，实现了3种stand-alone index, 2种embedded filter进行多指标的比较。选择Level DB主要是因为它单线程单节点，可解释性很强。
既进行了静态比较（只读），又进行了动态比较（读写都有）。 - 实验结果总结：
- 与时间相关的属性，embedded filter更好(zone-map)；
- 可利用空间较小时，embedded filter；
- 写操作在50%以上，对辅助属性的检索很少<5%时，embedded filter更好（索引维护开销更小）；
- 以上三个都不是，读比写多，而且经常Top-K query(lookup & range lookup)的，stand alone index- lazy updates很合适;
-
如果对Top-K没有执念的话，比如通用的分析，或者主要是聚合操作，stand alone index-composite key index更为合适。
image.png
2 RELATED WORK
3 EMBEDDED INDEX
对于LSM-tree来说，分若干level，第一个level在内存中，其他level在磁盘上，level越大，数据容量越大。在每个level中，都会有一个或多个数据文件（SSTable），每个SSTable可能控制多个blocks。embedded index会对每一个block，每一个进行index的属性，都去构造一个bloom filter/zone map。
每当一个磁盘上的SSTable生成时，我们就构建embedded index on it。
此外，这些embedded index都会被加载到内存里，因此对数据的扫描在内存中就可以进行。
这种改造在levelDB上具体体现就是在原先只针对primary key的embedded index补充一下。
除此之外，本文还在block-level zone map的基础上，建立了一个SSTable-level zone map，粒度更粗，可以更为global的进行筛选。
对于内存的MemTable，由于数据量较小，作者直接建立一颗内存B树当辅助索引了。
Top-K query：主要思路就是逐层扫描，知道找到K条记录。由于data不是按照插入时间排序的，而是按照primary key进行排序的，因此数据本身的顺序不能作为Top-K排序的key。好在LevelDB和其它NoSQL在数据插入时会分配一个sequence number，这个是按照插入时间来定的，因此可以用这个来在每个level内部定序。
具体实现可以用一个大小为K的最小堆，以sequence number排序。每当找到一个record，首先判断相比于堆顶，是新的还是旧的（如果堆已经满了）。如果是新的，或者堆没满，那么只要这个Record是valid的，那么就可以插入。这里的valid主要是指这个Record是不是已经被overwrite了。
确定一个record是否是valid的，只需要在上层搜索一遍是否有相同的key即可，如果有，证明已经被overwrite了，那么就放弃入堆，否则插入。RANGELOOKUP(Ai , a,b, K).：主要利用zone-maps。也是level-byl-level的，通过global zone-maps, block zone-maps，两层剪枝，找到可能的block，再去逐个record验证。用的也是堆。也要验证overwrite的问题。
有关primary key的其他三个操作，涉及写的两个只要把内存的B树维护好就行了。
3.1 Cost Analysis
首先是primary key的三个操作，都没有额外负担的，和之前是一样的。
对于TopK lookup，要对L层数据的所有blocks乘上一个布隆过滤器假阳性概率，再加上K个真阳性blocks，再加上个因为以level为级别进行包装的额外blocks。
注意到这里其实不应该忽略掉布隆过滤器的CPU运算，因为blocks会非常多，布隆过滤器同样也会非常多。好在对于与时间相关的属性，zone-map首先会筛掉很多table，那么就大幅度削减了布隆过滤器的CPU代价。
对于rangelookup，主要取决于数据的分布，如果是时间无关的属性，索引根本无法生效，只能顺序扫描；如果是与时间有关的属性，可以做到只有次读block。
4 STAND-ALONE INDEX
4.1 Stand-Alone Index with Posting Lists
首先，stand-alone index的逻辑结构就是如下图所示这样的翻转索引，key是辅助属性的值，value是primary key的list，是按照sequence number(插入时间)排序的，很容易理解。
注意LSM-Tree不同层之间虽然是按照插入时间顺序排列的，但是同一层内部，是按照key的顺序进行排列的。
4.1.1 Eager Index
对于一次数据插入，如果特定属性A=a不空的话，eager index会读出最高层级的A=a的条目，然后在后面的primary key list上面补充一个，然后再写回去（写到MemTable去）。Eager Index是没有update和delete的，所以只有最高层的那个是有效的，底层的辅助属性key相同的都是废弃的。
查询的时候，现在index上做一次GET，GET到所有的primary key list，逐个验证validity
range query也是类似地的。
4.1.2 Lazy Index.
相比于Eager Index每次插入的时候，不会先把已有的读出来，而是直接把新的写进去，在flush/compaction的时候，再进行merge。这意味着每一层的一个key只会出现一次，因为flush/compaction的时候，会对key进行merge。对于删除操作，也是put一个带Deletion标记的就可以了，merge的时候会进行删除。
LOOKUP：一层一层的去找，每个primary key都需要去主表验证，直到某一层topK全部找到，则停止遍历。
RANGELOOKUP：基本和LOOKUP一致，但是要扫描所有的level。
为什么要扫描所有的level呢？这源于LevelDB的compaction方式，LevelDB是以round rubin的方式对于一个level中的某些范围的key进行一次compaction的。注意，也就是说可能两个key在某一时刻都在一个level，但是key1突然被compaction到下一层了，未来可能还会再下一层，但是key2可能还在原来的一层。然而事实上，key1和key2谁先插入的不能明显确定。因此对于一个范围的key来说，LSM-Tree的不同level的时序性已经被打破，因此要扫描所有的level。
4.2 Stand-Alone Index with Composite Keys
composite keys和lazy index的方式是有点像的，有趣的是这种索引的value都是null。composite keys前缀是辅助属性，后面是primary key。
LOOKUP：由于辅助属性是前缀，lookup就是一个范围查询操作，与lazy index 的range lookup类似，这里也是需要扫描所有level才能得到可靠的TopK。注意每找到一个match
RANGGELOOKUP：和LOOKUP基本一致。
注意这两个操作每找到一个match都要会主表，check一次validity。
4.3 Cost Analysis
stand-alone的方式对于GET操作，完全没有影响。
对于PUT和DELETE，会在index table做一次写，具体取决于索引了多少个属性；而Eager Index，则需要做一次额外的读，严重地影响了吞吐量。
注意这里表格有一个WAMF(write amplication factor），指的是一条记录因为LSM-Tree的flush/compaction机制，会被重复写多少次。显然，Eager Index重复写次数是最多的。
对于LOOKUP，Eager Index则只需要做一个index table的I/O（假设布隆过滤器没有假阳性），而其它两种最差要做L次I/O，L是LSM-Tree层数。Lazy Index在不同层之间进行merge的时候，会有较大的CPU排序代价，但是如果TopK中的K比较小的话，会有比较大的early abondoning，相对于Composite Keys性能较好。
对于RANGE LOOKUP，最差情况下都要遍历所有的blocks，然后再去主表复核。
5 EXPERIMENTS
8核16GB单机, 基于LevelDB，snappy压缩。没有用block cache，内存被用于存放metadata和大部分的布隆过滤器。
5.1 Workload
- 合成数据集：基于种子数据集，在满足其数据分布的情况下，进行扩展。对于时间属性，按照原有的频率范围进行生成。
- 种子数据集：10GB，18million条tweets，22个属性。
作者实际用种子数据集扩大了10倍，实验用100GB，基于user_id, create_time作为索引属性。测试分静态负载和动态负载，静态负载是索引建好之后对于各种类型的查询进行分别测试；动态负载则模拟真实场景，有各种query以及插入、删除、更新等。
5.2 Experimental Evaluation
5.2.1 Results on Static workload.
- 索引额外占用空间在5%-10%左右，embedded的更小。composite keys无需维护posting list，因此空间更小，eager index的posting list更紧凑，空间相对更小。
- GET操作，任何索引都没有产生较大影响。
-
PUT操作，Embedded开销最小，composite次之，相比于lazy没有那么多CPU开销。而eager，对于时间关系较大的属性开销还不错（因为没有随机update），较小的属性则由于其一个GET操作，大幅增加了开销。
Eager Index对于与时间无关属性的吞吐量激烈退化，主要是由于随机更新而导致在flush/compaction过程产生的大规模的读写。
因此，Eager Index并不在实际应用中有意义，后续的比较也就不考虑它了。
image.png
image.png
- index on user_id
- lookup
- K较小时，Lazy由于其高剪枝率，性能最好；K较大时，composite由于较紧凑的结构和基本无CPU开销，性能最好。
- 当K较小时，embedded由于布隆过滤器可以生效，性能也很好；但是由于过高的CPU cost，不如Lazy的高剪枝率方案。
- range lookup
- K较小时，Lazy性能最好；K较大时，性能最好。
-
embedded在选择率较小时，由于是时间无关的属性，zone-map效果很差，性能最差；但是在选择率较大的时候，由于可以在顶层进行blocks筛选，性能居中。
image.png
- lookup
- index on creation time
- 基本结论不变；
-
embedded 在range query中，表现非常突出，原因在于zone-map在时间相关属性能发挥较大作用。
image.png
5.2.2 Results on Mixed workloads
- 无论哪种workload，lazy方案都最好也最稳定；
- 对于write heavy workload，此时Composite开始激增。分析此时数据量正好达到16GB，GET操作会开始出现大量的Cache Miss，而Composite的LOOKUP总是需要大量的GET，因此性能退化；
- Embedded在非时间关系属性上的索引无法有效使用zone-map，对于read heavy workload效果很差。
- 对于update heavy workload，数据量大时composite比lazy效果略好，主要是由于composite的compaction更容易，没有merge操作。
-
对于update heavy workload，embedded在后期激增，主要是由于update导致了额外的compaction。
image.png
image.png
Summary of novel results.
- Eager Index虽然被广泛使用，但是不具备可扩展性，写吞吐率也极低。
- embedded index即使在非时间强相关属性上，也保持了不错的性能，但是目前没有被使用过。
- Lazy Index对于TopK密集型的应用非常合适，但是由于实现容易，反而是composite Index被应用的最为普遍。
- 由于LSM-Tree重度依赖Compaction，而Compaction会涉及一次大规模读写，造成原本的工作集cache大范围的miss，这在实际应用中需要被重视。(已有工作进行改善)
