程序员应该知道的数据库知识

Open AlexiaChen opened this issue 5 years ago • 1 comments

程序员应该知道的数据库知识

数据库范式与反范式

这里没啥好讲的，一般传统企业重业务，对性能，高并发要求小的开发，对数据库设计的时候尽量遵守范式，尽可能达到第三范式要求，如果是大并发，追求灵活的开发，可以适当的对范式取舍，加入违背范式的设计也没什么，互联网反范式的设计有很多。

分库分表

怎么拆分

根据业务拆分，根据读写比重拆分

分布式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级别，如何解决最后一个问题？就是丢失更新的问题，那么就涉及到乐观锁和悲观锁了

悲观锁和乐观锁

丢失更新的问题在业务场景中非常常见，数据库没有帮程序员解决这个问题，只好靠程序员自己动手了。这里的乐观锁和悲观锁是解决问题的思想手法，不是数据库中的东西。

考虑一个最简单的充钱和扣钱的金融业务场景，假设有一张表中的一条记录:

user_id          balance
1                 30

两个事务并发地对同一条记录修改，一个充钱，一个扣钱，大概如下:

事务A:

begin transaction
int b = select balance from T where user_id = 1
b = b + 50
update T set balance = b where user_id = 1
commit

事务B:

begin transaction
int b = select balance from T where user_id = 1
b = b - 50
update T set balance = b where user_id = 1
commit

如果以上两个事务串行地正确地执行，无论先后，那么最终结果都是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。原因都是事务没有串行化。

要解决这个问题，有以下几种方法:

利用单条SQL语句的原子性

事务A:

begin transaction
update T set balance = balance + 50 where user_id = 1
commit

事务B:

begin transaction
update T set balance = balance - 50 where user_id = 1
commit

这样，避免了事务存在的中间结果。但是这个不实用，现实中，业务要对balance做各种计算，必然有业务代码块，中间结果，然后回写到数据库。

悲观锁

认为数据发生并发冲突的概率很大，所以读之前就上锁。利用select xxx for update语句。

事务A:

begin transaction
int b = select balance from T where user_id = 1 for update
b = b + 50
update T set balance = b where user_id = 1
commit

事务B:

begin transaction
int b = select balance from T where user_id = 1 for update
b = b - 50
update T set balance = b where user_id = 1
commit

但是悲观锁有潜在问题，比如事务A在拿到锁后，commit之前出了问题，崩溃异常什么的，会造成锁不能释放，数据库死锁。另外事务A拿到锁之后，事务B就会被阻塞，也就是select会“卡”住不返回，这样在高并发场景下会造成客户端大量的请求阻塞。所以才有了乐观锁。

乐观锁

乐观锁比较乐观，认为数据发生并发冲突的概率小，所以读之前不上锁。等写回去的时候再判断数据是否被其他事务改了，即多线程高并发里面会提到的CAS(CompareAndSet)的思路。

说白话点就是保证读写的数据记录是同一个版本。在表中需要加一个version字段:

user_id          balance      version
1                 30

事务A:

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
}

注意，balance的更新，version的比较和自增都是在一条update语句完成的，这个非常关键，不然version字段又会出现丢失更新的问题。

其实就是通过版本号知道数据是不是被修改了，被修改了update就是失败的，所以重新循环读取，再次进行业务逻辑计算，回写。当然，现实中不会无限重试，一般重试3到5次，然后操作界面提示用户稍后操作就可以了。

分布式锁

乐观锁只是预防select和update对于同一张表的同一条记录。但是如果涉及到多表select和update，那么事务A和事务B也可能会相互覆盖。乐观锁的版本号就行不通了。它针对的是同一个行记录。

这种场景需要分布式锁，就是引入一个“中心节点”作为锁，其他节点判断这个锁状态，利用Redis的一些机制可以实现分布式锁，但是在极端情况下可能会有问题，不完善。当然Redis的作者基于Redis设计出来了一个分布式锁叫RedLock，这个业界一直存在争议。还可以用Zookeeper的“瞬时节点”机制和Zab协议的强一致性来实现分布式锁，但是性能QPS不高。

Feb 02 '20 09:02 AlexiaChen

snowflake 没更新了呀

Dec 12 '20 07:12 songtianyi

AlexiaChen.github.io AlexiaChen.github.io copied to clipboard