发表于

目录

  • 分布式事务的需求与挑战
  • Google Percolator简介
  • Apache Tephra简介
  • 附录

分布式事务的需求与挑战

分布式事务的需求在于同时更新两个或两个以上的数据记录时，需要保持其原子性。往大一点说，就是对两个账户之间进行转账操作，不能一个账户成功，另外一个账户失败。往小一点说，对数据建立索引，不能数据更新了，索引更新失败。

业务里面有许多情况都需要实现事务，其实事务完全可以在应用层面来完成。举个简单例子，支付网关的实现：两套系统之间通过约定的协议进行交互，双方响应确认后，事务成功，否则失败。不过这种事务衡量的标准是BASE，并不是强一致性。

强一致性分布式事务传统的实现方法是2PC。2PC因为其可用性及锁粒度，一直被诟病，无法应用于大规模高并发的场景，而恰恰随着业务的发展，大规模高并发会是分布式事务遇到的第一个门槛。

Google Percolator简介

Google Percolator（简称Percolator）提出了强一致性分布式事务的解决方案，解决了传统2PC的缺陷。首先，通过MVCC机制，消除了锁机制带来的并发性问题；其次，通过依赖底层存储的高可用性和细粒度锁，将分布式事务失败带来的影响降低到很低的程度。

Percolator的构思很巧妙，既然底层的存储可以支持单操作ACID，那么就可以在单操作ACID的基础上，构建出多操作的ACID，这其实和数据库实现ACID的思路是一样的。通过类似WAL的操作，记录操作的状态，如果完成则设置为成功，否则就是一段废弃的操作记录。

在分布式环境下，MVCC并发提交的时候，会面临如何确保来自不同的客户端的请求，可以按先后次序进行排队操作的问题。Percolator是通过原子钟实现全局时钟的方式对操作进行排序。在实际实现中，通过全局授时也是可以的。

附录中有Percolator的介绍，含paper地址和中文简介。不过中文简介中步骤的描述有一些瑕疵，对时序6中，写上data@5并没有阐述，在下面的整体流程中，会补充说明一下。

整体流程大致如下：

  • 参与操作的所有记录都打上写时序标记，进入写锁状态
  • 对所有的操作记录进行操作，操作时，会记录当前记录操作关联的记录，这样当自己操作失败时，可以追溯到上一条记录进行回滚
  • 当所有的操作都成功时，开始改变自身的锁状态，完成数据的提交

MVCC机制在Percolator的实现中，是关键基石。有了MVCC，才能保证数据在事务没有结束前，也可以被访问。

Apache Tephra简介

Apache Tephra（简称Tephra）是专用于HBase的分布式事务实现。包含以下模块：

  • 客户端模块，负责发起事务的操作
  • HBase corprocessor模块，通过改变HBase的存储逻辑完成Percolator中记录状态的逻辑
  • 服务器模块，实现事务的控制，支持zookeeper管理下的单主多实例，通过zookeeper保证数据的一致性，以及管理多个服务器模块的选主

从实现上来看，把事务控制放在服务器模块，必然会带来服务器模块的性能问题。如何实现多服务器的事务管理以及如何保证服务器模块的数据一致性问题，这是Tephra可以改进的地方。

附录

发表于

目录

  • 引入Bitmap倒排索引
  • BitmapInvertedIndex
  • KtSQL的实现思路
  • 附录

引入Bitmap倒排索引

多维查询支持对于复杂化查询是一项必备的功能，KtSQL在设计时，则把复杂化查询作为一项核心特性考虑到系统实现中。对于以实时小批量查询为主要应用场景的事务型数据库，bitmap索引自然成为首选的对象之一。

复杂查询中，bitmap支持对某类对象的特性进行查询，如查询符合某些过滤条件的物品。bitmap还可以对多个集合间的关系进行处理，如进行or或and处理。bitmap还支持如TopN、contains、Total等操作，对于计算下推，这些功能都有极大的帮助。

不同于bitmap是把多个维度值作为一个单值进行编码，倒排索引对每一个column的值进行编码。倒排索引帮忙我们把每一个列(column)的取值映射到编码后，建立起取值编码和对应的rowkey位置的关系。通过bitmap计算，即可快速得出取值对应的rowkey值。

BitmapInvertedIndex

