生成可排序（时间序列）的唯一 id

Posted on

参考文章:https://www.callicoder.com/distributed-unique-id-sequence-number-generator/

已有解决方案

UUID

UUID是全局唯一的128位十六进制数字。 两次生成相同UUID的可能性可以忽略不计。
UUID的问题在于它们的大小非常大并且索引不好。 当您的数据集增加时，索引大小也会增加，并且查询性能会受到影响。

MongoDB的ObjectId

MongoDB的ObjectID是12字节（96位）十六进制数字，由 - 组成 -
一个4字节的纪元时间戳，以秒为单位，
一个3字节的机器标识符，
一个2字节的进程ID，和
一个3字节的计数器，以随机值开始。
这比早期的128位UUID小。但同样，大小比我们通常在单个MySQL自动增量字段（64位bigint值）中的长度要长。

Database Ticket Servers

此方法使用集中式数据库服务器生成唯一的递增ID。 这就像一个集中的自动增量。 Flickr使用此方法。
这种方法的问题是票证服务器可能成为写入瓶颈。 此外，您还需要在基础架构中引入一个需要管理和扩展的组件。

Twitter Snowflake

Twitter Snowflake是一种专用网络服务，用于大规模生成64位唯一ID。 此服务生成的ID大致可按时间排序。
ID由以下组件组成：
Epoch时间戳以毫秒为单位精度 - 41位（使用自定义纪元为69年）
配置的机器ID - 10位（最多可提供1024台机器）
序列号 - 12位（每台机器的本地计数器，每4096重复一次）
为了后续扩展，他们保留了1位。 由于ID使用时间戳作为第一个组件，因此它们是可排序的。

Twitter Snowflake 生成的ID符合64位，并且是时间可排序的, 这就是我们想要的。但如果我们使用Twitter Snowflake，我们将再次在我们需要维护的基础架构中引入另一个组件。

Distributed 64-bit unique ID generator inspired by Twitter Snowflake

该序列生成器生成的ID由 - 组成；
Epoch时间戳以毫秒为单位精度 - 42位。 可以使用42位表示的最大时间戳是2^42-1，或4398046511103，其发布时间是2109年5月15日星期三7：35：11.103 AM。 可以使用139年的定制时代。
节点ID - 10位。 这为我们提供了1024个节点/机器。
每台机器的本地计数器 - 12位。 计数器的最大值为4095。
您的微服务可以使用此序列生成器独立生成ID。 这是有效的，适合bigint的大小。

java版本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

import java.net.NetworkInterface;
import java.security.SecureRandom;
import java.time.Instant;
import java.util.Enumeration;

/**
 * Distributed Sequence Generator.
 * Inspired by Twitter snowflake: https://github.com/twitter/snowflake/tree/snowflake-2010
 *
 * This class should be used as a Singleton.
 * Make sure that you create and reuse a Single instance of SequenceGenerator per node in your distributed system cluster.
 */
public class SequenceGenerator {

    private static final int TOTAL_BITS = 64;
    private static final int EPOCH_BITS = 42;
    private static final int NODE_ID_BITS = 10;
    private static final int SEQUENCE_BITS = 12;

    private static final int maxNodeId = (int)(Math.pow(2,NODE_ID_BITS)-1);
    private static final int maxSequence = (int)(Math.pow(2,SEQUENCE_BITS)-1);
    //2019-03-30 22:59:53
    private static final long CUSTOM_EPOCH =1553957993000L;

    private  int nodeId;

    private volatile long lastTimestamp = -1L;
    private volatile long sequence = 0L;

    public SequenceGenerator(int nodeId){
        if(nodeId <0 || nodeId > maxSequence){
            throw new IllegalArgumentException(String.format("NodeId must be between %d and %d",0,maxNodeId));
        }
    }

    public SequenceGenerator(){
        this.nodeId = createNodeId();
    }

    public synchronized long nextId(){
        long currentTimestamp = timestamp();
        if(currentTimestamp < lastTimestamp){
            throw new IllegalStateException("Invalid System Clock!");
        }
        if(currentTimestamp == lastTimestamp){
            sequence = (sequence+1)&maxSequence;
            if(sequence == 0){
                // Sequence Exhausted, wait till next millisecond.
                currentTimestamp = waitNextMillis(currentTimestamp);
            }
        }else{
            // reset sequence to start with zero for the next millisecond
            sequence = 0;
        }
        lastTimestamp = currentTimestamp;
        long id = currentTimestamp <<(TOTAL_BITS-EPOCH_BITS);
        id |= (nodeId <<(TOTAL_BITS-EPOCH_BITS-NODE_ID_BITS));
        id |= sequence;
        return id;
    }

