A)

網(wǎng)絡(luò)上現(xiàn)在有很多的分布式ID生成算法, 各大廠商也開源了自己的分布式id生成算法. 前段時(shí)間項(xiàng)目里有個(gè)生成唯一id的需求, 思考了一下, 將flick的id生成方案和Twitter的id生成算法結(jié)合到一起, 寫了個(gè)小算法, 也算是站在巨人的肩膀上做了點(diǎn)小東西, lol

B)

原理大致是這樣的, 利用mysql insert來(lái)計(jì)算出集群中某個(gè)節(jié)點(diǎn)處于集群中的位置, 算出serverId, 然后利用雪花算法在該id上生成分布式id.

目前的實(shí)現(xiàn)是采用long來(lái)進(jìn)行存儲(chǔ)的, 因此只能在生成時(shí)間維度, 節(jié)點(diǎn)數(shù)量, 和每毫秒內(nèi)生成的數(shù)量上進(jìn)行調(diào)節(jié), 如果你們可以存儲(chǔ)字符串的話, 那么可以拓展一下該算法, 加大時(shí)間和空間的容量.

C)

算法實(shí)現(xiàn)

/**
 * ID 生成器
 * <p>
 * 整個(gè)ID算法很簡(jiǎn)單,
 * 1. 參考Flickr ID生成算法, 使用MYSQL獲得一個(gè)自增ID, 然后對(duì)ID取模, 算出一個(gè)服務(wù)器ID
 * 2. 參考Twitter的雪花算法, 算出一個(gè)long型ID
 * <p>
 * 該算法保證在30年內(nèi), 6萬(wàn)臺(tái)機(jī)器, 單機(jī)每秒可以產(chǎn)出128, 000個(gè)不重復(fù)ID
 * <p>
 * <p>
 * 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;
 * <p>
 * <p>
 * |1, 000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0000, 0 |000, 0000, 0000, 0000, 0 |000, 0000           |
 * | |                   時(shí)間戳(40位)                                |   服務(wù)器ID(16位)         | 單個(gè)時(shí)間戳內(nèi)的Id(7位) |
 */
@Service
public class IDGeneratorService implements CommandLineRunner {

    private static final Logger LOG = LoggerFactory.getLogger(IDGeneratorService.class);

    // 時(shí)間戳從哪一年開始計(jì)時(shí)
    private static final int START_YEAR = 2018;

    // 時(shí)間取40位, 保證ID34年內(nèi)不會(huì)重復(fù)
    private static final int timeBitsSize = 40;
    private static final int serverIdBitsSize = 16;
    private static final int countBitsSize = 7;

    private long maxIdPerMill;

    // 時(shí)間開始時(shí)間戳, 相當(dāng)于System.currentTimeMillis()的1970年
    private long startDateTime;
    // 服務(wù)器ID表示位, 在集群中表示一個(gè)節(jié)點(diǎn)
    private long serverIdBits;
    // 單機(jī)中, 某個(gè)時(shí)刻生長(zhǎng)得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. 計(jì)算出開始生成ID的起始時(shí)間戳
        LocalDateTime start = LocalDateTime.of(START_YEAR, 1, 1, 0, 0);
        startDateTime = start.toInstant(ZoneOffset.of("+8")).toEpochMilli();

        // 2. 算出支持最大年限的時(shí)間
        maxTime = ((Double) Math.pow(2, timeBitsSize)).longValue();

        // 3. 算出每毫秒能產(chǎn)出多少ID
        maxIdPerMill = ((Double) Math.pow(2, countBitsSize)).longValue();

        /**
         * 4. 根據(jù)Mysql自增ID取模, 算出每個(gè)服務(wù)器ID, 在生產(chǎn)環(huán)境中, 應(yīng)該保證服務(wù)器數(shù)量是該值的一半, 如此一來(lái)就可以避免, 服務(wù)器集群整體
         * 重啟時(shí), 不會(huì)拿到與重啟之前的服務(wù)器相同的Id
         * 這個(gè)值的計(jì)算是為了適應(yīng)這種場(chǎng)景, 在服務(wù)器灰度上線的時(shí)候, 有可能是原來(lái)的服務(wù)器還沒有關(guān)閉, 但是新的服務(wù)器已經(jīng)起來(lái)了, 此時(shí)會(huì)有倆套
         * 服務(wù)器同時(shí)在處理業(yè)務(wù)邏輯, 那么它們就有可能拿到一樣的服務(wù)器ID, 從而導(dǎo)致產(chǎn)生一樣的ID號(hào)
         */
        long serverSize = ((Double) Math.pow(2, serverIdBitsSize)).longValue();

