技术

对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go细节 codereview mat使用 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 MVCC 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes自动扩容缩容 神经网络模型优化 直觉上理解机器学习 knative入门 如何学习机器学习 神经网络系列笔记 TIDB源码分析 《阿里巴巴云原生实践15讲》笔记 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 扩展Kubernetes 副本一致性 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全机制 jvm crash分析 Kubernetes监控 Kubernetes 控制器模型 Prometheus 学习 容器日志采集 容器狂占cpu怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes objects之编排对象 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 kubernetes实践 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 《深入剖析kubernetes》笔记 精简代码的利器——lombok 学习 编程语言的动态性 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 分布式计算系统的那些套路 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 mysql 批量操作优化 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS2——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 硬件对软件设计的影响 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记2 《mysql技术内幕》笔记1 log4j学习 为什么netty比较难懂? 回溯法 apollo client源码分析及看待面向对象设计 学习并发 docker 环境(主要运行java项目)常见问题 Scala的一些梗 OpenTSDB 入门 spring事务小结 事务一致性 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型 java exception Linux IO学习 network channel network byte buffer 测试环境docker化实践 netty(七)netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Macvlan Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker中涉及到的一些linux知识 hystrix学习 Linux网络源代码学习——整体介绍 zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty(六)netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 Redis概述 机器学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 异构数据库表在线同步 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM内存与执行 git spring rmi和thrift maven/ant/gradle使用 再看tcp 缓存系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 VPN(Virtual Private Network) Kubernetes存储 Kubernetes 其它特性 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 使用etcd + confd + nginx做动态负载均衡 如何通过fleet unit files 来构建灵活的服务 CoreOS 安装 CoreOS 使用 Go学习 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

标签


MVCC

2019年11月20日

前言

截止到2019.11.19,对mvcc 的理解仍然有很多黑洞,可能需要阅读源码才能解开。我们需要知道的是,基于一个全局自增id,事务在start时申请id 作为自己的标识,修改(删除也可视为修改)一条记录时 不改变原有记录并新增 一条带上事务id的记录 即可成功的将修改操作转换为新增操作,提交时

mvcc 干啥的,同类的解决方案有哪些

多个并发执行体操作一个数据 会引起数据冲突,需要进行并发控制,并发控制有两个思路

  1. 悲观机制,You can avoid them, by employing a pessimistic locking mechanism (e.g. Read/Write locks, Two-Phase Locking)
  2. 乐观机制,You can allow conflicts to occur, but you need to detect them using an optimistic locking mechanism (e.g. logical clock, MVCC)

具体到数据库层面,追求绝对的并发安全会导致性能的下降。为了提高性能,可以降低并发控制”强度“,从读写的角度提出了一个隔离性的概念来描述并发安全的程度。 隔离性的要求不同,悲观 和乐观机制 可以调整内部细节 来达到不同的隔离性。

  1. 悲观锁,以mysql innodb 为例彻底理解事务的4个隔离级别

     
    Read uncommitted 事务在读数据的时候并未对数据加锁 事务在修改数据的时候只对数据增加行级共享锁
    Read committed 事务对当前被读取的数据加 行级共享锁(当读到时才加锁),
    一旦读完该行,立即释放该行级共享锁
    事务在更新某数据的瞬间(就是发生更新的瞬间),
    必须先对其加 行级排他锁,直到事务结束才释放
    Repeatable read 事务在读取某数据的瞬间(就是开始读取的瞬间),必须先对其加 行级共享锁,直到事务结束才释放 事务在更新某数据的瞬间(就是发生更新的瞬间),必须先对其加 行级排他锁,直到事务结束才释放
    Serializable 事务在读取数据时,必须先对其加 表级共享锁 ,直到事务结束才释放 事务在更新数据时,必须先对其加 表级排他锁 ,直到事务结束才释放

    为了实现隔离性的效果,不仅用了锁, 加锁的时间、粒度和性质(共享or排他)也很讲究。

  2. 乐观锁,MVCC 只是一个思想,并不是某个特定的实现。做到了读与读不冲突,读与写不冲突,但写写还需要锁去控制冲突

多事务 对同一个数据记录 同时读写的准确性,<read,read><write,write> 一般都没疑问,主要说的是<read,write>,具体的说就是<read,udpate><read,delete>,再具体的说,是write 一方的update/delete 操作read 一方能不能看到、何时看到。

snapshot isolation 事务隔离级别SI到RC以及优化RR和SI是一个差不多强度的隔离级别,RR有幻读问题,SI没有;而SI有写偏问题,RR没有。它们都解决了读未提交,不可重复读,然后都有对方处理不了的异常,所以算是差不多强度。只不过当年定义隔离级别的ANSI标准的时候,大家思维还局限在基于锁的实现,所以标准定义不是很完美,定义了RU,RC,RR,Serializability,后来基于MVCC的实现流行之后,才有了SI。SI的实现,需要拿一次startTS和一次commitTS

各家实现mvcc的方式不一致

