分布式存储中，生成全局唯一ID的几种方案

1.自定义生成规则
 eg:
 3位服务器编码+15位年月日时分秒毫秒+3位表编码+4位随机码 （这样就完全单机完成编码任务）---共25位
 3位服务器编码+15位年月日时分秒毫秒+3位表编码+4流水码 （这样流水码就需要结合数据库和缓存）---共25位
2.单独开一个数据库，获取全局唯一的自增序列或个表的MaxId
 eg:
 Flickr 方案 --- http://blog.csdn.net/taotao4/article/details/46520053
 replace into + 奇偶2个数据库主键生成服务器(防止单点故障)

数据在分片时，典型的是分库分表，就有一个全局ID生成的问题。
单纯的生成全局ID并不是什么难题，但是生成的ID通常要满足分片的一些要求：
1 不能有单点故障。
2 以时间为序，或者ID里包含时间。这样一是可以少一个索引，二是冷热数据容易分离。
3 可以控制ShardingId。比如某一个用户的文章要放在同一个分片内，这样查询效率高，修改也容易。
4 不要太长，最好64bit。使用long比较好操作，如果是96bit，那就要各种移位相当的不方便，还有可能有些组件不能支持这么大的ID。

一 twitter
twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成机制，于是自己开发了一套全局唯一ID生成服务：Snowflake。
1 41位的时间序列（精确到毫秒，41位的长度可以使用69年）
2 10位的机器标识（10位的长度最多支持部署1024个节点）
3 12位的计数顺序号（12位的计数顺序号支持每个节点每毫秒产生4096个ID序号）最高位是符号位，始终为0。
优点：高性能，低延迟；独立的应用；按时间有序。缺点：需要独立的开发和部署。

原理

时间戳

这里时间戳的细度是毫秒级，具体代码如下，建议使用64位Linux系统机器，因为有vdso，gettimeofday()在用户态就可以完成操作，减少了进入内核态的损耗。

<span style="font-size:18px;"><strong><code class="hljs cpp" style="display: block; padding: 0.5em; color: rgb(0, 0, 0); background: rgb(255, 255, 255);"><span class="hljs-keyword" style="color:#0088;">uint64_t</span> generateStamp()
{
    timeval tv;
    gettimeofday(&tv, <span class="hljs-number" style="color:#06666;">0</span>);
    <span class="hljs-keyword" style="color:#0088;">return</span> (<span class="hljs-keyword" style="color:#0088;">uint64_t</span>)tv.tv_sec * <span class="hljs-number" style="color:#06666;">1000</span> + (<span class="hljs-keyword" style="color:#0088;">uint64_t</span>)tv.tv_usec / <span class="hljs-number" style="color:#06666;">1000</span>;
}</code></strong></span>

默认情况下有41个bit可以供使用，那么一共有T（1llu << 41）毫秒供你使用分配，年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你只给时间戳分配39个bit使用，那么根据同样的算法最后年份 = 17.4年。

工作机器ID

严格意义上来说这个bit段的使用可以是进程级，机器级的话你可以使用MAC地址来唯一标示工作机器，工作进程级可以使用IP+Path来区分工作进程。如果工作机器比较少，可以使用配置文件来设置这个id是一个不错的选择，如果机器过多配置文件的维护是一个灾难性的事情。

这里的解决方案是需要一个工作id分配的进程，可以使用自己编写一个简单进程来记录分配id，或者利用Mysql auto_increment机制也可以达到效果。

工作进程与工作id分配器只是在工作进程启动的时候交互一次，然后工作进程可以自行将分配的id数据落文件，下一次启动直接读取文件里的id使用。

PS：这个工作机器id的bit段也可以进一步拆分，比如用前5个bit标记进程id，后5个bit标记线程id之类:D

序列号

序列号就是一系列的自增id（多线程建议使用atomic），为了处理在同一毫秒内需要给多条消息分配id，若同一毫秒把序列号用完了，则“等待至下一毫秒”。

<span style="font-size:18px;"><strong><code class="hljs nginx" style="display: block; padding: 0.5em; color: rgb(0, 0, 0); background: rgb(255, 255, 255);"><span class="hljs-attribute">uint64_t</span> waitNextMs(uint64_t <span class="hljs-literal" style="color:#06666;">last</span>Stamp)
{
    <span class="hljs-attribute">uint64_t</span> cur = <span class="hljs-number" style="color:#06666;">0</span>;
    <span class="hljs-section">do</span> {
        <span class="hljs-attribute">cur</span> = generateStamp();
    } <span class="hljs-attribute">while</span> (cur <= <span class="hljs-literal" style="color:#06666;">last</span>Stamp);
    <span class="hljs-attribute">return</span> cur;
}</code></strong></span>