    private static long timestamp(){
        return Instant.now().toEpochMilli() - CUSTOM_EPOCH;
    }

    private long waitNextMillis(long currentTimestamp){
        while ( currentTimestamp == lastTimestamp){
            currentTimestamp = timestamp();
        }
        return currentTimestamp;
    }

    private int createNodeId(){
        int nodeId;
        try {
            StringBuilder sb = new StringBuilder();
            Enumeration<NetworkInterface> networkInterfaceEnumeration = NetworkInterface.getNetworkInterfaces();
            while(networkInterfaceEnumeration.hasMoreElements()){
                NetworkInterface networkInterface = networkInterfaceEnumeration.nextElement();
                byte[] mac = networkInterface.getHardwareAddress();
                if(mac != null){
                    for(int i=0;i<mac.length;i++) {
                        sb.append(String.format("%02X", mac[i]));
                    }
                }
            }
            nodeId = sb.toString().hashCode();
        }catch(Exception e){
           nodeId = (new SecureRandom().nextInt());
        }
        nodeId = nodeId & maxNodeId;
        return nodeId;
    }


}

go版本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package main

import (
	"fmt"
	"strings"
	"strconv"
	"net"
	"time"
)

const (
	TotalBits    = 64 // 总位数
	EpochBits    = 42 // 起始时间位数
	NodeIdBits   = 10 // 节点位数，最大支持 1024 个节点
	SequenceBits = 12 // 序列位数，最大支持 4096 个序列

	MaxNodeId   = 1<<NodeIdBits - 1   // 最大节点数
	MaxSequence = 1<<SequenceBits - 1 // 最大序列数

	CustomEpoch = 1553957993000 // 起始时间
)

var (
	mac       uint64
	seq       uint64
	timestamp uint64
)

func init(){
	mac = getMac()
	seq = getSeq()
	timestamp = getTimestamp()
}
//加锁引用
func generateUniqueId() uint64{
	ct := getTimestamp()
	if ct == timestamp{
		seq = (seq+1)%MaxSequence
		if seq == 0{
			ct = getNextTimestamp()
		}
	}else{
		seq=0
	}
	timestamp=ct
	nodeId := getNodeId()
	
	id := ct<<(TotalBits-EpochBits)
	id |= nodeId <<(TotalBits-EpochBits-NodeIdBits)
	id |= seq
	return id
}

// 获取节点 Id
// 根据 Mac 地址取模，0 ～ 1023
func getNodeId() uint64 {
	return mac % MaxNodeId
}

// 获取毫秒时间戳
func getTimestamp() uint64 {
	ns := time.Now().UnixNano()
	ms := uint64(ns / 1000 / 1000)
	shift := ms - CustomEpoch

	return shift
}

// 获取下一个毫秒时间戳
func getNextTimestamp() uint64 {
	t := getTimestamp()
	for t != timestamp {
		t = getTimestamp()
	}
	return t
}

func getMac() uint64{
	var mac uint64
	macAddress :=""

	netInterfaces, err := net.Interfaces()
	if err != nil{
		fmt.Println("err",err)
		return mac
	}
	for _,netInterface := range netInterfaces {
		macAddress = netInterface.HardwareAddr.String()
		if len(macAddress) != 0 {
			break
		}
	}
	macAddress = strings.Replace(macAddress,":","",-1)
	mac,err = strconv.ParseUint(macAddress,16,64)
	if err != nil {
		fmt.Println("convert err", err)
		return mac
	}
	return mac
}
// 获取序列号
func getSeq() uint64{
	return 0
}

参考文章

https://github.com/twitter-archive/snowflake/tree/snowflake-2010
https://en.wikipedia.org/wiki/Universally_unique_identifier
https://docs.mongodb.com/manual/reference/method/ObjectId/
http://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/
https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c
https://stackoverflow.com/questions/2671858/distributed-sequence-number-generation/5685869