• 2021-05-02

    数据库事务ACID和锁

    Views: 1598 | No Comments

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

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

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

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

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

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

    Posted by ideawu at 2021-05-02 13:30:21
  • 2021-04-30

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

    Views: 1673 | 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: 1545 | 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: 1169 | 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: 1311 | No Comments

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

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

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

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

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

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

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

    这个理论有什么用?

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

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

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

    Views: 1331 | 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
|<<<34567891011>>>| 7/138 Pages, 825 Results.