算法

Js安全的雪花算法降级版

目录
  1. 雪花算法
    1. 优点：
    2. 缺点：
  2. 改版雪花算法基本需求
    1. 实现方案
    2. 优点：
    3. 缺点：

雪花算法

long类型
1位无用 41位毫秒时间戳 10位实例区分 12位自增
41位毫秒可存 (Math.pow(2,41)-1)/24/3600/1000/365 = 69.73057000098301 年
10位实例区分，可表示1024个实例
12个自增位，可表示4096个Id
所以每毫秒最大能生成4194303个id

优点：

  • 每个实例严格递增
  • 不同实例在毫秒级的范围外递增
  • 纯内存生成，性能高

缺点：

  • 时间回拨，id可能会重
  • js最多只支持(Math.pow(2,53)-1)的数值，再大就出问题了，故只能把他当成字符串去处理

改版雪花算法基本需求

  • 还是long类型
  • 取值落在 Number.MAX_SAFE_INTEGER = 2^53 -1 =9007199254740991内
  • 毫秒级范围外递增

　​

实现方案

  • 39位时间戳 17年
  • 14位随机数 16384个id
  • 单记录插入，时间戳+使用随机id，依赖于数据库主键做冲突重试
  • 批量插入，第一条按单条插入的方式生成id，后续的直接自增，保证id自增性，并减少冲突
  • 超过17年，直接升级为正规的雪花算法，让前端改版使用es6的bigint进行支持，支持更多范围id
  • 数据库本身插入是有速度限制的，业务上插入速度几乎更是最多几条，冲突概率还是比较低的

假设1毫秒最多插入n条，那么冲突概率为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
f(1) = 0
f(n) = 1/16384
 + (1-1/16384) * 2/16384
 + (1- ((1-1/16384) * 2/16384)) * 3/16384
 +……
 + (1 - f(n-2)) * (n-2)/16384
 + (1 - f(n-1)) * (n-1)/16384


 function conflictRate(n){
 	if(n.equals(new Decimal(1))){
 		return new Decimal(0);
 	}
 	return new Decimal(1).minus(conflictRate(n.minus(1))).times(n.minus(1)).dividedBy(16384)
 }

每毫秒1000次的话，冲突率为0.057473058323851231054

1
2
3
4
5
6
7
8
conflictRate(new Decimal(1)).toString() // 0
conflictRate(new Decimal(2)).toString() //'0.00006103515625'
conflictRate(new Decimal(3)).toString() //'0.00012206286191940307617'
conflictRate(new Decimal(10)).toString() //'0.00054904829990288953926'
conflictRate(new Decimal(100)).toString() //'0.0060065504357153884835'
conflictRate(new Decimal(1000)).toString() //'0.057473058323851231054'
conflictRate(new Decimal(2000)).toString() //'0.10874704486888446672'
conflictRate(new Decimal(5000)).toString() //'0.23379222465695678157'
  • 为进一步降低冲突概率，同一实例的毫秒内，可以记录以使用的id，在内存内就识别到冲突。
    这样一个实例时间没回拨的化，是不会冲突的，一般小应用只会部署3个实例，假设不是m个实例，冲突概率可能为（m-1）/m*x
  • 正常请求发生冲突，重新发起请求，毫秒数已经不一样了，几乎不会再发生第二次冲突，故请求耗时是可以保证的

优点：

  • 满足大部分业务id生成规则
  • 在js安全数值范围内，前端处理方便

缺点：

  • 依赖于数据库主键冲突
  • 不支持超级高并发