雪花算法原理以及JS精度丢失问题

简介: 雪花算法原理以及JS精度丢失问题

背景

最近项目上遇到一个改造主键生成策略的问题:需要将原Redis自增id改造成雪花算法。

一个好消息是项目用的ORM框架(Mybatis-Plus)自带雪花算法生成策略,只需在id字段上加上特定的注解。

而问题在于该策略生成id为19位数, 如:1582631966690799617,这样的id返给前端存在精度丢失问题。

当然,一个简单的办法就是将id转化为string类型,但是该业务流程长,涉及范围广,改动地方太多。

所以为了解决这样的问题,我起了改造雪花算法生成策略的心思,也将这次改造过程中的收获分享出来。

在此之前我先给大家介绍一下什么是雪花算法及原理

雪花算法

起源

雪花算法(snowflake)最早是twitter内部使用的分布式下唯一id生成算法

https://github.com/twitter-archive/snowflake

该算法具有以下特性

  • 唯一性:高并发分布式系统中生成id唯一
  • 高性能:每秒可生成百万个id
  • 有序性:生成的id是有序递增的

原理

雪花算法生成的id由64个bit组成,其中41bit填充时间戳,10bit填充工作机器id,12bit作为自增序列号。

Snowflake算法核心

假设时间戳:1666168108422(ms), 转为二进制:11000001111101111010110111011010110000110

工作机器id: 1, 转为二进制:0000000001

序列号:1,转为二进制:000000000001

以上组成二进制为:11000001111101111010110111011010110000110-0000000001-000000000001

转为十进制:6988415561826833844,一个id号就这样生成了。

接下来分别介绍每部分的内容。

时间戳

时间戳一般通过当前时间-基准时间计算得出。

基准时间一般取最近时间(系统上线时间)。

因为当前时间是以1970年为基准时间算起的,而我们只需要从系统上线时算起就可以了。

为什么要这样做呢?我们可以来算一下该算法可以支持系统运行到多少年。

首先算出41bit的最大数值:11111111111111111111111111111111111111111(二进制) -> 2199023255551(十进制)

假设我们以1970年作为基准时间,那么当时间达到2199023255551时,时间戳部分就超出41bit了。

2199023255551进行时间戳转换:2039-09-07 23:47:35

以1970年作为基准时间,该算法可运行至2039-09-07 23:47:35

假设我们以最近时间2022-10-19 00:00:00作为基准时间。

2022-10-19 00:00:00转为时间戳:1666108800000

那么系统可达到的最大时间为:1666108800000 + 2199023255551 = 3865132055551

3865132055551进行时间戳转换:2092-06-24 15:47:35

以2022年10月19日作为基准时间,该算法可运行至2092-06-24 15:47:35

工作机器id

工作机器id部分可以用来保证生成id的唯一性:分布式系统中,每个节点的工作机器id不同,那么生成的id也一定不同。

该部分占用10bit, 意味着可以部署1024个节点。

工作机器id的设置可以由开发者手动设置,比如设置在JVM启动参数中,或者配置文件里,以保证工作机器id在每个节点的唯一性。

当然,如果节点太多对于配置来说也是灾难性的,此时可以考虑使用机器的mac地址或者ip做hash运算,以此作为工作机器id,但这就可能造成hash碰撞导致工作机器id重复(碰撞概率取决于hash算法),从而会有极小的概率生成id重复。

有时我们没有那么多的节点需要部署,那么就可以缩减该部分的bit位,用于增加时间戳部分bit位延长算法的使用时间,或者增加序列号部分增加每毫秒可生成的id树。

有时我们一个节点可能会部署多个实例,那么可以将10bit拆分,取5bit作为机器id,5bit作为进程id。

当然,你也可以取其中几个bit做业务标识。

由此可见,工作机器id部分是最容易自定义的部分

序列号

序列号部分用于在同一毫秒同一机器上生成不同的id号。

该部分占12bit,意味着同一毫秒同一机器上可生成4096个序列号,1秒即为4096000个(4百万)

和另外两个部分一样,该部分同样可以调整,如果单个实例的并发量确认达不到这么高,那么同样可以缩减该部分,将bit位让予其他部分使用。

实现

知道原理之后,接下来分析一下代码应当如何实现。

时间戳

