自增主键与雪花算法的优缺点、设计更适合分库分表的UUID算法

(目录)

为什么不推荐使用自增主键

递增主键的作用

我们在数据库里保存的数据就跟excel表一样，一行行似的

而在底层，这一行行数据，就是保存在一个个16k大小的页里。

每次都去遍历所有的行性能会不好，于是为了加速搜索，我们可以根据主键id，从小到大排列这些行数据，将这些数据页用双向链表的形式组织起来，再将这些页里的部分信息提取出来放到一个新的16kb的数据页里，再加入层级的概念。于是，一个个数据页就被组织起来了，成为了一棵B+树索引。

而当我们在建表sql里声明了PRIMARY KEY (id)时，mysql的innodb引擎，就会为主键id生成一个主键索引，里面就是通过B+树的形式来维护这套索引。

到这里，我们有两个点是需要关注的：

• 数据页大小是固定16k
• 数据页内，以及数据页之间，数据主键id都是从小到大排序的

由于数据页大小固定了是16k，当我们需要插入一条新的数据，数据页会被慢慢放满，当超过16k时，这个数据页就有可能会进行分裂。

针对B+树叶子节点，如果主键是自增的，那它产生的id每次都比前一次要大，所以每次都会将数据加在B+树尾部，B+树的叶子节点本质上是双向链表，查找它的首部和尾部，时间复杂度O(1)。而如果此时最末尾的数据页满了，那创建个新的页就好。

如果主键不是自增的，比方说上次分配了id=7，这次分配了id=3，为了让新加入数据后B+树的叶子节点还能保持有序，它就需要往叶子结点的中间找，查找过程的时间复杂度是O(lgn)，如果这个页正好也满了，这时候就需要进行页分裂了。并且页分裂操作本身是需要加悲观锁的，性能变低。总体看下来，自增的主键遇到页分裂的可能性更少，因此性能也会更高。

分库分表下的id

分库分表，那我就需要说明下，递增和自增的区别了，自增就是每次都+1，而递增则是新的id比上一个id要大就行了，具体大多少，没关系。

mysql在水平分库分表时，一般有两种方式。

1. 一种分表方式是通过对id取模进行分表，这种要求递增就好，不要求严格自增，因为取模后数据会被分散到多个分表中，就算id是严格自增的，在分散之后，都只能保证每个分表里id只能是递增的。

2. 一种分表方式是根据id的范围进行分表（分片），它会划出一定的范围，比如以2kw为一个分表的大小，那02kw就放在这张分表中，2kw4kw放在另一张分表中，数据不断增加，分表也可以不断增加，非常适合动态扩容，但它要求id自增，如果id递增，数据则会出现大量空洞。

但不管哪种分表方式，一般是不可能继续用原来表里的自增主键的，原因也比较好理解，原来的每个表如果都从0开始自增的话，那好几个表就会出现好几次重复的id，根据id唯一的原则，这显然不合理。

所以我们在分库分表的场景下，插入的id都是专门的id服务生成的，如果是要严格自增的话，那一般会通过redis来获得，当然不会是一个id请求获取一次，一般会按批次去获得，比如一次性获得100个。快用完了再去获取下一批100个。**

但这个方案有个问题，它严重依赖redis，如果redis挂了，那整个功能就傻了。

有没有不依赖于其他第三方组件的方法呢？

雪花算法（Snowflake）

概念

雪花算法通过64位有特殊含义的数字来组成id

解读：

首先第0位不用。

接下来的41位是时间戳。精度是毫秒，这个大小大概能表示个69年左右，因为时间戳随着时间流逝肯定是越来越大的，所以这部分决定了生成的id肯定是越来越大的。

再接下来的10位是指产生这些雪花算法的工作机器id，这样就可以让每个机器产生的id都具有相应的标识。

再接下来的12位，序列号，就是指这个工作机器里生成的递增数字。

