这一章主要介绍向量空间和子空间。
Permutations矩阵每一行都有一个"1"，一个矩阵乘以Permutations矩阵会达到交换行的效果。对于在消元时需要将0移出pivot位置的情况，可以用Permutations矩阵实现，因此LU分解又可以写成
另外还有
Transposes就比较简单了，矩阵Transposes就是将行变成列，列变成行，即
向量空间就是一对向量通过线性组合所形成的所有向量，比如
Closure：比如只有正实数的向量就不是一个向量空间，它只是向量空间的一部份；
Subspaces：一个向量空间被包含在另一个向量里面则称为子空间，比如
Column space：假设A是
线性代数中最重要的一个操作就是矩阵分解，一个矩阵分解成两三个特别的矩阵。这一节主要介绍LU矩阵分解，这是从高斯消元法中得来的，L和U分别是下三角矩阵和上三角矩阵。
然后将上面的等式转为
分解后，U是一个上三角矩阵，其主元都在对角线上，L是下三角矩阵，并且对角线都是1，有时也会把主元拉出来成一个对角矩阵。
对于3x3的矩阵也是类似的，如果存在
那么
这一节主要是将计算机在进行消元操作时进行了多少次操作，以第一列为例，第一次做消除操作时，先将一行相乘，然后从另一行中减去它，这需要
n
次操作。第一列需要进行n次（实际上是n-1次，因为第一行不改变），因此总操作是
如果主元为0，需要交换行。对于矩阵而言，行交换可以左乘一个置换矩阵P。如果需要交换第一和第二行：
论文介绍了一个前身为MemSQL的分布式通用SQL数据库，现在叫SinglestoreDB (S2DB)。它是市场上最早的分布式HTAP数据库之一，可以做横向扩展以有效利用100台主机、1000个核心和10TB的RAM，同时保持类似于Oracle或SQL Server等单机数据库的用户体验。 S2DB的表存储通过快速扫描、查找、过滤、聚合和更新等操作有效地满足TP和AP负载。
当前市场上存在着各种针对特定场景的数据库，这其中有两个趋势推动了这些新数据库的发展，一是利用弹性的云原生架构，像blob存储S3和块存储EBS允许数据库利用几乎无限的、高可用性和持久的数据存储，而弹性计算实例如EC2则允许数据库弹性扩缩容提供更多计算以处理复杂查询或吞吐量峰值。二是开发者需要存储更多数据并以更低的延迟和更高的吞吐量访问数据库，这种性能和容量，访问模式相结合，导致应用程序对数据库的要求非常高。
解决这些要求的常用方法是为应用程序的不同组件使用特定的数据库。相比之下，S2DB团队认为可以设计一个数据库，充分利用弹性云基础设施，同时满足AP和TO负载的需求。这样一个可以处理多种应用程序类型的、集成的、可扩展的数据库对用户有很多好处，能减少成本，减少对开发者的要求等。
本文介绍了SingleStore数据库引擎的架构，作为一个云原生数据库，其擅长在大型数据集（100 TB）上运行复杂的交互式查询，以及以可预测的响应时间运行高吞吐量、低延迟的读写查询（每秒写入或更新数百万行）。相同的SingleStore数据库引擎用于 SingleStore Managed Service（一种云数据库服务）和 SingleStoreDB (S2DB) 数据库产品上。S2DB可以通过仅将冷数据推送到Blob存储并在运行查询时智能地使用本地状态来最大程度地减少网络使用，从而支持减轻存储上的各种工作负载。
对于S2DB而言，有两个部分对AP和TP的云原生负载很重要：
S2DB是一个水平分区、shared-nothing架构的DBMS，同时也可以使用存放冷数据的blob存储作为共享存储。S2DB集群由协调查询的聚合器节点和保存数据分区副本并负责大量查询计算的叶节点组成。每个叶子包含几个数据分区，每个分区要么是提供读写的主副本，要么是只读副本。
表通过一组叫shard key的东西来做hash分区，这使得点读足够快速并且查询形态上也不需要移动数据。当join的条件或者group-by列满足它们引用表的shard keys时，S2DB会将执行下推到各个分区，从而避免任何数据移动。否则，S2DB会在查询期间通过broadcast或reshuffle来重新分配数据。
SingleStore还支持基于中间字节码通过LLVM编译成的native code去查询。
S2DB在内部使用两种存储类型：由无锁跳表支持的内存行存储和基于磁盘的列存储。下文描述的统一表存储在内部结合了这两种格式，以使用单一存储设计支持OLAP和OLTP工作负载。
内存行存储是使用无锁跳表来进行索引的，跳表的一个节点对应着一行，每个节点都会存储行的版本链表，从而实现MVCC，使得读无需等待写。写入使用的是悲观并发控制，通过跳表节点的行锁来处理对同一行的并发写入。除了写入内存的跳表之外，写入操作还会在提交之前将相关的信息写入日志。这个日志也是比较常规的设计，磁盘存储，每个数据库分区一个日志。节点重启时，数据库分区的状态通过重放恢复。后台进程定期创建快照，减少恢复过程中重放日志需要的时间。
列存储表的数据按segment组织，其中每个segment都将不相交的行子集存储为磁盘上的一组数据文件。在一个段中，每一列都以相同的行顺序存储，单独压缩。列的压缩支持多种编码方式，包括bit packing, dictionary, run-length encoding, and LZ4。段元数据存储在持久的内存行存储表中，其中包括文件位置、编码方式和每列的最小/最大值在内的信息，另外还有一个bitvector来表示段中被删除的行。
这种结构主要针对了OLAP进行了优化，为了加快 OLTP 工作负载中常见的点读取操作，每个列编码都实现为可搜索的，以允许在特定行偏移处进行有效读取，而无需解码所有行。存储最小/最大值允许使用内存中的元数据执行段消除，以跳过获取没有匹配行的段。
可以在每个列存储表上指定排序键，以实现更有效的段消除。如果指定了排序键，行将按每个段内的排序键进行排序，跨段的排序顺序与LSM 类似，后台合并则用来增量合并段。
对于每个列存储表，S2DB都会创建一个行存储表作为写入优化存储，这类似于RocksdDB的MemTable，后台线程定期从行存储中删除行并将这些行转换为事务中的列存储段。
另外，列存储表还支持向量化执行，在适当时使用SIMD指令来加速过滤和聚合操作。
S2DB支持带blob存储和不带blob存储运行，对于后者，S2DB就像一个常规的shared-nothing分布式数据库，使用本地磁盘来持久化数据。对于前者则有点不同，S2DB新写入的数据会现在本地持久化，然后异步地备份到blob存储。这种设计使得S2DB的写入延迟更低，并且由于冷数据在blob存储上，也充分利用了blob存储的有点，包括更好扩展，成本更低，容量更大，支持按时间点恢复等。
集群的持久化是通过每个分区的复制实现的，集群内的复制速度很快，log page可以无序复制，无序等待事务提交。默认情况下，当数据在内存中复制到每个master分区中至少一个副本分区时，数据就会被认为已提交。如果一个分区的所有副本都发生节点故障，只有最近新写入的内存中数据会被丢失。默认情况下，S2DB不会将事务同步提交到本地磁盘（是指不同步等log写完再更新memtable？），这是考虑到在云环境中host的损失往往意味着附加的磁盘也会丢失。
下图展示了列存储的表分区数据如何以LSM的形式去表示，顶层是内存行存储，下层是HTAP优化的列存数据。数据写满了，就会被被转换为列存储段，然后flush来创建以log page命名的data files。data files是不可变的，所以如果是从段中删除一行，仅会更新段元数据以将该行标记为已删除。当然这个过程中的所有操作都需要写log。
S2DB的存算分离设计如下所示，概括而言就是：
这种设计的一大优点是，写入事务不需要写Blob，并且Blob的故障不会影响对于热数据的访问（论文认为Blob的可用性远低于其保证的那样）。缺点就是本地磁盘或者内存保存的状态需要一些高性能的复制和恢复协议，并且存算不够解耦，添加或者删除主机都需要移动本地数据。另外就是节点大规模故障会有丢掉还没上传到blob的那部分数据的风险。这个设计更多数的云数据库不大一样，S2DB的节点相对会比较重，并且持久性和可用性会有风险。
这章主要介绍远程存储启用的一些功能作用：
总的来说，S2DB的存算分离即利用了传统云数仓的设计来满足可用性和弹性，并提供几乎无限的持久化存储，也有一定的灵活性来扩展计算能力，并规避了传统云数仓可能带来的写入延迟。
考虑到大多数用户没办法很好决定自己的访问模式是更适合行存还是列存，S2DB提出了一种Unified table storage，简单来说就是基于原来的列存做优化，从而更好地支持TP，并且不会牺牲对于AP的支持。
与常规的LSM实现不同，S2DB在内存中实现了一个bit vector来表示删除，而像RocksDB、Cassandra和BigTable往往是在每一层的LSM使用tombstone entries来表示删除，S2DB的实现避免了merge on read带来的读放大。
与常规的LSM一样，S2DB仍然需要在内存中写入，除此之外还需要修改segment的元数据，来避免tombstone records。需要注意避免对同一个segment的并发修改带来的阻塞。
如下图所示，S2DB还构建了基于LSM实现的二级索引来满足高效的点查。
为了在最小化存储成本的同时支持多列二级索引，S2DB为每个索引列构建一个二级索引，并允许单列索引在引用相同列的多索引时被共享。以对列(a,b,c)构建二级索引为例：
前面两步可以满足对组合索引列子集中某些列的查询需求，第三步则可以直接跳过与所有索引列匹配的行对应的segment，从而加速查询。
大多数列存实现都不支持唯一性约束，S2DB通过二级索引可以满足需求。具体的实现就是在插入之前读一下全剧索引判断是否存在，再根据重复与否来决定用户的行为。
由于针对segment元数据的修改存在并发的可能性，如果是直接使用segment级别的锁会阻止可能上百万行的修改，降低吞吐。因此S2DB实现了行锁机制来降低事务负载，将内存行存储的主键作为lock管理器，其中插入行的副本会锁定行，防止并发修改，然后通过合并事务来降低blocking。
S2DB旨在通过统一的表存储满足ap和tp负载，并使用了倒排索引来提高点查能力，其使用blob存储实现了shard disk的成本、持久性和弹性优势，并且尽量避免了blob存储通常会带来的高延迟、低吞吐量写入事务的问题。
本文提出了一个叫RocksMash的LSM存储，使用本地存储来存放经常访问的数据和元数据，云存储保存其他数据以降低成本效益。
LSM KV存储像RocksDB、LevelDB、Dynamo等已经被广泛应用到了数据库存储系统中。随着云存储的出现，提高效率，出灾速度越来越受到关注，如何设计一个本地存储和云存储混合的存储系统也成为了一个关注的重要话题。然而构建这样的一个存储服务仍然具备不少的挑战：首先是性能和成本，虽然云存储的成本更低数据可靠性更高，但其读写性能都会有严重的下滑；其次是需要开发一种有效的缓存来弥补内存空间不足的局限从而提高性能；最后是可用性的问题，需要尽可能快地从远程存储完成数据的恢复。
本文提出了一个叫RocksMash的系统，结合本地和云存储同时实现高性能和低成本，并保证一定的可用性。RocksMash包含了一个读取优先的数据布局，高效的LSM持久缓存LAP、节省空间且快速的元数据MashMeta以及并行恢复技术。RocksMash是基于RocksDb实现的，通过使用节点的NVMe SSD作为本地存储和AWS Elastic Block Store (EBS) gp2作为云存储。
这一章主要讲述LSM的存储架构，如下图所示主要由多层的sstable组成，从L0到Ln逐层变大。
本地存储和云存储表现出不同的性能和成本，文中提到了云存储能降低八成的成本，但基于本地存储的Rocksdb其读取性能和写入吞吐量都要比云存储高出80倍和4成，因此使用本地存储和云存储的高效LSM存储变成了优先考虑的事。
为了减少对云存储的读取IO，其重要的避免对sstable元数据的访问。如下图所示，在将SQL表数据映射到各种数据库中的键值存储时，这些复合键的公共前缀是很常见的。此外，LSM存储压缩操作进一步巩固了sstable中键之间的前缀相似性，因此这使得底层sstable中的键倾向于共享更长的前缀。在这种情况下，sstable中的索引键本质上是索引具有高相似性的排序字符串，并且越底层的sstable共享了更多前缀。
由于原生WAL不会记录各层的所有数据，如果云实例失败然后走正常的恢复流程，则存储在本地存储中的从L0到Li的sstable将丢失。简单地扩展WAL以包含从L0到Li sstables的数据非常低效的，一是耗时很久，二是replay导致重复compaction进一步加大写放大，因此论文提到的做法是直接构建sstables，而不是通过WAL间接恢复。
RocksMash将LSM的上面i层放在更快成本更高的本地存储，其余部分则由云存储维护。由于上层比下层数据更少访问更热，LSM的顶层放在本地存储进一步降低了操作的耗时。
下图是RocksMash的存储架构，内存用仍然保留了原始的LSM MemTable，此外还使用了细粒度的LAP缓存来进一步减少对云存储的访问。LAP缓存分为MetaCache和DataCache， 由于元数据相比LSM的访问频率更高，因此MetaCache会存储云上sstable的元数据块，而DataCache则将精彩访问的数据块缓存起来。
下图描述了写入和读取的请求处理，写入请求基本与常规的LSM处理流程一样，但在触发compaction的过程中，RocksMash会讲sstable的元数据插入到本地存储的LAP MetaCache中。而对于读请求，从依次从L0层到LN层搜索候选sstable，如果要读取的sstable在云存储上，则将block读到LAP DataCache以供访问。
LSM存储支持使用SSD来作为持久化缓存，以此在内存不够时尽可能提高读性能。如上图所示，rocksdb的持久化缓存包含了多个缓存文件，这些文件以LRU的形式组织，一个kv对在读不到的情况会从磁盘加载到rocksdb的持久化缓存中，即append到CacheFile i+1中。如果可写的缓存文件满了，则通过LRU的策略逐出。这个实现存在一个文件，即持久化缓存并未感知compaction，比如上图，sst被压缩后kv3和kv1已经无效了，但仍存留在文件中导致大量的浪费和所需键被过早逐出。
RocksMash的解决方法是在本地存储上使用LSM-tree- aware持久化缓存LAP。LAP分为MetaCache和DataCache。MetaCache存粗云上sstable的所有元数据块，避免远程的元数据访问，MetaCache将这些元数据分组并使用哈希表去做管理。DataCache则是一种能感知compaction的缓存，用于存储热数据块来加速读请求。如上图所示，存储在DataCache的kv对被组织称LRU列表，无效的kv对则通过位图标记失效，而加载数据到DataCache则可以直接覆盖那些无效的kv对。
这一章主要是介绍为了提高缓存空间效率，RocksMash使用了一种叫MashMeta的succinct
tree的技术，从而为每一个云存储的sstable构建一个压缩前缀树。这种trie能以深度优先的一元度序列进行编码，下图就是一个样例。本质是为了以最小的空间消耗避免filter的误报，提高对每个key的精准查询速度。
基于RocksMash的布局设计，快速恢复对存储在鼓掌节点本地存储上的sstable访问是非常重要。这里假设云存储的sstable是可靠的，WAL文件则存储在快速且专用的云存储上，然而由于本地存储的sstable数据相对WAL来说较小，从大量WAL文件快速恢复会使得这个设计变得更加困难。
一般的恢复方法如下图所示，按顺序重做写入操作，但这种逻辑对于大型数据集的效率很低，因为WAL的每一个kv对都会写入一次，并经过memtable一步一步flush下来，产生更多的写放大。
因此RocksMash提出通过并行化恢复L0到Li的sstables来解决效率问题，这里仍然存在两个挑战：
如上图所示，RocksMash扩展了WAL以包含从L0到Li的所有sstable数据，当生成这些sstable时，RocksMash会讲更改记录到MANIFESY，然后将其key列表同时记录到WAL以便能连接到sstable。因为除非所有新的sstable都成功持久化，否则compaction不会被认为是完整的，所以RocksMash可以批处理新sstable的键列表以减少写入它们的I/O数量。这样，RocksMash可以确保安全回滚到与 MANIFEST 和key列表一致的最新状态，并且不会丢失任何有效数据，
逆时间顺序搜索：RocksMash为每个需要恢复sstable分配一个worker，每个worker由新到旧搜索WAL，这种方式能LSM存储的读取路径首先读到key的最新版本。通过逆顺序搜索WAL，RocksMash进一步减少WAL的读取数量。
并行构建sstable：当实例节点发生故障时，RocksMash使用新实例将恢复原来存储在故障实例中的L0-Li sstables。 RocksMash读取MANIFEST和扩展的WAL以获取最后一致状态的sstable文件列表。 RocksMash然后借助key列表从扩展的WAL中并行重建这些sstables。下图是具体的步骤
经过以上步骤，RocksMash就完成了将故障实例的内存和本地存储中的数据恢复到最新的一致状态，并大幅度减少了恢复重建的时间。
本文集中研究了集成云存储会如何影响LSM存储的性能，由于存储成本的问题，云存储的性能上限严重影响了读取性能，因此提出了一种快速高效的LSM存储RocksMash。RocksMash可以将LSM tree在本地存储和云存储之间进行拆分，从而在成本和性能之间达到平衡。此外，为了减少元数据的内存占用并提高读取性能，RocksMash使用能感知LSM结构的持久缓存，并以节省空间的方式（succinct tree）存储元数据，并使用了能感知压缩情况的缓存来存储热数据块。为了实现快速并行的数据恢复，RocksMash还扩展了WAL的使用。
RocksDB是一个针对大规模分布式系统的kv存储，并针对SSD的特性进行了优化。本文描述了在过去八年中RocksDB的开发过程。这种演变是硬件趋势的结果，也跟许多组织大规模使用RocksDB有关。本文描述了 RocksDB的资源优化目标是如何以及为什么从写放大转变到到空间放大，再到CPU利用率。通过一系列的使用经验总结得知，资源分配需要跨不同的RocksDB实例进行管理，数据格式需要保持向后和向前兼容以允许新软件推出，并且需要对数据库复制和备份的进行支持。故障处理的经验则可以归结为需要在系统的每一层及早发现数据损坏错误。
RocksDB起源于LevelDB，并针对SSD的一些feature做了定制优化，同时也会被设计成可以嵌入到其他系统的KV库，每个RocksDB节点只管理自己的数据，相互之间没有交互。RocksDB在Database、Stream processing、Logging/queuing services、Index services等领域都有一定的应用。使用RocksDB作为底下的存储引擎也有利有弊，弊端在于每个系统都需要在RocksDB之上处理好一系列复杂的failover recover的操作，优势则是可以复用很多基础功能。下图是针对不同应用特性的总结和负载相关的信息：
基于flash特性的考虑，RocksDB在设计上采用了flash友好的数据结构，并对当前的硬件进行了优化。
由于flash-based SSD的发展，提供了更高吞吐和更低延迟的设备，使得软件设计需要考虑如何充分使用期全部功能。SSD提供了数十万IOPS和数百MB的带宽，在很多场景下使得性能瓶颈从IO转移到了网络，这就增加了对嵌入式kv存储引擎的需求，RocksDB就是如此应运而生的。
LSM tree是RocksDB存储数据的主要数据结构。
本章描写了RocksDB的资源优化目标：从写放大到空间放大，再到CPU利用率。
一开始RocksDB主要关注如何节省flash- based SSD的擦拭次数来减少内部的写放大。这里的写放大主要集中在两个方面，一是SSD本身的写放大（1.1-3），二是软件自身的写放大，有时可能会到100，比如小于100Bytes的修改也需要写入一个4K/16K的页。
Leveled Compaction在RocksDB中通常会引入10-30的写放大，虽然Tiered Compaction能将写放大降低到4-10，但这也降低了写性能。如下图所示：
RocksDB通常会选择一种自适应的压缩方法，写频率高时减少写放大，写频率低时更积极地压缩。
再到后面考虑到flash的写周期和开销都没有做限制，Space amplification的问题会更加明显。RocksDB的策略是Dynamic Leveled Compaction，即LSM中每个Level的大小会根据最后一个Level的实际大小自动调整，而不是更死板的设置每个level的大小。
有一些观点会认为性能瓶颈已经从SSD转移到了CPU上，但该论文并不认为这是一个问题，一是因为只有少部分应用会被SSD提供的IOPS所限制，大多数应用还是受限于空间；二是任何具有高端CPU的服务器都有足够的计算能力来饱和一个高端SSD。但同时论文也认为减少CPU开销是一个很重要的优化目标，这是因为减少Space amplification已经做得差不多了，而提高CPU利用率可以尽量优化成本。论文提到的关于CPU优化的努力包括引入prefix bloom filter和其他bf的改进。
论文提到了RocksDB发展过程中采用或考虑过的一些新技术。
目前得出的结论是LSM tree仍然是更适合SSD的存储引擎，用CPU或DRAM交换SSD也不是一个普遍的现象。当然RocksDB在发展过程中也不断收到用户关于降低写放大的需求，当对象很大时，可以通过key value分离来减少写放大，RocksDB也添加了BlobDB作为相关的支持。
RocksDB作为需求各异的大型分布式系统的基石，也需要在包括资源管理、WAL处理、文件批量删除、数据格式兼容和配置管理方面进行改进。
大规模的分布式系统通常需要对数据进行分片，每个分片分布在多个存储节点上，并且需要限制大小，因为考虑到需要进行备份和负载均衡，同时也会由于原子性做一些一致性的保证。一个RocksDB通常只会对应一个分片，因此一个节点上可能会运行着多个RocksDB实例，这就对资源管理有一定的影响。共享主机的资源，则需要对资源进行全局的管理，以确保能公平使用，这里的资源管理包括：write buffer和block cache的内存使用、compaction的IO带宽、compaction的线程数、磁盘使用情况、文件的删除比例等。为了确保单个实例不会占用过多资源，RocksDB为每种类型的资源都提供了若干个资源控制器，同时也会支持一些优先级策略。
另一个运行多实例的教训是，大量的非池化的线程可能会给CPU带来过载，因此论文建议若需要使用一个可能会休眠或等待某个条件的线程来执行一些工作，最好使用一个线程池，便于限制线程的大小和资源使用。
考虑到每个分片只有局部的信息，当RocksDB运行在单进程里时，全局的资源管理将会变得更加困难。这里可以采用两种策略：为每个实例配置更为谨慎的资源使用；让实例之间共享资源使用信息，并进行相应的调整。
传统数据库倾向于在每个写操作都强制执行WAl，而大规模的分布式系统为了可用性和性能，往往会通过各种一致性保证来做到这一点，比如从其他正常副本重建本机的损坏副本，或者通过自己的复制日志（比如分布式系统通常会有的Paxos日志等），这种情况下一般不需要RocksDB的WAL。
考虑到这点，RocksDB提供了不同的WAL操作模式：同步WAL写，缓冲WAL写，不进行WAL写。
RocksDB通过文件系统与底层设备交互，每当删除文件时，可以发送TRIM命令到SSD，这会改善SSD性能和Flash性能，但也会引起性能问题。这是因为TRIM会更新地址映射，并且还需要将修改写入带flash的FTL日志，这会进一步触发SSD内部的GC，并进一步对IO延迟造成负面影响。因此RocksDB引入了文件删除的速度限制，以防止多个文件同时被删除。
这一章主要讲RocksDB需要确保数据格式的前后兼容，这样在一个大规模的分布式应用中，可以逐步灰度设计各个实例，也方便在出现问题时进行回退。
关于配置管理的方面，RocksDB具备高度的可配置性，但原来继承自leveldb的方法将参数选项嵌入到代码中，也容易造成以下两个问题：参数配置通常与存储在磁盘的文件强绑定，当使用一个选项创建的数据文件可能无法被新配置了另一个选项的RocksDB实例打开，这会带来兼容性的问题；当RocksDB更新时可能会改变默认配置参数。为了解决这些问题，RocksDB引入了对随数据库存储选项文件的可选支持，同时也加入了一些验证和迁移工具来对不同配置进行兼容。
高度的可配置性带来的另一个问题就是配置参数过多，难以针对不同类型的应用进行选择。因此RocksdDB在改进开箱即用性能和简化配置上花费了大量的功夫，并尽可能提供自适应的配置。
RocksDB作为一个单节点存储引擎，分布式系统通常会有复制和备份的需求，因此RocksDB也需要对此进行支持，基于已有副本生成新副本的方式有两种：扫源副本的所有数据，然后将其写入目标副本；直接物理复制sstable和其他需要的文件来建立一个新的副本。
基于生产环境的经验，论文提到了三个关于故障处理的教训：尽早检测到数据损坏；数据完整性保护需要覆盖到整个系统；错误需要以不同的方式进行处理。
基于性能的考虑，RocksDB不实用SSD的数据保护（如DIF/DIX），而是通过RocksDB的block checksum进行校验和检测。CPU/内存的损坏很少发生，并且也很难量化。使用RocksDB的应用程序经常会进行数据的一致性检查，比较副本间的一致性，捕获的错误可能是由RocksDB或client引入的。另外传输数据时也会发生数据损坏，比如处理网络故障时，底层存储系统的错误会在一段时间后显现出来，每PB级别的物理数据大约会有17个checksum miss。
越快检查到数据损坏可以尽可能减少停机时间和数据丢失，对于分布式系统而言，当检测到checksum miss的时候可以丢弃损坏的副本，然后用正常的副本做替换。如下所示，RocksDB进行了多层的文件数据校验，并同时使用了块校验和文件校验。
到目前为止，文件IO层以上的数据还是缺乏保护的，例如MemTable中的数据和块缓存，此级别的损坏数据无法检测，会进一步暴露给用户，也会因为flush和compaction导致损坏被持久化。为了解决这个问题，RocksDB正在为每个kv对实现checksum。
RocksDB遇到的大多数错误都是底层存储系统返回的错误，比如文件系统只读，访问远程存储的网络问题等。因此RocksDB的目标是在错误不能在本地恢复的情况下中断RocksDB的操作，比如网络错误时进行周期性重试恢复，而不需要用户手动重启。
KV接口的用途非常广泛，几乎所有的存储系统都可以通过一个KV接口的API来提供存储服务，其是通用的，key和value都是变长的字节数组，由应用程序决定如何打包信息和如何进行编码解码。
尽管如此，KV接口还是存在一些限制，比如构建并发控制等还是有需要考虑的东西。RocksDB已经意识到了数据版本控制的重要性，也规划支持合适的功能，如MVCC和point in time read等。
本文很像是一个综述，主要是把RocksDB相关的一些问题和开发设计思路进行了总结，包括写放大、空间放大，CPU利用率提高、remote storage等，同时也提到了开发过程中的一些反思，包括数据格式的前后兼容，如何支持数据库的备份和复制，简单化配置系统等。总而言之，这是一篇总结类的工业论文，非常适合进一步学习RocksDB。
无界、无序、大规模的数据集在日常业务中越来越普遍，并且，这些数据的消费端也发展出更复杂的需求，例如事件时间排序和数据本身特征的窗口化等，以及对消费速度有了更高的要求。本文介绍了Google在数据流模型的核心设计原则
现代的数据处理是一个非常复杂且发展蓬勃的领域，从MapReduce到SQL社区内大量关于流的工作如窗口、查询系统等，再到Spark Streaming、Storm等低延迟领域的发展。然而，现有的模型和系统在许多常见场景中仍然存在不足。批处理系统会遇到导入系统带来的延迟问题，而对于流处理系统，要么缺乏大规模的容错机制，要么缺乏提供exactly-once语义的能力影响数据准确性，又或者缺少窗口所必需的时间原语等等。Lambda架构可以满足很多需求，但由于必须和构建两套系统就会带来简单性的不足。论文提出的观点是，不再关注执行引擎决定系统语义的主流思维，而是通过考虑批处理，微批处理和流传输系统之间潜在的差异（即延迟和资源成本）来选择执行引擎。
本文提出了一个简单统一的模型概念：
具体而言可以分为以下几个部分：
Dataflow统一用Bounded/Unbounded Dataset来描述有限/无限数据集，而Streaming/Batch则用来特指某些执行引擎。
Window即窗口化，是指将无限的数据集切分为有限的数据片以便进行聚合处理。对于无边的数据集，有些操作如aggregation，outer join，time-bounded都需要窗口。窗口一般是基于时间的，但也有些系统支持基于记录数的窗口，这可以理解为是逻辑时间，其中的元素按顺序依次增加逻辑时间戳。
窗口模型主要由三种主要分为以下三种：
在流式处理中有两个关于时间的概念需要重点关注：
在数据处理过程中，由于系统自身收到的影响如通信延迟，调度算法，处理时长，管道中间数据序列化等，会导致上述两个值之间存在一定的差值，诸如punctuations或watermarks之类的全局进度指标都提供了一种可视化这种差值的好方法，本文则是使用了一种类似MillWheel的水位标记，这是一个时间戳，用来表示小于这个时间戳的数据已经完全被系统处理了。理想情况下，这两个时间的差值应该为0，即事件一旦发生则马上做处理，如下图所示。但实际上，由于前面提到的原因，水位标记会偏离真实时间，这是非常正常的现象。
接下来将讨论Dataflow的正式模型。
首先从经典的批处理模型开始，Dataflow把所有的数据都抽象成键值对，并提出了两个核心的数据转换操作：
支持GroupByKey的系统通常会将其重新定义为GroupByKeyAndWindow，Dataflow在这里的主要贡献是支持未对齐窗口，其底层的优化则是通过下面两部来实现：
为了在本地支持事件时间的窗口，这里不再是传递简单的键值对，而是传递(key, value, eventtime, window)4元组。元素进入系统时会带有事件时间的时间戳，并且在最初会分配一个磨人的全局窗口。
窗口赋值就是指将数据拷贝到对应的窗口。下图就是一个窗口大小为2分，滑动窗口间隔为1分钟的例子。
窗口合并是GroupByKeyAndWindow操作的一部分，具体来说这是一个由五部分组成的复合操作：DropTimestamps、GroupByKey、MergeWindows、GroupAlsoByWindow和ExpandToElements，其具体的含义可以参考下图：
能够构建未对齐的事件时间窗口是一种进步，但仍面临两个问题：
论文这里主要讨论第二种情况，就是如何保证窗口数据的完整性。最原始的想法是使用某种全局事件时间戳，比如watermark来处理，这里可以立即为一个阈值，但watermark设计的过长过短对数据处理的准确性会有一定的影响，过短会导致水位标记到达后仍有记录到达，过长则可能会使得迟到的数据影响到整个数据处理管道的watermark。
Dataflow的处理方法是用一种叫Trigger的机制，这种机制是受信号激励从而触发GroupByKeyAndWindow执行并输出结果的机制，相对于窗口是决定哪些event time数据被分到一组进行聚合操作，Trigger更多是决定在什么处理时间窗口的结果会被输出。Trigger提供了三种不同的模式来控制不同计算结果之间是如何关联的：
无边界的数据时数据处理的未来，有边界的数据本身也是由无边界的对应部分所包含的，并且处理数据的消费者进化的越来越快，因此需要更强大的架构支持例如事件时间顺序和未对齐的窗口等。Dataflow模型把数据处理的逻辑划分了以下几个部分：计算什么、在哪个event time范围内计算、在什么处理时间点触发计算，如果用新的结果修正之前的处理结果，这使得整个数据处理逻辑变得更加透明清晰。
Mesa是一个可扩展的分析型数据仓库，可用于存储Google广告业务相关的数据，能满足多数据中心、高可用、近实时等特性。
Mesa满足了以下的要求：
Mesa充分利用了Google内部的基础设施，包括Colossus、BigTable和BigTable等。Mesa主要是分shard存储，批量更新，每个更新分配一个版本号来满足MVCC，同时基于Paxos算法做元数据的一致性管理。
Mesa存储的数据是多维度的，其中维度属性称为keys，指标属性则是values。
Mesa的数据是以表的概念来维护的，每个表都会有一个schema。通常来说，表会有key空间和对应的value空间，分别就是前面提到的维度和对应的指标。同时values列需要定一个聚合函数，例如SUM、MIN、MAX等。聚合函数必须满足结合律，可选择性满足交换律。Mesa往往会存储上千张表，每个表有几百个列。如下图就是三张经典的Mesa表，其中表C是表B的物化视图：
为了实现高吞吐，Mesa是通过批量的方式进行更新，上游数据源以分钟级的频率批量更新。每一个更新都有对应的一个递增版本号，更新以串行的方式进行。因此对于Mesa的查询需要提供版本号和Predicate，这样就可以在[0, n]的版本key集合里做filter。
如下图所示，表A和B经历了两个更小的Batch，其中表C是B的物化视图，B的更新，对应的物化视图都能保持和原表的一致性原子更新。
另外对于一些数据会滚的需求，Mesa支持negative facts，则对一些指标列做减法，以最终一致的实现来实现会滚。
数据版本在Mesa的读写过程中扮演着非常重要的角色，但也存在一些问题，一是存储成本会变高，二是无论查询还是更新，聚合所有版本的代价也会比较高。
Mesa的做法就是提出Delta的概念，每一个Delta包含的是不重复key的数据，并使用[V1, V2]表示版本号，V1小于或等于V2，其中的数据就是在版本号V1和V2之间更新的key，value则是这些更新操作聚合后的。另外由于每个delta内部数据都是有序的，因此合并可以以线性的时间完成。
Mesa对于delta的结构分成了三层：每次批量写入都会当作是一个单例delta合并到Mesa，单例delta的V1等于V2。因为Mesa对于指标列都会有相关的聚合函数，因此delta[V1, V2]和delta[V2, V3]可以通过合并key、聚合value的方式合并成delta[V1, V3]，这些就是cumulative delta。另外还存在一个base delta，设它的版本号为[0, B], 其中B大于或等于0，生成base delta，后续任意一个[V1, V2]只要满足0 <= V1 <= V2 <= B就可以被删除（唯一的删除条件），这就是异步的base compaction。这也是为什么Mesa仅仅支持一段时间以内的所有版本，比如24小时内的，因为更早的版本已经可能被聚合到base delta里。
如下图，对于版本n的查询，就可以通过聚合这三层的delta来返回值。任何时刻都存在一个基本delta[0, B], 一系列的累积delta[B+1, B+10], [B+1, B+20],[B+1, B+30],...以及B以后的所有单例delta。这样的好处就是，对于某个版本n的查询，可以方便通过查询cumulative delta来减少IO开销。举个例子，如果查询版本91的数据，在没有cumulative delta的情况下，就需要查询61-91这32次的delta；如果存在cumulative delta，则只需要一次base的查询，61-90的cumulative，外加91这一个单例delta。
Mesa的解决思路总结起来就是：及时删除过期数据，merge小文件。
Mesa的delta，无论哪些类型其存储格式都是一样的，并且都是immutable。因此Mesa关于物理数据的存储主要关注空间成本以及查询性能。关于存储，论文没介绍太多细节，主要是分成index files和data files。Mesa将delta的行按顺序存储在大小受限的data files中，若干行的数据会组织成一个row blocks，每个row blocks则是按照column进行存储（提高压缩率，并且因为查询性能的问题优先考虑解压效率高的）。Index files存储的则是row blocks第一个key的固定长度前缀以及对应row blocks在data files中的偏移量，然后就可以将index files加载进内存通过二分查找去读数据。
每一个Mesa实例都包含了两个子系统：update/maintenance系统和querying系统，这些子系统可以独立扩展。元数据信息存在BigTable里，数据文件则是存在Google的Colossus。
update and maintenance子系统主要负责以下的操作：加载更新数据、执行表压缩，在线进行Schama修改，检查表的checksum等。这些操作都是由下图的controller/worker framework完成的。
controller可以看作是表元数据的cache，同时负责worker的调度，worker队列的管理。controller不做任何数据相关的工作，只负责调度和元数据管理。元数据存在BigTable上，controller会去订阅表的更新，同时也是元数据唯一的修改方。
worker组件则是负责在每个Mesa实例中的具体数据操作工作，不同的worker是隔离的，有自己独立的职责，有一组独立的worker池。空闲的worker会定期轮询controller，请求对应类型的任务，收到工作任务后，会去验证并处理，最后则在任务完成后通知controller。图中还有一个Garbage Collector，主要是负责清理因为worker执行失败而留下的中间状态数据。worker与controller之间通过租约的方式，防止挂掉的worker一直霸占着任务，同时controller也只接受分配的worker的任务结果，确保执行安全。
Mesa的query subsystem由下图的查询服务器组成，这些服务器接收用户查询、从元数据和数据集中查找对应内容、执行相关聚合、并在返回client前将数据转换到client协议格式。
Mesa的客户端对不同的请求有不同要求，有些要求低延时、有些要求高吞吐。因此Mesa会通过标记工作负载和隔离、优先级等机制来满足不同的延迟和吞吐量要求。
出于性能的考虑，相似的数据查询往往会路由到某个查询服务器的子集（比如同一张表的查询都由某一批查询服务器负责），这样做的好处就是，查询服务器可以通过预取和缓存的方式来提供低延时保证。在启动时，每个查询服务器都会向Global Locator Service注册所主动缓存的表列表，client可以通过这个列表来决定如何路由。
Mesa可以多中心部署，每个数据中心是相互隔离的的，有一份独立的数据。
Mesa中的表都是多版本的，上游系统每几分钟生成一批更新数据以供Mesa合并，如下图，Mesa入了committer组件引入了committer组件。committer为每个更新批次分配一个新版本号，并将与更新相关的所有元数据发布到版本数据库（a globally replicated and consistent data store build on top of the Paxos consensus algorithm），应该就是spanner或者F1。committer是无状态的，可以多中心部署。
Mesa的controller会监听版本数据库，以检测新更新，然后将相应的工作分配给Update workers，并将更新结果报告回版本数据库。然后committer会检查verion提交的一致性条件是否满足（例如Mesa表的物化视图是否已经更新完成）。当满足提交标准时，committer将在版本数据库里更新版本号。
Mesa的更新机制对性能非常友好：MVCC使得Mesa不需要在查询和更新之间无锁；所有更新数据都由各Mesa实例异步合并，元数据则基于Paxos协议同步更新。
Mesa会使用P2P的方法，通过一个load worker去加载新的Mesa实例，可以将表从另一个Mesa实例复制到当前的表。另外这一机制也支持从损坏的表中恢复。
论文中心还提到了Mesa关于查询性能的优化：
Mesa利用MapReduce框架来并行化处理worker任务。
Mesa用户经常需要修改schemas，一些常见的更改比如添加或者删除列、添加或删除索引等。Mesa使用两种技术来执行在线的schemas变更：
但这种方法成本很高，需要临时存有两份存储资源，也需要删掉历史数据。另一种技术则是linked schema change，不再是重新灌一遍历史数据，而是对增量数据以新的schema处理。如果是新加的列，对于历史数据则以数据类型的默认值填充。但这种方法无法处理所有情况：比如删除修改列等。
这一章主要是讲Mesa在容错方面的努力，通过在线写入的检查和定期离线的全量检查来确认数据不会有损坏。当出现数据损坏时，Mesa实例会自动从另一个实例重新加载该表的正常副本。如果都损坏了，则从备份中恢复旧版本的表并重放更新。
本文介绍了Google近实时、可扩展的数据仓库的设计与实现——Mesa系统。Mesa支持在线查询和批量更新，同时提供强大的一致性和事务正确性保证，并且在数据模型上有非常创新的理论设计。
Google产生的大量应用数据，需要有一个可扩展性强、响应时间短、可用性高和强一致性的存储提供服务。Napa就是Google用来满足这些要求的系统，其核心的数据就是使用一致的物化视图。
Napa其实是用来替代Google另一款OLAP产品Mesa的，并且从Mesa迁移了PB级的历史数据，与Mesa相比，Napa的设计需求更为广泛：一是更稳定的查询性能，期望毫秒级的低查询延迟和无论集群负载如何延迟相对稳定；二是更灵活，支持用户根据需求在查询性能、数据新鲜度等方面进行取舍；三是数据写入高吞吐，在海量更新负载下，Napa实现了一个LSM范式的分布式表和视图维护框架。
这一章主要是将Napa的设计过程中考虑了哪些关键目标，最理想的情况当然是以尽可能低的成本实现最高的查询性能和最高的数据新鲜度。数据新鲜度是通过将数据添加到表的时间点到可用于查询的时间点之间的维度来衡量的，而成本则主要是数据处理和存储所需要的机器资源成本。
这一个前面也说了，Napa需要支持client在下面三个因素（数据新鲜度、资源成本和查询性能）之间进行权衡选择。
一个重要的考虑点在于数据写入和当前存储是否耦合，如果将新的数据和当前存储结合起来，这意味着数据的写入只有只有在应用到表及其所有视图后才会提交，这是Mesa的设计，但有一个比较大的缺点，即额外添加视图会导致数据写入变慢，这种设计虽然提高了查询速度，但牺牲了一定的数据新鲜度。另一种就是视图的生成可以作为查询的一部分选择性地完成，维护视图的异步模型会在一定程度上影响表及视图之间的一致性。
因此Napa需要提供一个灵活的client，以便随时调整系统对于这些目标的需求。
Napa中的一个关键设计选择是依靠物化视图来实现更高的查询性能。Napa的主要架构由下图三个组件组成：
Napa将数据写入、视图维护与查询处理进行解耦，允许client根据自己的需要在数据新鲜度、性能和成本之间进行权衡。
Napa会将client在数据新鲜度、查询性能和成本方面的要求转换为对应的数据库配置、比如视图数量、写入任务的quota限制、查询期间的最大打开delta数量等等，这是一个动态但易于理解的数据库状态指示器。
为此Napa引入了称为可查询时间戳 (QT) 的概念。QT是数据新鲜度的直接指标，因为[Now() - QT]表示数据延迟，客户端可以查询到 QT 时间戳之前的所有数据。下文就介绍了三类Napa client以及系统如何使用QT来调整Napa。
关于数据可用性，Napa的做法是将数据和元数据操作解耦，在数据中心的每个副本上异步执行数据操作，并定期在Spanner使用元数据操作以确保副本彼此保持同步，确保副本之间的一致性，将同步和异步的模式进行组合。
如下图，Napa的架构由数据平面和控制平面组成，数据平面则是由上述的数据写入、存储和查询服务组成的。控制平面则负责协调各个子系统之间的工作，多个数据中心同步和元数据事务。
Napa大量依赖了Google现有的基础设施，比如Napa的表数据就是存储在Colossus文件系统上、Spanner负责元数据管理和系统状态存储、F1 Query则用来做查询服务和大规模的数据处理。
Napa客户端使用ETL管道将数据写入表中，数据摄取框架可以承受高达数十GB/s压缩数据的负载。同时，Napa的存储组件通过压缩表和视图的delta，创建更大的delta，从而减少在线查询期间的合并操作。查询服务则在运行时进行必须要缓存、预取和合并Delta的操作，提供低延迟和稳定的查询，前者是通过查询定向到预先计算的物化视图实现的，后者则是通过控制compaction和一些系列IO优化技术来减少长尾。
Napa依赖视图作为获得良好查询性能的主要机制，包含物化视图的Napa表按其主键进行排序、索引和Range分区。与现有数据库更多倾向于使用Scan的查询处理不同，Napa考虑到负载和查询性能等要求，最终选择了按索引key查找，当然这可能会带来热点和负载均衡等问题，但论文中并没有详细讲述如何应对的。
Napa的控制平面则调度compaction和视图的更新任务，以控制表的deltas保持在一个配置值。如前所述，QT构成了数据新鲜度的基础，查询系统使用它来提供稳定的查询性能。如果数据相对落后了（写入慢了），Napa会通过牺牲查询性能来将写入速度拉回到一个合理的配置值。
数据写入框架的目标是允许写入管道在没有显着开销的情况下将大量数据写到Napa中。该子系统的目标是接受数据、执行最少的处理并使其持久化，而不考虑后续视图维护的速度。如下图所示，所有写入的行都会被分配一个元数据时间戳用于排序，然后在满足其他持久性条件（例如复制）后标记为已提交。其次，该子系统允许通过配置增加或减少批处理、聚合复制等worker数量的方式来控制机器成本。
客户端将要写入的数据发送到所有的Napa副本，该框架会产生写入优化的delta，但不能立即用于查询。这些就是unqueryable delta，需要在可查询前将它们进行压缩。
表的可查询时间戳（QT）是一个时间戳，它表示可以查询的数据的新鲜度。假设QT(table) = X，则client可以查询到时间 X之前的所有数据，并且时间X之后摄入的数据属于不可查询数据的一部分，即一个表的新鲜度是[Now() - QT]。一旦在(Y-X)时间范围内写入的数据经过优化后满足了查询性能要求，QT的值将从X变成Y。因此client可以使用Napa的配置选项和这个指标来调整新鲜度、查询性能和成本。如果client想要高查询性能和低成本，但可以牺牲数据新鲜度，则系统优先使用较少的机器资源进行视图维护以降低成本，QT的推进则变得缓慢。
确保更高查询性能的一个重要方法是优化读取的基础数据并确保视图可用以加快查询速度。Napa中的表是其所有delta files的集合，每个delta对应于在一个时间窗口内为该表接收的更新，如下图所示，不可查询的delta对应于最近写入的数据。每个delta都按key排序、范围分区，并具有类似本地B树的索引，在查询时合并需要读取的delta。
一般client查询都会有严格的延迟限制，通常会在查询期间对打开和合并读的最多delta做限制，通常会限制不超过数十个delta，并且会根据对数据的查询性能做自动设置。通过保持给定数据库的增量数量接近恒定，Napa能够提供强大且稳定的查询性能。
QT本质上会依赖于后台操作如compaction和视图维护的进度。数据库的QT是数据库中所有表的QT的最小值。 另外，QT还用于为client提供跨所有Napa副本的一致数据视图。每个副本都有一个局部QT，它基于本地副本中数据的新鲜程度的得出的。 QT的全局值则是根据查询服务可用性要求从本地QT值计算出来的，实际就是一个基于Quorum机制的选择。
Napa的存储子系统负责维护视图和delta的compaction，其目标是能有效地管理数千个表和视图，并且数据量通常是PB级的。但视图维护遇到的一个困难是，基表的更新转换为视图更新的过程中，由于key空间的映射带来的数据倾斜问题。另外就是由于数据库的QT往往会受到长尾视图的影响，因此Napa利用了下面的技术来解决视图维护的问题：
Napa的视图维护过程有效地利用了输入中的数据属性，由于处理的数据量和特定数据属性使大规模查询处理变得更复杂，视图更新必须解决独特的优化挑战。数据属性的一个例子就是要更新的视图相对于基表的排序顺序。如果基于视图排序顺序对视图key重新排序，这可能会是一个非常昂贵的方案，而尽可能维护输入顺序反而是低成本。因此如下图所示，根据维护它们的成本，存在三类视图：
压缩将多个输入delta组合成一个输出delta，异步压缩能有效减少查询时的合并负载，但对于高频写入的表来说，压缩是非常高的代价，会使得数据新鲜度变低。由于delta files是单独排序的，因此压缩本质上是归并排序。合并过程会在各种输入之间分配固定的内存预算，因此输入越多，每个输入流的内存越小，并且当其中一个输入被消耗完时，归并过程将停止。因此大型的归并会使得发送归并终止的可能性越高。
维护较低的查询性能是业务使用的关键，本节主要讲Napa如果使用QT、视图等一系列技术实现强大的查询性能。
这里主要讲了几点：
Napa是Google新一代的OLAP系统，具备高可用性，并且与其他数据库依赖列存储、并行、压缩等方式不同，其强依赖物化视图提供了更好的查询能力，同时允许client自行在数据新鲜度、查询延迟和成本之间进行权衡选择，总体而言是一篇非常具备启发性的OLAP论文。
Greenplum是一个老牌的、基于MPP架构的数据仓库系统，主打的OLAP功能，采用了share nothing和sharding的架构，能够处理PB级别的数据。Greenplum存在一个固定的coordinator节点，负责与client交互，查询计划的生成与分布式执行、事务的管理等，是一个比较重要的节点。其他segment节点（单机Postgres）则存储数据与本地查询和事务。为了增强Greenplum的OLTP能力，往HTAP的方向发展，论文中提到了Greenplum对以下几个方面进行了增强：
从某种角度来说，Greenplum演变成HTAP数据库的路径与大多数数据库不一样，它是在传统的OLAP数据库上加强了OLTP功能的支持。
GreenPlum是一个典型的MPP架构，集群由多个worker segments组成，每个segment都是一个增强版的PostgreSQL。下图就是GreenPlum的架构。
一个GreenPlum集群由许多个跨主机的segments组成，其中会有一个segment是coordinator，其他的统称为segment server。coordinator是一个比较重的节点，负责接收client请求，生成分布式查询计划，根据计划生成分布式进程，将计划分配到每个进程，收集结果，返回到client。
segment server则是存储数据，从coordinator接收查询计划。为了提高可用性，segment也可以配置镜像节点，不参与计算，但会接收WAL并回放日志。
作为一个share nothing的架构，GreenPlum中每个segment都会有自己的共享内存和数据目录。
由于是share nothing的架构，当两个表需要进行join时，通常需要检查不同的segment server的元组是否满足条件，免不了需要在segment server移动数据。GreenPlum引入了一种叫Motion的算子来实现移动。Motion算子会通过网络来接发数据，Motion算子将查询计划切成不同的slice，在slice之间会做数据的分发，每个slice的执行都由一组特定的worker负责，这组进程就是gang。coordinator将查询计划分配个跨集群的进程组，不同的segment server生成不同的进程，都有相关的上下文信息。
如下图，顶部是一个join的分布式计划，下方则是在两个segment server集群的执行过程。在segment server上有两个slice，一个slice会扫描class表并通过redistributed Motion发送元组，两个slice则是从Motion节点接收元组，并扫描Student表执行hash join，将结果发送至顶部的coordinator。
Greenplum通过分布式快照和2PC来确保ACID属性，在单个segment节点上，则是Postgres原生的事务机制。
Greenplum支持三种表类型：PostgreSQL原生的heap表，行存储；还有就是两种新加入的，Append Optimized的行存储和列存储。AO表更有利于批量IO而不是heap表的随机访问模式，因此更适合AP的工作负载。特别是AO column表，可以用不同的压缩算法对不同的列进行压缩。Greenplum的查询引擎不敢直表的存储类型，同一个查询可以join不同的表类型。
表可以按用户指定的key和分区策略（list、Range）进行分区，其中每个分区可以是heap、AO-row、AO-column、甚至是外部表（比如AWS的S3）。以下图的销售表为例，每个分区由日期范围定义，从老到新分别是外部表、heap表和AO-column表。
至于优化器、Greenplum也提供两种选择（不是自适应的），分别是适合执行时间长的Orca和适合短查询Postgres原生的优化器。
这一节主要讲的是锁优化，这是Greenplum增强OLTP性能的关键，着眼于解决分布式系统的全局死锁。
Greenplum有三种锁：spin锁、LW锁和对象锁。前两种用于保护读写共享内存的临界区，并遵循某些规则来避免死锁。这里主要关注的是操作表、元组或事务等数据库对象时的对象锁。
其锁级别如下，level越高，并发控制粒度更严格。
在Greenplum中处理全局死锁时，DML语句的锁定级别非常重要：在分析阶段，事务会对表上锁；在执行阶段，则是用tuplelock。由于Greenplum会夸与多个segment server执行锁，很难避免全局死锁。如下图，在segment server0上，事务B等待事务A，而在segment server1上，事务A等待事务B。但本地的PostgreSQL却没有发现本地死锁。
更复杂的例子如下，包括协调者在内的所有segment server都导致了全局死锁。
在旧版本的Greenplum中，会在coordinator分析阶段，用X模式锁定目标表。因此对于执行写操作的事务来说，它们是以串行的方式运行，而且即便是更小不同元组也会串行运行，降低了OLTP的性能。
新版的Greenplum的全局死锁检查方法（GDD）如下：会在coordinator起一个守护进程，然后该进程会定期收集每个segment server上的Wait-for图，并检查是否发送全局死锁，然后用预定的策略终止全局的死锁。（比如终止最新的事务）
对于全局Wait-for图来说，事务就是顶点，其中输出边是顶点的出度，输入边数量则是入度。顶点的局部度是在某单个segment server的wait-for图中计算的值； 顶点的全局度则是在所有segment server的所有局部度的总和。另外考虑收集Wait-for图的过程是异步的，因此在下检测结论的时候，需要判断下涉及的事务是否还存在。如果有事务结束了，则放弃本轮检测，等待下一个周期。
对于Wait-for图有两种类型的边，实边是指等待的锁只有在事务结束的时候才能释放，pg中大多数对象都是这个类型。如果等待的锁无需事务结束则可以释放，比如tuple lock，则对应虚边。
至于具体的检测方法如上图，是一种贪婪的算法，在每一轮的循环中：
如果仍然存在无法消除的边，则认为死锁存在，此时再确认下之前的事务是否还存在。
下面就是一个具体的例子，上面一个图是全局和局部的Wait-for图，下图则是GDD算法执行过程。由于事务C没有全局出度，因此删除它和关联的边，变为(b)图。再看局部图，s1中A到B是一个虚边，并且B的局部出度为0，这条边也可以去掉，变成(c)图。再看全局图中B -> A的边，A没有全局出度了，可以继续消除而变为(d)。
Greenplum的事务是由coordinator创建的，并将其分发到各个segment server中。coordinator为每个事务分配了一个单调递增的整数，作为分布式事务id。在每个局部segment上，根据分布式事务id也会利用原生的PG事务机制来生成本地事务标id。
Greenplum利用了Postgres原生的snapshot机制来构建全局的分布式snapshot，可以应付分布式环境下的事务隔离。元组的可见性是由本地事务id和分布式事务id共同决定的。对于一个给定的事务，在修改一个元组时会给该元组创建一个新版本并打上局部事务ID，维护局部事务到分布式事务ID的映射。
考虑到维护本地事务ID映射分布式事务ID的开销较大，因此仅维护一个最大的分布式事务ID，和周期性地截断映射关系的元数据。
一般来说，coordinator会使用2pc来保证事务在所有segment server上要么abort要么commit。至于这里说的一阶段优化，则是指如果事务只会修改单个segment上的数据，则可以省掉不必要的PREPARE过程。如下图，coordinator将跳过PREPARE阶段，直接把Commit命令分发至参与segment server上，节省掉一个网络来回的PREPARE消息：
还有进一步的优化，最后一个Query可以和Prepared/Commit消息合并，多节省一轮roundtrip。
Greenplum还引入资源组的概念，考虑到TP和AP同时运行时，AP的工作负载会对TP产生极大的影响，通常前者会消耗大量的CPU、内存和IO带宽，并对后者的查询性能产生影响。目前Greenplum主要是实现了对CPU和memory的限制。
CPU的使用隔离是利用cgroup实现的，可以通过cpu.shares来控制着CPU的使用百分比或者优先级，也可以通过cpuset.cpus来指定资源组的cpu的核数。
内存的使用隔离则是基于内存管理模块Vmemtracker实现的，但由于想要显式控制内存的使用不是那么容易，引入了三个层次来管理内存使用情况：
论文主要讲了主要面向OLAP的数据库如何转换成一个HTAP系统，考虑到OLAP的工作负载会极大影响OLTP的性能，论文提出的方法如全局死锁检测器和1PC的提交协议会显著提高OLTP性能。另外就是通过资源组的使用，限制CPU和内存，保证了在单个系统中同时运行OLTP和OLAP工作负载不会有太大的影响。
本文介绍了F1 Lightning的设计与经验，该系统不是从头设计一个HTAP系统，而是在已有的若干个事务系统中存在着大量数据的情况，如何由一个独立的联合引擎实现对原事务系统的快速组合查询和事务操作。
HTAP系统的研究表明，数据所有者强烈希望能处理对同一数据集的同时处理查询和事务。已经有大量与 HTAP 系统相关的研究和开发（甚至在“HTAP”一词出现之前很久就开始了）。其中大部分工作都是在考虑：理想的 HTAP 系统应该是什么样子，以及需要哪些技术进步才能获得良好的性能。本文则考虑了另一种方法：一个松散耦合的 HTAP 架构，支持 在不同约束条件下的HTAP工作负载。
这样考虑主要是因为在Google中存在着多个事务数据存储系统来处理不同的工作负载，和与这些系统松耦合的联合查询引擎。为了避免高昂的迁移代价和提高事务存储系统的灵活性，需要一个单一的HTAP解决方案，可以跨事务存储来进行启用。
本文提出的Lightning是一种松耦合的HTAP解决方案，即HTAP as-a-service。只需将事务存储中架构中的某些表标记为“Lightning表”，Lightning即可透明地提供应用程序需要的HTAP功能。创建读取优化数据副本的所有工作，都由Lightning 及其集成处理使用的联合查询引擎来提供的，业务使用上甚至不需要知道Lightning的存在。
现有的HTAP系统一般分为同时承载OLTP和OLAP的单一系统和单独的OLTP和OLAP系统。再进一步的，后者又分为用于OLTP和OLAP的共享存储和解耦存储，共享存储需要对OLTP系统进行修改，以利用现有的分析查询引擎来实现OLAP。又或者是维护一个单独的、离线的ETL过程，使用松解耦的存储来实现HTAP架构，但这容易带来高延迟的问题。F1 Lightning通过与变更数据捕获 (CDC) 机制的集成以及结合内存驻留和磁盘驻留存储层次结构的使用来提高数据新鲜度。
文中介绍了几个类似系统的对比：SAP HANA异步并行表的复制机制；为行存储TiDb添加了一个列式存储和矢量化处理层的TiFlash。Oracle Database In-Memory则是结合OLTP 和 OLAP的单一系统代表，通过为活跃数据维护一个内存中列存储来加速HTAP工作负载，该列存储在事务上与持久行存储保持一致。LinkedIn Databus则是一个数据源不可知的分布式变更数据捕获系统，能将来自真实源系统的变更提供给下游应用程序，以构建用于不同目的的专用存储和索引。
该HTAP系统由三个部分组成：一个OLTP，作为数据来源并公开数据变更捕获接口；F1 Query，分布式SQL查询引擎和Lightning，维护和服务读优化的副本。
在Google有两个主要的OLTP数据库：F1 DB和Spanner，前者是在后者基础上实现的。F1 Query则是一个联合查询引擎，它的查询执行依赖的是内部称为GoogleSQL（开源为 ZetaSQL）的SQL语言。F1 Query是一个联合引擎，支持许多不同的内部数据源，包括F1 DB、Spanner、Mesa、ColumnIO , 和BigTable等，用户能够编写无缝连接这些系统的查询。一般来说，F1 DB和Spanner能通过高效的面向行的存储和索引来优化OLTP工作负载，如写入和点查找查询，并且用户也会设计特定的模式以最大化写入吞吐量。虽然F1 Query能够通过多worker的方式来运行分布式分析查询，提高查询性能，但会导致大量的计算资源成本。
针对这些问题，一些团队设置了pipeline，用于将F1 DB的表复制到ColumnIO文件或其他文件格式以供进一步分析。但这种实现也有几个问题，一是导致重复存储资源，多个团队各自保留自己的相同数据副本。二是ColumnIO文件不支持就地更新，副本必须作为一个整体定期全量更新，另外就是数据新鲜度比较差。三是需要显式更改查询模式，因为两个数据源来自不同的系统，具有不同的语义。最后就是权限问题，如何保持权限上的同步。
为了解决这些问题，论文提到了一个新的HTAP系统Lightning，可将OLTP数据库中的数据复制为针对分析查询优化的格式。既可以为单个表启用Lightning，也可以为整个数据库启用Lightning。对于每个启用的表，Lightning的一个组件 Changepump会使用F1 DB或者Spanner公开的数据变更捕获机制来检测新的数据更改。Changepump会将这些变更转发到由单个Lightning服务器管理的分区，每个服务器会维护由分布式文件系统支持的LSM树。当Lightning摄取到这些变更时，它会将相关行数据转换为针对分析优化的列存储格式。
Lightning与对应OLTP数据库保持快照一致的方式来读取数据，包括F1 DB和Spanner在内的数据库都支持使用时间戳的多版本并发控制，因此提交到Lightning的每个更改也都保留其原始的提交时间戳。Lightning保证在特定时间戳下的读取将产生与在同一时间戳读取OLTP数据库相同的结果，这就为F1 Query通过重写符合条件的查询以提高性能，也就是某个查询可能会分别从Lightning和对应的OLTP数据库读取数据。
将Lightning添加到查询系统中，具备以下的有点：
Lightning由以下组件组成：
Lightning支持具有快照隔离的MVCC。所有针对Lightning特定表的查询都指定了一个读取时间戳，并且Lightning返回与该时间戳的OLTP数据库一致的数据。这一点主要是与Google内部的OLTP数据库保持一致。
由于Lightning会异步应用来自OLTP数据库的更改日志，因此在OLTP数据库中所做的更改对Lightning上的查询可见之前会存在延迟。此外，Lightning支持控制单个查询的读取时间上限。这个上限可以是无限的（即Lightning可以存储所有的更改），但实际上大多数查询都集中在最近的数据上，限制Lightning中的数据量可以节省成本。
Lightning可查询的时间戳称为安全时间戳。最大安全时间戳表示Lightning已经获取到该时间戳之前的所有更改，最小安全时间戳即表示可以查询到的最旧版本时间戳。
Lightning将数据以表的形式组织，数据库表、索引和视图在Lightning中都被视为物理表。每个Lightning表都按range partitioning划分为一组分区。每个分区都存储在多组件的LSM树中。LSM树中的每个组件称为delta。
Delta包含其相应Lightning表的部分行版本数据，每个行版本由相应行的主键和该版本在OLTP数据库中提交时的时间戳标识。Lightning存储三种类型的版本，对应于对源数据所做的更改：
单个Delta可能包含同一键的多个版本，并且同一分区的不同Delta之间可能存在重复版本。在Delta内，部分行是由 (hkey,timestamp)唯一标识，并且为了支持对特定时间戳的快速查找，Delta按键升序、时间戳降序排序。
当Lightning接收更改时，生成的部分行数据首先写入内存驻留的、按行构造的B树，类似于C-Store的写优化存储。
一个Memory-resident Delta最多有两个活跃的Writer，以及许多读取者。另外还有后台线程应用来自OLTP事务日志的新更改和定期运行垃圾收集过程。
一旦数据写入Memory-resident Delta，它就可以立即用于查询，这取决于Changepump提供的一致性协议。Memory-resident Delta并不持久，在系统故障的情况下，存储在内存中的更改可能会丢失。Lightning会通过OLTP重放的方式恢复，同时为了提高恢复速度，会将B树按原样定期checkpoint到磁盘。
当Delta变得太大时，当到达每个Delta的大小限制或者服务器内存限制时，Lightning都会将它们写入磁盘，并且会转换成为读取优化的列格式。
含有Lighting数据的Disk-resident deltas被存储在读取优化的文件中，Lighting通过构建了一个具有通用接口的抽象层，允许使用许多不同的文件格式来存储Delta。文中只介绍了一种文件格式，每个增量文件存储两部分：数据部分和索引部分。数据部分以PAX风格的行列混合。索引部分包含主键上的稀疏B树索引，其中叶节点跟踪每个row bundles的键范围。索引比较小，通常在缓存中。
Delta合并包含两个逻辑操作：merging和collapsing。merging对源Delta中的更改进行重复数据删除，还可能执行Schama变更。collapsing将同一key的多个版本合并为一个版本。
此过程使用的是LSM逻辑的矢量化执行，先枚举需要参与合并的Deltas，然后从每个输入Delta读取一个Block，进行多路归并，但这里需要确认在这一轮中可以collapsing的key范围。
比如这两个Deltas的合并，当前轮Lightning只能collapse小于K2的数据。K2的数据可能需要等到下一轮collapse，读入下一个Block再说。
由于Lightning是复制OLTP数据库并透明地提供查询服务，因此它必须处理与OLTP数据具有相同语义的Schema演变。Lightning监控源数据库schema的更改并自动应用该更改。
为了实现这一点，Lightning使用了两级schema抽象。第一级是逻辑架构，它将OLTP的schema映射到Lightning表schema。逻辑schema包含复杂类型、比如Protocol Buffer，还有一些简单类型。对于特定的逻辑schema，Lightning会生成一个或多个物理schema。物理schema只包含基本类型，例如整数、浮点数和字符串。Lightning的文件格式接口仅在物理schema级别运行，降低工程实现难度。
如下图，逻辑schema和物理schema通过逻辑映射连接。映射指定如何将逻辑行转换为物理行，反之亦然，数据在读取期间从逻辑行转换为物理行。
映射的一个好处就是能为相同的逻辑数据实现使用不同的存储布局。例如，在存储protocol buffer时，有两种选择，一是序列化后存储，另一种则是将各字段单独存储，甚至可以同时存储，以提供极致的性能。映射还有助于仅元数据schema的更改。 Lightning可以适应许多常见的schema更改，而无需明确重写磁盘上的数据，比如增删一列。
因此，每当发生schema更改时，Lightning都会创建一个新的逻辑schema，schema更改后创建的增量会使用新的物理schema进行写入。当schema映射关系太多时，Lighting也会在compaction时将数据转换为新schema，从而减少数据转换的开销。
Lightning支持四种不同的压缩方式：active compaction, minor compaction, major compaction和base compaction。
其他三个任务都不在Lighting服务器上进行，由Lighting服务器调度，但在专门的任务worker上执行，
Changepump提供跨不同OLTP源的统一接口，将各个OLTP的CDC接口细节从主要的Lightning数据存储层抽象出来，并提供了一种可扩展且有效的方式将事务变更呈现给对应的变更订阅者。作用包括了：隐藏了各个OLTP数据库的详细信息；面向事务的变更日志适应为面向分区的变更日志，一个事务可能对应不同的Lighting分区；维护事务一致性，跟踪已应用于Lightning服务器的所有更改时间戳，并发出检查点，以提高每个分区的最大安全时间戳。
对于每个partitions，Lightning都会对Changepump做一个订阅。订阅会指定partitions的表和key范围，Changepump则负责将这些更改传送到Lightning服务器。订阅会有一个开始时间戳，Changepump只会返回在该时间戳之后提交的更改。
Changepump订阅会返回两种数据：change updates和checkpoint timestamp updates。前者就是数据本身的修改，同一个key的修改按时间戳升序排序，跨行则没有严格顺序保证。后者则是用来表明该时间戳之前的修改都已经传递完成，方便Lighting服务器提交其最大的安全时间戳。
Lightning使用两种机制来检测Schema的变化：lazy detection和eager detection。前者则是在收到OLTP数据库传来的修改时，如果发现它引用了没见过的架构，则会停止对该partition的更改处理，直到加载并分析了新schema。这种机制会增加处理延时。后者则是用后台线程轮询OLTP数据库以查看是否发生了任何新的schema更改。
Changepump本身也是一个sharding的服务，单个订阅可以在内部连接到多个Changepump服务器，Changepump客户端会将多个这样的连接合并成一个单一的变更流中。与Lightning服务器不同，Changepump是根据数据量划分sharding的，后者是按全量数据量。
Changepump会对增量的修改记录做缓存，好处是方便一个partition的不同副本能够共享这些数据，另外也可以加速partition的failover。
Lighting还会维护二级索引和物化视图，这是与正常表同等看待的，但生成方式不一样，不是通过Changepump订阅产生，而是Lightning需要根据基础表的变更日志计算派生数据的修改。由于派生表需要按key排序，但基表可能是由不同的Lighting服务器维护的，因此Lighting的做法是将其写进BigTable。目前Lightning只能支持有限的几种物化视图。
Lightning支持在线重分区，以期达到负载均衡，这里的重分区方案基本是元数据操作。Lighting的分区在达到数据大小阈值或者流量瓶颈的时候，就会进行分区分裂。在分裂分区时，Lightning就会新分区标记为非活跃。这是一个meta only的操作——新分区会共享老分区的所有delta，之后新的分区会从Changepump订阅数据并应用为新的delta，直到追上所有的新数据后才会被标记为活跃。至于老的分区，则会被标记为非活跃，然后等待所有请求都服务完后再被清理掉。由于新分区是继承自老分区的，因此读取时需要一个过滤器处理超过新分区边界范围的数据。
分区也会被触发合并，操作过程类似。
对于查询失败，Lighting使用集群内和跨集群复制来处理这些故障。在一个数据中心内，Lightning为每个partition分配给多个Lightning服务器。这些Lightning服务器都从Changepump订阅相同的更改，并且它们独立维护其内存delta，但它们共享一组相同的磁盘delta和内存delta checkpoint。每个partition都只有一个主副本可以执行compaction来写入delta。当一个副本完成写入时，它会通知其他副本更新它们的LSM树。
这些副本中任一个都可以为查询提供服务，查询请求可以在这些副本之间维持负载均衡，Lighting可以为流量大的partition增加更多的副本。在服务器更新，每个partition最多同时重新启动一个副本，以保持数据的高可用性，并且重启时会尝试从其他副本加载修改。
Lighting也可以部署在多个数据中心。单个数据中心拥有自己的一套Changepump服务器、Lightning服务器等等。这些服务器独立于其他数据中心运行，在每个数据中心维护数据的完整副本，所有数据中心共享同一个元数据数据库（假设meta DB永远可用）。如果出现数据中心级别的故障，也可以将请求转给其他数据中心的相同partition。
数据摄取也会出现相关的故障，比如OLTP系统的CDC出现问题或者Changepump服务器崩溃。对于前者，Changepump会自动连接另一个datacenter的OLTP系统（Google的OLTP系统本身也是跨数据中心部署的）。对于后者，Changepump是无状态的，可以连接另一个服务器继续服务。
Lightning master还会监控每个分区上所有数据中心的Changepump延迟，如果延迟过大，会重启这个数据中心的分区，使得可以从其他数据中心搬运数据过来。
Lighting也会配备表级别的failover，当某张表本身有问题时（比如到达资源瓶颈，或者数据坏了），系统可以自动将查询路由回 OLTP 系统。但用户可以选择是否进行这样的容错，以防AP的查询压力突然打垮TP系统。
本文提到的Lighting是HTAP系统的另一种实现方式，与同时承载OLTP和OLAP的单一系统不同，它是直接基于多个OLTP系统透明地提高HTAP性能的能力，而无需修改OLTP系统，也无需用户数据迁移到新系统。通过与F1 Query的结合，能够无感知地重写query plan（甚至在在逻辑计划阶段对查询也是生成一样的计划，到了物理计划阶段才会决定访问OLTP和OLAP系统），向量化列式处理查询请求，下推subplan。Google大规模部署Lighting后，在不影响查询语义的情况下，计算资源和查询延迟方面都实现了数量级的收益。