BitmapInvertedIndex在OLAP是较常见的，业界有名的案例是apache druid, linkedin pinot。

Pinot BitmapInvertedIndex的实现细节描述如下：

  1. 使用roaringbitmap作为底层的实现支持
  2. 数据保存在文件上，inverted index存储的方式：|1st start|1st end|2nd end|…|data for 1st bitmap|data for 2nd bitmap|…
  3. 支持保存在OnHeap和OffHeap，接口提供了addSingleColumn和addMultiColumn，参数为docId和dictId
  4. 每一个column会创建一个InvertedIndexCreator，以OnHeapBitmapInvertedIndexCreator为例
  5. 每个OnHeapBitmapInvertedIndexCreator包含一个MutableRoaringBitmap[]，用来保存每个column的bitmap array
  6. MutableRoaringBitmap支持serialize写到stream

KtSQL的实现思路

参考Pinot的实现，先实现OnHeap模式，创建inverted index时，每个column创建一个bitmapInvertedIndex，采取实时构建的方式，通过适当牺牲入库的性能，避免复杂化数据的查询步骤，流程如下：

  • 将rowkey映射到array index中，把rowkey编码成唯一值，如取值为long，可以容纳 2^64 的数值
  • 不允许对建立了位图倒排索引的数据记录进行删除，也不允许对rowkey进行修改
  • 将每一个column的取值进行编码（依赖全局字典），对该取值维护一个队列，记录该值所在的rowkey对应的long值
  • 因为每个取值都会消耗掉一个array，所以column的取值越多，存储空间消耗越大。所以有观点提出column取值应该在10万以下，过多则不适合建立bitmap索引。
  • 全局字典表在分布式环境下，面临一个同步的问题，构建全局字典表。需考虑算法上支持特定值的编码在不同环境下取值一致是否可行，否则就需要用强一致的共享内存进行编码同步处理。
  • 位图倒排索引的数据保存在hbase中。在分布式环境下不同节点都需要访问同一份位图倒排索引，也需要维护数据和位图倒排索引的强一致性。这种处理方法也可避免在内存中过大。

实时入库，会面临rowkey动态增加和column值编码持续增加的情况，也要面对分布式环境下编码一致性的问题

附录

发表于

目录

  • Calcite实现DML操作的概述
  • Calcite DML操作的详解
  • Calcite DML的性能及优化思路
  • 附录

Calcite实现DML操作的概述

Calcite使用javacc生成语法解析器，javacc和freemaker模版技术为解析器的自定义提供了可能，SQL语句经过解析后，生成SqlNode，然后通过convertQuery转换成RelNode。RelNode用于表达逻辑表达式，也用于优化执行树，最后的RelNode逻辑树生成后，转成Expression(Node)，Expression具备转换成java代码的能力，然后再通过JinanoCompiler转换成字节码执行。这是三次解析一次编译的执行过程。

SqlNode转换成RelNode的时候，会补充上下文，所以RelNode包含丰富的相关信息，可用于执行计划的优化。但是RelNode转换成Expression时，很多上下文信息是无用的，会被丢弃。

Calcite内置了EnumerableConvention用于实现SQL的查询语句，Expression在转换成java代码时，使用Enumerable表达SQL语句的相关操作，对于不能全面支持SQL操作的adaptor，借助转换成Enumerable，是保证adaptor能全面支持SQL操作的关键。那么存储层只需要实现数据读写即可满足SQL的DML操作。

Calcite DML操作的详解

DML相关功能对应模块

概述环节对主要流程进行了描述，现对各流程中，DML操作的过程使用到的模块进行说明。

ModifiableTable赋予了Table查询和修改的能力，ModifiableTable继承QueryableTable，Queryable继承Enumerable，Queryable提供了数据的查询能力。也就是说，当需要select的时候，QueryableTable会被调用；而insert/update/delete时，ModifiableTable会被调用。

查询select的实现流程

在查询(select)时，有两种查询数据的方法，分别是：Schemas.queryable和Schemas.enumerable

Schemas.queryable会调用table.asQueryable，把需要查询的数据转换成Enumerable，这时的操作，需要table adaptor实现接口table.asQueryable

Schemas.enumerable会调用table.scan，把数据从table中读出来，这时的操作，需要table adaptor实现接口table.scan

