技术想法分享

[codefollower]

此贴用于记录、分享日常工作中随时出现或已经实现的技术想法。

目录:

1. 事务引擎 - 读时撤销算法

2. 事务引擎 - 列锁

3. 存储引擎 - 以 Page 为粒度的混合行列存储

4. 存储引擎 - 异步并行化的无锁 BTree

5. Java语言 - 接口默认方法-多重继承

6. 数据库 - 统一的异步任务调度器

[codefollower]

技术分类: 数据库-事务引擎
技术思想: 读时撤销算法
实现状态: 已经实现

细节描述:

Lealone 数据库很早就使用了事务引擎与存储引擎分离的架构，例如内置的 AOSE 自适应优化存储引擎和 MVCC 多版本并发控制事务引擎就是采用这样的架构设计的。

不同于 MySQL 中的 InnoDB 和 MyISAM 存储引擎，常见的说法是某某存储引擎是否支持事务，比如 MyISAM 不支持事务，InnoDB 是一个支持事务的存储引擎，这种说法代表了在传统观念中事务是应该内置到存储引擎中去实现的。

Lealone 打破了这种传统观念，按关注点分离的原则，存储引擎就只负责数据的读写，而事务引擎只专注事务的 ACID 特性的实现，不同的存储引擎和事务引擎可以相互搭配使用，比如，如果单独使用 AOSE，那么按传统观念就是一个不支持事务的存储引擎，搭配了 MVCC 事务引擎后，AOSE 就支持事务了。

事务引擎与存储引擎分离是一种灵活优雅的架构，在 Lealone-Plugins 项目中就额外支持三个第三方的存储引擎: MVStore、RocksDB、WiredTiger，这三个存储引擎有的内置了事务支持(比如 WiredTiger)，有的不支持，不管是否支持事务，第三方存储引擎中的事务用于数据库中都不够优雅，因为数据库中的事务涉及的面比较广，更适合放到上层去做，而不是放入存储引擎这种更低的层次中。

得益于这种分离的架构，通过搭配 MVCC 事务引擎，为 Lealone 数据库引入第三方的存储引擎就轻而易举了，不管第三方的存储引擎是否支持事务，都只单纯的将它们用于简单的数据读写，忽略它们的事务功能。

当然，这种架构也有缺点，比如有的存储引擎像 MVStore 内置了数据自动保存机制，按照事务引擎的常见要求来看，如果当前某个事务把底层存储引擎中的数据加载到内存修改了，在事务未提交前，然后底层存储引擎很快就把内存中的脏数据保存到硬盘了，更糟糕的是，如果此时系统立刻崩溃了，事务无法再提交，那么重启系统时就读到不一致的数据了。

正因为这种事务引擎与存储引擎分离的架构，导致了底层存储引擎保存数据的时机是不可控的，虽然 MVStore 也提供了禁用自动保存的参数，但是既然选择了这种分离的架构，理想情况是上层的事务引擎就应该无视或不关心底层存储引擎的实现细节。

为了解决这种分离架构的缺点，Lealone 引入了一种读时撤销算法，因为写入底层存储引擎的每一条记录都会最终系列化为一个 Key/Value ，而 Lealone 的 MVCC 事务引擎在写入前会对其中的 Value 再包装一次，变成一个 TransactionalValue，如果是已经提交的事务，那么会在 TransactionalValue 中多加一个字节，代表这个 Value 是已经提交的正常数据了，如果是未提交的，那么会在 TransactionalValue 中记下事务 ID 和原来的值，当下次读出这个值时，会使用读时撤销算法去判断，如果它的事务 ID 小于当前事务的所有 ID，那么就肯定知道它是在系统崩溃前写入的脏数据(事务 ID 是递增的，当前正在运行的事务 ID 总是大于原来的事务 ID)，然后就可以进行撤销了，如果原来的值为空，说明上次是一次 insert 操作，撤销时直接按 Key 删除即可，如果不为空，可能是 update 或 delete(未提交事务在执行delete前只是把原来的值设为null，并未真实删除，直到提交时才删除)，那么重新用原来的值替换。

使用了读时撤销算法后，上层的事务引擎就不用再关心底层的存储引擎的实现细节了。