时间戳部分有41bit, 值为当前时间戳 - 基准时间,转化为JAVA代码即为

long twepoch = 1666108800000L;
long time = System.currentTimeMillis() - twepoch;

这里在高并发多线程的场景下有个小小的优化点,可以使用定时任务线程池将System.currentTimeMillis()缓存起来,其他线程从缓存中获取。

public class SystemClock {
    private final long period;
    private final AtomicLong now;
    private SystemClock(long period) {
        this.period = period;
        this.now = new AtomicLong(System.currentTimeMillis());
        scheduleClockUpdating();
    }
    private void scheduleClockUpdating() {
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor(runnable -> {
            Thread thread = new Thread(runnable, "System Clock");
            thread.setDaemon(true);
            return thread;
        });
        scheduler.scheduleAtFixedRate(() -> now.set(System.currentTimeMillis()), period, period, TimeUnit.MILLISECONDS);
    }
    private long currentTimeMillis() {
        return now.get();
    }
}

摘自:https://gitee.com/yu120/sequence

这里直接给出原因:

  • 单线程情况下,直接调用System.currentTimeMillis()更快
  • 高并发多线程情况下,使用缓存获取时间戳更快

具体测试过程见文末参考

工作机器id

工作机器id可以在构造方法中传入,也可以取mac地址hash,方法如下

long id = 0L;
try {
  NetworkInterface network = NetworkInterface.getByInetAddress(getLocalAddress());
  if (null == network) {
    id = 1L;
  } else {
    byte[] mac = network.getHardwareAddress();
    if (null != mac) {
      id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
      id = id & 1023;
    }
  }
} catch (Exception e) {
  log.warn(" getWorkId: " + e.getMessage());
}
return id;

序列号

序列号在每一毫秒从0开始,如果同一毫秒生成多个id,则进行自增即可。

这里有两个要注意的点:

1、当序列号达到最大值时的问题

比如序列号占12bit位,最大值为4095,当序列号在同一毫秒自增到4095时,再加1则会超出bit位,此时需要将序列号重置为0,但是重置为0就会出现同一毫秒有两个序列号为0的id,所以重置为0的同时还需要等待至下一毫秒。

2、数据倾斜问题

如果序列号从0自增,那么对于大部分同一毫秒内只会有一个请求的系统,生成的id号序列号大部分为0(偶数),此时如果以id进行分表,就会造成数据的严重倾斜。该问题可以用过序列号从(0,1)随机开始自增。

3、时间回拨问题

时间回拨时可通过等待,或者使用过去时间生成id解决。

private long getSequence(){
  long timestamp = timeGen();
  // 闰秒
  if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
      try {
        // 休眠双倍差值后重新获取,再次校验
        wait(offset << 1);
        timestamp = timeGen();
        if (timestamp < lastTimestamp) {
          throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
        }
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    } else {
      throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
    }
  }
  if (lastTimestamp == timestamp) {
    // 相同毫秒内,序列号自增
    sequence = (sequence + 1) & sequenceMask;
    if (sequence == 0) {
      // 同一毫秒的序列数已经达到最大
      timestamp = tilNextMillis(lastTimestamp);
    }
  } else {
    // 不同毫秒内,序列号置为 0|1 随机数
    sequence = ThreadLocalRandom.current().nextLong(0, 2);
  }
  return sequence;
}
protected long tilNextMillis(long lastTimestamp) {
  long timestamp = timeGen();
  while (timestamp <= lastTimestamp) {
    timestamp = timeGen();
  }
  return timestamp;
}
protected long timeGen() {
  return System.currentTimeMillis();
}

整体代码

