面试题: 集群高并发情况下如何保证分布式唯一全局ID生成?
1、问题 1.1、为什么需要分布式全局唯一ID以及分布式ID的业务需求 在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。
如在美团点评的金融、支付、餐饮、酒店;
猫眼电影等产品的系统中数据日渐增长,对数据分库分表后需要有一个唯一ID来表示一条数据或者消息。
特别一点的如订单、骑手、优惠劵也都需要一个唯一ID做为标识。
此时一个能生成唯一ID的系统是非常必要的 。
1.2、ID生成规则部分硬性要求 既然是唯一标识,那么全局唯一是最基本的要求 。
在MySQL的InnoDB引擎中使用的是聚集索引,由于多数RDBMS使用Btree的数据结构来存储索引数据,在主键的选择上面我们应该尽量使用有序的主键来保证写入性能。
保证下一个ID一定大于上一个ID,例如事务版本号、IM增量消息、排序等特殊需求。
如果ID是连续的,那么恶意用户的扒取工作就非常容易做了,直接按照顺序下载指定URL即可;
如果是订单号那么更加危险,竞争对手可以知道我们一天的单量。
所以在一些应用场景下,需要ID无规则不规则,让竞争对手不好猜。
这样就能在开发中快速了解这个分布式ID的生成时间。
1.3、ID生成系统的可用性要求 发一个获取分布式ID的请求,服务器就要保证99.999%的情况下给我创建一个唯一分布式ID
发一个获取分布式ID的请求,服务器就要快,极速
假如并发一口气10万个创建分布式ID请求同时过来,服务器需要顶得住且成功创建10万个分布式ID
2、一般通用方案 2.1、UUID 1 2 3 4 public static void main (String[] args) { String uuid = UUID.randomUUID().toString(); System.out.println(uuid); }
如果只是考虑唯一性,那么UUID基本可以满足需求。
1 无序,无法预测他的生成顺序,不能生成递增有序的数字
2 主键,ID作为主键时在特定的环境下会存在一些问题,比如做DB主键的场景下,UUID非常不适用,MySQL官方有明确的建议主键要尽量越短越好,36位的UUID不合要求。
3 索引,会导致B+树索引的分裂。
2.2、数据库自增主键 在高并发集群上此策略不可用。
2.3、基于Redis生成全局ID策略 因为Redis是单线程,天生保证原子性,所以可以使用INCR和INCRBY来实现。 集群分布式 在Redis集群下,同样和MySQL一样需要设置不同的增长步数 ,同时key需要设置有效期。
可以使用Redis集群来获取更高的吞吐量。
假如一个集群中有五个Redis,那么初始化每台Redis步长分别是1,2,3,4,5,然后步长都是5。
3、snowflake 3.1、概述 1 推特的雪花算法生成ID能够按照时间有序生成。
2 雪花算法生成ID的结果是一个64bit大小的整数,为一个Long型(转换为字符串后长度最多19)
3 分布式系统内不会产生ID碰撞(由datecenter和workerId作区分),并且效率较高。
分布式系统中,有一些需要使用全局唯一ID的场景,生成ID的基本需求 1 分布式环境下必须全局且唯一。
2 一般都需要单调递增,因为一般唯一ID都会存到数据库,而lnnodb的特性就是将内容存储在主键索引树上的叶子节点,而且是从左往右,递增的,所以考虑到数据库性能,一般生成的id也最好是单调递增。为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID般是无序的。
3 可能还会需要无规则,因为如果使用唯一lD作为订单号这种,为了不然别人知道一天的订单量是多少,就需要这个规则。
3.2、结构 雪花算法的几个核心组成部分
号段解析
雪花算法可以保证
所有生成的id按时间趋势递增 整个分布式内不会产生重复id,因为有datacenterId和workerId来做区分。 3.3、源码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 public class SnowFlake { private final static long START_STMP = 1480166465631L ; private final static long SEQUENCE_BIT = 12 ; private final static long MACHINE_BIT = 5 ; private final static long DATACENTER_BIT = 5 ; private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT); private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); private final static long MACHINE_LEFT = SEQUENCE_BIT; private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT; private long datacenterId; private long machineId; private long sequence = 0L ; private long lastStmp = -1L ; public SnowFlake (long datacenterId, long machineId) { if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0 ) { throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0" ); } if (machineId > MAX_MACHINE_NUM || machineId < 0 ) { throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0" ); } this .datacenterId = datacenterId; this .machineId = machineId; } public synchronized long nextId () { long currStmp = getNewstmp(); if (currStmp < lastStmp) { throw new RuntimeException("Clock moved backwards. Refusing to generate id" ); } if (currStmp == lastStmp) { sequence = (sequence + 1 ) & MAX_SEQUENCE; if (sequence == 0L ) { currStmp = getNextMill(); } } else { sequence = 0L ; } lastStmp = currStmp; return (currStmp - START_STMP) << TIMESTMP_LEFT | datacenterId << DATACENTER_LEFT | machineId << MACHINE_LEFT | sequence; } private long getNextMill () { long mill = getNewstmp(); while (mill <= lastStmp) { mill = getNewstmp(); } return mill; } private long getNewstmp () { return System.currentTimeMillis(); } public static void main (String[] args) { SnowFlake snowFlake = new SnowFlake(2 , 3 ); for (int i = 0 ; i < (1 << 12 ); i++) { System.out.println(snowFlake.nextId()); } } }
测试,使用雪花算法生成id
构造SnowFlake对象,构造方法中传入一个datacenterId和workerId 使用SnowFlake对象的nextId方法生成唯一Id 1 2 3 4 5 6 7 8 SnowFlake snowFlake = new SnowFlake(1 ,1 ); for (int i = 0 ; i < 10 ; i++) { long id = snowFlake.nextId(); System.out.println("id:" + id + "\t" + String.valueOf(id).length() + "位" ); System.out.println("------------------------------------------" ); }
3.4、Spring Boot整合雪花算法 引入hutool-all ,maven依赖引入如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 <dependencies > <dependency > <groupId > cn.hutool</groupId > <artifactId > hutool-all</artifactId > <version > 5.4.2</version > </dependency > <dependency > <groupId > org.springframework.boot</groupId > <artifactId > spring-boot-starter-web</artifactId > <version > 2.2.1.RELEASE</version > </dependency > <dependency > <groupId > org.projectlombok</groupId > <artifactId > lombok</artifactId > <version > 1.18.16</version > </dependency > </dependencies >
使用SnowFlake对象的nextId方法即可生成唯一ID
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 @Configuration public class SnowFlakeConfig { @Value("${application.datacenterId}") private Long datacenterId; @Value("${application.workerId}") private Long workerId; @Bean public Snowflake snowflake () { return new Snowflake(workerId,datacenterId); } }
1 2 3 4 5 application: datacenterId: 2 workerId: 1 server: port: 7777
1 2 3 4 5 6 7 8 9 @Service public class OrderService { @Autowired private Snowflake snowflake; public String getIdBySnowFlake () { return String.valueOf(snowflake.nextId()); } }
1 2 3 4 5 6 7 8 9 10 @RestController public class OrderController { @Autowired private OrderService orderService; @RequestMapping("/snowflake") public String index () { return orderService.getIdBySnowFlake(); } }
3.4、优点 毫秒数在高位,自增序列在低位,整个ID都是趋势递增的 不依赖数据库、redis等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。 可以根据自身业务分配bit位,非常灵活。 3.5、缺点 依赖机器时钟,如果机器时钟回退,会导致重复ID生成 在单机上是递增的,但是由于设计到分布式环境,每台机器上的时钟不可能完全同步,有时候会出现不是全局递增的情况。(此缺点可以认为芜锁胃,一般分布式ID只要求趋势递增,并不会严格要求递增,90%的需求都只需要趋势递增) 4、其他补充 雪花算法的改进方案:
百度开源的分布式唯一ID生成器UidGenerator Leaf–美团点评分布式ID生成系统