System|事务|Silo OCC

Silo是SOSP13发表的原型数据库，目的是在众核情况下支持高性能。其核心是基于epoch的OCC提交协议,避免global TID。

Architecture

常见的SQL数据库，次级索引树存储主键。

基于MassTree作为存储引擎，MassTree是多层B+树构成的Trie树，特点在于叶子节点指向record或者子树。

作者进行了优化，例如

• read-copy-update (RCU) 用于GC
• version number validation
• software prefetching of cacheline

Epoch

时间按照固定间隔的Epoch进行分段，由单工作线程进行Epoch的增加。

record由TID、上个版本数据的指针、Data组成，MVCC。

TID

每条记录都附带着TID代表最后的写事务，分为三个部分。

Epoch的目的是作为恢复的基本单元，保持All-or-nothing

Sequence的目的是保证事务串行化

Status bit分别是lock bit，lastest-version bit(是否最新)，absent bit(是否删除)

Commit Protocol

OCC的思想都是直到提交时再检查数据是否有被修改

Pre-commit execution

read set存放(tuple -> tid_read)，write set则存放(tuple -> value_to_write)。

Commit

一阶段 全write 置位lock bit(由全局的线程来做防止死锁),获取当前epoch

二阶段 全read检查TID是否改变(已被写)或者lock bit（正在被写)

为了避免幻读，在范围查询时还会查询整个B+ Tree叶节点的version。

三阶段 生成新的TID，并写入数据

1. 必须大于所有read/write set
2. 必须比本线程之前生成的TID大
3. 使用一阶段的epoch

// Phase 1
for w, v in WriteSet {
Lock(w); // use a lock bit in TID
}
Fence(); // compiler-only on x86
e = Global_Epoch; // serialization point
Fence(); // compiler-only on x86
// Phase 2
for r, t in ReadSet {
Validate(r, t); // abort if fails
}
tid = Generate_TID(ReadSet, WriteSet, e);
// Phase 3
for w, v in WriteSet {
Write(w, v, tid);
Unlock(w);
}

Returning results

直到所有之前epoch的事务在磁盘上后再返回(相当于做checkpoint，恢复的时候只恢复最后的epoch即可)

void
txn_logger::wait_until_current_point_persisted()
{
  const uint64_t e = ticker::s_instance.global_current_tick();
  cerr << "waiting for system_sync_epoch_="
       << system_sync_epoch_->load(memory_order_acquire)
       << " to be < e=" << e << endl;
  while (system_sync_epoch_->load(memory_order_acquire) < e)
    nop_pause();
}

总结

事实上,我们可以发现

1. 必须大于所有read/write set
2. 必须比本线程之前生成的TID大
3. 使用一阶段的epoch

这三条规则并没有要求事务生成绝对的全局顺序,而仅仅保证事务涉及的数据的串行化,这样能够避免访问global critical section.

另一点在于避免non-local memory writes for read operation,不是很清楚什么意思,大概是RCU的作用?

总而言之,对于多核NUMA而言,最关键的就是尽可能减少跨域内存访问,这样性能随着核数增长才会趋近线性. MCS锁也是相同的思路,在本地自旋而不是在上个节点自旋.

Reference

read-only transaction之类的细节看原文吧,作者也开源了