技术

并发的成本 基础设施优化 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分析 Prometheus 学习 Kubernetes监控 Kubernetes 控制器模型 容器日志采集 容器狂占cpu怎么办? 容器狂打日志怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes objects之编排对象 源码分析体会 自动化mock AIOps说的啥 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 kubernetes实践 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 marathon-client 源码分析 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 swagger 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初识 mesos 的一些tips mesos 集成 calico calico学习 AQS2——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 硬件对软件设计的影响 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记2 《mysql技术内幕》笔记1 log4j学习 为什么netty比较难懂? 回溯法 apollo client源码分析及看待面向对象设计 学习并发 从一个marathon的问题开始的 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并发机制及语言层工具 mesos深入 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 简介 那些有用的sql语句 异构数据库表在线同步 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 mesos简介 缓存系统 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快速入门

标签


《mysql技术内幕》笔记2

2017年11月12日

简介

索引

全文索引

红黑树

二叉树的演化逻辑

红黑树深入剖析及Java实现

基本要点:BST,Balanced BST,Red-Black Tree

  1. 二叉树在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。平衡树在插入和删除的时候,会通过旋转操作将高度保持在logN。具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂,而且插入和删除性能差,在实际环境下的应用不如红黑树。
  2. 二叉树通过旋转保持平衡,旋转算法是不同树的具有区分性的特质之一。红黑树通过引入颜色的概念,通过颜色这个约束条件的使用来保持树的高度平衡。
  插入维持平衡 删除维持平衡
二叉树 旋转 旋转
B+Tree 节点的分裂、元素的上浮 向兄弟节点借元素、合并节点、元素的下沉

二叉树与高阶(一个节点多于2个叉)树不同在于,高阶树中每个节点元素的个数,为旋转算法提供了决策依据,体现在:

  1. 是否需要分裂合并等操作
  2. 大多数时候,一个插入和删除操作影响节点本身、父亲和兄弟节点,通过父节点元素个数,可以简单的判断是否波及其他节点。

而对于二叉树来说,这些都可以实现,大不了整棵树遍历一遍。但没有类似于“节点个数”(因为都是一个)这样直接的信息来提供决策,这也是为什么说“AVL树实现比较复杂”的原因吧。红黑树,节点的颜色标记,估计与“节点个数”有异曲同工的作用。有一句话说,“纠结的原因通常是因为掌握的信息不够(或信息获取比较难)”,其存在标识一种平衡状态,通过局部的直接判断,即可进行旋转决策。

事务

《软件架构设计》通俗的讲,事务就是一个“代码块”,这个代码块要么不执行,要么全部执行。事务要操作数据(数据库里面的表),事务与事务之间会存在并发冲突,就好比在多线程编程中,多个线程操作同一份儿数据,存在线程间的并发冲突是一个道理。

理解事务 - MySQL 事务处理机制基本要点(太经典,要低水平的复制粘贴了):

重新理解一致性:在事务T开始时,此时数据库有一种状态,这个状态是所有的MySQL对象处于一致的状态,例如数据库完整性约束正确,日志状态一致等,当事务T提交后,这时数据库又有了一个新的状态,不同的数据,不同的索引,不同的日志等,但此时,约束,数据,索引,日志(binlog/redo/undo log)等MySQL各种对象还是要保持一致性(正确性)。 这就是 从一个一致性的状态,变到另一个一致性的状态。也就是事务执行后,并没有破坏数据库的完整性约束。有分布式一致性,其实一致性问题分布式和单机都有。

事务的原子性和持久性——redo/undo log

一次事务实际执行的伪代码

start transaction
	写undo log1: 备份该行数据(update)
	update 表1某行记录
	写redo log1
	写undo log2:备份该行数据(insert)
	delete 表1某行记录
	写redo log2
	写undo log3:该行的主键id(delete)
	insert 表2某行记录
	写redo log3
commit

InnoDB将Undo Log看作数据,因此记录Undo Log的操作也会记录到redo log中,包含Undo Log操作的Redo Log,看起来是这样的:

 记录1: <trx1, Undo log insert <undo_insert …>>
 记录2: <trx1, insert …>
 记录3: <trx2, Undo log insert <undo_update …>>
 记录4: <trx2, update …>
 记录5: <trx3, Undo log insert <undo_delete …>>
 记录6: <trx3, delete …>

宕机恢复后

  1. 会把redo log 全部重放一遍,并不关心事务性,提交的事务和未提交的事务都被重放了,从而让数据库”原封不动“的回到宕机前的状态
  2. 重放完成后,再把未完成的事务找出来,逐一利用undo log进行逻辑上的“回滚”。 undo log 记录了sql 的反操作,所谓回滚即 执行反操作sql

可以看出,redo log 不保证事务原子性, 只是保证了持久性, 不管提交未提交的事务都会进入redo log。

redo log和undo log所做的一切都是为了提高 数据本身的IO效率,已提交事务和未提交事务的数据 可以随意立即/延迟写入磁盘。代价是,事务提交时,redo log必须写入到磁盘,数据随机写转换为日志数据顺序写。PS,随机写优化为顺序写,也是一种重要的架构优化方法。

