全局唯一的 ID 几乎是所有系统都会遇到的刚需。这个 id 在搜索, 存储数据, 加快检索速度 等等很多方面都有着重要的意义。工业上有多种策略来获取这个全局唯一的id,针对常见的几种场景,我在这里进行简单的总结和对比。

多种ID生成方式


1. UUID

算法的核心思想是结合机器的网卡、当地时间、一个随记数来生成UUID。

  • 优点:本地生成,性能好,没有高可用风险;
  • 缺点:长度过长,且无序

2. 数据库sequence

使用数据库的id自增策略,如MySQL的auto_increment。并且可以使用两台数据库分别设置不同步长,生成不重复ID的策略来实现高可用。

  • 优点:数据库生成的ID绝对有序,高可用实现方式简单。
  • 缺点:需要独立部署数据库实例,成本高,有性能瓶颈

3.雪花算法

twitter生成全局ID生成器的算法策略。

简单来说:就是把64的Long型数据由以下几个部分组成:
符号位(1位)-时间戳(41位)-数据中心标识(5位)-ID生成器实例标识(5位)-序列号(12位)
通过部署多个ID生成器,位各个业务系统生成全局唯一的Long型ID。

  • 优点:生成Long型易操作,有序
  • 缺点:需要独立部署id生成器,增加维护成本

雪花算法实现代码

package com.example.demo.function;


import java.lang.management.ManagementFactory;
import java.net.InetAddress;
import java.net.NetworkInterface;


//雪花算法代码实现
public class SnowflakeIdGenerator {
    // 时间起始标记点,作为基准,一般取系统的最近时间(一旦确定不能变动)
    private final static long twepoch = 1288834974657L;
    // 机器标识位数
    private final static long workerIdBits = 5L;
    // 数据中心标识位数
    private final static long datacenterIdBits = 5L;
    // 机器ID最大值
    private final static long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 数据中心ID最大值
    private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    // 毫秒内自增位
    private final static long sequenceBits = 12L;
    // 机器ID偏左移12位
    private final static long workerIdShift = sequenceBits;
    // 数据中心ID左移17位
    private final static long datacenterIdShift = sequenceBits + workerIdBits;
    // 时间毫秒左移22位
    private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
    /* 上次生产id时间戳 */
    private static long lastTimestamp = -1L;
    // 0,并发控制
    private long sequence = 0L;

    private final long workerId;
    // 数据标识id部分
    private final long datacenterId;