各家方案的共同点

  1. 每一个record 有一个 唯一标识primary key
  2. 同一个record 存在多个版本,一个事务一个版本,多个版本的数据 可能是一个数据形态(postgresql),也可能是不同形态(mysql,老版本以undo log 形式存在)
  3. 对于不同隔离级别,mvcc 处理机制不同。
  4. mvcc 的工作基于 额外的数据结构 及 作用于之上的策略。

PostgreSQL、Oracle/MySQL和SQL Server的MVCC实现原理方式

postgresql

While Oracle and MySQL use the undo log to capture uncommitted changes so that rows can be reconstructed to their previously committed version, PostgreSQL stores all row versions in the table data structure.

PostgreSQL 中的 MVCC 实现原理可简单概括如下(真的可以不用锁实现三种隔离性)

  1. 数据文件中存放同一逻辑行的多个行版本(称为 Tuple )
  2. 每个行版本的头部记录创建以及删除该行版本的事务的 ID (分别称为 xmin 和 xmax )
  3. 每个事务的状态(运行中,中止或提交)记录在 pg_clog 文件中,所以能根据事务id 查询事务是否已提交
  4. 根据上面的数据并运用一定的规则每个事务只会看到一个特定的行版本

    1. 未提交读和提交读实际上都被实现为提交读
    2. Read committed, 只读取已经提交事务的结果 SQL优化(六) MVCC PostgreSQL实现事务和多版本并发控制的精华
    3. Repeatable read, 只读取xmin小于当前事务ID且已提交的事务的Tuple。postgresql RR隔离级别不允许幻读

How does MVCC (Multi-Version Concurrency Control) work

Transaction Id is a 32-bit integer, when connection start a new transaction, and we can see their transaction ids by calling the txid_current() PostgreSQL function.

一个update a record 为例,在Read committed 时

  1. Both Alice and Bob start a new transaction, and we can see their transaction ids by calling the txid_current() PostgreSQL function
  2. When Bob updates a post record, we can see two operations happening: a DELETE and an INSERT. The previous row version is marked as deleted by setting the t_max column value to Bob’s transaction id(用xmax>0来标识该<row,version>元组被删除), and a new row version is created which has the t_min column value set to Bob’s transaction id
  3. Under default Read Committed isolation level, until Bob manages to commit his transaction, Alice can still see the previous record version.
  4. After Bob has committed, Alice can now see the new row version that was updated by Bob
ACID 实现技术
原子性(Atomicity) MVCC
一致性(Consistency) 约束(主键、外键等)
隔离性 MVCC
持久性 WAL

对于插入操作,PostgreSQL会将当前事务ID存于xmin中。对于删除操作,其事务ID会存于xmax中。对于更新操作,PostgreSQL会将当前事务ID存于旧数据的xmax中,并存于新数据的xin中。换句话说,事务对增、删和改所操作的数据上都留有其事务ID,可以很方便的提交该批操作或者完全撤销操作,从而实现了事务的原子性。

MVCC 的实现让我想起了 基于区块链的比特币,区块链的比特币从来没有一个余额存在,余额是根据历史的交易记录累计算出来的。PostgreSQL 的数据会有大量的Tuple 存在(当然会有一个gc 机制去清理Tuple),不同的事务 按规则读取自己可见的Tuple。

mysql

MVCC机制

InnoDB为每行记录都实现了三个隐藏字段:6字节的事务ID(DB_TRX_ID );7字节的回滚指针(DB_ROLL_PTR);隐藏的ID。

InnoDB MVCC RR隔离级别下的数据可见性总结

innodb 中注意的一个点:事务ID并非在事务begin时就分配,而是在事务首次执行非快照读操作(SELECT … FOR UPDATE/IN SHARE MODE、UPDATE、DELETE)时分配。

tidb

tidb mvcc 机制一个难点是 其mvcc 既实现了多版本(解决多个事务同时读写一个key的问题),也实现了分布式事务(一个是事务中涉及多个key,每个key在不同的region/机器上,所以要保证多个key同时修改成功或失败)。

ACID 实现技术
原子性 两阶段提交时,通过 primary key 保证原子性。 primary key commit 成功与否决定事务成功与否
一致性  
隔离性 通过MVCC,保证隔离级别为 Repeatable Read(也有一说是SI)
持久性 tikv 保证持久化,多副本

分布式事务

TiKV 事务模型概览,Google Spanner 开源实现其实本质上来说,在一个分布式系统中实现跨节点事务,只有两阶段提交一种办法(3PC 本质上也是 2PC 的一个优化),一般都会有一个中央节点作为事务管理器。TiDB 的事务模型参考了 Percolator 论文,Percolator仅仅依靠客户端侧的协议和一个全局的授时服务器TSO就实现了跨机器的多行事务。Percolator 的模型通过对于锁的优化,去掉了单点的事务管理器的概念,将整个事务模型中的单点局限于授时服务器上。

对分布式事务的猜测

假设分布式kv 不支持ts,想原子修改k1和k2,直接修改

  1. set k1 成功
  2. set k2 失败
  3. 此时应该回滚,set k1 到原来的值,但这个时候 kv client 挂了呢,k1,k2就永远不一致了