另外一些可能的方案:

比如引入传统的 undo 日志，在内存中修改记录之前就先把 undo 日志同步到硬盘，因为 Lealone 自身已经用了 redo 日志记录正常提交的事务了，所以再引入 undo 日志变得不够高效，使用读时撤销算法即能达到 undo 日志的效果，又能节省大量开销，毕竟在系统崩溃前存储引擎保存的未提交事务的脏数据是比较少的，发生的频率也很低。

[codefollower]

技术分类: 数据库-存储引擎
技术思想: 相比于行存储，几乎无读写开销的以Page为粒度的混合行列存储
实现状态: 已经实现

细节描述:

不管是传统的像 MySQL 还是新型的像 Lealone 这样的关系数据库，都会优先考虑使用按行顺序存储的底层存储模型，行存储实现简单，如果字段数不多，每次查询都会查大多数字段时就不存在什么问题，如果有上百个字段，当执行少量字段查询或者进行max(f1)、avg(f2)这样的聚合运算时就会加载其他大量没用到的字段，不但浪费内存，性能也慢。

显然，当加载少量字段时，列存储就有明显优势了，只要按需读取相关列即可。

过去，一些存储引擎会把一些列组合成一个分组，比如 HBase 就有 Column Family 的概念，每个分组会存入不同的文件中，这种方案是以牺牲写性能为代价的，一行记录分开写入不同文件会影响性能。

如果不引入列分组的概念，又不写入多个文件是不是更好呢？考虑到关系数据库的行式存储引擎都会使用B-Tree(或它的变体)来组织数据，B-Tree 通常都由一个个的 Page 组成一棵有层次的树，Page 又细分成 Node Page 和 Leaf Page，Node Page 只存放搜索 Key 和子 Page 的引用，每个 Leaf Page 存放一个小范围内的记录，以 Page 为粒度的混合行列存储思想 就是把原有的 Leaf Page 再按字段切分成多个 Field Leaf Page，这些 Field Leaf Page 是连续存放的，共同组成一个 Row Leaf Page，而 Node Page 保持不变，当上层查询数据时，只需提供搜索 Key 和搜索字段，只要每个 Page 都对应一个起始物理位置，当通过Node Page 定位到所属的 Row Leaf Page 后，只需要按搜索字段读取对应的 Field Leaf Page 即可。

Lealone 目前已经支持按 SQL 优先级来调度任务了（慢 SQL 会随着执行时间变长被降低优先级，保证新来的 SQL 有机会运行），如果配合这里的混合行列存储思想，那么对于实现真正的 HTAP(Hybrid Transactional/Analytical Processing) 数据库会带来很大的想像空间。

2018/10/12 补充说明:

在行式存储中，通常每个 Leaf Page 的大小在 4kb - 16kb 之间，所以对于字段数很多的记录，一条记录占用的大小就常常超过 1kb 了，所以导致一个 Leaf Page 只能存放几条记录，每个 Leaf Page 存放的记录数少，又会直接影响 B-Tree 的层数，层数越多，中间的 Node Page 就越多，从而导致读一批记录的某几个字段要加载无数个 Page ，如果按列存储，每个 Leaf Page 就能转成类似 Node Page 的角色了， Leaf Page 被细分为多个 Field Leaf Page，这样划分之后，只有 Leaf Page 的记录数越多，那么切分成多个 Field Leaf Page 才有意义，如果像最初只有几条记录，那么每个 Field Leaf Page 就过小了。

归属到每个 Leaf Page 的记录数越多，那么 B-Tree 的层数就会越少，同时，又能按需加载不同的 Field Leaf Page，从而能有效解决多字段表的存储问题。

2018/10/13 更新:

初步做完原型，如果有10个字段，列存储模型只取两个字段时，性能是行存储的5倍以上，
因为行存储需要完整读取所有字段，光是反系列化的时间就多了5倍。

2018/10/14 更新:

已经实现

[codefollower]

技术分类: Java语言-接口默认方法
技术思想: 使用接口默认方法和简单的适配器模式让实现类模拟出多重继承的效果
实现状态: 已经实现

细节描述:

