idea's blog

有一些文章, 包括 Raft 协议的论文, 已经从反例的角度解释了为什么不允许 Leader 直接 commit 前任的日志, 而是必须追加本任期的一条日志, 以达到隐式地 commit 前任的日志. 我想从 Raft 的几项原则的角度, 在逻辑上解释这个问题.

Raft 策略1: 节点的日志一旦 commit 便不可撤销

某个节点的一条日志, 一旦 commit 它, 那么就会对状态机造成不可逆的改变. 也许某些状态机有回滚功能, 但在 Raft 的架构中, 假设状态机不可回滚. 因此, 日志一旦 commit, 便不可撤销.

注意, 这里用的是"策略"一词, 表明这是人为规定的规则, 不是客观存在的定理.
Continue reading »

系统结构

       request
client -------> server

在一个系统中, 有 client 和 server 两个角色, client 向 server 发起请求(request), 这里的请求指写数据请求, 例如某条类似 "update table set a=1" 这样的 SQL 语句. 我们把 server 进行拆分, 得到下面这个更细化一些的系统结构:

       request         write
client -------> server -----> database

Server 的内部其实有一个数据库存储引擎, 例如可以使用 sqlite, 或者 LevelDB. 这个结构还可以继续拆分, 在分布式数据库, 需要有多副本, 所以会引入 binlog 技术(日志复制状态机), 把用户的请求保存下来(持久化), 然后复制到其它机器上. 因此, 系统的架构就变成:
Continue reading »

我还没有发现有人把 Raft 协议和区块链关联到一起讨论, 但是经过仔细分析, 穿透问题的本质之后, Raft 和区块链技术具有非常多的共同点. 可以整理出一个表格:

Raft 和区块链的不同概念, 其实往往对应到通用技术里面的一个共同的概念.
Continue reading »

数据库事务功能非常重要, 任何应用只要操作的多个对象之间有依赖(约束)关系, 都会不约而同地想到使用事务, 例如银行转账功能, 社交 App 中的粉丝关注功能, 购物网站下订单功能. 任何一个数据库系统, 如果不提供事务功能, 就不能减少用户(应用开发者)的某些麻烦, 因为用户不得不自己在应用层去实现类似事务的代码逻辑.

从用户的角度看, 如果数据库不提供事务, 他就要多写代码, 这让他很不爽. 所以, 即使是 KV 数据库, 也应该提供事务功能. 但是, 不仅事务功能的实现是有成本的, 使用也有成本. 比如, 很多用户不能准确地理解事务的特点和作用.

抽丝剥茧, 我们来分析一下数据库事务的本质是什么? 用户对事务功能的需求的本质是什么?

先从 ACID(Atomicity, Consistency, Isolation, Durability)说起.

• Durability(持久化), 这不是事务的特性, 而是数据库系统的本能特性, 没有持久化的数据库是"伪数据库", 是缓存系统. 所以, 没有啥可讨论的.
• Consistency(一致性), 一致性用于解决多副本不相同, 和解决数据依赖(约束)级联更新问题. 多副本和数据依赖, 本质上都是多处数据更新时间差的问题, 因为多处数据绝对不可能立即同时更新. 一致性本质上是原子性(Atomicity)问题.
• Isolation(隔离性), 隔离性本质上也是受多数数据不能"立即同时"更新所限而产生的. 因为多数数据不能立即同时更新, 所以看到更新的先后顺序会对业务的因果关系(数据依赖)产生影响. 不同的隔离级别产生不同的影响.
• Atomicity(原子性), 原子性是数据库事务的最重要特性, 也是用户的目的(本质). 用户之所以使用事务, 是因为用户追求的正是原子性

数据库事务常常和锁一起使用, 无论是用户的意图, 或者是数据库系统的实现原理, 事务都和锁紧密联系在一起. 大部分的事务都涉及到单一资源的争抢.
Continue reading »