具体采用哪种(queryable/enumerable)转换的方式，是在RelOptTableImpl.getClassExpressionFunction中实现的，做计划优化的时候(Prepare.optimize)，RelNode.optimize会调用RelOptTableImpl.create，RelOptTableImpl.create会调用RelOptTableImpl.getClassExpressionFunction来完成转化，queryable此时调用getExpression作为参数传给RetOptTableImpl，而enumerable调用Schemas.tableExpression

修改操作的实现流程

在修改时，Insert语句从SqlNode转换到RelNode，再转换到Expression。

  • parseQuery

    • values(…)在sql parse的时候，会被转换成为row(…)，表示一个结构体类型

  • convertQuery

    • validate，SqlValidatorImpl会执行操作值数量检查checkFieldCount、操作值类型检查checkTypeAssignment、约束检查checkConstraint、权限检查validateAccess，依赖adaptor getRowType的实现
    • convert，convertInsert会调用createModify，toModificationRel被调用，用于获取adaptor的上下文并保存到RelNode中。KtSQL只需要获得table的实例即可包含所需的上下文
    • optimize，convert返回的是LogicTableModify，经过optimize后，变成了EnumerableTableModify。optimize会把传进去的RelNode都转成EnumerableRel，才能和下一环节的implement对接

  • implement

    • EnumerableInterpretable.toBindable被调用，Calcite系统允许提供多个Implementor，且每个Implementor对节点的解析机制可以不一样，默认的实现是EnumerableInterpretable。通过遍历每一个节点的implement，生成Bindable返回。
    • RelNode需要被转换为Bindable执行，Bindable继承InterpretableRel，包含implement接口，实现该接口的Bindable，可以返回Java代码。EnumerableTableModify.implement就是代码生成的一个例子，根据需要调用的函数，输出相应的字符串。
    • Bindable的子类包括有：BindableAggregate, BindableFilter, BindableProject, BindableJoin, BindableSort, BindableTableScan, BindableUnion, BindableValues, BindableWindow, EnumerableBindable, EnumerableInterpretable. 所以可以需要实现代码输出的子类是可控的，可实现的。

toModificationRel

RelNode在SqlToRelConverter的过程中，需要根据SqlNode的输入，生成特定的RelNode，adaptor的接口，需要按RelNode的需要，提供相关的信息。遗憾的是，这部分的说明，Calcite官方并没有给出很好的文档指引。

toModificationRel会生成TableModify，在SqlToRelConverter中被调用，用于获取相关的上下文并保存到RelNode中，Interpreter调用TableModify最终会转换为EnumerableTableModify，并且在转换成执行的binary code时，调用getModifiableCollection()

TableModify是RelNode的子类，用于把DML操作转换为Enumerable操作，并实现了TableModify转换到Expression的逻辑。

继承于TableModify的EnumerableTableModify和JdbcTableModify，都实现了implement接口，但是两者的含义一样，实现并不一样。EnumerableTableModify扩展于EnumerableRel，但JdbcTableModify扩展于JdbcRel。

Calcite对语法树的解析，支持通过实现RelImplementor接口，来获得不同的implementor的能力，在系统中，现在有两个实现，分别是JavaRelImplementor和EnumerableRelImplementor，

Calcite DML的性能及优化思路

在现代计算机的单核CPU上，Calcite解析转换一条DML操作的耗时为毫秒级，对于需要复杂计算的select语句，转换的耗时是很小的。对于KtSQL的分布式架构来说，Calcite的SQL解析处理并不会成为瓶颈，反而是Enumerable的计算能力受限于CPU和内存。

单机的数据库系统，受限于单机的计算机架构，只能满足百万级数据的快速处理。JVM受限于其实现机制，千万级的数据处理就需要消耗上百G的内存，如果要把计算能力提升到十亿级别，则对计算能力的优化提出了极大的挑战。数据量越小，主键和二次索引对操作的影响越大。随着数据量的上升，则基于二次索引和范围处理的优化显得越发重要。Spark tungsetn、Kylin的RoaringBitmapIndex、SnappyData的基数引擎，都是计算优化的极好案例。Enumerable的优化有多种思路，比如支持网络堆外内存读取、堆外内存计算、异构计算加速，都可以有效提升计算的能力。这是将来可以优化的方向，而且其优化的思路与最终需适应的场景息息相关。

