技术

下一个平台Agent 激发LLM涌现——提示工程 LLM微调理论及实践 大佬沉思 LLM外挂知识库 LLMOps 多模态LLM Python一些比较有意思的库 LLM部分技术源码学习 LangChain源码学习 通用分布式计算引擎Ray Python并发 go依赖注入 go collection gc的基本原理 golang性能分析及优化 数据湖 高性能计算与存储 Linux2.1.13网络源代码学习 《大数据经典论文解读》 三驾马车学习 Spark 内存管理及调优 Yarn学习 从Spark部署模式开始讲源码分析 容器狂占内存资源怎么办? 多角度理解一致性 golang io使用及优化模式 Flink学习 c++学习 学习ebpf go设计哲学 ceph学习 学习mesh kvm虚拟化 学习MQ go编译器以及defer实现 学习go 为什么要有堆栈 汇编语言 计算机组成原理 运行时和库 Prometheus client mysql 事务 mysql 事务的隔离级别 mysql 索引 坏味道 学习分布式 学习网络 学习Linux go堆内存分配 golang 系统调用与阻塞处理 Goroutine 调度过程 重新认识cpu mosn有的没的 负载均衡泛谈 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go channel codereview gc分析 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes扩缩容 神经网络模型优化 直觉上理解深度学习 如何学习机器学习 TIDB源码分析 什么是云原生 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 共识算法 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全访问机制 jvm crash分析 Prometheus 学习 Kubernetes监控 容器日志采集 Kubernetes 控制器模型 容器狂占资源怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes类型系统 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言那些事儿 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 如何分发计算 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记 log4j学习 为什么netty比较难懂? 递归、回溯、动态规划 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 OpenTSDB 入门 spring事务小结 分布式事务 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型和jvm内存布局 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker namespace和cgroup zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 深度学习泛谈 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 maven/ant/gradle/make使用 再看tcp kv系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go基础 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

架构

大模型推理服务框架 模型服务化(未完成) 大模型RHLF 大模型训练 大模型推理 从Attention到Transformer k8s设备管理 LLM工具栈 ddd从理念到代码 如何应用LLM 小鼠如何驾驭大象(LLM)? 多类型负载协调员Koordinator controller-runtime细节分析 finops学习 kubevela多集群 kubevela中cue的应用 基于k8s的工作流 容器和CPU那些事儿 kubevela源码分析 数据集管理fluid 应用管理平台kubevela karmada支持crd 多集群管理 AutoML和AutoDL 特征平台 实时训练 分布式链路追踪 helm tensorflow原理——python层分析 如何学习tensorflow 数据并行——allreduce 数据并行——ps 机器学习中的python调用c 机器学习训练框架概述 embedding的原理及实践 tensornet源码分析 大模型训练和推理 X的生成——特征工程 tvm tensorflow原理——core层分析 模型演变 《深度学习推荐系统实战》笔记 keras 和 Estimator tensorflow分布式训练 分布式训练的一些问题 基于Volcano的弹性训练 图神经网络 pytorch弹性分布式训练 从混部到统一调度 从RNN到Attention pytorch分布式训练 CNN 《动手学深度学习》笔记 pytorch与线性回归 多活 volcano特性源码分析 推理服务 kubebuilder 学习 mpi 学习pytorch client-go学习 tensorflow学习 提高gpu 利用率 GPU与容器的结合 GPU入门 AI云平台梳理 tf-operator源码分析 k8s批处理调度/Job调度 喜马拉雅容器化实践 Kubernetes 实践 学习rpc BFF openkruise学习 可观察性和监控系统 基于Kubernetes选主及应用 《许式伟的架构课》笔记 Admission Controller 与 Admission Webhook 发布平台系统设计 k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 深入controller openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go informer源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 资源调度泛谈 业务系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 概率论 serverless 泛谈 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 架构大杂烩 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 用户认证问题 资源的分配与回收——池 消息/任务队列

标签

k8s设备管理 多类型负载协调员Koordinator controller-runtime细节分析 finops学习 kubevela多集群 kubevela中cue的应用 基于k8s的工作流 容器和CPU那些事儿 kubevela源码分析 数据集管理fluid 应用管理平台kubevela karmada支持crd 多集群管理 helm 从混部到统一调度 volcano特性源码分析 kubebuilder 学习 client-go学习 tf-operator源码分析 k8s批处理调度/Job调度 喜马拉雅容器化实践 Kubernetes 实践 openkruise学习 基于Kubernetes选主及应用 Admission Controller 与 Admission Webhook k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 深入controller openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go informer源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? Kubernetes events学习及应用 CRI 资源调度泛谈 如何学习Kubernetes 以应用为中心 kubernetes operator kubernetes扩缩容 serverless 泛谈 什么是云原生 自定义CNI IPAM docker和k8s安全访问机制 Kubernetes监控 Kubernetes 控制器模型 Kubernetes资源调度——scheduler Kubernetes类型系统 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 Kubernetes源码分析——从kubectl开始 kubernetes yaml配置 CNI——容器网络是如何打通的 当我在说PaaS时,我在说什么 《深入剖析kubernetes》笔记 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件

