A long line of concurrency-control (CC) protocols argues correctness via a single serialization point (begin or commit), an assumption that is incompatible with snapshot isolation (SI), where read-write anti-dependencies arise. Serial Safety Net (SSN) offers a lightweight commit-time test but is conservative and effectively anchored on commit time as the sole point. We present ESSN, a principled generalization of SSN that relaxes the exclusion condition to allow more transactions to commit safely, and we prove that this preserves multiversion serializability (MVSR) and that it strictly subsumes SSN. ESSN states an MVSG (Multiversion Serialization Graph)-based criterion and introduces a known total order over transactions (KTO; e.g., begin-ordered or commit-ordered) for reasoning about the graph's serializability. With a single commit-time check under invariant-based semantics, ESSN's exclusion condition preserves monotonicity along per-item version chains, and eliminates chain traversal. The protocol is Direct Serialization Graph (DSG)-based with commit-time work linear in the number of reads and writes, matching SSN's per-version footprint. We also make mixed workloads explicit by defining a Long transaction via strict interval containment of Short transactions, and we evaluate ESSN on reproducible workloads. Under a commit-ordered KTO, using begin-snapshot reads reduces the long-transaction abort rate by up to approximately 0.25 absolute (about 50% relative) compared with SSN.


翻译:一系列并发控制协议长期以来通过单一串行化点(开始或提交)论证正确性,这一假设与快照隔离不兼容,因为后者会产生读写反依赖。串行安全网提供了一种轻量级的提交时测试,但较为保守,且实质上以提交时间作为唯一锚点。我们提出了ESSN,这是SSN的一种原则性泛化,它放宽了排除条件以允许更多事务安全提交,并证明其保持了多版本可串行化,且严格包含SSN。ESSN阐述了一种基于多版本串行化图的准则,并引入了事务上的已知全序(如开始有序或提交有序)用于推理图的可串行性。在基于不变量的语义下,通过单次提交时检查,ESSN的排除条件保持了每项版本链上的单调性,并消除了链遍历。该协议基于直接串行化图,提交时的工作量与读写操作数量呈线性关系,与SSN的每版本开销相匹配。我们还通过严格区间包含定义短事务来显式处理混合工作负载中的长事务,并在可复现工作负载上评估ESSN。在提交有序的已知全序下,使用开始快照读取相比SSN可将长事务中止率降低最多约0.25绝对值(约50%相对值)。

0
下载
关闭预览

相关内容

【AAAI2021】“可瘦身”的生成式对抗网络
专知会员服务
13+阅读 · 2020年12月12日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
国家自然科学基金
17+阅读 · 2017年12月31日
国家自然科学基金
4+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
VIP会员
相关基金
国家自然科学基金
17+阅读 · 2017年12月31日
国家自然科学基金
4+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
Top
微信扫码咨询专知VIP会员