一次提交只能对原始数据修改,中途宕机没办法callbak,所以一个直观的想法就是, 每次update k1 ,k1 原来的值还在,另外创建一个新k1 row,于是key 便有了版本的概念。为防止版本号冲突,版本使用全局唯一id/时间戳来表示。key 有了多个版本,如何认定哪个版本有效呢?将存储分为两份 default store 和 commit store,在commit store 里对 k1 的version 进行确认。于是数据有两个版本,有两次提交。重新走下流程:

  1. 假设k1已有版本是ts1,add k1_ts2
  2. 假设k2已有版本是ts1,add k2_ts2 ,但add 失败
  3. 此时应该回滚, 因为没有 对k1_ts2 进行确认,所以k1_ts2 不是有效数据,所谓的callback 什么都不做即可。
  4. 假设k2已有版本是ts1,add k2_ts2 成功, 则commit store中 add <k1_ts3,ts2><k2_ts3,ts2>进行确认

此处有一个问题,如何判断事务完成(成功失败都叫完成)?default store 存储了暂存的或有效的key,commit key 只是标记default store中哪些key 有效,却无法标记事务是否提交。 对于一个事务的读操作来说,假设新的事务只读取k2,它如何知道k2 在不在一个事务里,只有知道另一个事务是否commit,自己才可以根据隔离性要求 决定 read commit 还是read uncommitted。

此外,两个写写 事务 也还是需要加锁 才可以防止写冲突(mvcc 解决写冲突也是靠锁的)

所以,事务开启之前,要先尝试 对k1和k2 加锁,当然在kv store上只能是逻辑锁,除default store 和 commit store之外再加一个lock store。事务关闭后,移除k1和k2锁。 lock 可以防止写写冲突,恰好因为事务开启和关闭会create和remove 逻辑lock,lock 存在与否 顺带也表示了事务处于commting 状态。 读操作 可以根据 是否check 这个lock 来支持隔离性强度。

加锁方式优化;TiDB 新特性漫谈:悲观事务标准的 Percolator 模型采用的是乐观事务模型,在提交之前,会收集所有参与修改的行(key-value pairs),从里面随机选一行,作为这个事务的 Primary row,剩下的行自动作为 secondary rows,这里注意,primary 是随机的,具体是哪行完全不重要,primary 的唯一意义就是负责标记这个事务的完成状态(secondary rows 的commit 和 remove lock 可以异步执行,这样事务可以尽早提前结束)。

Google Percolator 的事务模型一系列文档只是阐述了 how,但没说为什么可以,留待以后研究吧。

整体上思索几个问题

  1. 如何实现原子性

    1. RocksDB’s atomic write batch and TiKV’s transaction scheduler make it atomic to read and write a single user key
    2. different CFs in the same RocksDB instance uses a common WAL, providing the ability to write to different CFs atomically.
    3. Two-phase commit (2PC) protocol. commit primary key + remove primary lock 成功即认为事务提交成功,否则即事务提交失败。但commit primary key + remove primary lock 两条指令如何原子写入还有待研究。
  2. 如何实现一致性
  3. 如何实现隔离性
  4. 如何实现持久性

MVCC

MVCC层暴露给上层的接口行为定义:

MVCCGet(key, version), 返回某 key 小于等于 version 的最大版本的值
MVCCScan(startKey, endKey, limit, version), 返回 [startKey, endKey) 区间内的 key 小于等于 version 的最大版本的键和值,上限 limit 个
MVCCPut(key, value, version) 插入某个键值对,如果 version 已经存在,则覆盖它。上层事务系统有责任维护自增version来避免read-modify-write
MVCCDelete(key, version) 删除某个特定版本的键值对, 这个需要与上层的事务删除接口区分,只有 GC 模块可以调用这个接口

编程语言中的并发安全控制

从CPU Cache出发彻底弄懂volatile/synchronized/cas机制

cpu 硬件因为多级缓存的缘故,一般的cpu 指令操作的是local cache,对于同一个数据,因为local cache 存在天然的有了多 verison。

各CPU都会通过总线嗅探来监视其他CPU,一旦某个CPU对自己Cache中缓存的共享变量做了修改(能做修改的前提是共享变量所在的缓存行的状态不是无效的),那么就会导致其他缓存了该共享变量的CPU将该变量所在的Cache Line置为无效状态,在下次CPU访问无效状态的缓存行时会首先要求对共享变量做了修改的CPU将修改从Cache写回主存,然后自己再从主存中将最新的共享变量读到自己的缓存行中。

缓存一致性协议通过缓存锁定来保证CPU修改缓存行中的共享变量并通知其他CPU将对应缓存行置为无效这一操作的原子性,即当某个CPU修改位于自己缓存中的共享变量时会禁止其他也缓存了该共享变量的CPU访问自己缓存中的对应缓存行,并在缓存锁定结束前通知这些CPU将对应缓存行置为无效状态。在缓存锁定出现之前,是通过总线锁定来实现CPU之间的同步的,即CPU在回写主存时会锁定总线不让其他CPU访问主存,但是这种机制开销较大