Cloud-Native Transactions and Analytics in SingleStore
论文介绍了一个前身为MemSQL的分布式通用SQL数据库，现在叫SinglestoreDB (S2DB)。它是市场上最早的分布式HTAP数据库之一，可以做横向扩展以有效利用100台主机、1000个核心和10TB的RAM，同时保持类似于Oracle或SQL Server等单机数据库的用户体验。 S2DB的表存储通过快速扫描、查找、过滤、聚合和更新等操作有效地满足TP和AP负载。
Introduction
当前市场上存在着各种针对特定场景的数据库，这其中有两个趋势推动了这些新数据库的发展，一是利用弹性的云原生架构，像blob存储S3和块存储EBS允许数据库利用几乎无限的、高可用性和持久的数据存储，而弹性计算实例如EC2则允许数据库弹性扩缩容提供更多计算以处理复杂查询或吞吐量峰值。二是开发者需要存储更多数据并以更低的延迟和更高的吞吐量访问数据库，这种性能和容量，访问模式相结合，导致应用程序对数据库的要求非常高。
解决这些要求的常用方法是为应用程序的不同组件使用特定的数据库。相比之下，S2DB团队认为可以设计一个数据库，充分利用弹性云基础设施，同时满足AP和TO负载的需求。这样一个可以处理多种应用程序类型的、集成的、可扩展的数据库对用户有很多好处，能减少成本，减少对开发者的要求等。
本文介绍了SingleStore数据库引擎的架构，作为一个云原生数据库，其擅长在大型数据集（100 TB）上运行复杂的交互式查询，以及以可预测的响应时间运行高吞吐量、低延迟的读写查询（每秒写入或更新数百万行）。相同的SingleStore数据库引擎用于 SingleStore Managed Service（一种云数据库服务）和 SingleStoreDB (S2DB) 数据库产品上。S2DB可以通过仅将冷数据推送到Blob存储并在运行查询时智能地使用本地状态来最大程度地减少网络使用，从而支持减轻存储上的各种工作负载。
对于S2DB而言，有两个部分对AP和TP的云原生负载很重要：
- 存算分离：与大多数云原生数据库一样，S2DB也会利用blob存储作为共享的远程存储，但S2DB会根据数据热度充分利用本地内存、本地磁盘和Blob存储，在本地磁盘上提交再将数据异步推送到blob存储，从而避免较高的写入延迟。在 blob存储中还可以保留历史记录比如已删除的数据，这可以按时间点还原到过去的数据库状态，而无需在还原时进行显式备份或复制任何数据。另外还可以通过blob存储创建相关的只读副本。
- 统一的表存储：S2DB的表同时需要列存储的扫描性能（每秒扫描数百万到数万亿行）和行存储索引的查找性能以加快点读和写入事务。在S2DB中，OLAP和 OLTP工作负载都使用单一的统一表存储设计，不需要像其他HTAP系统那样将数据复制到不同的数据布局中。统一表存储在内部同时使用了行存储和列存储格式，但这个对用户是透明的。在较高层次上该设计仍然是列存储的设计，但经过修改后能更好地支持读取和写入，并且对列存储的压缩和表扫描性能影响很小。列存储数据组织为LSM，支持二级哈希索引以加速TP查询
Background on SingleStoreDB
S2DB是一个水平分区、shared-nothing架构的DBMS，同时也可以使用存放冷数据的blob存储作为共享存储。S2DB集群由协调查询的聚合器节点和保存数据分区副本并负责大量查询计算的叶节点组成。每个叶子包含几个数据分区，每个分区要么是提供读写的主副本，要么是只读副本。
表通过一组叫shard key的东西来做hash分区，这使得点读足够快速并且查询形态上也不需要移动数据。当join的条件或者group-by列满足它们引用表的shard keys时，S2DB会将执行下推到各个分区，从而避免任何数据移动。否则，S2DB会在查询期间通过broadcast或reshuffle来重新分配数据。
SingleStore还支持基于中间字节码通过LLVM编译成的native code去查询。
Table storage formats
S2DB在内部使用两种存储类型：由无锁跳表支持的内存行存储和基于磁盘的列存储。下文描述的统一表存储在内部结合了这两种格式，以使用单一存储设计支持OLAP和OLTP工作负载。
Rowstore storage
内存行存储是使用无锁跳表来进行索引的，跳表的一个节点对应着一行，每个节点都会存储行的版本链表，从而实现MVCC，使得读无需等待写。写入使用的是悲观并发控制，通过跳表节点的行锁来处理对同一行的并发写入。除了写入内存的跳表之外，写入操作还会在提交之前将相关的信息写入日志。这个日志也是比较常规的设计，磁盘存储，每个数据库分区一个日志。节点重启时，数据库分区的状态通过重放恢复。后台进程定期创建快照，减少恢复过程中重放日志需要的时间。
Columnstore storage
列存储表的数据按segment组织，其中每个segment都将不相交的行子集存储为磁盘上的一组数据文件。在一个段中，每一列都以相同的行顺序存储，单独压缩。列的压缩支持多种编码方式，包括bit packing, dictionary, run-length encoding, and LZ4。段元数据存储在持久的内存行存储表中，其中包括文件位置、编码方式和每列的最小/最大值在内的信息，另外还有一个bitvector来表示段中被删除的行。
这种结构主要针对了OLAP进行了优化，为了加快 OLTP 工作负载中常见的点读取操作，每个列编码都实现为可搜索的，以允许在特定行偏移处进行有效读取，而无需解码所有行。存储最小/最大值允许使用内存中的元数据执行段消除，以跳过获取没有匹配行的段。
可以在每个列存储表上指定排序键，以实现更有效的段消除。如果指定了排序键，行将按每个段内的排序键进行排序，跨段的排序顺序与LSM 类似，后台合并则用来增量合并段。
对于每个列存储表，S2DB都会创建一个行存储表作为写入优化存储，这类似于RocksdDB的MemTable，后台线程定期从行存储中删除行并将这些行转换为事务中的列存储段。
另外，列存储表还支持向量化执行，在适当时使用SIMD指令来加速过滤和聚合操作。
Separation of storage and compute
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。
Staging Data from Local to Remote Storage
S2DB的存算分离设计如下所示，概括而言就是：
- 无论开不开启blob storage，S2DB的事务提交只需要追加log并且等其复制到其他节点，这个过程不需要同步写blob；
- 新提交的列存储数据文件会尽快异步上传到blob存储；
- 待日志复制到多个节点之后，事务日志会以chunk的方式上传到Blob存储；
- master节点会在blob上对行存数据做snapshot（即MemTable）。一个新的副本或者落后的副本可以从Blob获取需要的快照和日志，还有master获取还没上传的log tail来完成数据追赶；
这种设计的一大优点是，写入事务不需要写Blob，并且Blob的故障不会影响对于热数据的访问（论文认为Blob的可用性远低于其保证的那样）。缺点就是本地磁盘或者内存保存的状态需要一些高性能的复制和恢复协议，并且存算不够解耦，添加或者删除主机都需要移动本地数据。另外就是节点大规模故障会有丢掉还没上传到blob的那部分数据的风险。这个设计更多数的云数据库不大一样，S2DB的节点相对会比较重，并且持久性和可用性会有风险。
Capabilities Enabled by Separated Storage
这章主要介绍远程存储启用的一些功能作用：
- S2DB使用更快的SSD来做临时的本地存储，而不像其他云数据库使用昂贵且更慢的EBS，这带来更高的IOPS；
- S2DB能保存数月的历史记录，因为Blob存储的成本很低。另外还支持通过PITR命令将数据库恢复到过去特定时间的状态，而不需显式备份。S2DB会找到跟给定PITR最接近的事务一致点，然后往前找到第一个snapshot，对每个分区进行分别恢复，一直重放到相关的事务一致点。不过S2DB不支持time travel querying，只是相当于回滚数据库状态；
- S2DB支持创建只读workspaces，即一组只读副本，从可写的主副本中异步复制最近写入的数据。这样的优点是提供更高的读并发，还支持创建一个独立的环境来运行繁重的ap查询；
总的来说，S2DB的存算分离即利用了传统云数仓的设计来满足可用性和弹性，并提供几乎无限的持久化存储，也有一定的灵活性来扩展计算能力，并规避了传统云数仓可能带来的写入延迟。
Unified table storage
考虑到大多数用户没办法很好决定自己的访问模式是更适合行存还是列存，S2DB提出了一种Unified table storage，简单来说就是基于原来的列存做优化，从而更好地支持TP，并且不会牺牲对于AP的支持。
- No merge-based reconciliation during reads
与常规的LSM实现不同，S2DB在内存中实现了一个bit vector来表示删除，而像RocksDB、Cassandra和BigTable往往是在每一层的LSM使用tombstone entries来表示删除，S2DB的实现避免了merge on read带来的读放大。
- Minimize disk access and blocking during writes
与常规的LSM一样，S2DB仍然需要在内存中写入，除此之外还需要修改segment的元数据，来避免tombstone records。需要注意避免对同一个segment的并发修改带来的阻塞。
Secondary indexes
如下图所示，S2DB还构建了基于LSM实现的二级索引来满足高效的点查。
- 对于每个segment都会构建一个倒排索引以将索引列的值映射到一个posting list，该列表存储该segment中具有该值的行偏移量。
- 另外还有一个全局索引将索引列的值映射到具有该值的segment id，以及每个segment的倒排索引中相应posting list的起始位置。
Multi-column secondary index
为了在最小化存储成本的同时支持多列二级索引，S2DB为每个索引列构建一个二级索引，并允许单列索引在引用相同列的多索引时被共享。以对列(a,b,c)构建二级索引为例：
- 先分别对a, b, c的每段构建倒排索引；
- 分别对a, b, c的构建全剧索引；
- 对索引列(a,b,c)元组构建全剧索引，每组(value_a, value_b, value_c)都映射到(value_a, value_b, value_c)相应每列的postings lists起始位置；
前面两步可以满足对组合索引列子集中某些列的查询需求，第三步则可以直接跳过与所有索引列匹配的行对应的segment，从而加速查询。
Uniqueness enforcement
大多数列存实现都不支持唯一性约束，S2DB通过二级索引可以满足需求。具体的实现就是在插入之前读一下全剧索引判断是否存在，再根据重复与否来决定用户的行为。
Row-level locking
由于针对segment元数据的修改存在并发的可能性，如果是直接使用segment级别的锁会阻止可能上百万行的修改，降低吞吐。因此S2DB实现了行锁机制来降低事务负载，将内存行存储的主键作为lock管理器，其中插入行的副本会锁定行，防止并发修改，然后通过合并事务来降低blocking。
Conclusion
S2DB旨在通过统一的表存储满足ap和tp负载，并使用了倒排索引来提高点查能力，其使用blob存储实现了shard disk的成本、持久性和弹性优势，并且尽量避免了blob存储通常会带来的高延迟、低吞吐量写入事务的问题。