redo log

为什么需要redo log

  1. 数据写磁盘一般是随机的,单次较慢,也不允许频繁写入
  2. 数据写入一般先保存在内存中,然后定期将内存数据写入到磁盘
  3. 磁盘的顺序写性能较高,所以采用Write-Ahead log机制,将日志顺序持久化到磁盘。Write-Ahead log 就是redo log

在支付业务中,有一个用户账户表,还会有一个用户账户临时表,更新用户账户的金额数据时,经常先在临时表中先插入一条日志,因为只有插入操作,自然没有并发问题,然后再去更新用户账户。此时,临时表的作用就类似于redo日志。

应用层所说的事务都是”逻辑事务“,以上图为例,在逻辑层面事务是三条sql语句,涉及两张表。在物理层面,可能是修改了两个Page,修改每个page 产生一部分日志,生成一个LSN,存储到Redo log 的Block 里。不同事务的日志在 redo log 中是交叉存在的。

redo log 的格式

从逻辑上来说,日志就是一个无限延长的字节流,从数据库启动开始,日志便源源不断的追加,直到结束。但从物理上来看,日志不可能是一个永不结束的字节流, 磁盘是块设备,磁盘的读取和写入都是不是按照一个个字节来处理的,日志文件不可能无限膨胀,过了一定时间,之前的历史日志就不需要了。

存储格式:physiological logging

I/O 写入的原子性

要实现事务的原子性,先得考虑磁盘I/O的原子性。 一个Log block 是512 byte,os 一次write 写一半宕机了,怎么办?可以通过在日志中加入checksum 解决,宕机后重启,可以通过check sum 来判断一个Log block 是否完整,不完整则丢弃。

数据 page(16kb) 的写入也有类似问题,可以使用double write 等技术解决。

笔者的个人感受:一个大粒度的原子性,终究会归结到一个小粒度的原子性。基于小粒度的原子性上添加各种机制(说白了就是成就成,不成就重试,再不成就报错),可以支持大粒度的原子性。

undo log

undo log 不是log,而是数据,每个事务在修改记录之前,都会先把该记录拷贝出来一份,存在undo log里,也就是copyOnWrite。也正因为每条记录都有多个版本,才很容易实现隔离性。同时修改同一条数据是不可能的,只能读取历史版本。事务提交后,没用其它事务引用的“历史版本/undo log”就可以删除了。PS:跟cpu 缓存导致一条内存数据多个cpu 副本异曲同工

数据库的并发安全

本文是innodb的读书笔记,更宏观的看待并发问题请参考腾讯云李海翔:数据库的并发控制技术深度探索基本要点:

  1. 数据库一共会发生11种异常现象,脏读、不可重复读、幻读只是其中三种。
  2. 主流的并发控制技术

    • 两阶段锁
    • 基于时间戳
    • 基于有效性检查
    • MVCC,常与其它技术一起使用
    • SCO

所谓并发控制技术就是抑制并发,或者发现数据异常并处理。 使各种共享资源在被并发访问变得有序所设计的一种规则

《软件架构设计》软件并发问题其实就是读写、写写冲突问题,读写冲突又可以细分为快照读与写冲突、当前读与写冲突

并发冲突 处理办法 示例
读读 无冲突  
快照读与写 copyOnWrite/MVCC select xx from xx
当前读与写 加锁,但锁有强弱(互斥、读写),粒度有大小(表、行、范围),锁住的对象有不同(索引、数据行)
可以根据容忍的读错误类型加不同的锁
select xx for udpate
select xx in share mode
写写 加锁  

事务的隔离性与一致性——MVCC与锁

mysql 作为一个数据库,其实就是sql的 解释执行器,这一点和jvm 作为字节码的解释执行器是一样一样的。但跟java语言层面的并发安全又有所不同,java语言层面就两个安全级别:安全,不安全。目的是为了保证一致性,但绝对的一致性要损失性能,因此允许某些异常便产生一致性强弱的区别,抽出几个常见的数据异常问题划分隔离性,总比不可重复读等说一堆,减少了沟通成本。一般mysql 引擎仅实现部分并发安全。隔离性描述了并发安全程度

事务 加解锁阶段
begin; 获取唯一自增的事务id等操作
insert… 加insert对应的锁
update… 加update对应的锁
delete… 加delete对应的锁
commit; 事务提交时,同时释放insert、update、delete对应的锁
  1. 可以看到,begin和commit除了标记一个事务的开始与结束外,在数据库实现中,是有对应的操作意义的。
  2. 具体到不同的sql 语句、不同的事务并发场景、不同的事务隔离级别、不同的索引类型,是不是加锁(比如用MVCC即可)、加的锁都可能不一样。

锁的实现

书中提到,在数据库中,锁有lock和latch,一般业务开发熟悉的锁对应的是latch,简单区别如下:

  对象 保护 持续时间 存在于
lock 事务 表、页、行 整个事务过程 lock manager的哈希表中
latch 线程 内存数据结构 很短 被保护的数据结构中

比如在java中,一个object内存结构就相应有锁的标记位,意味着任何一个object都有可能被竞争访问,如果object已经被锁住(标记位是某个值),则线程会被挂起。

