背景

使用雪花算法生成的主鍵，二進(jìn)制表示形式包含4部分，從高位到低位分表為：1bit符號(hào)位、41bit時(shí)間戳位、10bit工作進(jìn)程位（也可以區(qū)分5bit數(shù)據(jù)中心、5bit機(jī)器ID）以及12bit序列號(hào)位。

• 符號(hào)位(1bit)
  預(yù)留的符號(hào)位，恒為零。

• 時(shí)間戳位(41bit)
  41位的時(shí)間戳可以容納的毫秒數(shù)是2的41次方減1，一年所使用的毫秒數(shù)是：365 * 24 * 60 * 60 * 1000。通過計(jì)算可知：
  (Math.pow(2, 41) -1) / (365 * 24 * 60 * 60 * 1000L);
  結(jié)果約等于69年。Sharding-Sphere的雪花算法的時(shí)間紀(jì)元從2016年11月1日零點(diǎn)開始，可以使用到2085年，相信能滿足絕大部分系統(tǒng)的要求。

• 工作進(jìn)程位(10bit)
  該標(biāo)志在Java進(jìn)程內(nèi)是唯一的，如果是分布式應(yīng)用部署應(yīng)保證每個(gè)工作進(jìn)程的id是不同的。該值默認(rèn)為0，可通過調(diào)用靜態(tài)方法DefaultKeyGenerator.setWorkerId(“xxxx”)設(shè)置。

• 序列號(hào)位(12bit)
  該序列是用來在同一個(gè)毫秒內(nèi)生成不同的ID。如果在這個(gè)毫秒內(nèi)生成的數(shù)量超過4096(2的12次方)，那么生成器會(huì)等待到下個(gè)毫秒繼續(xù)生成。

代碼樣例

public final class DefaultKeyGenerator {
    public static final long EPOCH;

    private static final long SEQUENCE_BITS = 12L;

    private static final long WORKER_ID_BITS = 10L;

    private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;

    private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;

    private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;

    private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS;

    private static long workerId;

    private static int maxTolerateTimeDifferenceMilliseconds = 10;

    static {
        //也可指定開始年份
        Calendar calendar = Calendar.getInstance();
        calendar.set(2016, Calendar.NOVEMBER, 1);
        calendar.set(Calendar.HOUR_OF_DAY, 0);
        calendar.set(Calendar.MINUTE, 0);
        calendar.set(Calendar.SECOND, 0);
        calendar.set(Calendar.MILLISECOND, 0);
        EPOCH = calendar.getTimeInMillis();
    }

    private byte sequenceOffset;

    private long sequence;

    private long lastMilliseconds;

    /**
     * Set work process id.
     *
     * @param workerId work process id
     */
    public static void setWorkerId(final long workerId) {
        Preconditions.checkArgument(workerId >= 0L && workerId < WORKER_ID_MAX_VALUE);
        DefaultKeyGenerator.workerId = workerId;
    }

    /**
     * Set max tolerate time difference milliseconds.
     *
     * @param maxTolerateTimeDifferenceMilliseconds max tolerate time difference milliseconds
     */
    public static void setMaxTolerateTimeDifferenceMilliseconds(final int maxTolerateTimeDifferenceMilliseconds) {
        DefaultKeyGenerator.maxTolerateTimeDifferenceMilliseconds = maxTolerateTimeDifferenceMilliseconds;
    }