可以看出，只要处于同一毫秒内，所有的雪花算法id的前42位的值都是一样的，因此在这一毫秒内，能产生的id数量就是 2的10次方✖️2的12次方，大概400w，肯定是够用了，甚至有点多了。

缺点

1. 细心的兄弟们肯定也发现了，雪花算法它算出的数字动不动就比上次的数字多个几百几万的，也就是它生成的id是趋势递增的，并不是严格+1自增的，也就是说它并不太适合于根据范围来分表的场景。这是个非常蛋疼的问题。
2. 还有个小问题是，那10位工作机器id，我每次扩容一个工作机器，这个机器怎么知道自己的id是多少呢？是不是得从某个地方读过来。
3. 时间回拨问题：

• 雪花算法通过时间来即将作为id的区分标准之一,对于同一台id生成机器,它通过时间和序号保证id不重复
• 当机器出现问题,时间可能回到之前,此时,时间就不能区分
• 又或者因为闰秒的出现,导致时间回拨

那有没有一种生成id生成方案，既能让分库分表能做到很好的支持动态扩容，又能像雪花算法那样并不依赖redis这样的第三方服务。

适合分库分表的uuid算法

设计：

我们可以参考雪花算法的实现，设计成下面这样。注意下面的每一位，都是十进制，而不是二进制。

解析：

• 开头的12位依然是时间，但并不是时间戳，雪花算法的时间戳精确到毫秒，我们用不上这么细，我们改为yyMMddHHmmss，注意开头的yy是两位，也就是这个方案能保证到2099年之前，id都不会重复，能用到重复，那也是真·百年企业。同样由于最前面是时间，随着时间流逝，也能保证id趋势递增。
• 接下来的10位，用十进制的方式表示工作机器的ip，就可以把12位的ip转为10位的数字，它可以保证全局唯一，只要服务起来了，也就知道自己的ip是多少了，不需要像雪花算法那样从别的地方去读取worker id了，又是一个小细节。
• 在接下来的6位，就用于生成序列号，它能支持每秒钟生成100w个id。
• 最后的4位，也是这个id算法最妙的部分。它前2位代表分库id，后2位代表分表id。也就是支持一共100*100=1w张分表。

举个例子，假设我只用了1个分库，当我一开始只有3张分表的情况下，那我可以通过配置，要求生成的uuid最后面的2位，取值只能是[0,1,2]，分别对应三个表。这样我生成出来的id，就能非常均匀的落到三个分表中，这还顺带解决了单个分表热点写入的问题。

如果随着业务不断发展，需要新加入两张新的表(3和4)，同时第0张表有点满了，不希望再被写了，那就将配置改为[1,2,3,4]，这样生成的id就不会再插入到对应的0表中。同时还可以加入生成id的概率和权重来调整哪个分表落更多数据。

有了这个新的uuid方案，我们既可以保证生成的数据趋势递增，同时也能非常方便扩展分表。非常nice。

总结

• 建表sql里主键边上的AUTO_INCREMENT，可以让主键自增，去掉它是可以的，但这就需要你在insert的时候自己设置主键的值。
• 建表sql里的 PRIMARY KEY 是用来声明主键的，如果去掉，那也能建表成功，但mysql内部会给你偷偷建一个 ROW_ID的隐藏列作为主键。
• 由于mysql使用B+树索引，叶子节点是从小到大排序的，如果使用自增id做主键，这样每次数据都加在B+树的最后，比起每次加在B+树中间的方式，加在最后可以有效减少页分裂的问题。
• 在分库分表的场景下，我们可以通过redis等第三方组件来获得严格自增的主键id。如果不想依赖redis，可以参考雪花算法进行魔改，既能保证数据趋势递增，也能很好的满足分库分表的动态扩容。
• 并不是所有数据库都建议使用自增id作为主键，比如tidb就推荐使用随机id，这样可以有效避免写热点的问题。而对于一些敏感数据，比如用户id，订单id等，如果使用自增id作为主键的话，外部通过抓包，很容易可以知道新进用户量，成单量这些信息，所以需要谨慎考虑是否继续使用自增主键。