public class MySequence {
    private static final Logger log = LoggerFactory.getLogger(MySequence.class);
    /**
     * 时间起始标记点,作为基准,一般取系统的最近时间(一旦确定不能变动)
     */
    private final long twepoch = 1666108800000L;
    /**
     * 10位的机器id
     */
    private final long workerIdBits = 10L;
    /**
     * 12位的序列号 每毫秒内产生的id数: 2的12次方个
     */
    private final long sequenceBits = 12L;
    /**
     * 1023
     */
    protected final long maxWorkerId = ~(-1L << workerIdBits);
    /**
     * 机器id左移动位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 时间戳左移动位
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits;
    /**
     * 4095
     */
    private final long sequenceMask = ~(-1L << sequenceBits);
    /**
     * 所属机器id
     */
    private final long workerId;
    /**
     * 并发控制序列
     */
    private long sequence = 0L;
    /**
     * 上次生产 ID 时间戳
     */
    private long lastTimestamp = -1L;
    public MySequence() {
        this.workerId = getWorkerId();
    }
    /**
     * 有参构造器
     *
     * @param workerId     工作机器 ID
     */
    public MySequence(long workerId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("Worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.workerId = workerId;
    }
    /**
     * 基于网卡MAC地址计算余数作为机器id
     */
    protected long getWorkerId() {
        long id = 0L;
        try {
            NetworkInterface network = NetworkInterface.getByInetAddress(InetAddress.getLocalHost());
            if (null == network) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                if (null != mac) {
                    id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
                    id = id % (maxWorkerId + 1);
                }
            }
        } catch (Exception e) {
            log.warn("getWorkerId: " + e.getMessage());
        }
        return id;
    }
    /**
     * 获取下一个 ID
     *
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        // 闰秒
        if (timestamp < lastTimestamp) {
            long offset = lastTimestamp - timestamp;
            if (offset <= 5) {
                try {
                    // 休眠双倍差值后重新获取,再次校验
                    wait(offset << 1);
                    timestamp = timeGen();
                    if (timestamp < lastTimestamp) {
                        throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
                    }
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            } else {
                throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));
            }
        }
        if (lastTimestamp == timestamp) {
            // 相同毫秒内,序列号自增
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                // 同一毫秒的序列数已经达到最大
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            // 不同毫秒内,序列号置为 1 - 3 随机数
            sequence = ThreadLocalRandom.current().nextLong(1, 3);
        }
        lastTimestamp = timestamp;
        // 时间戳部分 | 机器标识部分 | 序列号部分
        return ((timestamp - twepoch) << timestampLeftShift)
                | (workerId << workerIdShift)
                | sequence;
    }
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    protected long timeGen() {
        return System.currentTimeMillis();
    }
}

改造

要解决JS精度丢失的问题,就要清楚原因是什么。

这是因为JS的number类型最大精度为2^53,即9007199254740992

转为二进制:100000000000000000000000000000000000000000000000000000 (54位)

那么我们只要让生成的id不超过9007199254740991即可

转为二进制:11111111111111111111111111111111111111111111111111111(53位)

可对此53位做以下分配

(1)时间戳(41位)-工作机器id(6位)-序列号(6位):最大支持64个workerId, 每毫秒生成64个序列号

(2)时间戳(39位)-工作机器id(4位)-序列号(10位):最大支持16个workerId, 每毫秒生成1024个序列号

此两种情况分别为两个极端,下面分别计算此两种情况的使用时长

第一种

41位时间戳的最大值为:2199023255551

取当前时间戳:1666108800000

计算:1666108800000 + 2199023255551 = 3865132055551(2092-06-24 15:47:35)

系统运行至2092年达到最大值

第二种

39位时间戳的最大值为:549755813887

取当前时间戳:1666108800000

计算:1666108800000 + 549755813887 = 2215864613887(2040-03-20 21:56:53)

系统运行至2040年达到最大值

使用

于是结合雪花算法原理,我对需要改造的项目从并发量(序列号)和实例数(工作机器id)方面做了调研。

从调研结果进行了bit位分配。

并且基于现有的id最大值,计算了基准数,让修改后的id生成策略必然大于以前的id。

最后该策略已上线运行,达到了预期结果。

小结

雪花算法的特点:唯一性,高性能,有序性。

雪花算法的三个部分:时间戳、工作机器id、序列号。

JS最大精度为2^53, 生成的id不超过该数即可。

使用时可根据实际业务情况对三个部分的bit位进行调整。

参考:

分布式高效ID生产黑科技: https://gitee.com/yu120/sequence

System.currentTimeMillis的性能真有如此不堪吗?: https://juejin.cn/post/6887743425437925383

目录
相关文章
|
25天前
|
运维 监控 JavaScript
内网网管软件中基于 Node.js 的深度优先搜索算法剖析
内网网管软件在企业网络中不可或缺,涵盖设备管理、流量监控和安全防护。本文基于Node.js实现深度优先搜索(DFS)算法,解析其在网络拓扑遍历中的应用。通过DFS,可高效获取内网设备连接关系,助力故障排查与网络规划。代码示例展示了图结构的构建及DFS的具体实现,为内网管理提供技术支持。
40 11
|
1天前
|
机器学习/深度学习 数据采集 算法
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
30 12
短视频到底如何推荐的?深度剖析视频算法推送原理详细且专业的解读-优雅草卓伊凡-【01】短视频算法推荐之数据收集
|
4天前
|
JavaScript 前端开发 算法
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
4天前
|
JavaScript 算法 前端开发
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
4天前
|
JavaScript 前端开发 Java
深入理解 JavaScript 中的 Array.find() 方法:原理、性能优势与实用案例详解
Array.find() 是 JavaScript 数组方法中一个非常实用和强大的工具。它不仅提供了简洁的查找操作,还具有性能上的独特优势:返回的引用能够直接影响原数组的数据内容,使得数据更新更加高效。通过各种场景的展示,我们可以看到 Array.find() 在更新、条件查找和嵌套结构查找等场景中的广泛应用。 在实际开发中,掌握 Array.find() 的特性和使用技巧,可以让代码更加简洁高效,特别是在需要直接修改原数据内容的情形。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一
|
3天前
|
监控 JavaScript 前端开发
MutationObserver详解+案例——深入理解 JavaScript 中的 MutationObserver:原理与实战案例
MutationObserver 是一个非常强大的 API,提供了一种高效、灵活的方式来监听和响应 DOM 变化。它解决了传统 DOM 事件监听器的诸多局限性,通过异步、批量的方式处理 DOM 变化,大大提高了性能和效率。在实际开发中,合理使用 MutationObserver 可以帮助我们更好地控制 DOM 操作,提高代码的健壮性和可维护性。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
MutationObserver详解+案例——深入理解 JavaScript 中的 MutationObserver:原理与实战案例
|
22天前
|
监控 网络协议 算法
基于问题“如何监控局域网内的电脑”——Node.js 的 ARP 扫描算法实现局域网内计算机监控的技术探究
在网络管理与安全领域,监控局域网内计算机至关重要。本文探讨基于Node.js的ARP扫描算法,通过获取IP和MAC地址实现有效监控。使用`arp`库安装(`npm install arp`)并编写代码,可定期扫描并对比设备列表,判断设备上线和下线状态。此技术适用于企业网络管理和家庭网络安全防护,未来有望进一步提升效率与准确性。
33 8
|
19天前
|
运维 NoSQL 算法
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
本文深入探讨了基于Redis实现分布式锁时遇到的细节问题及解决方案。首先,针对锁续期问题,提出了通过独立服务、获取锁进程自己续期和异步线程三种方式,并详细介绍了如何利用Lua脚本和守护线程实现自动续期。接着,解决了锁阻塞问题,引入了带超时时间的`tryLock`机制,确保在高并发场景下不会无限等待锁。最后,作为知识扩展,讲解了RedLock算法原理及其在实际业务中的局限性。文章强调,在并发量不高的场景中手写分布式锁可行,但推荐使用更成熟的Redisson框架来实现分布式锁,以保证系统的稳定性和可靠性。
38 0
【📕分布式锁通关指南 04】redis分布式锁的细节问题以及RedLock算法原理
|
4天前
|
JavaScript 前端开发 Java
详解js柯里化原理及用法,探究柯里化在Redux Selector 的场景模拟、构建复杂的数据流管道、优化深度嵌套函数中的精妙应用
柯里化是一种强大的函数式编程技术,它通过将函数分解为单参数形式,实现了灵活性与可复用性的统一。无论是参数复用、延迟执行,还是函数组合,柯里化都为现代编程提供了极大的便利。 从 Redux 的选择器优化到复杂的数据流处理,再到深度嵌套的函数优化,柯里化在实际开发中展现出了非凡的价值。如果你希望编写更简洁、更优雅的代码,柯里化无疑是一个值得深入学习和实践的工具。从简单的实现到复杂的应用,希望这篇博客能为你揭开柯里化的奥秘,助力你的开发之旅! 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一
|
2月前
|
机器学习/深度学习 算法 PyTorch
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
399 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现

热门文章

最新文章