0
0

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

ideawu 发表于 2021年04月17日 18:20 | Hits: 104
Tag: C/C++语言编程 | Computer System | 分布式 | 数据库 | 算法

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

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

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

有趣的是, SSD 硬盘技术的内部实现, 也不是 in-place 的, 其内部也是有类似"指针"的地址表的东西.

把硬盘上的多版本技术, 反哺回内存操作, 将会如何帮助并发编程呢? 如果更新某个对象时, 并不是在对象原来的内存空间里进行修改, 而是分配新的内存空间来保存对象, 保存完毕后, 再原子性地修改指向对象的"指针", 是不是就不需要锁了呢?

确实是这样的, 在旧的内存空间中的对象(旧版本), 因为永远不会被修改, 所以, 在读取时完全不需要加锁, 因为我们加锁是为了保证原子性(完整性). 也许修改"指针"指向时需要加锁, 但至少访问对象本身时是 Lock Free 的.

多版本(Multi Version)技术或者思想有什么优势? 它的借鉴意义是什么?

我认为, 这项技术借鉴意义在于, 只要我们引入一个极小成本的"指针", 就能让极大成本的访问对象的操作可以并发执行, 从而提高了性能. 如果这个对象不是在内存, 而是在磁盘的不同位置, 或者在不同的机器, 那样, 便可达到分布式并发处理能力. 所以, 这个技术(思想)是非常强大的.

数据库内核有很多地方都会用到多版本技术, 例如 MVCC(Multi Version Concurrency Control)技术, 名字上就带有 Multi Version. 在数据库领域, 我们把数据写入文件, 原始的做法会对读和写操作加互斥锁. 在引入多版本技术之后, 我们打开文件两次, 获取两个文件描述符(fd), 一个 fd 用于写, 另一个 fd 用户读. 写操作永远只追加写, 所以我们在内存中维护指向上一次写的位置(指针), 然后可以通过另一个 fd 去读文件, 只要不超过内存中维护的指针的位置即可. 这样, 就实现了并发地操作(读和写)同一个对象(文件).

从 in-place 到 Multi Version 的转变, 是从点到线的重大转变. 前者数据是一个点, 后者数据则是一个列表. 掌握了 Multi Version 技术的真谛之后, 你才能真正地了解数据的本质, 真正地掌握并发技术.

总结一下: 不要 in-place 修改对象的数据, 而是维护对象的多个版本, 引入一个极小成本的"指针", 指向对象的某一个版本.

理论结合实践

讨论了理论之后, 我们看看理论是如何指导实践的. 以 Multi Version 在数据库事务领域的作用为例.

考虑有 A, B 两个银行资金账户, 初始时(t0) A 有 100 元, 而 B 有 0 元. A 要转账 10 元给 B. 因为 A 和 B 的资金账户是独立的, 所以, 需要独立地修改两次, 一次修改 A 的余额, 一次修改 B 的余额.

现实中, 修改两个账户一定会有先后顺序, 不可能完全"同时的". 所以, 在 t1 时刻将 A 的余额修改为 90, 而此时 B 的余额还是 0.

我们把时间作为数据的版本号, 那么对于 t1 版本, 就出现了所谓的不符合原子性问题: 整个系统丢失了 10 元钱. 在 t2 时刻, "丢失"的 10 元钱终于进到 B 的账户里了.

t0 t1 t2
A 100 90
B 0 0 10

我们在额外的地方引入一个"指针", 指向 t2, 并且保证这个"指针"永远不指向 t1, 也就保证了整个系统永远不会丢失 10 元. (注意, 在 t2 时刻, A 没有对应的版本, 所以往前找, 找到 t1)

这个所谓的"指针", 就是数据库事务技术的 Commit Point(提交点).

所以说, Multi Version 技术(思想)是非常强大的, 能解释许多问题, 能指导很多工作.

Related posts:

  1. Redis 的作者狂喷某 NoSQL 数据库
  2. 为什么 Leader Based 的分布式协议 Raft 是更好的
  3. Paxos学习-instance
  4. HBase 在 Linux 下安装和配置
  5. Paxos 与分布式强一致性

原文链接: https://www.ideawu.net/blog/archives/1143.html

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)