论文摘要 传统的数据库分成两种不同类型： 偏重事务处理（online transactional processin, OLTP）：此类数据库将不同属性连续存储，也即按行存储。按行存储可以使得插入/更新/删除更快，毕竟一条数据的所有属性是连续存储的。这种存储模型也叫做 N-Ary Storage Model (NSM)。 偏重数据分析（online analytical processing, OLAP）：此类数据库将不同数据的同一属性连续存储，也即列存储。这种存储可以使得查询操作只读关心的数据属性，而不是一整条数据，减少浪费；按列储存可以更好地支持复杂查询。这种存储模型也叫做 Decomposition Storage Model (DSM)。 很多企业架构中，这两种不同类型的任务分别有不同的技术栈不同的团队完成，且 OLAP（很多情况下也叫商业智能，Business Intelligence） 类的任务一般都离线进行；然而随着时间的推移，数据分析的价值越来越小。且技术上面临如下问题： OLAP 和 OLTP 系统间通常会有几分钟甚至几小时的时延，OLAP 数据库和 OLTP 数据库之间的一致性无法保证，很难满足对分析的实时性要求很高的业务场景。 企业需要维护不同的数据库以便支持两类不同的任务，管理和维护成本高。 企业软件开发团队需要为不同的数据库编写查询语句，且有可能需要将不同系统的数据进行聚合，开发成本高。 本篇论文描述了单一数据库如何支持分析(Hybrid transactional/analytical processing, HTAP) 。 HTAP 数据库列表 为了应对上述挑战，HTAP 数据库即单一数据库同时支持 OLAP/OLTP业务场景应运而生，比如： 腾讯云 TiDB 阿里云 HybridDB for MySQL 百度 BaikalDB 数据库 MemSQL HTAP 为什么合理？ 数据刚进入数据库的时，可称之为“热数据”；热数据在 OLTP 场景下会被频繁修改。此时数据宜行存储。 随着数据慢慢变久，数据越来越“冷”；这个时候数据不太可能被频繁的修改，对数据的查询和分析越来越多。此时数据宜列存储。 如何实现 HTAP？ 本篇论文提供了一种统一的架构，同时支持 OLTP/OLAP： 数据不再纯粹的行存储、或者列存储；而是按照块(Tile)连续存储，即若干属性组成一个块。 数据库执行引擎会实时收集执行的指标，这些指标通过聚类算法(K Means) 实时调整那些一个块由那些属性组成。“热数据” 块涵盖其所有属性，随着数据变“冷”，数据块仅涵盖相关性强的属性；即在行存储和列存储是块存储的两种不同的形式，在块存储中，数据随着时间的推移，慢慢由行存储变成列存储。 物理的数据块之上，提供了一次能够逻辑数据块的抽象，其主要的目的在于使得数据库的执行引擎无需关系数据的存储；操作开始执行的时候创建逻辑块，在最终返回结果的时候，将逻辑快转换成物理块，整个执行过程中，执行引擎无需知道块存储的细节。 HTAP 由于要支持 OLAP 场景，因此并发控制要求读不阻塞写，因此选择 MVCC 作为并发控制。 总结 在大数据推动行业发展的年代，企业往往选择多种数据库产品，分别支持在线交易、报表生成、日志存储、离线分析等，用以驱动业务的高速发展，但这种组合式解决方案，需要精细的控制不同产品间的数据流转和一致性问题，使用难度颇高，每个数据库产品间的数据同步和冗余，也带来了很高的成本开销，进一步限制了企业级应用的发展。HTAP 数据库在高度可扩展的情况下，同时支持 OLTP/OLAP，是解决这些问题的有效手段。

