https://blog-image-1258275666.cos.ap-chengdu.myqcloud.com/My-Avatar.png

每周一论文:Bridging the Archipelago betweenRow-Stores and Column-Stores for Hybrid Workloads

论文摘要 传统的数据库分成两种不同类型: 偏重事务处理(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 有如下优势:

每周一论文:An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

论文概要 多版本并发控制(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 在事务过程中不可避免的会产生很多的旧版本,这些旧版本会在下列情况下被回收

每周一论文:A Survey of B-Tree Locking Techniques

论文概要 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 语句运行时编译

数据库性能之翼: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:内部调用陷阱

摘要 最近写代码,遇到一个 奇怪的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(); .