TiDB Percolator 事务实现解析
2019 年读源码时做的笔记，今天偶然翻到，搬到这里来。
看了一下 tidb 和 tikv 的源码，总结一下其事务实现如下，很多细节已经与 Percolator 不同。
基于 KV 的分布式事务方案
最近打算为内部的 KV 系统增加分布式事务的功能，因此再次回过头来细细看了 Google Percolator、Yahoo Omid 三部曲等相关论文。尽管先前对分布式事务的概念和实现方案已经有所了解，但此次详细回顾仍然收获良多，对于 2PC 在分布式 KV 上的抽象、设计取舍以及实现方式都有了新的认识，这里做一个记录以备忘。
分布式事务抽象
提到分布式事务，首先想到的肯定是两阶段提交（2PC）协议。本文不会详细地介绍两阶段提交协议的理论内容，而是针对 2PC 在 KV 领域的实现方案做一个总结。
C++ 模板特性之 SFINAE
最近在看 Facebook 开源的 C++ 组件库 folly 的源码，不仅收获了很多 Modern C++ 的编程技巧(e.g. type_traits，meta-programming)，也了解了很多高效数据结构的设计思想(e.g. FBString，Atomic Data Structures)。不得不说，folly 与 Leveldb 一样具有很高的源码质量，尽管采用了较多的高级特性及平台相关特性，但是阅读起来并不会因代码风格而吃力。今天这篇文章，我们来介绍一下在 folly 中被大量使用的现代 C++ 模板特性 – Substitution failure is not an error (SFINAE)。
在开始今天的主题之前，先思考一下如下两个通常可能会遇到的问题：
- 如何在编译期间判断某个类型 T 是否是 class 类型或者判断某个 class T 是否有指定的成员变量或成员函数？
- 如何在函数编译期间根据特定的条件来选择启用或禁用特定的重载？
分布式系统一致性
Linearizability vs. Sequential consistency
说到『一致性』这个词，你首先想到了什么？
图1：CAP 定理趣图
是 ACID 中的 consistency? 还是 Raft 或者 Paxos 中的 consensus? 是 MESI cache 一致性协议中的 coherence? 亦或是 CAP Theory 中的 consistency?
Lock-free 编程：A Case Study（下）
Hazard Pointer
在上文 Lock-free 编程：A case study（上） 中，我们介绍了如何通过 CAS2 操作实现一个无锁的支持并发访问的 Map。尽管 CAS2 帮助我们达到了 Lock-free 的要求，但不管怎么说，最终的实现在不太「优雅」的同时也不具有较好的性能。为了更进一步完善我们的 Lock-free Map，今天我们来介绍一些更高级的技术。
回忆一下前文中我们在通过 C++ 实现 Lock-free 的过程中面临的最主要的问题：什么时候释放旧的 map 指针 pOld。抛开使用 CAS2 实现的引用计数的方案，我们也可以简单粗暴一点，直接在『一段时间以后』去 delete 掉 pOld。然而，『一段时间』是一个很奇妙的说法，究竟多长时间才可以被定义为『一段时间呢』呢？显而易见的是，如果这个时间太长会导致内存释放不够及时，产生大量的内存垃圾；而如果这段时间被定义的太短，又可能在删除的时刻还有读线程仍持有这个旧的 Map，从而使读线程产生异常。那么，我们如何来定义『最适当』的删除时间呢？
Lock-free 编程：A Case Study（上）
基于 CAS 的无锁数据结构
在并行和分布式编程领域，Lock-free 是一个非常复杂也非常具有挑战性的话题。前面的文章 Memory reordering 浅析 中，我们提到了一个与 Lock-free 息息相关的概念–内存屏障。今天我们通过一个由浅入深的编程范例来具体介绍 lock-free 数据结构和算法思想，包括 Hazard Pointer 和 Read-Copy Update 的基本概念。这篇文章的初衷都来源于对 Andrei Alexandrescu 的文章 Lock-Free Data Structures 的扩展和理解。
Lock-free vs. Wait-free
从直观上理解，lock-free 数据结构即不使用任何锁的数据结构，Lock-free 编程则指利用一组特定的原子操作来控制多个线程对于同一数据的并发访问。相比于基于锁的算法而言，Lock-free 算法具有明显的特征：某个线程在执行数据访问时挂起不会阻碍其他的线程继续执行。这意味着在任意时刻，多个 lock-free 线程可以同时访问同一数据而不产生数据竞争或者损坏。
