图解各路分布式ID生成算法 _分布式ID

在分布式系统中，通常会用到分布式ID来标注数据的唯一性，而分布式ID的生成方式又多种多样，今天我们就来讨论一下主流的分布式ID生成策略。
分布式ID基本需求

全局唯一
趋势递增
信息安全

全局唯一
这是基本要求，不必解释
趋势递增
为什么要趋势递增呢？
第一，由于我们的分布式ID，是用来标识数据唯一性的，所以多数时候会被定义为主键或者唯一索引。
第二，并且绝大多数互联网公司使用的数据库是：MySQL，存储引擎为innoDB 。
对于 B+Tree这个数据结构来讲，数据以自增顺序来写入的话，b+tree的结构不会时常被打乱重塑，存取效率是最高的。
信息安全
由于数据是递增的，所以，恶意用户的可以根据当前ID推测出下一个，非常危险，所以，我们的分布式ID尽量做到不易被破解。
数据库主键自增(Flicker)
基于数据库主键自增的方案，名为 Flicker 。
主要是利用MySQL的自增主键来实现分布式ID 。
以下为 Flicker实现分布式ID的主流做法：
【图解各路分布式ID生成算法】1、需要单独建立一个数据库实例：flicker
create database `flicker`;2、创建一张表：sequence_id
create table sequence_id( id bigint(20) unsigned NOT NULL auto_increment,stub char(10) NOT NULL default '', PRIMARY KEY (id), UNIQUE KEY stub (stub)) ENGINE=MyISAM;为什么用 MyISAM？不用 InnoDB？个人推测原因是： flicker算法出来的时候，MySQL的默认引擎还依旧是 MyISAM而不是 InnoDB，作者只是想用默认引擎而已，并无其他原因。

stub: 票根，对应需要生成 Id 的业务方编码，可以是项目名、表名甚至是服务器 IP 地址。
stub 要设置为唯一索引

3、使用以下SQL来获取ID
REPLACE INTO ticket_center (stub) VALUES ('test'); SELECT LAST_INSERT_ID(); Replaceinto 先尝试插入数据到表中，如果发现表中已经有此行数据（根据主键或者唯一索引判断）则先删除此行数据，然后插入新的数据，否则直接插入新数据。
一般 stub为特殊的相同的值。
这样，一个分布式ID系统算是可以搭建运行了。但是，有人要问：“这是一个单实例、单点的系统，万一挂了，岂不是影响所有关联的业务方？”
改进升华
是的。确实如此，因此又有人说：“可以利用MySQL主从模式，主库挂了，使用从库。”
这只能算是一种比较low的策略，因为如果主库挂了，从库没来得及同步，就会生成重复的ID 。
有没有更好的方法呢？
我们可以使用“双主模式“，也就是有两个MySQL实例，这两个都能生成ID 。
如图所示，我们原来的模式：

文章插图

双主模式是该怎么样呢？如何保持唯一性？
我们可以让一台实例生成奇数ID，另一台生成偶数ID 。
奇数那一台：
set auto_increment_offset=1;--起始值set auto_increment_increment=2;--步长偶数那一台：
set auto_increment_offset=2;--起始值set auto_increment_increment=2;--步长当两台都OK的时候，随机取其中的一台生成ID；若其中一台挂了，则取另外一台生成ID 。
如图所示：

文章插图

细心会发现，N个节点，只要起始值为1，2，...N，然后步长为N，就会生成各不相同的ID 。(PS:后文有推导公式)
总结
优点：

简单。充分利用了数据库自增 ID 机制，生成的 ID 有序递增。
ID递增

缺点：

并发量不大。
水平扩展困难，系统定义好了起始值、步长和机器台数，跑起来之后，添加额外的机器困难。
安全系数低

redis
Redis为单线程的，所以操作为原子操作，利用 incrby命令可以生成唯一的递增ID 。
原理

文章插图

单机单点，吞吐不够，加集群

文章插图

假设N个节点，则步长为N，节点起始值为1，2，…… N 。则三个节点生成的ID一定不同！
想想为什么？
以上信息条件可以转化为数学推理： 1+x*N=2+y*N且x、y、N都为整成数且N不为1，试问等式存不存在？
答：假设存在在起始值是1的节点上叠加x次之后等于起始值为2、叠加y次的值，既 “1 + x * N = 2 + y * N” 等式成立则：x * N = 1 + y * Nx * N - y * N = 1(x - y) * N = 1(x - y) = 1 / N又因为 x、y都为整成数；所以x - y 必为整成数；又因为只有N等于1的时候，1/N才为整成数；与条件N为1不符合，所以不存在。