不遵守UUID协议规范的唯一识别码生成

twitter/snowflake

【此节转载】

Snowflake算法核心

把时间戳，工作机器id，序列号组合在一起。

除了最高位bit标记为不可用以外，其余三组bit占位均可浮动，看具体的业务需求而定。默认情况下41bit的时间戳可以支持该算法使用到2082年，10bit的工作机器id可以支持1023台机器，序列号支持1毫秒产生4095个自增序列id。下文会具体分析。

Snowflake – 时间戳

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

uint64_t generateStamp()
{
    timeval tv;
    gettimeofday(&tv, 0);
    return (uint64_t)tv.tv_sec * 1000 + (uint64_t)tv.tv_usec / 1000;
}

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

Snowflake – 工作机器id

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

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

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

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

Snowflake – 序列号

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

uint64_t waitNextMs(uint64_t lastStamp)
{
    uint64_t cur = 0;
    do {
        cur = generateStamp();
    } while (cur <= lastStamp);
    return cur;
}

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

语言实现

其他的方法

业务属性

• 滴滴：时间+起点编号+车牌号
• 淘宝订单：时间戳+用户ID
• 其他电商：时间戳+下单渠道+用户ID，有的会加上订单第一个商品的ID。

举例roll业务场景--用户参与roll房间记录
时间+roll房间id+用户id

数据库方案-Flicker的解决方案

Redis分布式方案

推荐

注意
UUID生成算法不保证返回值绝对唯一
170亿分之1的重复概率(数据来源维基百科)

UUID

UUID 是 通用唯一识别码（Universally Unique Identifier），UUID的目的，是让分散式系统中的所有元素，都能有唯一的辨识资讯，而不需要透过中央控制端来做辨识资讯的指定。
目前最广泛应用的UUID，是微软公司的全局唯一标识符（GUID）

GUID

全局唯一标识符，简称GUID（Globally Unique Identifier），通常表示成32个16进制数字（0－9，A－F）组成的字符串，如：{21EC2020-3AEA-1069-A2DD-08002B30309D}，它实质上是一个128位长的二进制整数。

UUID的格式

xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
8位 4位 4位 4位 12位
M那个位置，代表版本号，由于UUID的标准实现有5个版本，所以只会是1,2,3,4,5
N那个位置，代表变种(Variant)，一般只会是8,9,a,b
rfc4122协议10XX四位只能表示成8,9,A(16进制的10),B(16进制的11)

VariantNCS(已经过时的老古董,NCS=Apollo Network Computing System) 0xxx
VariantRFC4122(本文档) 10XX
VariantMicrosoft(微软) 110x
VariantFuture(未来) 111X

各个版本简介

http://www.uuid.online/ 可以演示不同版本的UUID

UUID目前协议规定的版本有5个，其中1、3、4版本较为常用

版本1

基于时间戳+MAC地址

通过当前时间戳、机器MAC地址生成；
由于在算法中使用了MAC地址，这个版本的UUID可以保证在全球范围的唯一性。
但与此同时，因为它暴露了电脑的MAC地址和生成这个UUID的时间，这就是这个版本UUID被诟病的地方。

版本2(大部分不使用)

基于时间戳+MAC地址

DCE安全的UUID和基于时间的UUID算法相同，但会把时间戳的前4位置换为POSIX的UID或GID。
不过，在UUID的规范里面没有明确地指定，所以基本上所有的UUID实现都不会实现这个版本。

版本3

基于命名空间的UUID(使用MD5散列化命名空间)

由用户指定1个namespace和1个具体的字符串，通过MD5散列，来生成1个UUID；
其中namespace根据协议规定，一般
domain name system, URLs, ISO Object IDs (OIDs), X.500 Distinguished
Names (DNs), and reserved words in a programming language.

版本4

基于随机数的UUID

最简单常用的一种

版本5

基于命名空间的UUID(使用SHA1散列化命名空间)

代码示例

import uuid
print "v1=",uuid.uuid1()
print "v3=",uuid.uuid3(uuid.NAMESPACE_DNS, "myString")
print "v4=",uuid.uuid4()
print "v5=",uuid.uuid5(uuid.NAMESPACE_DNS, "myString")

//java只实现了v3和v4
import java.util.UUID;

public class code
{
    public static void main(String[] args)
    {
        System.out.println("v3="+UUID.nameUUIDFromBytes("myString".getBytes()).toString());
        System.out.println("v4="+UUID.randomUUID());
    }
}

UUID和各个编程语言

注:PHP内置函数uniqid并不是uuid协议的实现