mysql 事务的隔离级别

2021年01月22日

前言

计算机科学中有一种思想:如果一个问题太难了解决不了,那就放宽假设,弱化需求。比如实现数据库事务的“隔离性”会导致性能很差,只能在实验室环境使用,无法用在现实世界,于是人们提出“弱隔离性”,罗列出“读提交”,“可重复读”之类的“弱隔离级别”,越弱的问题越好解决;比如想实现“对业务透明”的分布式事务比较难,要付出很多代价,于是人们就提出放弃“对业务透明”,于是就有了 TCC 和 Saga;……

可能你对隔离性还有点陌生,其实在编程的过程中,我们通常会利用锁进行并发控制,确保临界区的资源不会出现多个线程同时进行读写的情况,这其实就对应了事务的最高隔离级别:可串行化,它能保证多个并发事务的执行结果和一个一个串行执行是一样的。为什么应用程序中可以提供可串行化的隔离级别,而数据库却不能呢?根本原因就是应用程序对临界区大多是内存操作,而数据库要保证持久性(即 ACID 中的 Durability),需要把临界区的数据持久化到磁盘,可是磁盘操作比内存操作要慢好几个数量级,一次随机访问内存、 SSD 磁盘和 SATA 磁盘,对应的操作时间分别为几十纳秒、几十微秒和几十毫秒,这会导致临界区持有的时间变长,对临界区资源的竞争将会变得异常激烈,数据库的性能则会大大降低。所以,数据库的研究者就对事务定义了隔离级别这个概念,也就是在高性能与正确性之间提供了一个缓冲地带,相当于明确地告诉使用者,我们提供了正确性差一点但是性能好一点的模式,以及正确性好一点但是性能差一点的模式,使用者可以按照自己的业务场景来选择。

为什么要有事务隔离级别?

浅谈对数据库隔离级别的理解”隔离性”实质上就是指对数据操作的并发控制。

为什么需要并发控制?它解决了什么问题?在数据库中,如果对于同一数据项的所有事务操作都被串行化地执行,那么执行过程与结果是没有问题的。如果存在并发操作,即多个事务的生命周期(时间区间)之间存在交集,就可能产生操作上的冲突和依赖,进而引发异常现象。操作顺序类型可以分为 读-读、读-写、写-读、写-写 4种类型,其中后三种包含写的操作序列是有冲突的,它们可能会引发执行结果的异常(其实就是与串行执行结果不一样),或者叫异常现象(Anomaly),比如脏读等。PS:因为数据不是写入就算,而是commit 才算数,所以对另一个事务来说,“眼见不一定为实”,看见X=10,结果可能因为事务执行失败X后来不是10了。PS:一系列操作时不可能一瞬间执行完,所以我们在执行多个操作时,要控制他们的中间状态对外的可见性

并发控制就是要解决这些异常,但是并发控制需要达到什么程度呢?因为并发控制程度高对应着并发执行效率低,数据库用户并非时刻都需要最强的并发控制方式,这是一致性与并发度的权衡,隔离级别就是这一权衡的控制参数。从数据库开发者的角度来看,需要解决并发操作时的异常现象是根本需求,而隔离级别是把这些无穷多的现象级需求进行了分类、抽象、归纳,将规避异常现象之需求转化为了满足有限种类隔离级别之需求。即数据库开发者只需要实现定义好的几种隔离级别,就可以为数据库系统提供规避某些(可能是无穷多)异常现象的功能。如果一个事务系统在运行时能够规避某些问题集,那么该系统的事务将具有某种相应的隔离级别,即隔离级别抽象出待规避的最小异常现象集合。至于DBMS的某种隔离级别的实现,是否还可能规避对应级别的最小问题集以外的异常序列,并不做限制。

数据库事务隔离发展历史事务隔离是事务并发产生的直接需求,最直观的、保证正确性的隔离方式,显然是让并发的事务依次执行,或是看起来像是依次执行。但在真实的场景中,有时并不需要如此高的正确性保证,因此希望牺牲一些正确性来提高整体性能。通过区别不同强度的隔离级别使得使用者可以在正确性和性能上自由权衡。随着数据库产品数量以及使用场景的膨胀,带来了各种隔离级别选择的混乱,数据库的众多设计者和使用者亟需一个对隔离级别划分的共识,这就是标准出现的意义。

如何标准化、形式化地描述并发读写的(异常)现象?1992年ANSI首先尝试指定统一的隔离级别标准,其定义了不同级别的异象(phenomenas), 并依据能避免多少异象来划分隔离标准。几年后,微软的研究员们在A Critique of ANSI SQL Isolation Levels一文中对ANSI的标准进行了批判,改造了异象的定义,本质是基于锁的定义,但太过严格的隔离性定义,阻止了Optimize或Multi-version的实现方式中的一些正常的情况。Adya在Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions中给出了基于序列化图得定义,思路为先定义冲突关系;并以冲突关系为有向边形成序列化图;再以图中的环类型定义不同的异象;最后通过阻止不同的异象来定义隔离级别。写写冲突ww;先写后读冲突wr;先读后写冲突rw。PS:总之挺麻烦一件事。