虽然多重继承有很多问题，但是在某些场景下使用多重继承能让代码更简洁，Java 语言不直接支持多重继承，过去只能同时实现不同接口来达到类似多重继承的效果，但是这种方式常常产生冗余的代码或设计出更多的类来满足，继承能复用代码减少冗余。

从 Java 8 开始引入了接口默认方法，这能让多重继承的模拟变得更优雅。

最近就碰到了一个适合使用多重继承的场景，Lealone 数据库在网络层设计了 NetServer 和 NetClient 两个接口，提供了一种插件机制，让不同的网络框架可以集成进来，比如6个实现类 VertxNetServer/VertxNetClient、NettyNetServer/NettyNetClient、MinaNetServer/MinaNetClient 分别用于集成 Vertx、Netty、Mina，另外，基于 NIO 还实现了内置缺省的 NioNetServer/NioNetClient。

因为所有的 NetServer/NetClient 实现类都有一些共同的行为，比如 start、stop、连接管理等等，所以适合把这些行为抽取出来放入基类中，所有的实现类直接从基类 NetServerBase/NetClientBase 继承。

不同于其他实现类，内置缺省的 NioNetServer/NioNetClient 是基于 NIO 原生实现的，其他实现类都只是简单的对现有网络框架或工具库的封装，所以 NioNetServer/NioNetClient 有更多的实现细节要考虑。

目前，NioNetServer/NioNetClient 都是基于 Event-Loop 的方式设计的，在一个线程中循环处理所有操作。两者都包含网络读写操作，NioNetServer需要额外处理 ACCEPT 操作，而 NioNetClient 多了 CONNECT 操作需要处理。

NioNetServer/NioNetClient 除了都有网络读写操作这样的相同行为外，还包括 select、wakeup 之类的相似操作，所以这些行为很适合设计成一个接口: NioEventLoop，然后使用者基于这个接口去调用。

为了复用代码，可以为 NioEventLoop 接口提供一个基类: NioEventLoopBase，但是考虑到 NioNetServer/NioNetClient 已经继承自NetServerBase/NetClientBase 了，所以不能再继承NioEventLoopBase。

另一个可行的方案是再额外设计两个类: ServerNioEventLoop/ClientNioEventLoop，让它们继承 NioEventLoopBase，然后在 NioNetServer/NioNetClient 中使用它们，这种方案的缺点是又多出了两个类，而且从类层次上看，已经看不出 NioNetServer/NioNetClient 是使用 Event-Loop 的线程模型了。

虽然从 Java 8 开始提供接口默认方法了，因为接口不能有实例字段，所以不适合保存状态，虽然接口默认方法能提供默认行为，当不能保存状态时使用场景还是受到很多限制，仅仅使用接口默认方法还解决不了问题。

所以，最终得出了如下方案:

先设计一个 NioEventLoopAdapter 类充当适配器，它实现了 NioEventLoop 接口中的通用行为，而 NioEventLoop 接口 API 使用简单的默认方法实现，所有默认实现都只是调用 getDefaultNioEventLoopImpl() 得到默认实现类让它去执行。

public interface NioEventLoop {

    NioEventLoop getDefaultNioEventLoopImpl();

    default void read() {
        getDefaultNioEventLoopImpl().read();
    }

    default void write() {
        getDefaultNioEventLoopImpl().write();
    }

    default void select() {
        getDefaultNioEventLoopImpl().select();
    }

    default void wakeup() {
        getDefaultNioEventLoopImpl().wakeup();
    }
}

public class NioEventLoopAdapter implements NioEventLoop {
    @Override
    public NioEventLoop getDefaultNioEventLoopImpl() {
        return this;
    }

    @Override
    public void read() {
         // do something
    }

    @Override
    public void write() {
         // do something
    }

    @Override
    public void select() {
         // do something
    }

    @Override
    public void wakeup() {
        // do something
    }
}

最后，NioNetServer/NioNetClient 在内部使用 NioEventLoopAdapter，但是依然实现 NioEventLoop 接口，只是依据自己的特殊情况覆盖具体的 API 即可。

public class NioNetClient extends NetClientBase implements NioEventLoop {
    private NioEventLoopAdapter nioEventLoopAdapter = new NioEventLoopAdapter();

    @Override
    public NioEventLoop getDefaultNioEventLoopImpl() {
        return nioEventLoopAdapter;
    }

