发布于

MySQL必知必会

什么是MySQL

MySQL是一个开源的关系型数据库管理系统，是非常流行的开源架构中LNMP的常用组件之一，MySQL几乎已经成为开源的标准数据库。在这篇文章，对MySQL的常用知识点进行整理。

MySQL架构

MySQL服务器架构，由以下几个组件构成，如客户端、连接池、查询缓存、分析器、优化器、存储引擎。整体步骤分为3步：

  1. 客户端发起请求->连接/线程处理->分析器/解析器
  2. 分析器/解析器->查询缓存->查询优化器
  3. 优化器从存储引擎查询/更新数据

整体流程见下图：

ACID

大多数数据库都会要求事务需要实现ACID特性，所谓的ACID就是：

  1. 原子性(atomicity):事务中的所有操作要么全部提交成功，要么全部失败回滚。
  2. 一致性(consistency):数据库总是从一个一致性状态转换到另一个一致性状态。
  3. 隔离性(isolation):一个事务所做的修改在提交之前对其它事务是不可见的。
  4. 持久性(durability):一旦事务提交，其所做的修改便会永久保存在数据库中。

隔离级别

InnoDB的默认隔离级别是REPEATABLE READ 可重读。

  1. READ UNCOMMITTED 可以读取未提交的事务
  2. READ COMMITED 只能读取已经提交的事务
  3. REPEATABLE READ 重复读取已提交的事务
  4. SERIALIZABLE 对事务进行加锁读
隔离级 脏读可能性 不可重复读可能性 幻读可能性 加锁读
READ UNCOMMITED 是 是 是 否
READ COMMITED 否 是 是 否
REPEATABLE READ 否 否 是 否
SERIALIZABLE 否 否 否 是

MVVC

InnoDB通过MVVC的并发控制解决了幻读问题。所谓的幻读就是，2个不同的线程，线程A执行查询操作时，得到结果集1，这时，线程B执行插入数据的操作并提交事务，线程A再次执行查询操作时，得到结果集2，会发现结果集2中出现新的插入的行，新增返回的行，就是所谓的幻影行。

通常数据的操作有3种，插入、更新、删除，删除内部与更新实现一致，特定位置标记为删除。通过在表的每一行添加3个字段记录相关回滚操作：DB_TRX_ID、DB_ROLL_PTR、DB_ROW_ID。

  1. DB_TRX_ID字段指示插入或更新该行的最后一个事务的事务标识符。
  2. DB_ROLL_PTR 滚动指针指向写入回滚段的撤消日志记录。如果更新了行，则撤消日志记录包含在更新行之前重建行内容所需的信息。
  3. DB_ROW_ID字段包含在插入新行时单独增加的行ID。

锁

InnoDB支持很多种锁，例如共享锁、排它锁、意向锁、行锁、间隙锁、下一键锁、插入意向锁等。

SELECT ... FROM 默认无锁，在 SERIALIZABLE 隔离级别会加锁，使用唯一索引查询唯一的行会要求索引记录锁定。

SELECT ... FROM FOR UPDATE
SELECT ... FROM LOCK IN SHARE MODE

对于唯一搜索条件的唯一索引，锁定找到的索引记录。对于其他搜索条件和非唯一索引，InnoDB锁定扫描的索引范围。

SELECT ... FROM FOR UPDATE会阻塞其他会话的共享锁，如LOCK IN SHARE MODE。

UPDATE WHERE 设置一个搜索匹配的每一行记录上添加排它的下一键锁定。对于唯一搜索条件的唯一索引，锁定找到的索引记录。

当UPDATE修改聚集索引记录是，对次要的索引记录进行隐式锁定。

DELETE FROM WHERE设置一个搜索匹配的每一行记录上添加排它的下一键锁定。对于唯一搜索条件的唯一索引，锁定找到的索引记录。

INSERT 在插入的行上设置独占锁，是索引记录锁，不会组织其他会话在插入行之前插入间隙。

INSERT ... ON DUPLICATE KEY UPDATE 与INSERT一致，不同在于发生重复键错误时，在要更新的行上采用独占锁而不是共享锁。对重复的主键值采用独占索引记录锁定，对于重复的唯一键值，采用独占的下一键锁定。

REPLACE 与INSERT一致，如果有唯一键冲突，将在要替换的行上放置专用的下一键锁。

