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,并写入数据
- 必须大于所有read/write set
- 必须比本线程之前生成的TID大
- 使用一阶段的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();
}
总结
事实上,我们可以发现
- 必须大于所有read/write set
- 必须比本线程之前生成的TID大
- 使用一阶段的epoch
这三条规则并没有要求事务生成绝对的全局顺序,而仅仅保证事务涉及的数据的串行化,这样能够避免访问global critical section.
另一点在于避免non-local memory writes for read operation,不是很清楚什么意思,大概是RCU的作用?
总而言之,对于多核NUMA而言,最关键的就是尽可能减少跨域内存访问,这样性能随着核数增长才会趋近线性. MCS锁也是相同的思路,在本地自旋而不是在上个节点自旋.
Reference
read-only transaction之类的细节看原文吧,作者也开源了
相关文章
- 人工智能为游戏带来提升
- 操作系统 存储管理实验报告
- 【TcaplusDB知识库】PB表定义示例
- 扫描域名和扫描IP的区别
- 安卓逆向 -- APK文件结构
- 操作系统 文件管理实验报告
- 11.3 VR扫描:Nextech AR获500万加元股权融资;微软宣布Mesh支持Teams
- 如何掌握 Framwork?《Android Framework 精编内核解析》,深入解析源码!
- 信息收集 -- ip段整理
- 10月VR圈聚焦Facebook Connect 2021,元宇宙再度走红
- 安卓逆向 -- Fiddler抓包
- 目标检测里,视频与图像有何区别?
- 子域名收集 -- 提莫(teemo)
- 图像梯度的基本原理
- 【node报错解决方案】Error: Cannot find module http-errors
- 安卓逆向 -- 常用命令与分区目录
- 6的!Pycharm实用技巧
- 【TcaplusDB知识库】快速上手TDR表的增删查改操作
- 【node】express的www.js文件里面的process.env.PORT
- bat使用forfiles自动批量删除过期文件