    public SnowflakeIdGenerator(){
        this.datacenterId = getDatacenterId(maxDatacenterId);
        this.workerId = getMaxWorkerId(datacenterId, maxWorkerId);
    }
    /**
     * @param workerId
     *            工作机器ID
     * @param datacenterId
     *            序列号
     */
    public SnowflakeIdGenerator(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
    /**
     * 获取下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        if (lastTimestamp == timestamp) {
            // 当前毫秒内,则+1
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                // 当前毫秒内计数满了,则等待下一秒
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        // ID偏移组合生成最终的ID,并返回ID
        long nextId = ((timestamp - twepoch) << timestampLeftShift)
                | (datacenterId << datacenterIdShift)
                | (workerId << workerIdShift) | sequence;

        return nextId;
    }

    private long tilNextMillis(final long lastTimestamp) {
        long timestamp = this.timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = this.timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     * <p>
     * 获取 maxWorkerId
     * </p>
     */
    protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {
        StringBuffer mpid = new StringBuffer();
        mpid.append(datacenterId);
        String name = ManagementFactory.getRuntimeMXBean().getName();
        if (!name.isEmpty()) {
            /*
             * GET jvmPid
             */
            mpid.append(name.split("@")[0]);
        }
        /*
         * MAC + PID 的 hashcode 获取16个低位
         */
        return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
    }

    /**
     * <p>
     * 数据标识id部分
     * </p>
     */
    protected static long getDatacenterId(long maxDatacenterId) {
        long id = 0L;
        try {
            InetAddress ip = InetAddress.getLocalHost();
            NetworkInterface network = NetworkInterface.getByInetAddress(ip);
            if (network == null) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                id = ((0x000000FF & (long) mac[mac.length - 1])
                        | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
                id = id % (maxDatacenterId + 1);
            }
        } catch (Exception e) {
            System.out.println(" getDatacenterId: " + e.getMessage());
        }
        return id;
    }

     public static void main(String[] args) {
        SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(0, 0);
        for (int i = 0; i < 100; i++) {
            long id = idWorker.nextId();
            //System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

4.MongoDB ObjectId

生成策略类似雪花算法。

时间戳+机器ID+进程ID+序列号=>ObjectId对象

  • 优点:本地生成,有序,成本低
  • 缺点:使用机器ID和进程ID,64位Long无法存储,只能生成特殊ObjectId对象。

总结对比

方式优点缺点
UUID本地生成,无中心,无性能瓶颈无序,过长
MongoDB ObjectId本地生成,含时间戳,有序过长
数据库sequence有序中心生成,独立部署数据库
雪花算法有序,Long型中心生成,独立部署ID生成器

大致的总结优略点如下:

方式优点缺点
UUID本地生成,无中心,无性能瓶颈无序,过长
MongoDB ObjectId本地生成,含时间戳,有序过长
数据库sequence有序中心生成,独立部署数据库
雪花算法有序,Long型中心生成,独立部署ID生成器

想要的

看了以上,我想要的ID生成策略是怎样的呢?
64位易操作存储,按时间有序,无中心本地生成。
好吧,其实本文也没有完全实现以上需求,如果哪位小伙伴有更好方案欢迎回复分享!!!
本文只是基于对以上几种方案的认识,稍加改进,尽可能的满足需求!

来吧


我的想法:

使用Long型,不可避免参考雪花算法的实现,但是要实现本地化生成,要参考ObjectId的生成策略,使用类似机器ID,进程ID来保证唯一性。

如何解决使用机器ID,进程ID时导致ID过长的问题?

解决方式:放弃使用机器ID,进程ID,使用serverId标识服务,使用instanceId标识服务进程,但是。。。没办法,需要一个中心来进行注册,保证唯一性,本例中使用Redis(不限于redis,database,memcached都可)。

  • 相对于使用独立部署的ID生成器,我想Redis之类的缓存集群是各个分布式系统架构中都会存在的,这样可以显著降低架构复杂度,降低成本。
  • 对redis的依赖较低,可以说只需要启动的时候访问redis即可,后续本地生成ID。
  • 另外serverId是固定不变的,是可以预先分配好的,比如会员中心微服务的serverId分配为10,这是固定不变的。

 

package com.example.demo.function;

import redis.clients.jedis.Jedis;
import redis.clients.jedis.exceptions.JedisException;

import java.net.Inet4Address;
import java.net.InetAddress;
import java.util.Random;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;
import java.util.logging.Logger;

public class IdGenerator {

    // 时间基线  2016/1/1
    private final long timeBaseLine = 1454315864414L;

    // 服务编号
    private volatile long serverId = -1;

    //服务实例编号
    private volatile long instanceId = -1;

    private volatile boolean inited = false;

    // 序列号
    private long sequence;

    private static final String ID_CREATOR_KEY = "ID_CREATOR";
    private static final String KEY_SEP = ":";

    //    private static final long timeBits = 41;
    private static final long serverIdBits = 7;
    private static final long instanceIdBits = 10;
    private static final long sequenceBits = 5;

    private static final long maxServerId = ~(-1L << serverIdBits);
    private static final long maxInstanceId = ~(-1L << instanceIdBits);
    private static final long maxSequence = ~(-1L << sequenceBits);


    private static final long timeBitsShift = serverIdBits + instanceIdBits + sequenceBits;
    private static final long serverIdBitsShift = instanceIdBits + sequenceBits;
    private static final long instanceIdBitsShift = sequenceBits;


    private long lastTimestamp = -1L;
    private static final Random r = new Random();

    private static IdGenerator idGenerator = new IdGenerator();

    private IdGenerator() {
    }


    public static IdGenerator getInstance() {
        return idGenerator;
    }

    /**
     * 应用启动完成后调用init
     *
     * @param serverId
     */
    public synchronized void init(long serverId) {
        if (serverId > maxServerId || serverId < 0) {
            throw new IllegalArgumentException("serveriId最小值为: 0,最大值为: " + maxServerId);
        }

        this.serverId = serverId;
        if (!inited) {
            inited = true;
            Jedis jedis = new Jedis("localhost", 6379);
            ScheduledExecutorService scheduledService = Executors.newScheduledThreadPool(1);
            RegisterIdCreatorInstanceTask registerIdCreatorInstanceTask = new RegisterIdCreatorInstanceTask(jedis);
            // 定义定时任务,定期调用redis注册,续约instanceId
            scheduledService.scheduleWithFixedDelay(registerIdCreatorInstanceTask, 0, RegisterIdCreatorInstanceTask.INTERVAL_SECONDS, TimeUnit.SECONDS);
        } else {
            System.out.println("已经初始化!");
        }
    }


    /**
     * 注册id生成器实例
     */
    private class RegisterIdCreatorInstanceTask implements Runnable {
        private Logger logger = Logger.getLogger(RegisterIdCreatorInstanceTask.class.getCanonicalName());

        public static final int INTERVAL_SECONDS = 30;

        private Jedis jedis;

        private RegisterIdCreatorInstanceTask(Jedis jedis) {
            this.jedis = jedis;
        }

        public void run() {

            try {

                long srvId = idGenerator.getServerId();
                long currentInstanceId = idGenerator.getInstanceId();

                String prefixKey = ID_CREATOR_KEY + KEY_SEP + srvId + KEY_SEP;

                if (currentInstanceId < 0) {
                    //注册
                    registerInstanceIdWithIpv4();
                } else {
                    //续约
                    String result = jedis.set(prefixKey + currentInstanceId, srvId + KEY_SEP + currentInstanceId, "XX", "EX", INTERVAL_SECONDS * 3);
                    if (!"OK".equals(result)) {
                        logger.warning("服务[" + srvId + "]ID生成器:" + currentInstanceId + "续约失败,等待重新注册");
                        registerInstanceIdWithIpv4();
                    } else {
                        logger.info("服务[" + srvId + "]ID生成器:" + currentInstanceId + "续约成功");
                    }

                }

            } catch (JedisException e) {
                logger.severe("Redis 出现异常!");
                e.printStackTrace();
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                if (idGenerator.getInstanceId() < 0) {
                    idGenerator.setInited(false);
                }
                if (jedis != null) {
                    jedis.close();
                }
            }
        }

        private int registerInstanceIdWithIpv4() {
            long ip4Value = getIp4LongValue();
            // Redis key 格式:key->val , ID_CREATOR:serverId:instanceId -> serverId:instanceId
            String prefixKey = ID_CREATOR_KEY + KEY_SEP + serverId + KEY_SEP;

            // 需要使用java8
            int regInstanceId = registerInstanceId((int) (ip4Value % (maxInstanceId + 1)), (int) maxInstanceId, (v) -> {
                String res = jedis.set(prefixKey + v, serverId + KEY_SEP + v, "NX", "EX", INTERVAL_SECONDS * 3);
                return "OK".equals(res) ? v : -1;
            });

            idGenerator.setInstanceId(regInstanceId);
            idGenerator.setInited(true);

            logger.info("服务[" + serverId + "]注册了一个ID生成器:" + regInstanceId);
            return regInstanceId;
        }


        /**
         * 注册instance,成功就返回
         *
         * @param basePoint
         * @param max
         * @param action
         * @return
         */
        public int registerInstanceId(int basePoint, int max, Function<Integer, Integer> action) {
            int result;
            for (int i = basePoint; i <= max; i++) {
                result = action.apply(i);
                if (result > -1) {
                    return result;
                }
            }

            for (int i = 0; i < basePoint; i++) {
                result = action.apply(i);
                if (result > -1) {
                    return result;
                }
            }
            return 0;
        }

        /**
         * IPV4地址转Long
         *
         * @return
         */
        private long getIp4LongValue() {
            try {
                InetAddress inetAddress = Inet4Address.getLocalHost();
                byte[] ip = inetAddress.getAddress();

                return Math.abs((ip[0] << 24)
                        | (ip[1] << 16)
                        | (ip[2] << 8)
                        | ip[3]);

            } catch (Exception ex) {
                ex.printStackTrace();
                return 0;
            }
        }
    }


    /**
     * 获取ID
     *
     * @return
     */
    public long getId() {
        long id = nextId();
        return id;
    }

    private synchronized long nextId() {
        if (serverId < 0 || instanceId < 0) {
            throw new IllegalArgumentException("目前不能生成唯一性ID,serverId:[" + serverId + "],instanceId:[" + instanceId + "]!");
        }

        long timestamp = currentTime();
        if (timestamp < lastTimestamp) {
            throw new IllegalStateException("Err clock");
        }
        sequence = (sequence + 1) & maxSequence;
        if (lastTimestamp == timestamp) {
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        lastTimestamp = timestamp;

        long id = ((timestamp - timeBaseLine) << timeBitsShift)
                | (serverId << serverIdBitsShift)
                | (instanceId << instanceIdBitsShift)
                | sequence;
        return id;
    }

    /**
     * get the timestamp (millis second) of id
     *
     * @param id the nextId
     * @return the timestamp of id
     */
    public long getIdTimestamp(long id) {
        return timeBaseLine + (id >> timeBitsShift);
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = currentTime();
        while (timestamp <= lastTimestamp) {
            timestamp = currentTime();
        }
        return timestamp;
    }

    private long currentTime() {
        return System.currentTimeMillis();
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("IdCreator{");
        sb.append("serverId=").append(serverId);
        sb.append(",instanceId=").append(instanceId);
        sb.append(", timeBaseLine=").append(timeBaseLine);
        sb.append(", lastTimestamp=").append(lastTimestamp);
        sb.append(", sequence=").append(sequence);
        sb.append('}');
        return sb.toString();
    }


    public long getServerId() {
        return serverId;
    }

    private void setServerId(long serverId) {
        this.serverId = serverId;
    }

    public long getInstanceId() {
        return instanceId;
    }


    private void setInstanceId(long instanceId) {
        this.instanceId = instanceId;
    }

    public boolean isInited() {
        return inited;
    }

    private void setInited(boolean inited) {
        this.inited = inited;
    }

}

源码 地址:https://github.com/darren-fu/IdGenerator

 

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