INSERT INTO T SELECT ... FROM S WHERE ... 在要插入到T的每一行上设置独占索引记录锁。

REPLACE INTO t SELECT ... FROM s WHERE ...` or `UPDATE t ... WHERE col IN (SELECT ... FROM s ...) InnoDB设置下一键锁在行上。

AUTO_INCREMENT InnoDB在与自动增量列关联的索引末尾设置独占锁。

InnoDB对定义外键约束的条件的INSERT，UPDATE，DELETE，都会设置一个共享记录锁。

LOCK TABLES 设置一个表锁，由在InnoDB层更高的MySQL层设置的。

死锁的产生

MySQL官方文章，讲解一个死锁的产生案例。

  1. 客户端A请求S lock START TRANSACTION;SELECT * FROM t WHERE i = 1 LOCK IN SHARE MODE;
  2. 这时客户端B 开启一个事务，删除这条数据。START TRANSACTION;DELETE FROM t WHERE i = 1; 删除操作要一个排它锁 X lock。
  3. 然后，客户端A也尝试删除这条数据。DELETE FROM t WHERE i = 1;
  4. 这时就发生了死锁。ERROR 1213 (40001): Deadlock found when trying to get lock;try restarting transaction

InnoDB自动检测事务死锁并回滚一个或者多个事务以打破死锁，默认会回滚较小的事务，其中事务大小取决于插入、更新或者删除的行数。

索引的实现

MySQL的InnoDB存储引擎采用的是B+Tree数据结构实现数据的存储。B+Tree通过降低高度，将节点的索引存储在内存里，非索引的节点数据存储在硬盘上，提升读取效率。在数据结构与算法之美里，也讲解了不同数据结构之间的对比。

查找条件/数据结构 散列表 平衡二叉查找树 跳表 B+Tree 备注
根据某个值查找数据 ✓ ✓ ✓ ✓
根据区间值来查找某些数据 ✗ ✗ ✓ ✓
二叉树 — — ✓ —
m叉树 — — — ✓ m预先计算

常用优化方法

在数据量达到一定级别，如TB级别，单库单表的容量比较大，会导致查询更新操作较慢。这时候，就需要对数据库进行物理级别的优化。

分库分表

优先独立拆分不同业务的数据库和表，方便后续管理维护，也就是所谓的垂直拆分。

  1. 对不同业务分离不同的数据库，如订单库、用户库、产品库等。
  2. 对较大的表，将常用的字段分离成不同的小表，不常用的字段分离单独的表，提升查询效率。

根据业务特点，将数据库特定的算法分布到不同的库和表，这就是水平拆分。

  1. 在同一个库里，根据hash取摸、范围切分、按时间、区域到不同的表。
  2. 大表拆分为小表，避免性能瓶颈。

范围分表是根据用户ID范围分布，比如1-10000一个表。

hash取模，例如根据用户ID或者订单ID对128取模，平均分布到128个表中。

按时间分表，最简单的是每天一个表，每天数据都存储在不同的表，也可以将3-6个月前的数据分离到其他的库表，毕竟历史数据查询概率较小，当前存储查询访问较大的热数据即可，这也就是所谓的冷热数据分离。

查询优化标准

让查询尽可能快的方法，就是尽可能命中索引。假设有这样的索引key(last_name ,first_name,dob)，那么MySQL可以非常高效工作的索引类型如下：

  1. 匹配全部的列 last_name = ‘Allen’ and first_name =’Cuba’ and Dob=’1960-01-01′
  2. 匹配最左前缀 last_name =’Allen’
  3. 匹配列前缀 last_name like “J%”
  4. 匹配范围值 last_name >= “Allen” and last_name <= “Barry”
  5. 精确匹配一部分并且匹配某个范围中的另一部分 last_name = “Allen” and first_name like “K%”
  6. 只访问索引的查询。也就是索引覆盖了全部查询字段的查询。

在阿里巴巴Java开发手册里，有一个SQL性能优化的目标推荐标准：至少要达到 range 级别,要求是 ref 级别,如果可以是 consts最好。

那这几个目标到底是啥意思呢？所谓的range是对索引进行范围检索。那到底什么是对索引进行范围检索呢？从上面例子，可以看出来，所谓的范围检索，就是对索引进行大于某个值且小于某个值的条件查找。

