• 2021-04-30

    Raft日志复制状态机模型的Apply进度问题

    Views: 1241 | No Comments

    日志复制状态机模型是 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 的核心之一就是读修复. 纯朴的思维认为所见即所得, 读就是只读一个地方, 读到什么就是什么, 不应该再读其它地方, 特别最重要的是, 读操作不应该修改数据. 但是, 如果技术思维想进阶, 一定要抛弃纯朴思维, 拓展到多版本, 多副本, 读修复. 读即是写.

    Posted by ideawu at 2021-04-30 22:25:39 Tags:
  • 2021-04-30

    分布式数据库的过期机制(TTL)实现原理

    Views: 1167 | No Comments

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

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

    TTL 是一种运维功能

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

    Posted by ideawu at 00:41:40
  • 2021-04-24

    数据库事务的原子性与隔离级别

    Views: 1010 | No Comments

    数据库事务的原子性并不仅仅是指写操作, 还包括读操作. 对于写操作, 众所周知, 原子性是指操作序列中的所有操作要么全部成功, 要么全部失败. 但多次读操作未必是指要么全部读到要么全部读不到. 如果不是 Snapshot Isolation, 那么两次读操作, 可能有其中一次读到旧值, 另一次读到新值. 但是, 读操作的原子性要求必须满足因果性. 当读到新值之后, 就说明事务中的所有写操作都已完成, 显然, 后续的读操作必须读到新值, 不能读到旧值.

    Snapshot Isolation 有一个最大的问题, 那便是在创建快照的时候(可能隐式创建), 如何处理 pending 状态的资源, 如果不处理, 那么同一个事务的两个资源, 在快照中可能处于不同的状态(一个已提交, 另一个未提交), 也显然违反了原子性.

    对于隔离级别来说, 只有 Serializable 才是符合原子性的. Read Committed 违反了原子性, 因为大部分的数据库实现, 只判断资源的状态是否为 committed, 并没有向上追查资源所关联的事务对象(commit point)的状态, 所以会出现先读到新值, 再读到旧值的情况(见后面的例子). 这种情况违反了因果关系, 也违反了一致性.
    Continue reading »

    Posted by ideawu at 2021-04-24 10:25:29
  • 2021-04-24

    操作的先后顺序的确定

    Views: 1054 | No Comments

    在计算机领域, 两个操作的先后顺序的确定, 是一个非常严肃的科学问题, 不能仅凭人的直觉来判定.

    有两种方式可以规划两个操作的先后顺序:

    • 通信协调
    • 绝对时间规划

    通信协调是指, 一个操作 (B) 在明确知道另一个操作 (A) 已经结束的前提下才启动, 那么便可以判定 (B) 在 (A) 之后. 这里说的"明确知道", 包含主观上的知道, 也包括客观上的知道. 例如, 对于顺序(串行)操作, 先后顺序是明确的客观的, 即使后一个操作不关心(或者说不知道)前一个操作是否已经完成, 它也应当知道.

    绝对时间规划不存在, 即使是原子钟也不是绝对时间. 因此, 绝对时间规划需要假设时间差异(gap), 让两个操作的时间区间有大于 gap 的距离.

    相关讨论: 数据库的并发操作与一致性

    并发操作对于程序员来说, 这个概念很常见, 但是, 很多人对它的理解未必那么准确.

    这个理论有什么用?

    有很多业务逻辑是严格依赖操作的先后顺序的, 先做什么, 后做什么, 做什么之前必须先做什么, 这些是业务逻辑的本质. 对于并发编程(多线程, 多进程, 分布式), 如果没有做通信协调, 那么系统必然有 BUG, 系统就是错的.

    Posted by ideawu at 10:14:44
  • 2021-04-24

    数据库的并发操作与一致性

    Views: 1106 | No Comments

    作为分布式强一致数据库的开发者, 被多次问到:

    如果我在新加坡和欧洲同时修改一条记录, 如在新加坡 set a=1, 在欧洲 set a=2, 结果 a 是多少?

    我的回答是:

    可能是 a=1, 也可能是 a=2.

    然后提问者会非常困惑和不满:

    你不是说数据库是强一致的吗? 为什么结果不确定呢?

    我非常理解他的困惑, 但是, 他所提到的"并发操作"和"一致性"并没有必然的联系.

    并发

    Martin Kleppmann 提到并发(Concurrency)的定义:

    For defining concurrency, exact time doesn’t matter: we simply call two operations concurrent if they are both unaware of each other, regardless of the physical time at which they occurred.

    要定义并发, 时间并不是一个影响因素: 如果两个操作不知道对方(的开始和结束以及结果), 无论物理时间上他们何时发生, 我们都称这两个操作是并发的.

    有这样的例子:
    Continue reading »

    Posted by ideawu at 10:08:22
  • 2021-04-18

    再谈 Paxos 和 Raft

    Views: 1648 | No Comments

    我之前写过一些谈 Paxos 的文章[1][2], 特别是将 Paxos[3] 和 Raft[4] 进行了对比. 由于我更多的是站在工程实现的角度考虑两种技术的优缺点, 所以造成了不少读者感受到我有非常强的"贬 Paxos, 赞 Raft"的倾向. 不可否认, 从工程实现的角度, Paxos 的指导意义非常抽象且不直接, 所以我们必须""亲 Raft 远 Paxos".

    实际上, 许多人认为 PaxosRaft 不是同一层面的东西. 另一方面, 某种角度看他们又同一层面的东西, 当然要做比较. 所以, 我们在讨论这两种技术时, 要注意所设的场景和条件, 否则极易让人误会.

    有一个说法比较经典:

    Mike Burrows, inventor of the Chubby service at Google, says that “there is only one consensus protocol, and that’s Paxos” - all other approaches are just broken versions of Paxos. - [source]

    翻译便是:

    Google Chubby 的发明者 Mike Burrows, 说过"世上只有一种共识协议, 那就是 Paxos" - 其它的全是 Paxos 的残缺版本. - [来源]

    这个说法常常引申之后用来对比 Paxos 和 Raft, 然后把 Raft 归结为所谓的"残缺版本", 以获得无知而且猥琐的心理满足感. 根据来源网址, 似乎 Mike 只说 Paxos 是唯一一种共识协议, 后面那句轻浮的, 狡黠的, 稚儿指点江山似的说法 - 其它的全是 Paxos 的残缺版本 - 估计是文章的作者加上的, 并非 Mike 本话.
    Continue reading »

    Posted by ideawu at 2021-04-18 11:59:48 Tags: ,
|<<<123456789>>>| 5/136 Pages, 812 Results.