并发控制

浅析数据库并发控制实现事务隔离的机制,称之为并发控制。并行执行的事务可以满足某一隔离性级别的正确性要求。要满足正确性要求就一定需要对事务的操作做冲突检测,对有冲突的事务进行延后或者丢弃。并发控制机制 根据检测冲突的时机不同可以简单分成三类:

  1. 基于Lock:最悲观的实现,需要在操作开始前,甚至是事务开始前,对要访问的数据库对象加锁,对冲突操作Delay;
  2. 基于Timestamp:乐观的实现,每个事务在开始时获得全局递增的时间戳,期望按照开始时的时间戳依次执行,在操作真正写数据的时候检查冲突并选择Delay或者Abort;
  3. 基于Validation:更乐观的实现,仅在Commit前进行Validate,对冲突的事务Abort

三种策略的立足点其实是对冲突的乐观程度,越乐观,也就是认为冲突发生越少,就越倾向于推迟冲突的检测。直观的也可以看出,越晚的冲突检测越有可能获得高的并发。但当冲突真正出现时,由于前面的操作可能都需要一笔勾销,因此在冲突较多的场景下,太乐观反而得不偿失。

相同的乐观程度下,还存在多版本的实现。所谓多版本,就是在每次需要对数据库对象修改时,生成新的数据版本,每个对象的多个版本共存。读请求可以直接访问对应版本的数据,从而避免读写事务和只读事务的相互阻塞。当然多版本也会带来对不同版本的维护成本,如需要垃圾回收机制来释放不被任何事物可见的版本。

并发控制机制并不与具体的隔离级别绑定。无论是乐观悲观的选择,多版本的实现,读写锁,两阶段锁等各种并发控制的机制,归根接地都是在确定的隔离级别上尽可能的提高系统吞吐,可以说隔离级别选择决定上限,而并发控制实现决定下限。

基于 B+Tree 和 Lock 方式的并发控制

B+树数据库加锁历史如何选择Lock/Timestamp/Validation 归根结底是由用户的使用场景决定的,在不能对用户场景做太多假设的通用数据库中,毫无疑问,基于Lock的方式显得更为合适。除此之外,由于MVCC的广泛应用消除了读写之间的冲突,使得Lock带来的并发影响大大降低,也使得基于Lock的并发控制仍然是主流。

