- A)
- B)
- C)
A)
网络上现在有很多的分布式ID生成算法, 各大厂商也开源了自己的分布式id生成算法. 前段时间项目里有个生成唯一id的需求, 思考了一下, 将flick的id生成方案和Twitter的id生成算法结合到一起, 写了个小算法, 也算是站在巨人的肩膀上做了点小东西, lol
B)
原理大致是这样的, 利用mysql insert来计算出集群中某个节点处于集群中的位置, 算出serverId, 然后利用雪花算法在该id上生成分布式id.
目前的实现是采用long来进行存储的, 因此只能在生成时间维度, 节点数量, 和每毫秒内生成的数量上进行调节, 如果你们可以存储字符串的话, 那么可以拓展一下该算法, 加大时间和空间的容量.
C)
算法实现
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
@Service
public class IDGeneratorService implements CommandLineRunner {
private static final Logger LOG = LoggerFactory.getLogger(IDGeneratorService.class);
private static final int START_YEAR = 2018;
private static final int timeBitsSize = 40;
private static final int serverIdBitsSize = 16;
private static final int countBitsSize = 7;
private long maxIdPerMill;
private long startDateTime;
private long serverIdBits;
private long currentID;
private long maxTime;
private long lastGenerateTime = System.currentTimeMillis();
private Object lock = new Object();
@Resource
private AccountServerIdMapper accountServerIdMapper;
public void init() {
LocalDateTime start = LocalDateTime.of(START_YEAR, 1, 1, 0, 0);
startDateTime = start.toInstant(ZoneOffset.of("+8")).toEpochMilli();
maxTime = ((Double) Math.pow(2, timeBitsSize)).longValue();
maxIdPerMill = ((Double) Math.pow(2, countBitsSize)).longValue();
long serverSize = ((Double) Math.pow(2, serverIdBitsSize)).longValue();
AccountServerId accountServerId = new AccountServerId();
accountServerIdMapper.nextId(accountServerId);
long serverId = (int) (accountServerId.getId() % serverSize);
serverIdBits = (serverId << (countBitsSize));
LOG.info("[ID生成器] 开始时间:{}, 时间戳:{} ", new Date(startDateTime), startDateTime);
LOG.info("[ID生成器] 结束时间:{}, 时间戳:{} ", new Date(startDateTime + maxTime), maxTime);
LOG.info("[ID生成器] 每毫秒生成最大ID数:{} ", maxIdPerMill);
LOG.info("[ID生成器] 当前serverId: {}, serverIdSize:{}", serverId, serverSize);
LOG.info("[ID生成器] serverIdBits: {}", Long.toBinaryString(serverIdBits));
}
public long next() {
synchronized (lock) {
long curTime = System.currentTimeMillis() - startDateTime;
if (curTime >= maxTime) {
LOG.error("[ID生成器] 超过负载, {}, {}！返回 -1", curTime, maxTime);
return -1;
}
if (lastGenerateTime != curTime) {
currentID = 0;
} else {
if (currentID >= maxIdPerMill) {
LOG.error("[ID生成器] 同一毫秒[" + curTime + "]内生成" + currentID + "个ID！返回 -1");
return -1;
}
++currentID;
}
lastGenerateTime = curTime;
long gid = (curTime << countBitsSize + serverIdBitsSize) | serverIdBits;
gid |= currentID;
return gid;
}
}
public String nextStrId() {
return String.valueOf(next());
}
public long tryNextId() {
for (int i = 0; i < 1000; i++) {
long start = System.currentTimeMillis();
long id = next();
long diff = System.currentTimeMillis() - start;
if (diff > 3) {
String tid = Thread.currentThread().getName();
LOG.warn("[ID生成器] 线程{} 生成ID: {} 大于3毫秒: {}", tid, id, diff);
}
if (id == -1) {
try {
TimeUnit.MILLISECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
continue;
}
return id;
}
return -1;
}
public String tryNextStrId() {
return String.valueOf(tryNextId());
}
@Override
public void run(String... args) throws Exception {
init();
}
}
|
mybatis
1
2
3
4
5
6
7
8
| @Mapper
public interface AccountServerIdMapper {
@Insert("REPLACE INTO server_id (stub) VALUES ('a');")
@SelectKey(statement = "SELECT LAST_INSERT_ID()", keyProperty = "id", before = false, resultType = Long.class)
Long nextId(AccountServerId accountServerId);
}
|
SQL
1
2
3
4
5
6
7
8
| CREATE TABLE `server_id` (
`id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
`stub` char(1) DEFAULT NULL,
`create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
`update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
|
测试
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
105
106
| @RunWith(JMockit.class)
public class IDGeneratorUtilTest {
private static final Logger logger = LoggerFactory.getLogger(IDGeneratorUtilTest.class);
private static final int MAX_TIMES = 2000000;
private static final int PRINT_TIMES = 100;
@Tested
private IDGeneratorService idGeneratorUtil;
@Injectable
private AccountServerIdMapper accountServerIdMapper;
@Test
public void testOneServerIdGenerate() {
new Expectations() {
{
accountServerIdMapper.nextId((AccountServerId) any);
result = 2;
}
};
idGeneratorUtil.init();
Set<Long> ids = new HashSet<>();
long start = System.currentTimeMillis();
for (int i = 0; i < MAX_TIMES; i++) {
long id = idGeneratorUtil.tryNextId();
if (ids.contains(id)) {
System.out.println(id);
}
ids.add(id);
}
logger.debug((System.currentTimeMillis() - start) + " 毫秒内生成 " + ids.size() + " 个ID");
Assert.assertEquals(ids.size(), MAX_TIMES);
Object[] idArray = ids.toArray();
for (int i = 0; i < PRINT_TIMES; i++) {
logger.debug(idArray[i] + " : " + Long.toBinaryString((Long) idArray[i]));
}
}
@Test
public void testMutilServerIdGenerate() {
new Expectations() {
{
accountServerIdMapper.nextId((AccountServerId) any);
result = 2;
}
};
idGeneratorUtil.init();
Runnable runnable = () -> {
Set<Long> ids = new HashSet<>();
long start = System.currentTimeMillis();
for (int i = 0; i < MAX_TIMES; i++) {
long id = idGeneratorUtil.tryNextId();
ids.add(id);
}
logger.debug((System.currentTimeMillis() - start) + " 毫秒内生成 " + ids.size() + " 个ID");
Assert.assertEquals(ids.size(), MAX_TIMES);
};
List<Thread> list = new ArrayList<>();
int cpus = Runtime.getRuntime().availableProcessors() + 2;
logger.debug("CPU : " + cpus);
for (int i = 0; i < cpus; i++) {
Thread thread = new Thread(runnable);
list.add(thread);
thread.start();
}
for (Thread thread : list) {
try {
thread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
|