摘要 数据库索引是数据库中最重要的组成部分，而索引的数据结构设计对数据库的性能有重要的影响。本文尝试选取几种典型的索引数据结构，总结分析，以窥数据库索引之全貌。 B+Tree B+Tree 是一种树数据结构，是一个n叉排序树，每个节点通常有多个孩子，一棵B+Tree包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。 B+Tree 几乎是数据库默认的索引实现，其细节如下： 维基百科在 B+ 树中的节点通常被表示为一组有序的元素和子指针。如果此B+树的序数（order）是m ，则除了根之外的每个节点都包含最少$ {\displaystyle \lfloor m/2\rfloor } \lfloor m/2\rfloor$ 个元素最多 m-1 个元素，对于任意的节点有最多 m 个子指针。对于所有内部节点，子指针的数目总是比元素的数目多一个。因为所有叶子都在相同的高度上，节点通常不包含确定它们是叶子还是内部节点的方式。 每个内部节点的元素充当分开它的子树的分离值。例如，如果内部节点有三个子节点（或子树）则它必须有两个分离值或元素 a1 和 a2。在最左子树中所有的值都小于等于 a1，在中间子树中所有的值都在 a1 和 a2 之间((a1，a2]），而在最右子树中所有的值都大于 a2。 B+Tree 有如下性质： 查询时间复杂度为 $O(\log _{m}n)$ 插入时间复杂度 $O(\log _{m}n)$ 删除时间复杂度 $O(\log _{m}n)$ 搜索一个范围的键（k 个键）时间复杂度为 ${\displaystyle O(\log _{m}n+k)}$ B+ Tree 的多线程同步 **搜索：**从根节点开始，获取子节点的读闩，然后释放父节点的读闩；重复这个过程，直到找到目标节点位置。 **插入/删除：**从根节点开始，获取子节点的写闩；重复这个过程，直到找到目标节点位置；如果子节点是安全的，插入/删除不会引起树结构的变化即父节点不需要调整，可释放所有祖先写闩；乐观的插入/删除是先走搜索获得目标节点的读闩，如果目标节点并不安全，则回归上述从根节点获得写闩的过程。 Skip List（跳表） Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。 一个跳表，应该具有以下特征： 一个跳表应该有几个层（level）组成； 跳表的第一层包含所有的元素； 每一层都是一个有序的链表； 如果元素x出现在第i层，则所有比i小的层都包含x； 第i层的元素通过一个down指针指向下一层拥有相同值的元素； 在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)； Top指针指向最高层的第一个元素。 相对于 B+Tree，Skip List 有如下优势：

论文概要 多版本并发控制(Multi-Version Concurrency Control，以下简称MVCC) 是当今数据库领域最流行的并发控制实现，MVCC 在最大化并发度的情况下尽可能保证事务的正确性，其好处有： 写不会阻塞读 只读事务无需数据库锁就能支持可重复读 可以很好地支持历史数据查询 MVCC 的关键在于首先假设数据库读写冲突不会很大，其次通过维护同一份数据的多个版本，是的事务之间的冲突尽可能小；当一个事务修改数据的时候，创建一个新的版本，当一个事务读数据的时候，返回最新版本数据；所有对于数据的修改都发生在事务的私有空间内，在提交的时候进行验证。 当今主流的数据库基本都支持MVCC： 本篇论文系统的总结了 MVCC 的技术要点，包括： 并发控制协议 多版本存储 垃圾回收 索引管理 并发控制协议 MVTO 通过预先计算顺序的方式来控制并发；事务的读操作返回最新的没有被写锁锁定数据的版本；事务的写操作过程如下： 当前没有活跃的事务锁定数据 当前事务的事务编号大于最新数据中的读事务的事务编号 如果这上述条件成立，那么创建一个新的数据版本 MVOCC 在 MVOCC 中，事务被分成三个阶段，分别是： 读数据阶段，着这个阶段新的版本被创建出来。 验证阶段，在这个阶段一个提交编号被分配给该事务，然后基于这个编号进行验证； 提交阶段，完成提交。 MV2PL 顾名思义，MV2PL 是传统的两阶段锁在多版本并发控制中的应用；事务读写或者创建数据版本都需要获得对应的锁。 SSI 可串行化快照隔离(serializable snapshot isolation或SSI)是在快照隔离级别之上，支持串行化。PosgtreSQL 中实现了这种隔离级别，数据库通过维护一个串行的图移除事务并发造成的危险结构。 多版本存储 数据库通过无锁指针链表维护多个版本，使得事务可以方便的读取特定版本的数据。 仅限追加存储(Append-Only) 所有的版本存储在同一个表空间 更新的时候追加在版本链表上追加新节点 链表可以以最旧到最新的方式组织， 链表也可以以最新到最旧的方式组织，表头为最新版本 时序存储(Time-Travel Storage) 每次更新的时候将之前的版本放到旧表空间 更新主表空间中的版本 仅差异存储(Delta Storage) 每次更新近存储修改的部分，将其加入链表，主表空间存储当前版本 通过旧的修改部分，可以创建旧版本 垃圾回收 MVCC 在事务过程中不可避免的会产生很多的旧版本，这些旧版本会在下列情况下被回收