对数据库的数据加锁这件事情,本身是跟数据的组织方式是密不可分的,数据组织方式可能给加锁带来限制,同时利用组织方式的特性,可能也能改造和优化加锁过程。如何在B+Tree数据库上,基于Lock的方式,来实现高并发、高效的数据库并发控制?B+Tree加锁的发展历史(不是很专业,就不介绍那么细了)

  1. 2PL,由于B+Tree的从根向下的搜索模式,事务需要持有从根节点到叶子节点路径上所有的锁。而两阶段锁(2PL)又要求所有这些锁都持有到事务Commit。更糟糕的是,任何插入和删除操作都有可能导致树节点的分裂或合并(Structure Modification Operations, SMO),因此,对根结点需要加写锁WL,也就是说任何时刻只允许一个包含Insert或Delete操作的事务进行。
  2. Tree Protocol。略。2PL和Tree Protocol中面临的最大问题其实在于:节点的SMO时需要持有其父节点的写锁。之所以这样,是由于需要处理父节点中的对应key及指针,节点的分裂或合并,跟其父节点的修改是一个完整的过程,不允许任何其他事务看到这个过程的中间状态。
  3. Blink Tree。巧妙的提出对所有节点增加右向指针,指向其Sibling节点,这是个非常漂亮的解决方案,因为他其实是提供了一种新的节点访问路径,让上述这种SMO的中间状态,变成一种合法的状态,从而避免了SMO过程持有父节点的写锁。
  4. ARIES/KVL 峰回路转。上面讲到的传统的加锁策略,认为Btree的节点是加锁的最小单位,而所做的努力一直是在降低单个事务需要同时持有的锁的节点数,能不能更进一步提升Btree的并发能力呢?ARIES/KVL首先明确的区分了B+Tree的物理内容和逻辑内容,逻辑内容就是存储在B+Tree上的那些数据记录,而B+Tree自己本身的结构属于物理内容,物理内容其实事务是不关心的,那么节点分裂、合并这些操作其实只是改变了B+Tree的物理内容而不是逻辑内容。因此,ARIES/KVL就将这些从Lock的保护中抽离出来,也就是Lock在Record上加锁,对物理结构则通过Latch来保护其在多线程下的安全。这里最本质的区别是Latch不需要在整个事务生命周期持有,而是只在临界区代码的前后。可以看作是分层事务的一种实现。
    1. Latch保护物理结构。Latch才是我们在多线程编程中熟悉的,保护临界区访问的锁。通过Latch来保护B+Tree物理结构其实也属于多线程编程的范畴,上述传统的B+Tree加锁方式的优化,也可以直接无缝转化过来。只是将Lock换成的Latch,其作用对象也从事务之间变成线程之间
    2. Lock保护逻辑结构。有了这种清晰的区分,事务的并发控制就变得清晰很多,不再需考虑树本身的结构变化。假设事务T1要查询、修改、删除或插入一个Record X,而Record X所在的Page为q,那么加Lock过程就变成这样:
       Search(X)and Hold Latch(q);
       SLock(X) or WLock(X);
       // Fetch, Insert or Delete
       Unlatch(q);
       ....
       T Commit and Unlock(X)
      
  5. Key Range Locking,前面这套结合Latch和Lock方案,已经可以很好的支持对单条Record的增删改查。但很多数据库访问并不是针对某一条记录的,而是基于条件的。比如查询满足某个条件的所有Record,这个时候就会出现《数据库事务隔离发展历史》中提到的幻读的问题,也就是在事务的生命周期中,由于新的满足条件的Record被其他事务插入或删除,导致该事务前后两次条件查询的结果不同。这其实是要求,条件查询的事务和插入/删除满足这个条件Record的事务之间,有相互通信或冲突发现的机制,最直接的想法是对所有可能的,还不存在的Key也加锁,在大多数情况下,由于Key范围的无限,这都是不可接受的。传统的解决幻读的方案是谓词锁(Predicate Lock),也就是直接对查询条件加锁,每次插入删除需要判断是否与现有的判断条件冲突,但通用数据库中,条件千变万化,判断条件冲突这件事情开销极大。也正是因此,谓词锁并没有成为主流。在B+Tree上,由于其Key有序的特点,通常会采用Key Range Locking,也就是对Key加锁,来保护其旁边的区间Range。其中最常见的一种实现是Next Key Locking。
  6. Instant Locking,上述加锁过程中,Insert需要对要插入位置的Next Key加Lock,如果已经是最大则需要对正无穷加Lock,并持有整个事务生命周期。在高频率顺序插入的场景,这个Next Key Lock就会成为明显的瓶颈。Instant Locking的方案很好地解决了这个问题。顾名思义,Instant Locking只在瞬间持有这把Next Key Locking,其加锁是为了判断有没有这个Range冲突的读操作,但获得锁后并不持有,而是直接放锁。乍一看,这样违背了2PL的限制,使得其他事务可能在这个过程获得这把锁。通过巧妙的利用Btree操作的特性,以及Latch及Lock的配合,可以相对完美的解决这个问题,如下是引入Instant Locking后的Insert加Next Key Lock的流程:
     Search(M,Y)and Hold Latch(q);
    
     XLock(Y);
     Unlock(Y)
    
     XLock(M);
    
     Insert M into q
    
     Unlatch(q);
     ....
    
     T Commit and Unlock(M)
    

    可以看出,Y上Lock的获取和释放,和插入新的Record两件事情是在Page q的Latch保护下进行的,因此这个中间过程是不会有其他事务进来的,等Latch释放的时候,新的Record其实已经插入,这个X到Y的区间已经被划分成了,X到M以及M到Y,新的事务只需要对自己关心的Range加锁即可。分析这个过程,可以提前放锁的根本原因是:Insert的New Record在其他事务对这个Range加锁的时候已经可见。Delete就没有这么幸运了,因为Delete之后这个Key就不可见了,因此Delete的持有的Next Key Locking似乎不能采用Instant Locking,这个时候Ghost Record就派上用场了。

  7. Ghost Records,Ghost Record的思路,其实跟之前讲到拆分物理内容和逻辑内容是一脉相承的,Ghost Record给每个记录增加了一位Ghost Bit位,正常记录为0,当需要删除某个Record的时候,直接将其Ghost Bit修改为1即可,正常的查询会检查Ghost Bit,如果发现是1则跳过。但是Ghost Record是可以跟正常的Record一样作为Key Range Lock的加锁对象的。可以看出这相当于把删除操作变成了更新操作,因此删除事务不再需要持有Next Key Lock。除此之外,由于回滚的也变成了修改Ghost Bit,不存在新的空间申请需要,因此避免了事务回滚的失败。Ghost Record的策略也成为大多数B+Tree数据库的必选实现方式。当然,这些Ghost Record最终还是需要删除的,其删除操作通常会放到后台异步进行,由于Ghost Record对用户请求是不可见的,因此这个删除过程只是对物理结构的改变,也不需要加Lock。但Record的删除会导致其左右的两个Lock Range合并,因此这个过程除了需要Page的Latch之外,还需要获得Lock系统中Lock的Latch,在Lock的Latch保护下对Lock Range合并。
  8. 后续的研究多围绕权衡Lock粒度、新的Lock Mode及缩短Lock持有时间等方向继续前进。事务在操作数据库时,会先对要访问的元素加对应的Lock,为了更高的并发, Lock通常有不同的Mode,如常见的读锁SL,写锁WL,不同Mode的锁相互直接的兼容性可以用兼容性表来表示。