什么是索引全扫描呢？explain的结果就是type=index的查询类型，针对索引全部记录进行查找呗。这个与全表扫描类似，一个对索引所有记录进行扫描，一个是对表所有记录进行扫描。

ref级别，就是指命中最左前缀、主键、唯一索引等多行的查询，在explain显示type=ref。

const级别，指最多有一个匹配行的查询，比如命中主键、唯一索引的查询。

高可用

什么是高可用(High Availability)？人们通常是这样定义的，很少或者几乎没有服务不可用，就是高可用。这其实从逆向来定义的，它不是什么。那到底什么是高可用？有没有一个相对准确的定义？业界常用的测量系统的高可用性，是故障发生到恢复的时间，如下表：

系统可用性% 宕机时间/年 宕机时间/月 宕机时间/周 宕机时间/天
90% (1个9) 36.5 天 72 小时 16.8 小时 2.4 小时
99% (2个9) 3.65 天 7.20 小时 1.68 小时 14.4 分
99.9% (3个9) 8.76 小时 43.8 分 10.1 分钟 1.44 分
99.99% (4个9) 52.56 分 4.38 分 1.01 分钟 8.66 秒
99.999% (5个9) 5.26 分 25.9 秒 6.05 秒 0.87 秒

那MySQL如何实现高可用性呢？较为常用的工具有MHA(Master High Availability Manager and tools for MySQL)。部署MHA后，通过VIP对外提供服务，MHA服务会定期检查master的存活状态，一旦Master发生故障，会尝试如下流程：

  1. 通过SSH保存master的二进制日志binlogs
  2. 选择最新的slave节点
  3. 同步最新slave节点与其他slave节点的差异，也就是应用差异的中继日志到其他slave。
  4. 应用从master保存的二进制日志binlogs
  5. 提升最新的slave为master
  6. 其他的slave连接slave尝试复制。

负载均衡

大多数互联网应用都遵循一个28原则，也就是大约80%的请求都是读请求，20%是写入的请求。常见的采用HAProxy提供两个VIP提供服务，一个VIP负责读请求，一个VIP负责写请求。MySQL集群可以为主从、主主模式。

故障转移/恢复/容灾

针对故障转移这类，按照范围可以分为数据中心内部和外部。

内部一般由于服务器故障或网络等原因导致服务不可用，需要针对服务做自动转移，服务切换。

外部的话，比如光缆挖断了，地震了这类不可控的因素导致服务不可用，必须提前准备容灾措施。

由于金融行业对数据的要求较高，比如阿里云的两地三中心架构，两地指同城和异地，三中心指生产中心、同城容灾中心、异地容灾中心，提供超高可用的服务架构。这类金融行业的架构，成本和收益是成正比的。笔者所在的公司，采用了同地两中心，分别在两个数据中心部署了相关的服务，随时可切换到不同的数据中心，然后对核心数据进行异地的同步备份，定期备份核心业务数据，对监管要求较高的业务，需要保存5年以上的时间。

总体来说，对于同城的数据中心实时同步数据，异地数据进行定期备份。

参考链接

  1. 关于高可用的系统
  2. 金融交易系统异地灾备方案
  3. 金融云存储灾备之两地三中心

发布于

练习 Web 爬虫

问题

在这个练习中，我们将会使用 Go 的并发特性来并行化一个 Web 爬虫。

修改 Crawl 函数来并行地抓取 URL，并且保证不重复。

提示：你可以用一个 map 来缓存已经获取的 URL，但是要注意 map 本身并不是并发安全的！

背景知识

  1. 学习 Go语言的sync.Mutex用法，阅读计数器实现的源代码，这个例子也可以参数计数器来实现。
  2. 在多个协程抓取时可以添加互斥锁，这也是Mutex的应用。
  3. 需要你深刻的理解协程的编程方式，也需要注意信道的数据获取方式。

