分布式系统唯一性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生成器,增加维护成本

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,这是固定不变的。

大致实现

类似雪花算法的参数

public class IdGenerator {

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

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

    //服务实例编号
    private volatile long instanceId = -1;
    
    private static final long serverIdBits = 7;
    private static final long instanceIdBits = 10;
    private static final long sequenceBits = 5;
    ...
}
  • serverIdBits = 7,最多支持128个服务。
  • instanceIdBits = 10, 每个服务支持1024个实例。
  • sequenceBits = 5,每毫秒可生成的id数量32个(由于本地生成,且时间戳精确到毫秒,同一毫秒内的ID冲突不会像中心那么严重。)

简单流程

服务A请求redis分配instanceId

主要方法:

 /**
     * 应用启动完成后调用init
     *
     * @param serverId
     */
    public synchronized void init(long serverId) {
        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(((0L | ip[0]) << 24)
                        | ((0L | ip[1]) << 16)
                        | ((0L | ip[2]) << 8)
                        | (0L | 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;
    }

如有问题欢迎指正!!

如有其他方案,欢迎回复告知,谢谢!!!

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,214评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,307评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,543评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,221评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,224评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,007评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,313评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,956评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,441评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,925评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,018评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,685评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,234评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,240评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,464评论 1 261
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,467评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,762评论 2 345

推荐阅读更多精彩内容

  • Entrance 数据在分片时,典型的是分库分表,就有一个全局ID生成的问题。 单纯的生成全局ID并不是什么难题,...
    天下无敌强阅读 2,259评论 2 5
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,599评论 18 139
  • 一,题记 所有的业务系统,都有生成ID的需求,如订单id,商品id,文章ID等。这个ID会是数据库中的唯一主键,在...
    架构师小秘圈阅读 4,040评论 1 18
  • 最近在proxy的分库分表,需要给表中的主字段产生一个全局唯一ID,考虑到后期DBA会拿这个ID做索引的,所以产生...
    luomoxyz阅读 3,212评论 0 4
  • 1、当兵后悔两年,不当兵后悔一辈子! 吾思:英雄需要用简短有力的言辞来激励和体现,男子汉一点,做热血的事业,亦可抱...
    LO晨歆VE阅读 256评论 0 1