从实现的角度对几种隔离级别进行理解从上锁的强弱考虑,我们有互斥锁(Mutex Lock,又称写锁)和共享锁(Shared Lock,又称读锁);从上锁的长短来考虑,我们有长时锁(Long Period Lock,事务开始获取锁,到事务结束时释放)和短时锁(Short Period Lock,访问数据时获取,用完旋即释放);从上锁的粗细来考虑,我们有对象锁(Row Lock,锁一行)和谓词锁(Predicate Lock,锁一个范围)。说到数据范围,由于数据库在存储层实现时都是基于 KV 模型,如 B+ 树中 Page 和 LSM-Tree 中的 Block 都是一组 KV 条目。对应到关系型数据库中,如果按行存储,则单条 KV 的 Key 通常是主键, Value 通常是一行数据。因此,之后事务修改数据的范围都可以理解为:

  1. 单个对象。可以理解为一个 KV 条目。
  2. 一组对象。如 where x > 5 谓词语句,会确定一个 KV 范围子集。 性能最好的隔离级别就是不上任何锁,但会存在脏读(Dirty Read,一个事务读到另一个事务未提交的更改)和脏写(Dirty Write,一个事务覆盖了另外一个事务未提交的更改)的问题。为了避免脏写,可以给要更改的对象加长时写锁,但读数据时并不加锁,此时的隔离级别称为读未提交(RU,Read Uncommitted)。但此时仍然会有脏读,为了避免脏读,可以对要读取的对象加短时读锁,此时的隔离级别是是读已提交(RC,Read Committed)。但由于加的是短时读锁,一个事务先后两次读 x,而在中间空挡,另一个修改 x 的事务提交,则会出现两次读取不一致的问题,此种问题称为不可重复读。为了解决此问题,需要在读取数据的时候也加长时读锁。解决了不可重复读的隔离级别称为可重复读(RR,Repeatable Read)。到可重复读级别,都是针对单条数据上锁。在此隔离级别下,如果一个事务两次进行范围查询,比如说执行两次 select count(x) where x > 5;另一个事务在两次查询中间插入了一条 x = 6,这两次读到的结果并不一样,这种现象称为幻读(Phantom Read)。为了解决幻读问题,需要针对范围查询语句加长时谓词读锁。解决了幻读的隔离级别,我们称为可串行化(Serializability)。

从更抽象角度来说,每个事务在执行过程中都要去摸(touch)一个数据子集,针对该数据子集可能会读,可能会写;如果两个并发的事务,摸到的数据子集并不相交,则不用加锁,可以放心并发。如果数据子集有相交之处,为了维持事务执行过程中的因果关系(也可以理解为依赖关系,如多次读取数据一致,依赖某个读取内容进行决策后修改,依赖的内容不能为其他事务所修改,不然做出的决策就有问题),从而维持事务并发执行后的一致性(从数据库层面看是要维持外键约束等不变性;从用户层面看是符合业务直觉,不能出现类似 1+1=3 的结果)。但这没有覆盖到到另一个常见的隔离级别——快照隔离(Snapshot Isolation),因为它引出了另一种实现族——MVCC。由于属于不同的实现,快照隔离和可重复读在隔离级别的光谱上属于一个偏序关系,不能说谁强于谁。

调度器

需要指出的是并发控制由数据库的调度器负责,事务本身并不感知。如下图所示,Scheduler将多个事务的读写请求,排列为合法的序列,使之依次执行:

数据库通常会有一个调度模块来负责资源的加锁放锁,以及对应事务的等待或丢弃。所有的锁的持有和等待信息会记录在一张Lock Table中,调度模块结合当前的Lock Table中的状况和锁模式的兼容表来作出决策。比如:事务T3已经持有了元素A的写锁WL,导致事务T1和T2无法获得读锁SL,从而在队列中等待,直到T3结束释放WL后,调度模块再依次唤醒等待的事务。

这个过程中,对可能破坏数据正确性的冲突事务,调度器可能选择下面两种处理方式:

  1. Delay:延迟某个事务的执行到合法的时刻
  2. Abort:直接放弃事务的提交,并回滚该事务可能造成的影响