实现思路

  1. 基本代码算是实现了，但是没有做协程安全，如果多个协程同时处理，就会有变量被覆盖的情况。
  2. 还有一种情况，就是并没有对爬虫进行去重判断，有可能实现的爬虫会一直死循环，并需要对map进行互斥锁判断，避免会有冲突。
  3. URL的抓取实现是一些测试用例，并不是真实世界的抓取，现实中的爬虫会比这个更复杂，简单的来讲，最少要添加一个超时的处理，异常的处理。
  4. 在Crawl中如何实现协程抓取URL?如何同步控制map的URL更新？
  5. 定义SafeCounter类型，类似计数器有两个变量，一个是字符串和整数的映射，另外一个是互斥锁的实现。定义一个全局变量sc，在全部的函数里都可以使用。
  6. 由于map不是协程安全，所有验证函数validUrl和标记函数markUrl函数，都需要加下互斥锁。
  7. 并行的抓取，可以在Crawl实现，对抓取回来的内容里的二级URL进行协程处理，并发抓取URL。
    难点在于下面这两个地方：
//方案1
//开启协程处理二级URL
ch := make(chan int, len(urls))
for _, u := range urls {
    go crawl(u, depth-1, fetcher, ch)
}
for i:=0; i < len(urls); i++ {
    //从信道接受数据
     <- ch
}

func crawl(url string, depth int, fetcher Fetcher, ch chan int) {
    Crawl(url, depth, fetcher)
    ch <- 1
}

第一个是，根据对应urls数量开启配置信道缓冲区大小。
通过for循环urls数量，实现并行协程处理，然后重点来了，从信道缓冲区，接受协程发送过来的数据。
第二个，在私有函数crawl，注意，调用完抓取函数Crawl后，需要关闭信道。

细节

一级URL 标题 内容里的二级URL
https://golang.org/ “The Go Programming Language” "https://golang.org/pkg/","https://golang.org/cmd/"
https://golang.org/pkg/ “Packages” "https://golang.org/","https://golang.org/cmd/","https://golang.org/pkg/fmt/","https://golang.org/pkg/os/",
https://golang.org/pkg/fmt/ “Package fmt” "https://golang.org/","https://golang.org/pkg/",
https://golang.org/pkg/os/ “Package os” "https://golang.org/","https://golang.org/pkg/",

实现代码

GitHub

参考链接

  1. 练习：Web 爬虫
  2. GO指南 练习：Web爬虫
  3. 学习一下golang 练习70 web crawler
发布于

练习 等价二叉查找树

问题

不同二叉树的叶节点上可以保存相同的值序列。例如，以下两个二叉树都保存了序列 `1，1，2，3，5，8，13`。


在大多数语言中，检查两个二叉树是否保存了相同序列的函数都相当复杂。 我们将使用 Go 的并发和信道来编写一个简单的解法。

本例使用了 tree 包，它定义了类型：

type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}
1. 实现 Walk 函数。

2. 测试 Walk 函数。

函数 tree.New(k) 用于构造一个随机结构的已排序二叉查找树，它保存了值 k, 2k, 3k, ..., 10k。

创建一个新的信道 ch 并且对其进行步进：

go Walk(tree.New(1), ch)
然后从信道中读取并打印 10 个值。应当是数字 1, 2, 3, ..., 10。

3. 用 Walk 实现 Same 函数来检测 t1 和 t2 是否存储了相同的值。

4. 测试 Same 函数。

Same(tree.New(1), tree.New(1)) 应当返回 true，而 Same(tree.New(1), tree.New(2)) 应当返回 false。

Tree 的文档可在[这里](https://godoc.org/golang.org/x/tour/tree#Tree)找到。

背景知识

  1. 你需要了解什么是等价二叉树？
  2. 阅读Tree类型的Go实现源代码。代码实现了3个函数，New函数新建二叉树，insert函数插入新元素，实现了打印字符串String接口
  3. 了解协程，信道的实现原理。
  4. 判断等价二叉树相等的话，那么左右节点的值都需要相等。

实现思路

  1. 实现 Walk 函数，循环通过信道发送数据，然后接受并输出。Walk的遍历方式为中序遍历，先遍历根节点，然后左节点，最后右节点。
  2. 注意tree的遍历方式，也就是获得值的方式，实现一个私有的walk函数，签名和Walk一致，因为Tree类型较为简单，并不能直接判断循环的结束。故采用这样的方式，循环遍历到最后，t == nil时，关闭信道，不然会报错的。
  3. 实现 Same 函数，循环判断tree每一个值是否相等。难点在于，创建2个信道，去读取Walk返回的Tree的节点值。

实现代码

GitHub

参考链接

  1. 练习：等价二叉查找树
  2. 二叉查找树
  3. Go指南练习之《等价二叉树》(Equivalent Binary Trees)