opengauss mot内存表大部分是参考的本篇文章中Silo提出的算法，并在工程上对其进行了优化，比如：通过FDW集成到opengauss中，支持非唯一索引，无锁GC，Read-after-Write的支持等等。

Silo的设计要点是：OCC-based，多核，epoch-based。

Abstract

Silo针对多核优化的内存数据库，避免中心化竞争点，比如TID的分配。本文提出了一种基于OCC的支持串行化隔离级别的算法，并且在多核系统下能够水平扩展。

1 Introduction

在高并发系统中即使像CAS这样的原子操作（锁内存总线）也会导致单点瓶颈无法线性水平扩展。Silo的事务一致性算法避免单点竞争，性能随着核数而线性增加，Silo使用Masstree做为底层数据结构。

Silo的算法是OCC的变种，在线程本地追踪read-set和write-set。在commit前，进行validation：如果没有并发事务的write-set修改了它的read-set则可以commit（参考RW冲突检测）。

OCC的优势：

1. 在commit之前，所有对内存的操作都发生在本地；
2. 在commit时，对内存的短暂操作有利于减少竞争；

Silo的关键点：

1. OCC的必要条件：必须保证在发生crash执行恢复流程时事务的执行顺序和正常执行时的顺序一致。可以通过2种方法：

• 在共享内存区域对read-set排序；
• 按照事务执行的顺序分配单调递增的TID；

2. 对于只读事务避免对内存共享区域的写入；
3. epoch-based group commit：

• 时间被切分成epoch；
• 只有epoch边界能确定顺序：

• 如果t1的epoch比t2小，那么t1在t2之前被调度执行；
• 系统以epoch单位批量写事务日志，在epoch边界返回client；
• epoch可以做为只读事务的snapshot；

Silo的性能：32核和8核心对比测试时，平均每个核心性能是8个核时的91%。

Silo方案：

1. shared-memory store，而不用partitiond的方式，每个事务都能访问所有的数据，partition的性能退化：单个事务涉及大量分区，数据和计算倾斜；
2. cache-friendly，底层使用Masstree结构；

2 Related work

2.1 Non-transactional systems

以下数据结构都是针对多核下的优化，但是不支持事务。

Masstree

关键点：trie-like结构，version替代read lock，综合多种已有BTREE的优化方案：Blink-tree，OLFIT

PALM

关键点：batch，prefetch，SIMD

Bw-tree

关键点：多版本，面向flash storage，delta record，CAS on a mapping table

2.2 Transactional systems

Hekaton

关键点：OCC，MVCC，针对OCC下面中心临界区的优化

和Silo对比：

1. 需要全局临界区用于分配timestamps；
2. 读操作需要更新全局内存区域；

DORA

1. partition方案；
2. 针对跨多个分区进行了优化，消除了全局的所管理器，只有20%的提升；

PLP

DORA的升级版

1. 一个线程管理一个tree；
2. 中心化的grouting table；

H-Store

1. partition极致优化；
2. 每个物理节点上，多个逻辑分区；
3. 跨分区事务需要上全局锁；

Multimed

主线程对写操作排序，其他副本异步应用；

2.3 Transactional memory

STM系统，比如：TL2算法，基于OCC并且维护读写集合（Database的OCC）。

3 Architecture

Silo的表由多个索引树构成：

1. 一个primary tree，0个或多个secondary tree；
2. record以chunk形式组织；
3. 必须有primary key；
4. secondary tree指向primary key；
5. 所有key都是strings；

Silo的测试是基于Masstree结构，当然也很容易把Silo的Commit Protocol应用到其他数据结构上。

1. 所有worker线程都能访问整个DB；
2. 记录WAL日志，确保数据不丢失；
3. 只读事务可以使用最近的一个快照（sql hint）；

4 Design

核心的思想是减少对共享内存区域的写入以减少竞争；

4.1 Epochs

Silo将时间切分成片段称为epoch：

1. epoch边界是有序的，epoch内部是并发的；
2. 基于epoch加速gc和只读事务；
3. E：全局epoch，每隔40ms增加1；
4. ew：局部epoch，每个worker维护本地epoch；
5. 局部的ew可能小于全局E，约束：E - ew <= 1。对于大部分小事务来说维护这个约束并不难，如果某个worker的ew落后很多，维护全局E的线程等待不再继续增加E，对于长事务需要定期同步自己的ew；

4.2 Transaction IDs

Silo的并发控制协议的核心是：TID：

1. 64位整数，分成3部分；
2. 最高部分为Epoch自身的值，在事务提交时和全局E同步一次（读取全局内存区域）；
3. 中间部分为该Epoch下每个事务的逻辑ID；
4. 最低 3bit是状态位；

TID的分配：