总体来说，是一个很高效很方便的GUID产生算法，一个int64_t字段就可以胜任，不像现在主流128bit的GUID算法，即使无法保证严格的id序列性，但是对于特定的业务，比如用做游戏服务器端的GUID产生会很方便。另外，在多线程的环境下，序列号使用atomic可以在代码实现上有效减少锁的密度。

最高位是符号位，始终为0。

优点：高性能，低延迟；独立的应用；按时间有序。

缺点：需要独立的开发和部署。

java 实现代码

 
         public class IdWorker { 
        
         private final long workerId; 
        
         private final static long twepoch = 1288834974657L; 
        
         private long sequence = 0L; 
        
         private final static long workerIdBits = 4L; 
        
         public final static long maxWorkerId = -1L ^ -1L << workerIdBits; 
        
         private final static long sequenceBits = 10L; 
        
         private final static long workerIdShift = sequenceBits; 
        
         private final static long timestampLeftShift = sequenceBits + workerIdBits; 
        
         public final static long sequenceMask = -1L ^ -1L << sequenceBits; 
        
         private long lastTimestamp = -1L; 
        
         public IdWorker(final long workerId) { 
        
         super(); 
        
         if (workerId > this.maxWorkerId || workerId < 0) { 
        
         throw new IllegalArgumentException(String.format( 
        
         "worker
 Id can't be greater than %d or less than 0", 
        
         this.maxWorkerId)); 
        
         } 
        
         this.workerId = workerId; 
        
         } 
        
         public synchronized long nextId() { 
        
         long timestamp = this.timeGen(); 
        
         if (this.lastTimestamp == timestamp) { 
        
         this.sequence = (this.sequence + 1) & this.sequenceMask; 
        
         if (this.sequence == 0) { 
        
         System.out.println("###########" + sequenceMask); 
        
         timestamp
 = this.tilNextMillis(this.lastTimestamp); 
        
         } 
        
         } else { 
        
         this.sequence = 0; 
        
         } 
        
         if (timestamp < this.lastTimestamp) { 
        
         try { 
        
         throw new Exception( 
        
         String.format( 
        
         "Clock
 moved backwards. Refusing to generate id for %d milliseconds", 
        
         this.lastTimestamp - timestamp)); 
        
         } catch (Exception e) { 
        
         e.printStackTrace(); 
        
         } 
        
         } 
        
         this.lastTimestamp = timestamp; 
        
         long nextId = ((timestamp - twepoch << timestampLeftShift)) 
        
         |
 (this.workerId << this.workerIdShift) | (this.sequence); 
        
         System.out.println("timestamp:" + timestamp + ",timestampLeftShift:" 
        
         +
 timestampLeftShift + ",nextId:" + nextId + ",workerId:" 
        
         +
 workerId + ",sequence:" + sequence); 
        
         return nextId; 
        
         } 
        
         private long tilNextMillis(final long lastTimestamp) { 
        
         long timestamp = this.timeGen(); 
        
         while (timestamp <= lastTimestamp) { 
        
         timestamp
 = this.timeGen(); 
        
         } 
        
         return timestamp; 
        
         } 
        
         private long timeGen() { 
        
         return System.currentTimeMillis(); 
        
         } 
        
         public static void main(String[] args){ 
        
         IdWorker
 worker2 = new IdWorker(2); 
        
         System.out.println(worker2.nextId()); 
        
         } 
        
         }

2 来自Flicker的解决方案
因为MySQL本身支持auto_increment操作，很自然地，我们会想到借助这个特性来实现这个功能。
Flicker在解决全局ID生成方案里就采用了MySQL自增长ID的机制（auto_increment + replace into + MyISAM）。一个生成64位ID方案具体就是这样的：
先创建单独的数据库(eg:ticket)，然后创建一个表：

 
         CREATE TABLE Tickets64 ( 
        
         id bigint(20) unsigned NOT NULL auto_increment, 
        
         stub char(1) NOT NULL default '', 
        
         PRIMARY KEY (id), 
        
         UNIQUE KEY stub (stub) 
        
         )
 ENGINE=MyISAM

当我们插入记录后，执行SELECT * from Tickets64，查询结果就是这样的：

+-------------------+------+
| id | stub |
+-------------------+------+
| 72157623227190423 | a |
+-------------------+------+
在我们的应用端需要做下面这两个操作，在一个事务会话里提交：

 
         REPLACE INTO Tickets64 (stub) VALUES ('a'); 
        
         SELECT LAST_INSERT_ID();