锁的类型

  1. 锁,锁表、锁行; 读写锁、互斥锁。
  2. 谓词锁,它的加锁对象不属于特定的对象(例如表中的一行),它属于所有符合某些搜索条件的对象。
    1. 比如间隙锁(Next-Key Locking)就是关于谓词锁的简化以及性能更好的一个实现。互斥锁是行锁,只会锁定一行特定的记录,而间隙锁则是锁定两行记录之间的空隙,防止其他事务在此间隙中插入新的记录(一种在记录前面添加的锁,该锁阻止新记录插入到当前记录的前面,直到当前记录的间隙锁释放后新记录才能正常插入)。间隙锁虽然解决了幻读问题,但因每次都会锁住一段间隙,大大降低了数据库整体的并发度,且因间隙锁和间隙锁之间不互斥,不同事务可以同时对同一间隙加上 Gap Locks,这也往往是各种死锁产生的源头
    2. Next-Key Locks 是 (Shard/Exclusive Locks + Gap Locks) 的结合,当 session A 给某行记录 R 添加了互斥型的 Next-Key Locks 后, 相当于拥有了记录 R 的 X 锁和记录 R 的 Gap Locks,在可重复读隔离级别下,update 和 delete 操作默认都会给记录添加 Next-Key Locks。
    3. 插入意向锁 (Insert Intention Locks) 也是一种间隙锁,由 INSERT 操作在行数据插入之前获取在插入一条记录前,需要先定位到该记录在 B+ 树中的存储位置,然后判断待插入位置的下一条记录上是否添加了 Gap Locks,如果下一条记录上存在 Gap Locks,那么插入操作就需要阻塞等待,直到拥有 Gap Locks 的那个事务提交(间隙锁释放后插入意向锁也会释放)。同时执行插入操作等待的事务也会在内存中生成一个锁结构,表明有事务想在某个间隙中插入新记录,但目前处于阻塞状态,生成的锁结构就是插入意向锁。

工作原理

浅析数据库并发控制基于Lock实现的Scheduler需要在事务访问数据前加上必要的锁保护,为了提高并发,会根据实际访问情况分配不同模式的锁,常见的有读写锁,更新锁等。最简单地,需要长期持有锁到事务结束,为了尽可能的在保证正确性的基础上提高并行度,数据库中常用的加锁方式称为两阶段锁(2PL),Growing阶段可以申请加锁,Shrinking阶段只能释放,即在第一次释放锁之后不能再有任何加锁请求。需要注意的是2PL并不能解决死锁的问题,因此还需要有死锁检测及处理的机制,通常是选择死锁的事务进行Abort。PS:跟分布式事务有点一样

Scheduler对冲突的判断还需要配合Lock Table,如下图所示是一个可能得Lock Table信息示意,每一个被访问的数据库对象都会在Lock Table中有对应的表项,其中记录了当前最高的持有锁的模式、是否有事务在Delay、以及持有或等待对应锁的事务链表;同时对链表中的每个事务记录其事务ID,请求锁的模式以及是否已经持有该锁。Scheduler会在加锁请求到来时,通过查找Lock Table判断能否加锁或是Delay,如果Delay需要插入到链表中。对应的当事务Commit或Abort后需要对其持有的锁进行释放,并按照不同的策略唤醒等待队列中Delay的事务。PS:java 是将锁信息附着在对象header 上,但feel 是一样的

MYSQL 中锁的各种模式与类型

具体细节

InnoDB 事务锁源码分析InnoDB 中的lock是事务中对访问/修改的record加的锁,它一般是在事务提交或回滚时释放。latch是在BTree上定位record的时候对Btree pages加的锁,它一般是在对page中对应record加上lock并且完成访问/修改后就释放,latch的锁区间比lock小很多。在具体的实现中,一个大的transaction会被拆成若干小的mini transaction(mtr),如下图所示:有一个transaction,依次做了insert,select…for update及update操作,这3个操作分别对应3个mtr,每个mtr完成:

1. 在btree查找目标record,加相关page latch;
2. 加目标record lock,修改对应record
3. 释放page latch

为什么latch的锁区间比lock小很多?是为了并发,事务中的每一个操作,在步骤二完成之后,相应的record已经加上了lock保护起来,确保其他并发事务无法修改,所以这时候没必要还占着record所在的page latch,否则其他事务 访问/修改 相同page的不同record时,这本来是可以并行做的事情,在这里会被page latch会被卡住。

RR支持可重复度,也就是在一个事务中,多次执行相同的SELECT…FOR UPDATE应该看到相同的结果集(除本事务修改外),这个就要求SELECT的区间里不能有其他事务插入新的record,所以SELECT除了对满足条件的record加lock之外,对相应区间也要加lock来保护起来。在InnoDB的实现中,并没有一个一下锁住某个指定区间的锁,而是把一个大的区间锁拆分放在区间中已有的多个record上来完成。所以引入了Gap lock和Next-key lock的概念,它们加再一个具体的record上

  1. Gap lock 保护这个record与其前一个record之间的开区间
  2. Next-key lock 保护包含这个record与其前一个record之间的左开右闭区间 它们都是为了保护这个区间不能被别的事务插入新的record,实现RR。

死锁

死锁一般是下面情况导致

循环依赖不同锁,但加锁顺序不一致

线程1   lock(l1x)  lock(l2x)
线程2   lock(l2x)  lock(l1x)

线程1   lock(l1s)  lock(l2x)
线程2   lock(l2s)  lock(l1x)

线程1   lock(l1s)  lock(l2x)
线程2   lock(l2x)  lock(l1x)