论文概要 B-Tree 及各种变种数据类型作为数据库索引已经有几十年的历史了，虽然此类数据结构功能简单，无非查询、插入和删除节点；然而并发控制却异常复杂，尤其是涉及到数据库事务的情况下。本篇论文系统的总结了基于 B-Tree 的数据库索引的并发控制，提纲挈领。 问题定义 数据库中的并发问题分为两类： 多线程并发访问内存数据的同步问题。数据库中有很多线程共享数据，比如数据库的锁定表(Locking Table)。此类问题即编程中常见的并发控制问题，通常大家通过锁(Locking)决此类同步问题，但在数据库同样的技术却被命名为闩(Latchs)，以便却别事务并发。 多个事务并发访问数据库内容的同步问题。比如两个事务并发读写问同一个索引节点，又或者两个事务同时读写同一个内存页。一般解决事务并发会用到锁(Locks)。 闩的实现 一切闩的基础 CAS(Compare and Swap): 即 CPU 原子指令，对于给定的内存地址M，比较其值A和给定值B CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论V值是否等于A值，都将返回V的原值。CAS 有效地说明了：我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可 数据库闩的实现 操作系统提供的互斥锁(Mutex): 其特点是简单易用；加锁或者释放锁操作需要系统调用，因此非常慢，大概需要几十 ns，大概相当于 100个 CPU 指令，50次 CPU L1 缓存访问。 读写锁(Reader and Writer Lock) 可以基于自旋锁实现；通过维护一个读和一个写的原子计数，允许多线程并发读；读写锁的设计需要考虑很多问题，读和写的优先级如何保证？锁的公平性如何保证？ 检查并设置自旋锁(Test-and-Set Spin Lock): Test-and-Set 是 CPU 的原子指令，给制定内存设置给定的值，并返回旧值。Test-and-Set SpinLock 是操作系统常用的锁技术，比较高效，但并不保证公平性。 排号自旋锁(Queue Based Spin Lock) MCS: 基于链表的自旋锁 MCS Spinlock 是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，直接前驱负责通知其结束自旋，从而极大地减少了不必要的处理器缓存同步的次数，降低了总线和内存的开销。笔者使用 Linux 内核开发者 Nick Piggin 的自旋锁压力测试程序对内核现有的排队自旋锁和 MCS Spinlock 进行性能评估，在 16 核 AMD 系统中，MCS Spinlock 的性能大约是排队自旋锁的 8.

数据库性能之翼：SQL 语句运行时编译 摘要 现代服务器的一大特点是内存越来越大，对于运行在这些服务器上的数据库，性能的瓶颈是 CPU 而非内存；然而传统 SQL 执行模型即“火山模型” 诞生于内存是瓶颈的年代，其以行为单位的迭代执行过程虽然灵活，但对 CPU 非常不友好。 在这个大背景下，SQL 语句运行时编译技术应运而生，为传统的关系型数据库的 SQL 执行性能插上翅膀。 一些 SQL 编译的实现如下： Apache Spark Tungsten 引擎运行时将 SQL 语句的 Where 部分转换成抽象语法树，然后再讲抽象语法树运行时编译成 Java 字节码。 Oracle 数据库将 SQL 语句运行时转换为 C\C++ 代码，然后将其编译为机器码。 Postgres 11 中提供了基于 LLVM 的即时编译(JIT) 的 SQL 语句执行引擎。有实验证明 Postgres 上 SQL 语句编译技术能够将 Postgres 的事务处理能力提升20%之500%。 随着 CPU 和多核瓶颈日益凸显，SQL 语句编译技术会成为重要的数据库性能提升技术。希望读者通过本篇博客能够了对 SQL 编译技术有个大概的认识。 为什么要进行 SQL 编译 通用（抽象） vs 定向优化 SQL 是一个非常优秀的抽象模型；对于使用者来讲，SQL 简单易用，不用关心 SQL 背后的诸如存储、同步及先写日志等细节；从而使得： SQL 可以运行在任何一台计算机上 开发人员不需要关心 SQL 语句的执行过程，通过陈述的方式描述业务逻辑 另外一方面，现代的计算机硬件在不断进步，SQL 语句运行速度的关键是针对这些硬件进行定向优化。

摘要 最近写代码，遇到一个 奇怪的Spring AOP 有关的问题；本文从这个问题出发，通过问问题的方式揭示这个问题背后深层原因。 AOP 问题代码清单 AOP Aspect: HttpHeaderValidator.java 1 2 3 4 5 6 7 @Aspect public class HttpHeaderValidator { @Before public void isUserInfoExist(){ ... } } AOP Joint Point: Logger.java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 @Aspect public class Logger { public void logTransactionA(){ String user = this.getUserFromHeader(); .