乐趣区

关于后端:雪花算法原理以及JS精度丢失问题

作者：

jiezi

在

背景

最近我的项目上遇到一个革新主键生成策略的问题：须要将原Redis自增id革新成雪花算法。

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

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

当然，一个简略的方法就是将id转化为string类型，然而该业务流程长，波及范围广，改变中央太多。

所以为了解决这样的问题，我起了革新雪花算法生成策略的心理，也将这次革新过程中的播种分享进去。

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

雪花算法

起源

雪花算法(snowflake)最早是twitter外部应用的分布式下惟一id生成算法

https://github.com/twitter-ar…

该算法具备以下个性

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

原理

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

假如工夫戳：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开始自增。这里有两个要留神的点：

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/688774…

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章