其实,锁的标记信息存储在被保护的数据结构上还是独立集中管理,都是一样的。

  1. 在操作系统中,一个文件在磁盘上的存在形式是一个个磁盘块,在内存中的存在形式除了磁盘块载入内存的缓冲块外,还有一个文件表,表中的文件结构体有锁的标志位。文件是否被某个线程独占,并不属于文件的内容信息,存入磁盘中是不恰当的。如果锁的信息存入磁盘块对应的缓冲块,则破坏了缓冲块与磁盘块的直接对应关系。
  2. 每个数据结构保有锁的标记信息有一个好处,即语言层面简化锁的使用,比如java的synchronized关键字, 比lock unlock方便多了。

上层应用开发会加各种锁,有些锁是隐式的,数据库会主动加(比如update),有些锁是显式的,比如select xx for update。 因为开发的使用不当,数据库会发生死锁,就像jvm 也会死锁一样。作为数据库,必须有机制检测出死锁(判断一个有向图是否存在环),并解决死锁问题,比如强制让其中某个事务回滚,释放锁。

线程阻塞 还是事务 阻塞

文中提到 “事务会阻塞”,而不是我们常说的 “线程会阻塞”,这种 表述是不是意味着,执行事务的线程 如果发现事务阻塞了,就可以转而执行其它事务, 就像goroutine 那样? 从 MySQL锁阻塞分析,mysql锁阻塞 可以看到,就实现上来说, 事务阻塞也就意味着 执行事务的线程阻塞。进而可以推断,并发读写比较多时,会导致大量的数据库线程在同一时间处于阻塞状态,进而拖慢 数据库执行 任务队列中事务的速度。

$ show engine innodb status

------------
TRANSACTIONS
------------
Trx id counter 4131
Purge done for trx's n:o < 4119 undo n:o < 0 state: running but idle
History list length 126
LIST OF TRANSACTIONS FOR EACH SESSION:
---TRANSACTION 0, not started
MySQL thread id 2, OS thread handle 0x7f953ffff700, query id 115 localhost root init
show engine innodb status
---TRANSACTION 4130, ACTIVE 41 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 360, 1 row lock(s)
MySQL thread id 4, OS thread handle 0x7f953ff9d700, query id 112 localhost root updating
delete from emp where empno=7788
------- TRX HAS BEEN WAITING 41 SEC FOR THIS LOCK TO BE GRANTED:   ## 等待了41s
RECORD LOCKS space id 16 page no 3 n bits 88 index `PRIMARY` of table `test`.`emp` trx id 4130 lock_mode X locks rec but not gap waiting
Record lock, heap no 9 PHYSICAL RECORD: n_fields 10; compact format; info bits 0  ## 线程4在等待往test.emp中的主键上加X锁,page num=3
 0: len 4; hex 80001e6c; asc    l;;
 1: len 6; hex 000000001018; asc       ;;
 2: len 7; hex 91000001420084; asc     B  ;;
 3: len 5; hex 53434f5454; asc SCOTT;;
 4: len 7; hex 414e414c595354; asc ANALYST;;
 5: len 4; hex 80001d8e; asc     ;;
 6: len 4; hex 208794f0; asc     ;;
 7: len 4; hex 80000bb8; asc     ;;
 8: SQL NULL;
 9: len 4; hex 80000014; asc     ;;

------------------
---TRANSACTION 4129, ACTIVE 45 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 360, 1 row lock(s)
MySQL thread id 7, OS thread handle 0x7f953ff6c700, query id 111 localhost root updating
update emp set sal=3500 where empno=7788
------- TRX HAS BEEN WAITING 45 SEC FOR THIS LOCK TO BE GRANTED:   ## 等待了45s
RECORD LOCKS space id 16 page no 3 n bits 88 index `PRIMARY` of table `test`.`emp` trx id 4129 lock_mode X locks rec but not gap waiting
Record lock, heap no 9 PHYSICAL RECORD: n_fields 10; compact format; info bits 0  ## 线程7在等待往test.emp中的主键上加X锁,page num=3
 0: len 4; hex 80001e6c; asc    l;;
 1: len 6; hex 000000001018; asc       ;;
 2: len 7; hex 91000001420084; asc     B  ;;
 3: len 5; hex 53434f5454; asc SCOTT;;
 4: len 7; hex 414e414c595354; asc ANALYST;;
 5: len 4; hex 80001d8e; asc     ;;
 6: len 4; hex 208794f0; asc     ;;
 7: len 4; hex 80000bb8; asc     ;;
 8: SQL NULL;
 9: len 4; hex 80000014; asc     ;;

------------------
---TRANSACTION 4128, ACTIVE 51 sec
2 lock struct(s), heap size 360, 1 row lock(s)
MySQL thread id 3, OS thread handle 0x7f953ffce700, query id 110 localhost root clean

show engine innodb status 输出可以看到, 一个事务id 通常 对应一个 thread id。

数据库和文件系统

书中有多处提到数据库和文件系统的关系:

  1. 事务是数据库区别于文件系统的重要特性之一
  2. 数据库的主要任务就是协调对数据记录的并发访问