    @Override
    public void write() {
         // 覆盖 NioEventLoopAdapter 的 write 实现
    }
}

public class NioNetServer extends NetServerBase implements NioEventLoop {
    private NioEventLoopAdapter nioEventLoopAdapter = new NioEventLoopAdapter();

    @Override
    public NioEventLoop getDefaultNioEventLoopImpl() {
        return nioEventLoopAdapter;
    }

    @Override
    public void read() {
         // 覆盖 NioEventLoopAdapter 的 read 实现
    }
}

实际场景完整的代码在下面几个文件中:

NioEventLoop
NioEventLoopAdapter
NioNetServer
NioNetClient

[codefollower]

技术分类: 数据库-事务引擎
技术思想: 列锁
实现状态: 已经实现

细节描述:

如果以Page为粒度的混合行列存储能实现，是否可以在事务引擎中引入更加细粒度的列锁？
最常见的是行锁，Lealone 数据库也支持行锁，但是有时候两个事务根据同一个记录 ID 修改这条记录的不同字段由于行锁的存在是不被允许的，如果有了列锁，因为修改的是不同列，所以这两个事务不会发生冲突，自然就允许同时执行了。

更多细节还在思考中……

2018/10/15 更新:

已经实现，例子见: UpdateTest
代码中的 testColumnLock 测试了 4 个事务对同一行进行不同字段的更新，只有第三个事务失败了。

[codefollower]

技术分类: 数据库-存储引擎
技术思想: 异步并行化的无锁 BTree (核心是把 Page 的更新操作绑定到固定线程)
实现状态: 已经实现

细节描述:

要在 B-Tree(或它的变体) 上实现高性能的无锁操作是一件很复杂的事情，考虑到 B-Tree 由一个个的 Page 组成，如果针对某个 Page 的更新操作都固定分配给唯一的线程执行，那么在这个 Page 上就不存在并发冲突了，考虑到实际场景中，一个 Page 的记录数多在 1000 行以下，所以只要 Page 之间的热点是均衡的，那么就能达到很好的并行效果，如果热点都落在同一个 Page 上，那么由一个线程处理这 1000 行记录的更新与多个线程同时修改这个 Page 达到的效果也许并不会差太多。

2018/10/21 更新:

H2 数据库的最新代码引入了非阻塞的 B-Tree : Make MVMap to operate in non-blocking fashion 但是从我自己的实测结果看，数据量从5万到50万，开多线程每个线程平分数据一起写还比原来的版本开单线程写要慢。

没有细看它的实现代码，原来的版本用的是类似 CopyOnWrite 的技术，支持多读单写，新的版本按理说支持多写了很自然就会想同样的数据量，用多个线程去写应该比单线程写要快才对，而且仅仅只是内存操作，如果比原来还慢，那引入更复杂的代码有什么意义。

2018/10/22 更新:

已经做了个原型，测试结果说明这样的思路还是可行的。

随机写(就是测试时生成的key是随机的)性能提升比较明显，在物理 cpu 核数之内，基本上每增加一个线程都能带来20%-80%的性能提升。

对于顺序写，也有提升，但并不是太显著，因为每次写都要层层通过二分查找定位到写入的 leaf page 和相应的位置，单线程顺序写，可以在每层中保持上次二分查找的结束位置，那么下次写时查找就很快了，而多线程同时写时，虽然是顺序写，但把 key 分配到每个线程时它不一定是最终把 key 写入 leaf page 的线程，这时它还得通知正确的线程去处理。多线程的运行时机是很不确定的，二分查找的结束位置很难像单线程那样维持从小到大的顺序。

这个技术思路值得单独写一篇文章，叫 <<异步并行化的无锁 BTree>> 比较符合主题。

2019/06/11 更新:

H2数据库的非阻塞版本之所以性能不够好，是因为它在root page那里大量使用了CAS，当并发很高时可能会产生大量重试，具体原因见: H2数据库的非阻塞B-Tree 。

目前我的异步并行化无锁 BTree 已经实现，不过目前没有开源。

2019/09/22 更新:

异步并行化无锁 BTree 已经开源。

[codefollower]

