高同時無ロック無IO待機分散ID生成スキーム
ネットワーク上には現在多くの分布式ID生成アルゴリズムがあり、各メーカーも独自の分布式id生成アルゴリズムをオープンソースしている.この間のプロジェクトで唯一のidを生成する需要があったので、考えてみましたが、flickのid生成案とTwitterのid生成アルゴリズムを組み合わせて、小さなアルゴリズムを書いて、巨人の肩に立って小さなものを作ったということです.lol
B)
原理は概ね、mysql insertを用いるクラスタ内のあるノードがクラスタ内にある位置を算出し、serverIdを算出し、そのid上に雪花アルゴリズムを用いて分布式idを生成する.
現在の実装ではlongを用いて記憶するため、生成時間次元、ノード数、ミリ秒当たりの生成数のみを調整することができ、文字列を記憶できれば、このアルゴリズムを拡張し、時間と空間の容量を増やすことができる.
C)
アルゴリズム実装
/**
* ID
*
* ID ,
* 1. Flickr ID , MYSQL ID, ID , ID
* 2. Twitter , long ID
*
* 30 , 6 , 128, 000 ID
*
*
* CREATE TABLE `account_server_id` (
* `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
* `stub` char(1) DEFAULT NULL,
* PRIMARY KEY (`id`),
* UNIQUE KEY `stub` (`stub`)
* ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;
*
*
* |1, 000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0 |000, 0000, 0000, 0000, 0 |000, 0000 |
* | | (40 ) | ID(16 ) | Id(7 ) |
*/
@Service
public class IDGeneratorService implements CommandLineRunner {
private static final Logger LOG = LoggerFactory.getLogger(IDGeneratorService.class);
//
private static final int START_YEAR = 2018;
// 40 , ID34
private static final int timeBitsSize = 40;
private static final int serverIdBitsSize = 16;
private static final int countBitsSize = 7;
private long maxIdPerMill;
// , System.currentTimeMillis() 1970
private long startDateTime;
// ID ,
private long serverIdBits;
// , id
private long currentID;
private long maxTime;
private long lastGenerateTime = System.currentTimeMillis();
private Object lock = new Object();
@Resource
private AccountServerIdMapper accountServerIdMapper;
public void init() {
// 1. ID
LocalDateTime start = LocalDateTime.of(START_YEAR, 1, 1, 0, 0);
startDateTime = start.toInstant(ZoneOffset.of("+8")).toEpochMilli();
// 2.
maxTime = ((Double) Math.pow(2, timeBitsSize)).longValue();
// 3. ID
maxIdPerMill = ((Double) Math.pow(2, countBitsSize)).longValue();
/**
* 4. Mysql ID , ID, , , ,
* , Id
* , , , ,
* , ID, ID
*/
long serverSize = ((Double) Math.pow(2, serverIdBitsSize)).longValue();
AccountServerId accountServerId = new AccountServerId();
accountServerIdMapper.nextId(accountServerId);
long serverId = (int) (accountServerId.getId() % serverSize);
/**
* 5. ID long ,
*/
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));
}
/**
* 64 GUID
*
* next() , , GC .
*
* @return
*/
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 {
// LOG.error("[ID ] ID -1, , 1 ");
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
@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
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;
テスト
@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;
/**
* 21026 [main] DEBUG c.f.l.service.IDGeneratorUtilTest - 20506 2000000 ID
*
* , MacBook Pro 97 id
*/
@Test
public void testOneServerIdGenerate() {
new Expectations() {
{
accountServerIdMapper.nextId((AccountServerId) any);
result = 2;
}
};
idGeneratorUtil.init();
Set 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]));
}
}
/**
* 207703 [Thread-7] DEBUG c.f.l.service.IDGeneratorUtilTest - 207136 2000000 ID
* 208031 [Thread-3] DEBUG c.f.l.service.IDGeneratorUtilTest - 207465 2000000 ID
* 208626 [Thread-10] DEBUG c.f.l.service.IDGeneratorUtilTest - 208059 2000000 ID
* 208630 [Thread-9] DEBUG c.f.l.service.IDGeneratorUtilTest - 208063 2000000 ID
* 209153 [Thread-6] DEBUG c.f.l.service.IDGeneratorUtilTest - 208586 2000000 ID
* 209170 [Thread-5] DEBUG c.f.l.service.IDGeneratorUtilTest - 208603 2000000 ID
* 209373 [Thread-2] DEBUG c.f.l.service.IDGeneratorUtilTest - 208807 2000000 ID
* 209412 [Thread-1] DEBUG c.f.l.service.IDGeneratorUtilTest - 208846 2000000 ID
* 209508 [Thread-4] DEBUG c.f.l.service.IDGeneratorUtilTest - 208941 2000000 ID
* 209536 [Thread-8] DEBUG c.f.l.service.IDGeneratorUtilTest - 208969 2000000 ID
*
* , MacBook Pro 9 id, ,
*/
@Test
public void testMutilServerIdGenerate() {
new Expectations() {
{
accountServerIdMapper.nextId((AccountServerId) any);
result = 2;
}
};
idGeneratorUtil.init();
Runnable runnable = () -> {
Set 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 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();
}
}
}
}