日志复制状态机模型是 Raft 协议里的一个基础概念, 用于保障多副本一致性. 这个概念并非 Raft 独创, 而是由 Raft 具体总结和推广的, 在 Raft 之前, 像 MySQL 的 binlog 等等, 都是广义的日志复制状态机模型.

采用日志复制状态机模型的系统, 把多副本一致性问题分解成两个部分(模块), 第一部分是日志本身的一致性, 第二部分是状态机(例如数据库引擎)的数据一致性. 这两个系统模式是独立运行的, 它们之间的通信(Apply)也是异步的. 由此带来了广义的可靠通信问题: 有序, 最终到达(不丢包), Exactly Once(去重).

为了解决可靠通信问题, 系统至少需要保存 Apply 进度. 但是, 由于微观上"保存进度"和"Apply 日志"是两个独立的操作, 如果系统在两个操作之间宕机再重启, 就会导致断点位置的日志被 Apply 两次(去重问题, 如果先 Apply 再保存进度), 或者没有被 Apply(丢包问题, 如果先保存进度再 Apply).

要解决这个问题, 必须把 Apply 和保存进度两个操作作为一个完整的不可分割的整体, 就跟数据事务一样, 具有原子性, 要么同时成功, 要么全部失败, 这样就解决了去重和丢包问题. 如果状态机是 LevelDB 引擎, 那么我们可以利用其 WriteBatch 功能.

仔细借鉴 WriteBatch 的实现原理, 也许我们可以扩展思路, 把 Apply 进度保存在状态机之外, 不侵入状态机.

事务原子性的本质, 可以简单概括为: 增加 commit point, 重启时回滚.

针对两个独立对象, 我们增加一个单点标记(commit point), 当读取到对象时, 去检查单点标记的状态, 以判断对象是否有效, 如果无效则丢弃(读修复, 回滚). 正应了那句话:

All problems in computer science can be solved by another level of indirection.

到了这里, 我们不要求状态机(数据库引擎)提供原子性保证, 但要求它提供回滚能力. 回滚能力必然伴随着进度, 也即序列号, 引擎内部也要有全局递增的序列号.

我们把 Apply 进度 {raft.log_index, db.seq} 保存到独立的进度文件, 如果系统重启, 从进度文件中读取最新的 db.seq, 然后要求 db 回滚, 甚至进度文件也能回滚. 这样, 就保证了 Raft 日志 Apply Excatly Once.

另外, 再提一句"读修复"技术, 这项技术的应用非常广泛, 例如 Paxos 的核心之一就是读修复. 纯朴的思维认为所见即所得, 读就是只读一个地方, 读到什么就是什么, 不应该再读其它地方, 特别最重要的是, 读操作不应该修改数据. 但是, 如果技术思维想进阶, 一定要抛弃纯朴思维, 拓展到多版本, 多副本, 读修复, 读即是写.

像 MySQL 这样的传统关系数据库, 没有提供数据过期自动删除功能(TTL), 因为从常规理解, MySQL 是一个持久化数据库, 不是缓存系统, 数据应该由用户主动地通过 DELETE 指令显式地删除. 不过, 从实践经验上看, 由数据库系统提供基于过期时间自动删除数据(TTL)的功能, 可以减少用户(应用开发者)的工作量. 所以, Redis, SSDB, MongoDB 这些新开的 NoSQL 数据库都提供了 TTL 功能.

TTL 功能非常有用, 能节省用户的工作, 但是, TTL 也可能被误用和滥用. 在讨论 TTL 的实现原理之前, 我们需要对 TTL 功能的特性和使用场景进行讨论, 形成共识, 然后才能决定应该采取哪种实现手段. 写代码(implementation)从来都是选择题, 而不是技术难题.

TTL 是一种运维功能

由于 Redis 是一种内存数据库, 其特点是速度快, 因此给了用户一种错觉, 误认为数据库的 TTL 都是精确地, 甚至 Redis 的 API 还将 TTL 精确到了毫秒级别. 许多数据库系统的设计者都被 Redis 误导, 把精确过期当成一种设计目标.
Continue reading »