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

47次阅读

共计 7740 个字符，预计需要花费 20 分钟才能阅读完成。

背景

最近我的项目上遇到一个革新主键生成策略的问题：须要将原 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…

正文完
后端
发表至： 后端
2022-10-21
 0
关于后端:质效中台助力实现质量度模型规模化落地
关于后端:Java异常捕获与处理防患于未然
关于后端:无需编写一行代码实现任何方法的流量防护能力
关于后端:Spring-源码解析十请求参数注解解析器与响应值注解处理器