• 2021-05-02

    数据库事务ACID和锁

    Views: 326 | 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: 274 | 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: 322 | 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: 430 | 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: 523 | 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-17

    并发编程的核心技术 – 多版本(Multi Version)

    Views: 994 | No Comments

    在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.

    我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就被其它线程读取了, 因此要加锁.

    单机的硬盘操作, 基本也是借鉴内存操作, 也是对象和硬盘空间强绑定. 至少大部分程序员的思想是这样的, 这样比较直观. 跟内存操作一样, in-place 也遇到了操作的原子性挑战. 内存本来就是易失的(掉电后丢失), 但硬盘不一样, 数据需要持久化(掉电不丢失), 即使靠加锁解决了访问原子性问题, 但解决不了数据丢失问题. 所以, 硬盘操作是最先引入多版本技术的. 当需要修改某个对象时, 在另外的地方保存对象的新数据, 然后在另外的地方原子性地修改指向新数据的"指针". 事实上, 指针的修改也是多版本的, 不是 in-place 的, 后面会细说.
    Continue reading »

    Posted by ideawu at 2021-04-17 18:20:34
|<<<12>>>| 1/2 Pages, 9 Results.