        AccountServerId accountServerId = new AccountServerId();
        accountServerIdMapper.nextId(accountServerId);
        long serverId = (int) (accountServerId.getId() % serverSize);

        /**
         * 5. 算出每個(gè)服務(wù)器ID在long類型中的數(shù)據(jù)位置, 然后緩存起來(lái)
         */
        serverIdBits = (serverId << (countBitsSize));

        LOG.info("[ID生成器] 開始時(shí)間:{}, 時(shí)間戳:{} ", new Date(startDateTime), startDateTime);
        LOG.info("[ID生成器] 結(jié)束時(shí)間:{}, 時(shí)間戳:{} ", new Date(startDateTime + maxTime), maxTime);
        LOG.info("[ID生成器] 每毫秒生成最大ID數(shù):{} ", maxIdPerMill);
        LOG.info("[ID生成器] 當(dāng)前serverId: {}, serverIdSize:{}", serverId, serverSize);
        LOG.info("[ID生成器] serverIdBits: {}", Long.toBinaryString(serverIdBits));
    }

    /**
     * 生成一個(gè)64位的GUID
     * <p>
     * 在next()方法中, 沒有使用任何的對(duì)象, 如此一來(lái)就可以減輕GC的壓力.
     *
     * @return
     */
    public long next() {

        synchronized (lock) {
            long curTime = System.currentTimeMillis() - startDateTime;
            if (curTime >= maxTime) {
                LOG.error("[ID生成器] 超過負(fù)載, {}, {}芬失！返回 -1", curTime, maxTime);
                return -1;
            }

            if (lastGenerateTime != curTime) {
                currentID = 0;
            } else {

                if (currentID >= maxIdPerMill) {
                    LOG.error("[ID生成器] 同一毫秒[" + curTime + "]內(nèi)生成" + currentID + "個(gè)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, 可能超過每毫秒內(nèi)生成最大數(shù)量, 等待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 '創(chuàng)建時(shí)間',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新時(shí)間',
  PRIMARY KEY (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

測(cè)試

@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 毫秒內(nèi)生成 2000000 個(gè)ID
     * <p>
     * 單線程的情況下, 在MacBook Pro上是每毫秒鐘生成 97 個(gè)id
     */
    @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) + " 毫秒內(nèi)生成 " + ids.size() + " 個(gè)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 毫秒內(nèi)生成 2000000 個(gè)ID
     * 208031 [Thread-3] DEBUG c.f.l.service.IDGeneratorUtilTest - 207465 毫秒內(nèi)生成 2000000 個(gè)ID
     * 208626 [Thread-10] DEBUG c.f.l.service.IDGeneratorUtilTest - 208059 毫秒內(nèi)生成 2000000 個(gè)ID
     * 208630 [Thread-9] DEBUG c.f.l.service.IDGeneratorUtilTest - 208063 毫秒內(nèi)生成 2000000 個(gè)ID
     * 209153 [Thread-6] DEBUG c.f.l.service.IDGeneratorUtilTest - 208586 毫秒內(nèi)生成 2000000 個(gè)ID
     * 209170 [Thread-5] DEBUG c.f.l.service.IDGeneratorUtilTest - 208603 毫秒內(nèi)生成 2000000 個(gè)ID
     * 209373 [Thread-2] DEBUG c.f.l.service.IDGeneratorUtilTest - 208807 毫秒內(nèi)生成 2000000 個(gè)ID
     * 209412 [Thread-1] DEBUG c.f.l.service.IDGeneratorUtilTest - 208846 毫秒內(nèi)生成 2000000 個(gè)ID
     * 209508 [Thread-4] DEBUG c.f.l.service.IDGeneratorUtilTest - 208941 毫秒內(nèi)生成 2000000 個(gè)ID
     * 209536 [Thread-8] DEBUG c.f.l.service.IDGeneratorUtilTest - 208969 毫秒內(nèi)生成 2000000 個(gè)ID
     * <p>
     * 多線程的情況下, 在MacBook Pro上是每毫秒鐘生成 9 個(gè)id, 可見由于鎖的競(jìng)爭(zhēng), 產(chǎn)生的影響還是非常大的
     */
    @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) + " 毫秒內(nèi)生成 " + ids.size() + " 個(gè)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();
            }
        }

    }
}