前缀匹配模糊查询。比如,where Key Like abc%,其实可以转换成范围查询:Key in [abc, abcz]。这样就按照范围查询逻辑来运行了。如果是其他匹配 where Key Like %abc%
或where Key like %abc则没办法转换成范围查询,只能一个个遍历。一言不合扫全表,就问你怕不怕。
while (!IsSuccess)
{
begin transaction
int b, v1 = select balance, version from T where user_id = 1
b = b + 50
IsSuccess = update T set balance = b, version = version + 1 where user_id = 1 and version = v1 // CAS
commit
}
事务B:
while (!IsSuccess)
{
begin transaction
int b, v1 = select balance, version from T where user_id = 1
b = b - 50
IsSuccess = update T set balance = b, version = version + 1 where user_id = 1 and version = v1 // CAS
commit
}
程序员应该知道的数据库知识
数据库范式与反范式
这里没啥好讲的,一般传统企业重业务,对性能,高并发要求小的开发,对数据库设计的时候尽量遵守范式,尽可能达到第三范式要求,如果是大并发,追求灵活的开发,可以适当的对范式取舍,加入违背范式的设计也没什么,互联网反范式的设计有很多。
分库分表
怎么拆分
根据业务拆分,根据读写比重拆分
分布式ID生成服务
分库之前,用数据库主键的自增就可以了,但是分库以后,需要一个全局ID服务,业界有snowflake。
拆分维度的选择
比如有个电商订单表,表里面有订单ID,用户ID,商户ID,到底是按照哪个ID进行拆分?
如果要进行多维度的查询,一般要建立一个映射表,建立辅助维度和主维度的映射关系,比如商户ID到用户ID的映射。
这个根据业务来看,不然东西太多,说不了。
Join查询问题
分库分表之后,join查询就不能用了,一般有以下方式解决,祖传秘方,如果不出意外,性能不好,一定是数据库的问题:
把Join拆分成多个单表查询,不让数据库join,在业务代码层面对结果进行拼装,大大降低慢查询概率
做宽表,重写轻读。做一个join表,提前把结果join好写入,空间换时间。
利用类似ES等搜索引擎,把数据导入进去,解决join问题
分布式事务
分库之后,数据库内建的事务就做不了了,一般解决办法就是优化业务,避免跨库的分布式事务,保证所有事务都落到单库中,实在无法避免,再考虑分布式事务的解决方案。
核心数据结构----B+树
B+树是B树的改进。关系型数据库在查询方面具备一些KV型没有的功能:
这些特性,一般归功于B+树。另外B树已经逐渐没啥应用了,所以就暂时不讨论B树了。
B+树的逻辑结构
数据库的主键对应了B+树的逻辑结构。
在叶子节点这一层,所有记录(真实数据)的主键按照从小到大的顺序排列,并且形成一个双向链表,叶子节点的每一个Key指向一条记录,一个节点有多个Key。
非叶子节点取的是下一层节点里面的Key的最小值或最大值。也就是所有的非叶子节点都是冗余的节点,为了加快查询性能,同一层的非叶子节点也是双向链表。
看到以上你可以感觉出来了,B+树是一颗平衡N叉树,只有叶子节点才有真正的data(记录),其他都是索引。B+树也比B树更加“矮胖”,IO次数更少,查询性能稳定等。
基于这样一种数据结构,实现那几个重要特性就容易了:
范围查询:比如找[1,40]之间的记录,两次查询,先查找1所在的叶子节点的记录位置,再查找40所在的叶子节点记录的位置,当然,根据上图,1的记录位置就是10的记录位置(因为1不存在),40的记录位置就是37。然后由于链表的特性,可以很方便地从10的位置遍历到37的位置。
前缀匹配模糊查询。比如,where Key Like abc%,其实可以转换成范围查询:Key in [abc, abcz]。这样就按照范围查询逻辑来运行了。如果是其他匹配 where Key Like %abc% 或where Key like %abc则没办法转换成范围查询,只能一个个遍历。一言不合扫全表,就问你怕不怕。
排序和分页。叶子节点天然就是有序的,支持排序和分页。
你知道了以上特性,你就清楚一些数据库的明文上的死规定的原理了。
B+树的磁盘存储结构
显然,工业界的B+树实现复杂,一般都不是纯内存的实现,纯内存实现没啥价值,真正的B+树需要与IO磁盘适配,B+树难就难在磁盘存储,所以实现复杂,难度高,其中各种细节不是三言两语就能说清楚的。B+树最终要存储在磁盘上,与其他数据结构不一样,一般B+树涉及到磁盘都需要定制,很难以通用库的形式抽象出来供人们调用,很难做出一个独立的组件,以InnoDB实现的B+树为例子,我们详细展开。
对于磁盘来说,不可能一条一条读写,都是以“块”为单位进行读写,InnoDB默认是16KB块大小,通过innodb_page_size指定,这里说的块,是一个逻辑单位,不是物理磁盘扇区的物理块。块是InnoDB读写磁盘的基本单位,InnoDB每一次磁盘I/O,读取的都是16KB的整数倍数据。
无论是叶子节点,非叶子节点都会装载到Page里(一个Page对应一个块)。InnoDB为每一个Page赋予一个全局的32位编号,所以InnoDB的存储容量的上限是64TB(2^32 * 16KB)。
一个Page是16KB是什么概念?以非叶子节点来说,一个Page可以装载1000个Key(假设Key是64位整数,8个字节),意味着B+树有1000个分叉;以叶子节点来说,一个Page可以装载200条记录(记录和Key是放在一起的,所以少点,假设记录大小是100字节)。
好了,我们来估算下一个三层的B+树可以hold多大的数据量,首先一个Page装载一个B+树节点,相当于一个节点算16KB大小。
第一层,根节点,也就是一个Page,里面存放1000个Key,对应1000个分叉
第二层,1000个节点,也就是1000个Page,每个Page装载1000个Key
第三层,1000 × 1000个Page(节点),每个Page装200条记录,1000 × 1000 × 200 = 2亿条记录,第三层总容量是16KB × 1000 × 1000 = 16GB。
所以第三层是不能装载到内存中的,第三层叶子节点是存到磁盘上了。第一层,第二层可以装到内存里, (1 + 1000) × 16KB = 16MB,一个三层B+树可以支撑2亿条记录,依次类推4层,5层B+树。因为第三层存储在磁盘上,所以做依次查询,只需要一次磁盘IO(读取叶子节点)就可以查到数据记录。如果是更多层数的B+树,可能就需要多次磁盘IO了,因为有些层的节点只能存物理磁盘。这些存储在物理盘上的节点你可以称为索引文件了。
非主键索引
一般主键或非主键索引都对应自己的一颗B+树,它们大同小异。在InnoDB中,非主键索引的叶子节点存储的不是记录的指针,而是主键的值。所以,对于非主键索引的查询,会查询两颗B+树,先在非主键索引的B+树上定位主键,再用主键去主键索引的B+树上找到最终记录,所以直接查主键索引理论上会更快点。
因为非主键索引的值可以重复,所以一个Key可能对应多条记录,B+树的结构可能稍有不同,首先非主键索引的B+树的叶子节点存储的主键的值还有索引值,对于非叶子节点,不仅存储了索引值,同时也存储了对应的主键的最小值或最大值。
事务与锁
事务的四个隔离级别
通俗的讲,一个事务就是一个代码块,这个代码块要么不执行,要不全部执行。这是事务的原子性。事务要操作表中的数据,如果多个事务并发就会存在冲突,跟多线程操作同一份数据需要加锁是一样的。
事务并发会导致下面几个问题:
脏读:事务A读取了一条记录,然后基于这个值做业务计算,在事务A提交前,事务B回滚了该记录,导致事务A读到了这条记录的一个脏数据
不可重复读: 在同一个事务A里面,两次读取同一行记录,但结果不一样。因为事务B对此记录进行了update操作
幻读: 在同一个事务A里面,select语句,执行两次,返回的记录条数不一样。因为另外一个事务B在进行insert/delete操作
丢失更新: 两个事务同时修改同一条记录,事务A的修改被事务B覆盖了。因为事务是并发的,没有串行化。
为了解决上面四个问题,数据库设置了不同的隔离级别,当然不同数据库实现各个隔离级别有差异,暂时不管。
级别1: Read uncommited,啥也没做,上面四个问题一个都没解决,实践中不会采用。
级别2:Read commited,只解决了脏读问题
级别3: Repeated Read, 解决了脏读,不可重复读,幻读的问题,InnoDB默认就是这个级别。
级别4: Serialization, 事务完全串行化,相当于独占锁,完全解决上面四个问题。性能无法接受,SQLite貌似就是这样串行化,在现实的重要场景中,不会采用这个级别。
现实中,一般采用2,3级别。
既然InnoDB默认是3级别,如何解决最后一个问题?就是丢失更新的问题,那么就涉及到乐观锁和悲观锁了
悲观锁和乐观锁
丢失更新的问题在业务场景中非常常见,数据库没有帮程序员解决这个问题,只好靠程序员自己动手了。这里的乐观锁和悲观锁是解决问题的思想手法,不是数据库中的东西。
考虑一个最简单的充钱和扣钱的金融业务场景,假设有一张表中的一条记录:
两个事务并发地对同一条记录修改,一个充钱,一个扣钱,大概如下:
事务A:
事务B:
如果以上两个事务串行地正确地执行,无论先后,那么最终结果都是30,30 + 50 - 50 = 30 - 50 + 50 = 30。但是如果两个事务并发执行,结果就不一定了,要不是30,要不是80或者-20。80或-20就是错误的结果,怎么导致的呢?
我们像分析多线程问题的那样,如果没有锁,会怎样呢?
事务A拿到数据30,进行计算,80。事务B显然看不到A事务的中间结果80,读出来30,进行计算-20,然后结果提交。然后事务A更新完毕提交结果,那么user_id=1的记录最终结果就是80,把-20覆盖了。这是事务A覆盖事务B。反过来事务B覆盖事务A就是-20。原因都是事务没有串行化。
要解决这个问题,有以下几种方法:
事务A:
事务B:
这样,避免了事务存在的中间结果。但是这个不实用,现实中,业务要对balance做各种计算,必然有业务代码块,中间结果,然后回写到数据库。
认为数据发生并发冲突的概率很大,所以读之前就上锁。利用select xxx for update语句。
事务A:
事务B:
但是悲观锁有潜在问题,比如事务A在拿到锁后,commit之前出了问题,崩溃异常什么的,会造成锁不能释放,数据库死锁。另外事务A拿到锁之后,事务B就会被阻塞,也就是select会“卡”住不返回,这样在高并发场景下会造成客户端大量的请求阻塞。所以才有了乐观锁。
乐观锁比较乐观,认为数据发生并发冲突的概率小,所以读之前不上锁。等写回去的时候再判断数据是否被其他事务改了,即多线程高并发里面会提到的CAS(CompareAndSet)的思路。
说白话点就是保证读写的数据记录是同一个版本。在表中需要加一个version字段:
事务A:
事务B:
注意,balance的更新,version的比较和自增都是在一条update语句完成的,这个非常关键,不然version字段又会出现丢失更新的问题。
其实就是通过版本号知道数据是不是被修改了,被修改了update就是失败的,所以重新循环读取,再次进行业务逻辑计算,回写。当然,现实中不会无限重试,一般重试3到5次,然后操作界面提示用户稍后操作就可以了。
乐观锁只是预防select和update对于同一张表的同一条记录。但是如果涉及到多表select和update,那么事务A和事务B也可能会相互覆盖。乐观锁的版本号就行不通了。它针对的是同一个行记录。
这种场景需要分布式锁,就是引入一个“中心节点”作为锁,其他节点判断这个锁状态,利用Redis的一些机制可以实现分布式锁,但是在极端情况下可能会有问题,不完善。当然Redis的作者基于Redis设计出来了一个分布式锁叫RedLock,这个业界一直存在争议。还可以用Zookeeper的“瞬时节点”机制和Zab协议的强一致性来实现分布式锁,但是性能QPS不高。