    /**
     * Generate key.
     *
     * @return key type is @{@link Long}.
     */
    public synchronized Number generateKey() {
        long currentMilliseconds = System.currentTimeMillis();
        if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
            currentMilliseconds = System.currentTimeMillis();
        }
        if (lastMilliseconds == currentMilliseconds) {
            //如果在這個(gè)毫秒內(nèi)生成的數(shù)量超過4096(2的12次方)，那么生成器會(huì)等待到下個(gè)毫秒繼續(xù)生成
            if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
                currentMilliseconds = waitUntilNextTime(currentMilliseconds);
            }
        } else {
            //下面方法的sequence只能為0或1，也可以隨機(jī)一個(gè)值如sequence = RandomUtils.nextLong(0L, 60L) * 60L;
            vibrateSequenceOffset();
            sequence = sequenceOffset;
        }
        lastMilliseconds = currentMilliseconds;
        return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
    }

    @SneakyThrows
    private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {
        if (lastMilliseconds <= currentMilliseconds) {
            return false;
        }
        long timeDifferenceMilliseconds = lastMilliseconds - currentMilliseconds;
        Preconditions.checkState(timeDifferenceMilliseconds < maxTolerateTimeDifferenceMilliseconds,
                "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastMilliseconds, currentMilliseconds);
        Thread.sleep(timeDifferenceMilliseconds);
        return true;
    }

    private long waitUntilNextTime(final long lastTime) {
        long result = System.currentTimeMillis();
        while (result <= lastTime) {
            result = System.currentTimeMillis();
        }
        return result;
    }

    private void vibrateSequenceOffset() {
        sequenceOffset = (byte) (~sequenceOffset & 1);
    }
}

單元測(cè)試

public class KeyGeneratorTest {
    @Test
    public void test() {
        //工作進(jìn)程位10位 取值1-1024 默認(rèn)0
        DefaultKeyGenerator.setWorkerId(1000);
        //時(shí)鐘回?fù)?，最大允許容忍差異毫秒數(shù)，超過這個(gè)時(shí)間將返回異常，默認(rèn)10ms
        DefaultKeyGenerator.setMaxTolerateTimeDifferenceMilliseconds(10);
        DefaultKeyGenerator keyGenerator = new DefaultKeyGenerator();
        for(int i=0;i<1000;i++){
            System.out.println(keyGenerator.generateKey());
        }
    }
}

優(yōu)化

為避免需要手動(dòng)設(shè)置workerId，可通過使用IP地址計(jì)算得出workId

public class IPSectionKeyGenerator {
    private final SnowflakeKeyGenerator snowflakeKeyGenerator = new SnowflakeKeyGenerator();

    static {
        InetAddress address;
        try {
            address = InetAddress.getLocalHost();
        } catch (UnknownHostException var8) {
            throw new IllegalStateException("Cannot get LocalHost InetAddress, please check your network!");
        }

        long workerId = 0L;
        byte[] ipAddressByteArray = address.getAddress();
        int ipLength = ipAddressByteArray.length;
        int count = 0;

        flag:
        switch(ipLength) {
            case 4:
                while(true) {
                    if (count >= ipLength) {
                        break flag;
                    }
                    byte byteNum = ipAddressByteArray[count];
                    workerId += byteNum & 255;
                    ++count;
                }
            case 16:
                while(true) {
                    if (count >= ipLength) {
                        break flag;
                    }
                    byte byteNum = ipAddressByteArray[count];
                    workerId += byteNum & 63;
                    ++count;
                }
            default:
                throw new IllegalStateException("Bad LocalHost InetAddress, please check your network!");
        }
        SnowflakeKeyGenerator.setWorkerId(workerId);
    }

    public long generateKey() {
        return this.snowflakeKeyGenerator.generateKey();
    }
}

總結(jié)

雪花算法是由Twitter公布的分布式主鍵生成算法，它能夠保證不同進(jìn)程主鍵的不重復(fù)性，以及相同進(jìn)程主鍵的有序性。
在同一個(gè)進(jìn)程中，它首先是通過時(shí)間位保證不重復(fù)，如果時(shí)間相同則是通過序列位保證。
同時(shí)由于時(shí)間位是單調(diào)遞增的，且各個(gè)服務(wù)器如果大體做了時(shí)間同步，那么生成的主鍵在分布式環(huán)境可以認(rèn)為是總體有序的。同時(shí)代碼對(duì)于時(shí)鐘回?fù)軉栴}也做了相應(yīng)的處理。