线程1   lock(l1x)  lock(l2x)
线程2   lock(l2s)  lock(l1x)

对同一个锁先共享后互斥
线程1   lock(ls)  lock(lx)
线程2   lock(ls)  lock(lx)

具体到mysql 则情况更为复杂,共享锁、排它锁、意向锁的兼容矩阵 ||X|IX|S|IS| |—|—|—|—|—| |X|冲突|冲突|冲突|冲突| |IX|冲突|兼容|冲突|兼容| |S|冲突|冲突|兼容|兼容| |IS|冲突|兼容|兼容|兼容|

避免死锁的办法:对不同的锁,加锁要顺序一致。对同一个锁,要避免先读后写。减少事务的粒度(行锁是在需要的时候才加上的,但并不是不需要了就立刻释放,而是要等到事务结束时才释放)。

查看当前数据库的死锁情况 SHOW ENGINE INNODB STATUS;

查看一条sql 会加那些锁

mysql> begin; # 开启事务,注意一定要在事务里操作,否则sql 执行完了,啥也看不到。
mysql> sql1;
mysql> SELECT * FROM performance_schema.data_locks; # 查看有哪些事务申请了哪些锁
...
mysql> commit;

其它细节:同一个sql 不同的隔离级别可能会加不同的锁;发生死锁后,innodb 会选择回滚undo 量最小的事务。

MVCC 为数据提供多个副本

数据库基础(四)Innodb MVCC实现原理 - 勤劳的小手的文章 - 知乎一种无锁并发控制技术。通过数据库事务版本号、记录中的隐式字段、undo log、read view来实现的。

  1. 每次事务开启前都会从数据库获得一个自增长的事务ID,可以从事务ID判断事务的执行先后顺序。
  2. 记录的隐藏字段
    1. DB_TRX_ID 记录操作该数据事务的事务ID;
    2. DB_ROLL_PTR 指向上一个版本数据在undo log 里的位置指针;
    3. DB_ROW_ID: 隐藏ID ,当创建表没有合适的索引作为聚集索引时,会用该隐藏ID创建聚集索引;
  3. 在innodb 中每个事务开启后都会得到一个read_view。主要保存了当前数据库系统中正处于活跃(没有commit)的事务的ID号,换句话说,保存的是系统中当前不应该被本事务看到的其他事务id列表。
    1. 当数据的事务ID不满足read view条件时候,从undo log里面获取数据的历史版本,然后数据历史版本事务号回头再来和read view 条件匹配 ,直到找到一条满足条件的历史数据,或者找不到则返回空结果;

工作原理(不同文章不同)

基于Timestamp的Scheduler会在事务开始时候分配一个全局自增的Timestamp,这个Timestamp通常由物理时间戳或系统维护的自增id产生,用于区分事务开始的先后。同时,每个数据库对象需要增加一些额外的信息(多像jvm 对象的mark word 的线程id),这些信息会由对应的事务在访问后更新,包括:

  1. RT(X): 最大的读事务的Timestamp
  2. WT(X): 最大的写事务的Timestamp
  3. C(X): 最新修改的事务是否已经提交 基于Timestamp假设开始时Timestamp的顺序就是事务执行的顺序,当事务访问数据库对象时,通过对比事务自己的Timestamp和该对象的信息,可以发现与这种与开始顺序不一致的情况,并作出应对:

  4. Read Late:比自己Timestamp晚的事务在自己想要Read之前对该数据进行了写入,并修改了WT(X),此时会Read不一致的数据。
  5. Write Late: 比自己Timestamp晚的事务在自己想要Write之前读取了该数据,并修改了RT(X),如果继续写入会导致对方读到不一致数据。 这两种情况都是由于实际访问数据的顺序与开始顺序不同导致的,Scheduler需要对冲突的事务进行Abort。
  6. Read Dirty:通过对比C(X),可以发现是否看到的是已经Commit的数据,如果需要保证Read Commit,则需要Delay事务到对方Commit之后再进行提交。

实现细节

为了实现多版本的并发控制,需要给每个事务在开始时分配一个唯一标识TID,并对数据库对象增加以下信息:

  1. txd-id,创建该版本的事务TID
  2. begin-ts及end-ts分别记录该版本创建和过期时的事务TID
  3. pointer: 指向该对象其他版本的链表

其基本的实现思路是,每次对数据库对象的写操作都生成一个新的版本,用自己的TID标记新版本begin-ts及上一个版本的end-ts,并将自己加入链表。读操作对比自己的TID与数据版本的begin-ts,end-ts,找到其可见最新的版本进行访问。根据乐观程度多版本的机制也分为三类:Two-phase Locking (MV2PL);Timestamp Ordering (MVTO);Optimistic Concurrency Control (MVOCC)

