原文：The End of an Architectural Era (It’s Time for a Complete Rewrite)
TL;DR
本文针对新硬件带来的新的趋势，提出了一种全新的OLTP DBMS，H-Store，可以大幅度提高传统的DBMS的性能。
传统的DBMS主要还是沿用System R的架构：
- 面向磁盘的存储和索引结构。
- 多线程。
- 基于锁的并发控制。
- 基于log的恢复机制。
本文观点是在这套架构上小修小补已经不够了，我们需要全新的设计。
尤其是传统RDBMS想用一套系统满足全部需求的想法已经过时了。
H-Store针对OLTP场景，打破了上面这种架构，主要是充分利用大内存和多节点，结合对OLTP场景的若干假设，省掉log和lock相关的很多机制，从而大幅度提升了性能。
OLTP Design Considerations
- 内存：随着内存容量上升，很大的OLTP数据库也可以整个放到内存中，而旧的设计是面向磁盘的，没办法充分利用内存的特点，新的设计需要将内存放到比磁盘更高优先级的位置。
- 多线程和并发控制：假如所有数据都在内存中，则OLTP的事务通常都比较短，此时多线程在延时方面的优势就不明显了，使用单线程可以去掉并发控制、并发数据结构，整体架构更可靠，性能也更好。
- 网格计算和停机升级：未来shared-nothing架构会是主流，多个节点只通过网络连接在一起；且用户不太可能接受停机升级，新的DBMS需要有能力不停机扩缩容和升级，比如在节点间复制数据的同时还不影响事务，这些能力不太可能加到已有系统上。
- 高可用：新的系统需要用热备或p2p来达到高可用，这样的系统中log可以非常简化，只需要undo log而不需要redo log，且undo log也只需要在内存中而不需要持久化。
- 不需要大量手动开关：新的系统要有self-everything（self-healing，self-maintaining，self-tuning）的能力。
Transaction, Processing and Environment Assumptions
为了实现这样的新系统，以下结论就很明显了：
- 持久化的redo log明显是性能瓶颈，即使有group commit，也会给每个事务带来若干ms的开销。
- 没有了redo log后，DBMS的输入输出接口——JDBC/ODBC——就是瓶颈了。作者推荐将应用逻辑全都写为像存储过程一样内置在DBMS里的形式，而不要用传统的交互式的C/S模式。
- 如有可能，省略掉undo log。
- 尽量削减传统的动态数据锁的开销，这是瓶颈之一。
- 多线程锁的开销也不可小视，鉴于大内存容量和短事务的特性，我们可以单线程运行，从而以非常低的代价省掉这部分开销。
- 尽量避免使用2PC。
Transaction and Schema Characteristics
H-Store要求只能用预定义好的Transaction类，每个类的SQL是固定的，可以有运行期参数，不能有显式的停顿，SQL中涉及到的表必须在注册Transaction类时已存在。
作者注意到很多OLTP场景都有着明显的树型结构，root表与子表有着1:n的join关系，这样可以让子表与root表使用相同partition策略，就可以保证在一个节点上执行equi-join了。
如果在此基础上，一个transaction类中的所有命令都可以在相同节点完成，我们称这个应用为constrained tree application（CTA）。CTA的价值在于它的执行不会受到其它节点的影响（除了因replication同步导致的）。
如果CTA中所有transaction的所有命令，除了有root上的相等性判断外，还对一个或多个子表的primary key有相等性判断，则我们还可以在整棵树上做更细粒度的分区。
OLTP应用很多都可以直接设计成CTA，或者分解为多个CTA。另一类技术是如何把非CTA应用也变成单节点的。作者这里提到两种方法：
- 只读的表可以复制到各个节点上，如果去掉这种表之后应用变成了CTA，则加上复制后的只读表它仍然会是CTA。
- 另一类应用是one-shot，其中的所有事务都可以并发执行而不需要跨节点的通信，且后面SQL也不会用到前面SQL的结果。这种事务就可以分解为若干个单节点的命令。
应用经常可以通过垂直分区实现one-shot（不更新的列复制到每个节点），如TPC-C。
一些应用是两阶段的（或可以转为两阶段），即先是只读阶段，再是只写阶段，如TPC-C。H-Store通过挖掘两阶段的应用从而消除undo-log。
如果两阶段的应用还保证了只读阶段在所有的节点上运行最终得到同样的继续还是abort的决定，这种应用称为强两阶段应用。
如果两个事务的任意单节点子计划交错执行都会得到相同的结果（假设都提交），则称这两个事务是可交换的。如果一个事务类与其它所有事务类（包括自己）都是可交换的，则称这样的事务类是sterile。
H-Store Sketch
每个H-Store节点被分为若干个虚拟节点，每个虚拟节点对应一个cpu核，单线程执行预定义好的事务类。与C-Store类似，H-Store中没有redo log，undo log也只在需要时用到。
H-Store会在定义事务类时应用基于开销的优化器将SQL转换为查询计划。这里假设了OLTP中很少有多路join（即使有，也通常满足树型要求）、group by、聚合。
事务类的查询计划可以是：
- 单节点的。
- one-shot的。
- 普通的，节点间可能需要传递中间结果，后面SQL的参数可能依赖前面SQL的结果。此时H-Store使用Gamma风格的执行模型，最开始处理事务的节点作为协调者。
对于普通事务，H-Store还会计算事务的深度，即节点间消息传递的次数。
H-Store有工具自动化设计分区、replication位置、需要索引的字段。为了实现高可用，每个分区都需要有一个或多个伙伴，它们包含相同信息，但可以有不同的形式（如不同的排序）。
自动化工具的目的是令尽可能多的事务能单节点运行。
H-Store会保证所有replica的更新满足事务性质，因此读命令可以选择任一replica，而写命令需要发给所有replica。
每个事务在执行时会收到一个时间戳，格式为(site_id, local_unique_timestamp)，这样给定site_id的顺序，时间戳就满足全序关系了。H-Store需要各个节点的本地时间尽量保持同步。
H-Store可以利用以下信息来简化并发控制和提交协议：
- 单节点/one-shot：如果所有事务类都是单节点或one-shot的，则每个事务都可以直接发给各个replica执行。如果其中有非sterile的事务，节点在执行事务前需要等一小会（考虑网络延迟）以保证事务是按时间戳顺序执行的，从而保证各个replica上事务执行顺序相同。同样地，这样的事务类保证了所有repilca要么都commit，要么都abort，这样各个replica可以只看本地结果决定是commit还是abort。此时我们不需要redo log、并发控制、分布式提交。
- 两阶段：（如果所有事务类都是两阶段的，）不需要有undo-log，结合上面这条，此时所有事务相关的机制都不需要了。
- sterile：如果所有事务类都是sterile，那么所有事务可以不做并发控制地正常执行，甚至不需要关心不同replica上事务执行的顺序。但如果事务涉及了多个节点，不能保证这些节点都commit或都abort，此时就需要使用2PC了。如果所有事务类都是强两阶段的，就可以省掉2PC。
- 其它情况：此时一定要有某种并发控制手段。最常用的并发控制手段是动态锁，但H-Store基于以下原因反对动态锁：
- 事务持续时间短，乐观方法要好于动态锁之类的悲观方法。
- H-Store已经把事务分解为单节点的命令，每个命令没有阻塞地单线程运行，就更倾向于乐观方法了。
- 作者假设H-Store可以一次看到全部事务类，可以利用这些全局信息来减小并发控制的开销。
- 设计良好的系统中事务冲突和死锁都非常少，此时要求应用开发者来移除这些意外也是合理的（不要为了小概率事件牺牲整体性能）。
H-Store会针对每个不满足各种优化条件的事务类找出所有与它冲突的事务类，在执行时会找一个协调者，其它节点在执行时也会等一小段时间看是否有与之冲突的、时间戳更小的事务到达，之后：
- 如果没有这样的冲突的、时间戳更小的事务，执行子计划。
- abort掉子计划并告知协调者。
如果abort频率太高，H-Store会降级到其它策略，比如多等一会，或使用标准的乐观锁控制。