技术分类: 数据库-调度器
技术思想: 减少服务线程种类，实现统一的异步任务调度器
实现状态: 已经实现

细节描述:

Lealone 数据库从2015年开始就引入了异步化思想，把原来的每连接每线程模型变成了多线程异步化模型，每个连接不再绑定到固定的线程，线程与连接分离，事务也与线程分离。

对于事务的处理流程也已经完全异步化，整个流程按运行阶段被打散成不同的子任务，每个子任务会放到不同的线程中运行，比如当客户端创建连接后发来一条 SQL 时，后端处理流程的第一个阶段会由 NetServer 的事件循环服务线程处理，它会读取字节流，得到一个完整的协议包后，进入流程的第二个阶段。

第二阶段由命令处理器负责，它会解析协议包，得到 SQL 字符串后就进入第三个阶段了。

中间还有很多个阶段，直到事务相关的 redo 日志由日志同步线程安全写入硬盘后才让 NetServer 把响应结果发给客户端，此时整个流程才算结束。

这种把一个大任务(整个处理流程)按阶段分成不同子任务然后由不同线程(或线程组)处理子任务的思想其实就是 SEDA。这种架构当然也有缺点，每个阶段的子任务会被放入放出到不同的队列，然后还得适当的调用线程唤醒操作，这些都是开销，而且当 cpu 核数小于流程的阶段数的话也会带来不少上下文切换开销。

既然子任务都异步化了，为何不把它们一视同仁呢，为何不用一个或少量的线程组就能处理完呢?
这其中的原因多半还是怕某个子任务是计算型的，只要运行这种任务，线程很快就会占满，所以在没有抢占调度的情况下，使用一个固定的线程组并不合适。

所以，问题的核心还是如何包装子任务，让这些已经异步化的子任务能在某些合适的检查点让出线程，或者当来了优先级更高的任务后低优先级的也要让出线程，只有这样才能放心使用统一的线程组调度这些任务。

2019/1/23 更新:

原型已经实现

2019/09/22 更新:

已经开源

[yuwentao]

“当下次读出这个值时...如果它的事务 ID 小于当前事务的所有 ID，那么就肯定知道它是在系统崩溃前写入的脏数据(事务 ID 是递增的，当前正在运行的事务 ID 总是大于原来的事务 ID)”这段话没有太看明白，是说系统崩溃了，本来要提交的事务还没有提交，但是数据库存储引擎中已经存储了该值，导致数据库中存储的值是脏值，下一次读取该值的时候.....没太明白，能否大神再解释一下。

[yuwentao]

以Page为粒度的混合行列存储这个思想不错，不过我这里有个需求，按照关系型数据库mysql来存储，目前是一个存储表中有大约500个列，其中50个列是固定的字段类型，其余的450个列分别假设有9种数据类型如：Long ,varchar,bigint...等每种数据类型大约也有50个字段，column1....column50 。这种存储方式带来的最大的问题就是存储空间的浪费和查询性能很差...不知道如何解决这种存储模式的问题，还要有事务的保证.

[codefollower]

第一个问题，因为事务ID是递增的，所以当客户端发来一个读或写请求时，都会开启一个新事务，并且事务ID总是大于以前的ID，并且当前事务ID列表里只会存放从系统启动以后新创建的事务，上次由于崩溃而写入硬盘的脏数据中携带的事务ID是不会大于当前事务ID列表中的ID的。事务ID是long类型，目前没有复用之前的老ID，也就是一直单调递增的。（当然，最好还是禁用底层存储的自动保存功能）

第二个问题，对于查询，如果是列存储模式，就是查哪列就从硬盘读哪列。但是内存每行对应一个object的对象数组，这样才能按列的index做正确的填充，目前没用map，而是用数组来表示内存中的一行记录。

null的列写到硬盘会用一个字节表示。
事务是一样的，并且还支持列锁，多个事务更新同一行的不同列不会冲突。这在MySQL是做不到的。

[codefollower]

要让每个事务有一个唯一的标识符不难，比如最简单的uuid，所有当前事务id肯定跟之前的id不一样，读到上次不小心写入的脏数据，只要拿出id跟所有当前事务id比一下就知道了，不在当前事务的id列表中，必然断定是脏的。