1. 在对写集合校验之后确定能提交后分配；
2. 比当前worker读取/写入的record的TID都大；
3. 比当前worker的TID大（一个epoch连续多次commit，依靠TID的中间部分来区分）；
4. 和全局E同步（确保E边界的事务是有序的）；

TID的状态位：

1. Silo可以对recode更新Epoch和上锁在一个atomic完成；
2. 3个bit分别为：lock，latest-verison，absent；
3. absent标记该record仅仅是占位，可以在恰当实际回收；

全局E和ew的设计和HLC有几分类似：

1. E相当于绝对准确的墙上时间；
2. 而每个ew是自己的本地时间；
3. ew定期和E同步，确保自己的本地时间在往前进；
4. 所有worker的ew和E不能保持绝对的同步，因此存在误差；
5. 运行慢的worker自己本地ew落后于E，打破了约束，此时全局E不再增长，等待落后worker追上来（HLC中c.j达到最大时也需要等待慢节点追上来）；

4.3 Data layout

一个record3部分组成：

1. TID；
2. previous-version指针；
3. record数据；

原地修改record数据，加速点写，减少内存分配压力。

4.4 Commit protocol

read-set：记录key和其对应的TID

write-set：记录key对应的新内容；

Silo的并发控制协议分成3阶段：

Phase1

对所有写集合上W锁（原子的获取TID的lock bit），次过程类似单机的行锁，对即将更新的行逐个上锁。和单机的区别是上锁时并没有检查存在并发的WW冲突，而是在后面的阶段检查了RW冲突（WW冲突是允许的）；

和FoundationDB相比：FDB也是做的RW检测，不同的是先做了RW检测，因为它有一批Resolver进程，所有的事务在Resolver上排队，委托由Resolver进程来逐个的检测RW冲突，不存在WW的冲突。

而Silo是每个进程自己做RW检测，此过程是并发的，存在多个事务同时修改同一行的问题，因此需要通过上锁来排队修改。

和PG相比：PG是单机上行锁，在上锁时如果有锁等待需要LostUpate的处理，而Sillo是通过RW检测来直接保证了串行化隔离级别（比LostUpdate更高）。

为了避免死锁，对write-set排序，确保并发事务上锁的顺序相同。

在上锁成功之后，读取全局内存区域的Epoch：

1. 读取E前后需要fence，确保读取内存；
2. epoch是事务的串行化点；

Phase2

进行RW的检测：逐个校验read-set：

1. 版本是否发生了变化；
2. lock-bit是否其他事务被置位；
3. 校验所有被读取masstree的node的version是否变化；
4. 使用read-set，write-set，ew生成一个TID；

Phase3

使用上面计算得到的TID，对write-set逐个的写入。

必须保证：一旦新的TID在record上生效了，那么就应该被读取到。由于lock-bit是在TID中的其中一个bit，因此通过一个原子操作很容易保证。

串行化论证

1. 对write-set上锁；
2. 把已经上锁的record看多dirty，一旦读到则abort；
3. fench确保能看到最新的TID；

串行化的证明：上述过程和S2PL是等价的，对所有的读集合上read锁，仅当commit时释放。

1. 对于读取一个record，在phase2中，没有发生version变化和lock-bit变化，则说明该record一直没有被修改过，则相当于一直在上read锁；
2. 对于更新一个record，相当于在phase中将read锁升级成了exclusive锁，然后在phase2校验是否发生变化；

fence确保phase2中对read version的校验能够读取到共享内存区域中最新的值：

1. fence放置在RW检测之前：保证之前已经提交的事务read-set/node-set不包含后续epoch的数据；
2. fence放置在集合上锁之后：保证上锁时能找到正确的数据版本。并发事务在使用更大epoch上锁时能读取到被本事务上的版本，读取会被本事务阻塞，直到本事务把phase3执行完成，做了更新释放了W锁，其他事务也就能读取到最新的值。类似PG的过程；

使用当前epoch对本事务的write-set进行上锁；

使用最新的epoch读取本事务read-set是否有变化；

下面A5B的例子中，Thread1先commit，Thread2会被abort掉。Thread1对x做RW校验通过，因此Thread2对x的上锁发生在Thread1的fence之后，而Thread2对y做RW校验会有两种情况：

1. Thread1还没结束，此时读取到record的状态是lock-bit被置1；
2. Thread1已经结束，由于Thread2执行了fence再进行RW检测，此时能读取到最新版本的数据；
   上面2中情况都说明存在RW冲突。

4.5 Database operations

写操作：

1. 为了提升性能，尽量原地更新。否则新分配空间并修改tree的指针；
2. phase3中对数据的修改期间持有锁，更新TID和释放锁原子操作；

事务中的读操作：

1. 读取TID，测试lock-bit，一直spin直到lock-bit被清零；
2. 检查latest version位是否是最新；
3. 读取record；
4. 执行fence；（RW阶段）
5. 检测TID；
   如果第2不检测到数据不是最新，或者1到5期间检测到TID变化，则重试或者abort。