这样我们就能拿到不断增长且不重复的ID了。
到上面为止，我们只是在单台数据库上生成ID，从高可用角度考虑，接下来就要解决单点故障问题：Flicker启用了两台数据库服务器来生成ID，通过区分auto_increment的起始值和步长来生成奇偶数的ID。

 
         TicketServer1: 
        
         auto-increment-increment
 = 2 
        
         auto-increment-offset
 = 1 
        
         TicketServer2: 
        
         auto-increment-increment
 = 2 
        
         auto-increment-offset
 = 2

最后，在客户端只需要通过轮询方式取ID就可以了。

优点：充分借助数据库的自增ID机制，提供高可靠性，生成的ID有序。
缺点：占用两个独立的MySQL实例，有些浪费资源，成本较高。

三 UUID

UUID生成的是length=32的16进制格式的字符串，如果回退为byte数组共16个byte元素，即UUID是一个128bit长的数字，
一般用16进制表示。
算法的核心思想是结合机器的网卡、当地时间、一个随即数来生成UUID。
从理论上讲，如果一台机器每秒产生10000000个GUID，则可以保证（概率意义上）3240年不重复
优点：
（1）本地生成ID，不需要进行远程调用，时延低
（2）扩展性好，基本可以认为没有性能上限
缺点：
（1）无法保证趋势递增
（2）uuid过长，往往用字符串表示，作为主键建立索引查询效率低，常见优化方案为“转化为两个uint64整数存储”或者“折半存储”（折半后不能保证唯一性）
四基于Redis的分布式ID生成器
首先，要知道redis的EVAL，EVALSHA命令：
原理

利用redis的lua脚本执行功能，在每个节点上通过lua脚本生成唯一ID。
生成的ID是64位的：

使用41 bit来存放时间，精确到毫秒，可以使用41年。
使用12 bit来存放逻辑分片ID，最大分片ID是4095
使用10 bit来存放自增长ID，意味着每个节点，每毫秒最多可以生成1024个ID
比如GTM时间 Fri Mar 13 10:00:00 CST 2015 ，它的距1970年的毫秒数是 1426212000000，假定分片ID是53，自增长序列是4，则生成的ID是：

5981966696448054276 = 1426212000000 << 22 + 53 << 10 + 41
redis提供了TIME命令，可以取得redis服务器上的秒数和微秒数。因些lua脚本返回的是一个四元组。

second, microSecond, partition, seq
客户端要自己处理，生成最终ID。

((second * 1000 + microSecond / 1000) << (12 + 10)) + (shardId << 10) + seq;
五 MongoDB文档（Document）全局唯一ID

为了考虑分布式，“_id”要求不同的机器都能用全局唯一的同种方法方便的生成它。因此不能使用自增主键（需要多台服务器进行同步，既费时又费力），
因此选用了生成ObjectId对象的方法。

ObjectId使用12字节的存储空间，其生成方式如下：

|0|1|2|3|4|5|6 |7|8|9|10|11|

|时间戳 |机器ID|PID|计数器 |

前四个字节时间戳是从标准纪元开始的时间戳，单位为秒，有如下特性：

1 时间戳与后边5个字节一块，保证秒级别的唯一性；
2 保证插入顺序大致按时间排序；
3 隐含了文档创建时间；
4 时间戳的实际值并不重要，不需要对服务器之间的时间进行同步（因为加上机器ID和进程ID已保证此值唯一，唯一性是ObjectId的最终诉求）。

机器ID是服务器主机标识，通常是机器主机名的散列值。

同一台机器上可以运行多个mongod实例，因此也需要加入进程标识符PID。

前9个字节保证了同一秒钟不同机器不同进程产生的ObjectId的唯一性。后三个字节是一个自动增加的计数器（一个mongod进程需要一个全局的计数器），保证同一秒的ObjectId是唯一的。同一秒钟最多允许每个进程拥有（256^3 = 16777216）个不同的ObjectId。

总结一下：时间戳保证秒级唯一，机器ID保证设计时考虑分布式，避免时钟同步，PID保证同一台服务器运行多个mongod实例时的唯一性，最后的计数器保证同一秒内的唯一性（选用几个字节既要考虑存储的经济性，也要考虑并发性能的上限）。

"_id"既可以在服务器端生成也可以在客户端生成，在客户端生成可以降低服务器端的压力。

参考：

http://www.cnblogs.com/heyuquan/archive/2013/08/16/global-guid-identity-maxId.html

秒客网

分布式存储中，生成全局唯一ID的几种方案

时间戳

工作机器ID

序列号

相关文章