附录

发表于

目录

  • 分布式数据库与系统设计
  • 在KtSQL中拓展一个类型的支持
  • Calcite的类型系统设计思路

分布式数据库与系统设计

对数据的处理，如果需要在应用层考虑底层的分布模型及实现，就会造成应用层的复杂度上升。比如，把汽车的位置存储到分布式数据库中，并获取距离A点最近的100辆汽车，把数据库里面所有的数据取出来计算，这样的做法是不可取的。分布式数据库除应当解决数据规模带来的存储挑战外，还应该简化数据的处理模型。

在上述的例子中，把坐标转换成可以计算的数据类型，并以此类型作为检索主键，将会大大加速处理的速度。我们知道，用GEOHASH可以把多维坐标位置转换成单值并作为主键，可以获得很好的数据处理速度。

由此可见，要在大规模数据的前提下，获得良好的数据处理能力，我们需要以下元素：

  • 可以把数据转换成底层系统可以处理的数值类型
  • 支持对数值类型的索引，以便提升处理的速度
  • 底层系统支持分布式处理的计算能力，从而获得计算能力的提升

在KtSQL中拓展一个类型的支持

KtSQL通过以下三个设计来获得良好的数据处理能力：

  • 在SQL引擎层支持自定义函数，可以实现数据类型的转换
  • 支持主键索引、二次索引的机制
  • 通过对存储层计算下推能力的扩展，获得分布式处理能力

引擎层支持的数值类型，直接影响着下层的具体实现。下面对SQL引擎层Calcite的类型系统设计思路进行阐述，以满足将来可能需要的各种扩展。

Calcite的类型系统设计思路

Calcite支持SQL2003中定义的数值类型。KtSQL前端现采取兼容MySQL协议的方式实现，也就意味着Calcite的类型系统需要具备从MySQL类型转换到Calcite类型的能力。同时，下层存储以Binary格式进行存储，不具备类型能力，这意味着Calcite的类型系统能够进行类型转换，并且具备元数据的能力。Calcite用Java实现，如果要实现类型转换成到runtime可以处理的类型，还需具备转换到Java类型系统的能力。

Calcite使用以下类来表达类型系统：

  • SqlLiteral：在解析SQL语句的过程中，用来表达类型的类。
  • SqlTypeName：SQL语句中支持的类型，SQL2003标准中，列举的需要支持的类型超过了Java语言中定义的SQL基础类型。
  • SqlTypeFamily：SqlType类型分类的枚举，定义了支持的类型分类。支持JdbcType里面的类型与SqlType进行相互转换。
  • RelDataTypeSystem：类型描述类系统，SqlTypeName的辅助类，如获取精度、长度、是否自增等属性。
  • RelDataType：类型描述类，用于描述一个算式或查询返回的一行的类型，即可以用于描述一个或多个的SqlType。RelDataType支持持久化，支持枚举组成RelDataType的每一个元素的类型。
  • RelDataTypeFactory：类型描述类工厂，支持从一个Clazz获取对应的RelDataType，支持从SqlType转换为RelDataType。

RelDataType是类型的描述类，借助TypeSystem、TypeName、TypeFamily，RelDatType获得了元数据的能力，通过RelDataTypeFactory，可以实现不同的类型转换。SqlLiteral是SQL描述，提供了变量的最初的信息。

发表于

目录

  • DDL在线操作的场景
  • DDL在线操作实现的思路
  • 补充材料
  • 附录

DDL在线操作的场景

最近在考虑KtSQL的索引实现，涉及到在线索引新建的思考。
如果要求系统在表创建时，就建立合理的索引格式，这是不符合实际情况的。所以索引建立存在运行后重建的需求。

索引的重建需要允许在线，对一个大规模的在线服务系统而言，停机是不允许的。

DDL在线操作实现的思路

约束

  • 数据一致性
  • 并发操作
  • 性能

数据一致性

索引建立过程中，如果允许数据变更（DELETE、UPDATE、INSERT），会导致索引和数据的不一致性，
所以数据库的常规做法，是对需要建立索引的表进行锁定，只允许查询，直到索引建立完毕后，才允许解除锁定。

并发操作

既然要实现DDL在线操作，分布式的环境下，必须要考虑操作的并发性，最直接的做法自然是操作串行。
对一个表进行串行修改，可以用锁机制来实现。