删除操作：

1. 维护版本链的正确性以便正在执行读的事务能够读取正确的版本；
2. 标记absent位；
3. 注册record以便后续执行GC；

插入操作：

1. 在commit protocol之前插入到tree中；
2. 如果插入键值k已经存在则本事务abort；
3. TID为0；
4. 新插入的key也要放入read-set进行检测，防止并发事务对tree中的k进行update；
5. 如果commit protocol顺利完成，则对应record上的TID会被更新；

4.6 Range queries and phantoms

通过masstree的version number避免幻读：

1. 记录读操作是tree的叶子node和version number；
2. phase2检查node version是否变化，如果变化则说明有add/delete发生，存在幻读的风险；

4.7 Secondary indexes

二级索引的实现：普通的表，其key是primarykey；对二级索引的查找需要跳到主索引上。

4.8 Garbage collection

Silo没有使用引用计数，使用类似RCU的epoch-base的回收算法。每个core上记录带回收内存和当时的epoch值：后续不在有epoch会访问到这个内存对象。

4.9 Snapshot transactions

snapshot epoch：比全局epoch慢

snap(e) = k . [e/k]，其中k为25，大约1秒；

读写事务不能delete/overwrite和snapshot epoch有交集的记录，通过previous-version组织成版本链表。

4.10 Durability

OCC需要按照顺序提交，epoch是持久化单位，epoch中的某个事务：只有在本epoch所有的事务都持久化才会返回给client。

日志记录了该epoch下所有事务的修改（最后条日志中记录了该epoch的值为D），在recover时从日志尾巴上找到最大已经提交epoch为D，然后开始恢复（epoch内部事务的顺序无法确定，因此必须恢复完整的epoch）。

实现中，分成多个logger线程，每个线程维护D，因此整体上需要根据每个线程的本地的D计算出全局的D。

5 Evaluation

5.1 Experimental setup

Intel Xeon E7-4830

4个socket，每个socket上8-core，共计32物理核

2.1GHz

32KB L1

256KB L2

24MB L3

总计：256GB，每个socket上64GB

开启2MB巨页

4线程分别写4个盘，确保磁盘总带宽不是瓶颈

5.2 Overhead of small transactions

结论：

1. 支持了事务的MemSilo和裸kv相比，增加的开销很小，1.07倍；
2. MemSilo+GlobalTID：中心化分配TID不能线性扩展，尽管是原子操作；

5.3 Scalability and persistence

tpcc测试，大部分订单可以在本地的warehouse处理，小部分需要和远程warehouse交互。

结论：

1. 无论是否持久化，增加线程数几乎线性增长；
2. 在线程数达到32时，单核平均性能是一个核心时的81%；
3. 在线程数达到8时，单核平均性能是一个核心时的98%，原因是：在线程数多时L3被争抢；
4. 持久化的Silo性能超微差点，原因是实际只有28core在工作，另外4core是logger线程；

下图是将日志存入到内存文件系统：

结论：

1. 仅仅有1.03倍，说明在图5中，持久化Silo比内存Silo稍差并不因为写磁盘导致，而是因为工作线程和logger线程交互导致；
2. Silo对CPU敏感：当达到28工作线城时，latency陡增，因为4个工作线程，而总计32物理核，此时CPU达到瓶颈；

5.4 Comparison with Partitioned-Store

下面是和基于分区的系统进行比较，

1. 按照warehouse-id分区；
2. 每个分区有一个B+-Tree；
3. 每个分区有partition lock；
4. 事务提交时需要对相应partition按序上锁（此处参考H-Store）；

测试条件：

1. 固定DB大小和工作线程数；
2. 调节cross-partition比例（大于一个partition）；
3. 单个事务设计5~15个item；
4. 观察new-order数目；

结论：

1. 没有cross-partition时，Partition-Store性能是MemSilo的1.54倍；
2. 随着cross-partition增加，Partition-Store性能线性减小，15%时和MemSilo相当；
3. 当60%是cross-partition时，MemSilo是Partition-Store的2.98倍；
4. MemSilo性能稳定；
5. MemSilo+Split性能略高，B+-Tree变小了；

下图测试skew的影响，100%new-order，压力规定到某个partition上。

结论：

1. Partition-Store无法提升；
2. MemSilo提升，单非线性，因为100% new-order存在竞争；

5.6 Space overhead of snapshots

维护快照而带来的空间膨胀很低，不再具体分析。

5.7 Factor analysis

具体分析每个技术点对性能的影响

结论：

1. 感知NUMA提升20%；
2. inplace写提升60%；
3. 持久化对性能的影响很小；

6 Conclusions

Silo的特点：OCC-based， multicore，避免全局临界区。其中，recovery，gc，readonly-snapshot是基于epoch实现。