什么是雪花算法

雪花算法的含义及用途

分布式结构中，常要求服务器集群内保持唯一id。如果在单个机器上实现唯一id，非常简单。但是在高并发集群中实现，则可能会出现id冲突的问题。雪花算法（SnowFlake）就是解决这一问题的。

算法思想

雪花算法是Twitter开源的分布式唯一id生成算法。它的核心思想就是用一个64bit的长整型作为唯一id，长整型中包含毫秒级时间戳，机器编号，机器内序号。

唯一id的组成

64个bit中，第一位的bit是不使用的。因为id的类型是长整型，如果第一位为1，则值为复数。所以第一位默认为0。后面的41位为时间戳，表示当前的时间，最小单位为毫秒。再后面十位表示机器编号。最后12位是序列号。
举例：
0|11111011110000001111000011110110101010110|0101110010|110011011110
该id中：

1. 第一位固定为0，无实际意义。
2. 2-42位表示当前系统时间，单位为毫秒。
3. 43-44为表示机器的编号。共10位。也就是该集群中最多有2的10次方也就是1024台机器。如果集群中的机器数量超过的该数，则需要调整各个字段的宽度。
4. 最后12位为单机序列号，用来表示id生成服务在当前这一毫秒内生成的不同的id。12位二进制数能表示的最大正整数为4096。也就是说雪化算法能容纳的最大并发量为每毫秒4096条请求，换算成秒是每秒409.6万次请求。若实际并发数量超过这一值，则超过了雪花算法的容纳范围，需要考虑拓宽id的长度等。

SnowFlake的golang实现

func genSnowFlake(machineId int, datacenterId int) int {
        // 如果想让时间戳范围更长，也可以减去一个日期
    curTimeStamp := time.Now().UnixNano() / 1000000

    if curTimeStamp == lastTimeStamp {
        // 2的12次方 -1 = 4095，每毫秒可产生4095个ID
        if sn > 4095 {
            time.Sleep(time.Millisecond)
            curTimeStamp = time.Now().UnixNano() / 1000000
            sn = 0
        }
    } else {
        sn = 0
    }
    sn++
    lastTimeStamp = curTimeStamp
        // 应为时间戳后面有22位，所以向左移动22位
    curTimeStamp = curTimeStamp << 22
    machineId = machineId << 17
    datacenterId = datacenterId << 12
        // 通过与运算把各个部位连接在一起
    return int(curTimeStamp) | machineId | datacenterId | sn
}