不同于DML可以采用MVCC和统一事务服务做隔离，DDL会对分布节点都产生影响。所以DDL操作时，
需要获得操作目标的锁才能进行操作。

锁的粒度决定了运行的性能，如只需要锁定元数据而不需要对表进行锁定，但是也不必过度追求并发，
如对表先拷贝后全量处理，再锁定原表增量处理的做法，就是很消耗资源的做法。

元数据和表数据可以分离，好处是对元数据锁定并进行操作时，DML依然可以运行。

HBase对表进行操作的时候，会先disable table。这个过程会关闭掉所有region server的handler，
HBase对元数据操作的方式，影响到并发操作的具体实现。

MySQL采用分级锁机制对数据请求进行分级：

  • LOCK=NONE: Permits concurrent queries and DML.
  • LOCK=SHARED: Permits concurrent queries but blocks DML.
  • LOCK=DEFAULT: Permits as much concurrency as possible (concurrent queries, DML, or both).
  • LOCK=EXCLUSIVE: Blocks concurrent queries and DML.

性能

假如需要对10亿的数据进行索引创建，共100个节点，则单个节点需要处理对千万级数据进行处理。
同时要生成10亿的数据记录，引发的网络通信和读写操作都将是很大的消耗。

补充材料

MySQL DDL的锁级别

假设要进行DDL，必须要执行锁的话，哪一种锁级别是在保证逻辑正确性的前提下性能最好的？MySQL整理了一些可以参考的思路。

Operation In-Place? Copies Table? Allows Concurrent DML? Allows Concurrent Query? Notes
添加索引 Yes* No* Yes Yes 对全文索引的一些限制
删除索引 Yes No Yes Yes 仅修改表的元数据
OPTIMIZE TABLE Yes Yes Yes Yes 从 5.6.17开始使用ALGORITHM=INPLACE，当然如果指定了old_alter_table=1或mysqld启动带–skip-new则将还是COPY模式。如果表上有全文索引只支持COPY
对一列设置默认值 Yes No Yes Yes 仅修改表的元数据
对一列修改auto-increment 的值 Yes No Yes Yes 仅修改表的元数据
添加 foreign key constraint Yes* No* Yes Yes 为了避免拷贝表，在约束创建时会禁用foreign_key_checks
删除 foreign key constraint Yes No Yes Yes foreign_key_checks 不影响
改变列名 Yes* No* Yes* Yes 为了允许DML并发, 如果保持相同数据类型，仅改变列名
添加列 Yes* Yes* Yes* Yes 尽管允许 ALGORITHM=INPLACE ，但数据大幅重组，所以它仍然是一项昂贵的操作。当添加列是auto-increment，不允许DML并发
删除列 Yes Yes* Yes Yes 尽管允许 ALGORITHM=INPLACE ，但数据大幅重组，所以它仍然是一项昂贵的操作
修改列数据类型 No Yes* No Yes 修改类型或添加长度，都会拷贝表，而且不允许更新操作
更改列顺序 Yes Yes Yes Yes 尽管允许 ALGORITHM=INPLACE ，但数据大幅重组，所以它仍然是一项昂贵的操作
修改ROW_FORMAT和KEY_BLOCK_SIZE Yes Yes Yes Yes 尽管允许 ALGORITHM=INPLACE ，但数据大幅重组，所以它仍然是一项昂贵的操作
设置列属性NULL或NOT NULL Yes Yes Yes Yes 尽管允许 ALGORITHM=INPLACE ，但数据大幅重组，所以它仍然是一项昂贵的操作
添加主键 Yes* Yes Yes Yes 尽管允许 ALGORITHM=INPLACE ，但数据大幅重组，所以它仍然是一项昂贵的操作。如果列定义必须转化NOT NULL，则不允许INPLACE
删除并添加主键 Yes Yes Yes Yes 在同一个 ALTER TABLE 语句删除就主键、添加新主键时，才允许inplace；数据大幅重组,所以它仍然是一项昂贵的操作。
删除主键 No Yes No Yes 不允许并发DML，要拷贝表，而且如果没有在同一 ATLER TABLE 语句里同时添加主键则会收到限制
变更表字符集 No Yes No Yes 如果新的字符集编码不同，重建表

参考