自增ID是数据库中最熟悉不过的功能了。在小型应用中，一台数据库承托业务，没有问题。在中小型业务里采用读写分离，主/从结构（一主一从，一主多从，甚至带中继的主从），单表的自增ID逻辑上没问题，但性能上就受制于单台写入机器，扩展性差，容错性也不理想。但在大型应用中，通常要用到分库，分表。如何让各库各表的ID在时间上是递增的，且不重复。这就成为一个课题。
DB自增
数据库自身就有 auto_increment 的功能。它能保证全局的唯一性和递增性质。而且保证每次递增的步长一致。但受制于该机器的性能,也不易扩展。这时候可以有两种方法：
按范围水平切分
将分水平切分成 N 个，比如 表 1 的ID的初始值设置为 0， 表 2 的值设为 1 亿，表 3 为 2 亿。 这样，保证了ID的唯一性，但从整体来看ID 不是递增的。因为表 2 中的ID肯定都比表 1 中的大，而且是大不少。
按步长水平切分
第二种方式是分成 N 个表，但表的递增步长设置为 N。比如有 3 个表，则将步长设置为 3。这样表1 中的ID可能是：1, 4, 7…表2 中则是：2, 5, 8…;表3 中是: 3，6，9…。
这样也是保证了全局的唯一，同时在一定程度上保证了递增性。但在局步上ID的递增性不那么严谨。而且如果要扩展，也不那么方便。需要重新设置步长。
自建服务
由于使用数据库自身的自增功能有这么多限制。则可以考虑自建ID生成服务。我们自己创建，维护全局的ID，这里又有几种方法：
利用自增
单独建一张表，专门用来管理ID。但表里只存一个值，即当前ID的最大值。如果现在有服务要插入数据，先请求ID；从该表中得知当前ID的最大值是 100。这时候ID生成器生成 N 个ID，如 101, 102—110，共 10 个ID，并将它记在内存中。然后返回 101 给服务，并将表里的最大值设置为 110。下一个请求过来时则直接从内存中返回 102 。当ID用完后，再次查库，并生成新一批ID。
这种做法的好处是对数据库的请求要少一些。因为使用数据库自增ID时，每次生成ID，它都会有一次数据库的请求。这里利用了ID池的做法，减少了请求。
但该方法的问题在于如果ID生成的服务器崩溃了，提前生成放在池中的ID就消失了。下次请求的时候会漏掉一些ID。比如现在池中有 102，103，104，105，106。ID表中记的最大值是 106。如果这时候服务器挂了，再申请ID时，就会从 106 往上分配。而 102 - 106 则漏了。但这种情况对业务的影响不大。
为了解决ID生成器的单点故障情况，可以使用主备的结构。如使用 keepalive 。
时间毫秒数
如果不利用数据库来辅助生成ID，可以自己设计一种自增的，且唯一的算法。
显然和时间相关的算法是最合适的。当前的时间肯定是递增的，但要保证唯一性，就需要时间尽量精确，所以这里用了毫秒。而且时间可以表现成数字，正好用来做ID，用来做索引的查询效率很高，而且在本地就可以生成ID，不用额外请求ID生成服务。
但在同一毫秒下如果还有多次请求（每秒超过 1000 次请求），那就需要在毫秒数后再额外加一些识别的值，以减少重复的机率。比如增加 N 位的随机数字等。但比较有名的是 twitter 开源的 snowflake 算法。
snowflake
twitter 的做法是用毫秒再加上许多其它额外的数据进行拼接。它使用的是一个 Long 型的整数，一共 64 位。其中 第 1 位不用，后 41 位存毫秒数，10 位是机器编号，12 位作为毫秒内的序列号。
将毫秒数放在最高位，保证生成的ID是趋势递增的。在局部来看，ID也不是绝对的递增。比如在同一秒内如果有多次请求，这一秒内的ID可能不是时间上的先后对应ID的大小。
这种算法，41 位的毫秒数，可以存储 241 个值，即 2.19亿亿个。而我们以 50 年为限，需要的ID是 50 * 365 * 24 * 3600 * 1000 = 1,576,800,000,000。光靠 41 位的毫秒数就足够生成 50 年用的ID了。10 位的机器编码则表示可以有 210 = 1024 台机器。 12 位的毫秒内序列号表示同一毫秒内可以支持 212个ID。通常是不会有这么多的。
注意：通常在分表时，我们会用ID取模来决定分在哪个表。为了分表时的均匀，ID生成的算法产生的ID的最后一位要足够的平均分布。所以上面的逻辑中，把毫秒内序列号放在最后。甚至我们可以在后面再加一个随机 0-9 的值，专门用来应对分库分表。
参照代码:
class IdWork
{
//开始时间,固定一个小于当前时间的毫秒数即可
const twepoch = 1420070400000;//2015/01/01 0:0:0
//机器标识占的位数
const workerIdBits = 10;
//毫秒内自增数点的位数
const sequenceBits = 12;
protected $workId = 0;
//要用静态变量
static $lastTimestamp = -1;
static $sequence = 0;
function __construct($workId)
{
//机器ID范围判断
$maxWorkerId = -1 ^ (-1 << self::workerIdBits);
if ($workId > $maxWorkerId || $workId < 0) {
throw new Exception("机器编号不能大于 " . maxWorkerId . " 或小于 0");
}
//赋值
$this->workId = $workId;
}
//生成一个ID
public function nextId()
{
$timestamp = $this->timeGen();
$lastTimestamp = self::$lastTimestamp;
//判断时钟是否正常
if ($timestamp < $lastTimestamp) {
throw new Exception("时光无法倒流,机器上时间错误!");
}
//生成唯一序列
if ($lastTimestamp == $timestamp) {
$sequenceMask = -1 ^ (-1 << self::sequenceBits);
// 同一微秒中的序列号
self::$sequence = (self::$sequence + 1) & $sequenceMask;
if (self::$sequence == 0) {
$timestamp = $this->tilNextMillis($lastTimestamp);
}
} else {
self::$sequence = 0;
}
self::$lastTimestamp = $timestamp;
//
//时间毫秒/机器ID,要左移的位数
$timestampLeftShift = self::sequenceBits + self::workerIdBits;
$workerIdShift = self::sequenceBits;
//组合3段数据返回: 时间戳.工作机器.序列
$nextId = (($timestamp - self::twepoch) << $timestampLeftShift) | ($this->workId << $workerIdShift) | self::$sequence;
return $nextId;
}
//取当前时间毫秒
protected function timeGen()
{
$timestramp = (float)sprintf("%.0f", microtime(true) * 1000);
return $timestramp;
}
//取下一毫秒
protected function tilNextMillis($lastTimestamp)
{
$timestamp = $this->timeGen();
while ($timestamp <= $lastTimestamp) {
$timestamp = $this->timeGen();
}
return $timestamp;
}
}
$work = new IdWork(1023);
for ($i = 0; $i < 10; $i++) {
$id = $work->nextId();
echo $id . PHP_EOL;
}
JAVA 版本:
/**
* 描述: Twitter的分布式自增ID雪花算法snowflake (Java版)
*
**/
public class SnowFlake {
/**
* 起始的时间戳
*/
private final static long START_STMP = 1480166465631L;
/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 12; //序列号占用的位数
private final static long MACHINE_BIT = 5; //机器标识占用的位数
private final static long DATACENTER_BIT = 5;//数据中心占用的位数
/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
private long datacenterId; //数据中心
private long machineId; //机器标识
private long sequence = 0L; //序列号
private long lastStmp = -1L;//上一次时间戳
public SnowFlake(long datacenterId, long machineId) {
if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}
/**
* 产生下一个ID
*
* @return
*/
public synchronized long nextId() {
long currStmp = getNewstmp();
if (currStmp < lastStmp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (currStmp == lastStmp) {
//相同毫秒内，序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒内，序列号置为0
sequence = 0L;
}
lastStmp = currStmp;
return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
| datacenterId << DATACENTER_LEFT //数据中心部分
| machineId << MACHINE_LEFT //机器标识部分
| sequence; //序列号部分
}
private long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}
private long getNewstmp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(2, 3);
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
System.out.println(snowFlake.nextId());
}
System.out.println(System.currentTimeMillis() - start);
}
}