《MySQL实战45讲》一个事务要更新一行,如果刚好有另外一个事务拥有这一行的行锁,它又不能这么超然了,会被锁住,进入等待状态。问题是,既然进入了等待状态,那么等到这个事务自己获取到行锁要更新数据的时候,它读到的值又是什么呢?

  1. begin/start transaction 命令并不是一个事务的起点,在执行到它们之后的第一个操作 InnoDB 表的语句,事务才真正启动。如果你想要马上启动一个事务,可以使用 start transaction with consistent snapshot 这个命令。
  2. 在 MySQL 里,有两个“视图”的概念
    1. 一个是 view。它是一个用查询语句定义的虚拟表,创建视图的语法是 create view … ,而它的查询方法与表一样。
    2. 另一个是 InnoDB 在实现 MVCC 时用到的一致性读视图,即 consistent read view,用于支持 RC(Read Committed,读提交)和 RR(Repeatable Read,可重复读)隔离级别的实现。它没有物理结构,作用是事务执行期间用来定义“我能看到什么数据”。
  3. 在可重复读隔离级别下,事务在启动的时候就“拍了个快照”。注意,这个快照是基于整库的。如果一个库有 100G,那么我启动一个事务,MySQL 就要拷贝 100G 的数据出来,这个过程得多慢啊。实际上,我们并不需要拷贝出这 100G 的数据。
  4. InnoDB 里面每个事务有一个唯一的事务 ID,叫作 transaction id。它是在事务开始的时候向 InnoDB 的事务系统申请的,是按申请顺序严格递增的。数据表中的一行记录,其实可能有多个版本 (row),每个版本有自己的 row trx_id(trx_id 即操作 row 的事务id)。一行记录的 多个版本并不是物理上真实存在的,而是每次需要的时候根据当前版本和 undo log 计算出来的

可重复读——可以读到什么数据

按照可重复读的定义,一个事务启动的时候,能够看到所有已经提交的事务结果。但是之后,这个事务执行期间,其他事务的更新对它不可见。在实现上, InnoDB 为每个事务构造了一个数组,用来保存这个事务启动瞬间,当前正在“活跃”的所有事务 ID。“活跃”指的就是,启动了但还没提交。数组里面事务 ID 的最小值记为低水位,当前系统里面已经创建过的事务 ID 的最大值加 1 记为高水位。

数据版本的可见性规则,就是基于数据的 row trx_id 和这个高低水位/事务视图(每个事务的高低水位都不同)对比结果得到的。对于当前事务的启动瞬间来说,一个数据版本的 row trx_id,有以下几种可能:

  1. 如果落在绿色部分,表示这个版本是已提交的事务或者是当前事务自己生成的,这个数据对当前事务是可见的;
  2. 如果落在红色部分,表示这个版本是由将来启动的事务生成的,是当前事务肯定不可见的;
  3. 如果落在黄色部分,那就包括两种情况:a 若 row trx_id 在数组中,表示这个版本是由还没提交的事务生成的,对当前事务不可见; b 若 row trx_id 不在数组中,表示这个版本是已经提交了的事务生成的,对当前事务可见。

有了这个声明后,系统里面随后发生的更新,是不是就跟这个事务看到的内容无关了呢?因为之后的更新,生成的版本一定属于上面的 2 或者 3(a) 的情况,而对它来说,这些新的数据版本是不存在的,所以这个事务的快照,就是“静态”的了。InnoDB 利用了“所有数据都有多个版本”的这个特性,实现了“秒级创建快照”的能力(PS:有点copy on write的feel)。一个数据版本,对于一个事务视图来说,除了自己的更新总是可见以外,有三种情况:

  1. 版本未提交,不可见;
  2. 版本已提交,但是是在视图创建后提交的,不可见;
  3. 版本已提交,而且是在视图创建前提交的,可见。

可重复读——更新逻辑

当事务要去更新数据的时候,就不能再在历史版本上更新了,否则其它事务的更新就丢失了。update 更新数据都是先读后写的,而这个读,只能读当前的值,称为“当前读”(current read):必须要读最新版本,而且必须加锁。当前读的规则,就是要能读到所有已经提交的记录的最新值。

如果当前记录的行锁被其他事务占用的话,就需要进入锁等待。根据两阶段锁协议,其他事务提交才会释放锁,因此可以读到其他事务提交后的row。

除了 update 语句外,select 语句如果加锁,也是当前读

# 加读锁
mysql> select k from t where id=1 lock in share mode;
# 加写锁
mysql> select k from t where id=1 for update;

mvcc 实现

postgresql、mysql、tidb对 mvcc 有着不同的实现方案。

TiKV 事务模型概览,Google Spanner 开源实现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 模块可以调用这个接口

读提交

读提交的逻辑和可重复读的逻辑类似,它们最主要的区别是:

  1. 在可重复读隔离级别下,只需要在事务开始的时候创建一致性视图(高低水位),之后事务里的其他查询都共用这个一致性视图;对于可重复读,查询只承认在事务启动前就已经提交完成的数据;
  2. 在读提交隔离级别下,每一个语句执行前都会重新算出一个新的视图(高低水位)。对于读提交,查询只承认在语句启动前就已经提交完成的数据;