首页 > 其他分享 >分布式主键 详解

分布式主键 详解

时间：2024-08-06 18:56:37浏览次数：11  
标签：雪花 算法 详解 进程 currentMilliseconds 主键 序列号 分布式

文章目录

雪花算法结合分库分表的问题

问题出现

使用ShardingSphere框架自带的雪花算法生成分布式主键，如果和分片算法结合使用不当就很有可能造成数据分布不均匀的情况

如下所示，我使用分布式主键生成策略是SNOWFLAKE，分表策略是常见的取模运算

	rules:
      sharding:
        # 分片键生成策略
        key-generators:
          # 雪花算法
          alg_snowflake:
            type: SNOWFLAKE
            props:
              worker:
                id: 1
        sharding-algorithms:
          # 定义分库策略
          db_alg:
            type: MOD
            props:
              sharding-count: 2
          # 分表策略
          sys_user_tab_alg:
            type: INLINE
            props:
              algorithm-expression: sys_user$->{((uid+1)%4).intdiv(2)+1}

进行新增操作后，这里并没有均匀的分布在四个数据表中，只存在两个数据表中




在这里插入图片描述



原因分析

造成这个问题的原因是，ShardingSPhere自带的雪花算法的序列号位是一个单位时间内自增，如果不是一个单位时间内那么就重置为0重新自增。

// 全类名 org.apache.shardingsphere.sharding.algorithm.keygen.SnowflakeKeyGenerateAlgorithm

@Override
public synchronized Long generateKey() {
    long currentMilliseconds = timeService.getCurrentMillis();
    // 处理雪花算法41bit时间戳位 时钟回拨 
    if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
        currentMilliseconds = timeService.getCurrentMillis();
    }
    // 处理12bit序列号位
    if (lastMilliseconds == currentMilliseconds) {
        // 单位时间内  sequence序列号位每次都是自增
        if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
            currentMilliseconds = waitUntilNextTime(currentMilliseconds);
        }
    } else {
        // 如果不是一个单位时间内，序列号位就又重置
        vibrateSequenceOffset();
        sequence = sequenceOffset;
    }
    lastMilliseconds = currentMilliseconds;
      //  时间戳位 | 工作进程位 | 序列号位
  return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}



进一步编写测试类验证

取出插入数据库中的uid值，进行位& 运算，最终就可以发现序列号位基本上都是 0 或者是1 那么这样我们就进行简单的 %2 %4 运算所以就导致了上方的数据分布不均匀问题

public void testSequence(List<Long> uidList) {
    int mask = (1 << 3) - 1;
    for (Long uid : uidList) {
        log.info("uid:{} 的后3位的结果为 {}", uid, uid & mask);
    }
}

uid:1027514136331812864 的后3位的结果为 0
uid:1027514137086787584 的后3位的结果为 0
uid:1027514137128730624 的后3位的结果为 0
uid:1027514137166479360 的后3位的结果为 0
uid:1027514137204228096 的后3位的结果为 0
uid:1027514137057427457 的后3位的结果为 1
uid:1027514137107759105 的后3位的结果为 1
uid:1027514137149702145 的后3位的结果为 1
uid:1027514137183256577 的后3位的结果为 1
uid:1027514137216811009 的后3位的结果为 1



解决思路

修改现有的雪花算法，让序列号位不要每次都重置。这种方式的确能解决当前业务功能。

@Override
public synchronized Long generateKey() {
    long currentMilliseconds = timeService.getCurrentMillis();
    if (waitTolerateTimeDifferenceIfNeed(currentMilliseconds)) {
        currentMilliseconds = timeService.getCurrentMillis();
    }
    if (lastMilliseconds == currentMilliseconds) {
//      if (0L == (sequence = (sequence + 1) & SEQUENCE_MASK)) {
        currentMilliseconds = waitUntilNextTime(currentMilliseconds);
//      }
    } else {
        vibrateSequenceOffset();
//      sequence = sequenceOffset;
        // SEQUENCE_MASK = (1 << 12L) - 1
        sequence = sequence >= SEQUENCE_MASK ? 0:sequence+1;
    }
    lastMilliseconds = currentMilliseconds;
    return ((currentMilliseconds - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (getWorkerId() << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}



但是带来的问题是分布式场景下，雪花算法的序列号位相当于没用了。因为雪花算法的初始目标就是分布式主键生成不冲突，它是靠 时间戳位+工作进程位+序列号位保证的。

如果在单位时间内，并且没有设置工作进程位，多台服务器中的序列号位相同了，那么也就导致了后续生成的id都可能出现重复的情况。



分布式主键要考虑的问题

  1. 主键除了要标识数据的唯一性之外，还通常会要求主键与业务不直接相关。因为这样不管业务如何变化，都不会影响主键来控制数据的生命周期
  2. 但是，另外一个方面，我们通常又会要求主键包含一部分的业务属性，这样可以加速对数据的检索。
  3. 主键也需要考虑安全性，让别人无法通过规律猜出主键来。

所以，对于主键，一方面，要求他与业务不直接相关。这就要求分配主键的服务要足够稳定，足够快速。不能说我辛辛苦苦把业务给弄完了，然后等着分配主键的时候，还要等半天，甚至等不到。另一方面，要求他能够包含某一些业务特性。这就要求分配主键的服务能够进行一定程度的扩展。



主键生成策略



数据库策略

业务层面不设置主键，直接使用数据库的自增长。这种方式实现简单，但是分库分表场景下就会造成主键冲突。当然也可以通过为各个数据库设置自增长步长来解决。但是又不能满足分库分表扩缩容的场景。



应用单独生成

数据库生成的主键不靠谱，那么就应用层面自己来生成。比较常见的算法就是：UUID、NANOID、SnowFlaks雪花算法

优点：简单使用。比如UUID使用JDK自带的工具类即可、SnowFlaks按照它定义的规则自行组合。比较容易扩展，可以随意组合生成主键。

缺点：

  • 算法不能太复杂，会消耗cpu计算资源与内存空间
  • 要考虑多线程并发安全问题，不能主键冲突。
  • 考虑数据库产品结合因素，比如mysql的InnoDB存储引擎，B+树索引，需要使用趋势递增的主键来避免B+树的分裂。UUID这类无序字符串主键就不能满足



第三方服务统一生成

借助第三方服务来生成主键，比如redis、zookeeper、MongoDB

redis：通过incr指令，配合lua脚本比较容易防并发

zookeeper：使用它的序列号节点；或者是在apache提供的Zookeeper客户端Curator中，提供了DistributedAtomicInteger，DistributedAtomicLong等工具，可以用来生成分布式递增的ID。

MongoDB：使用MongoDB的ObjectID。



缺点：

  • 这些原生的方式大都不是为了分布式主键场景而设计的，所以，如果要保证高效以及稳定，在使用这些工具时，还是需要非常谨慎。
  • 每一次生成主键都需要调用第三方服务，效率问题也需要考虑



与第三方结合的segment策略

还是从第三方获取主键，只不过是一次获取一批主键，缓存在本地，当使用完后再去申请一批。

比如我们设计下面这种数据表

在这里插入图片描述

biz_tag表示具体的某一业务标识，用户或订单他们都对应的一整个集群服务。max_id表示当前已经分配的最大id，step表示每次分配的步长。max_id会随着每一次分配id而增加。

这种方式的缺点是应用向第三方申请id有网络消耗，这段时间内应用会出现无主键可用的情况。



与第三方结合的多segment策略

双Buffer写入，向第三方服务申请两个segment放入本地缓存。避免出现应用在向第三方申请主键这段期间没有主键可用的情况

在这里插入图片描述



扩展点：

  • 比较依赖DB，上方max_id 和step这两个字段都是保存在数据库的。我们可以保存在其他存储方式
  • 第三方应用宕机，在我服务中双buffer中的id使用完之前重新提供服务，这样问题都不大。所以我服务中保存的buffer个数可以多一些，进而提高容错性



雪花算法详解

雪花算法使用8字节的二进制序列来生成一个主键

在这里插入图片描述

  • 41bit的时间戳为主体，时间戳位保证趋势递增，放在最高位；

  • 10bit的工作进程位标识服务器中运行的进程，而不是标识机器，需要应用自行扩展；

  • 12bit序列号位是用来区分单位时间内 单机器内的自增序列。

而在具体实现时，雪花算法实际上只是提供了一个思路，并没有提供现成的框架。比如ShardingSphere中的雪花算法就是这样生成的。




在这里插入图片描述



时间戳位问题

41bit的时间戳为主体，时间戳位保证趋势递增，放在最高位；

时间戳位存在时钟回拨的问题。

一台服务器上，获取时钟只能依赖于内核的电信号维护，而电信号很难保持稳定。在高并发场景下获取高精度的时间戳有时会往前跳，有时会往回拨。

一旦时钟回拨就有可能产生重复的id。



各个框架的雪花算法都有对时钟回拨的问题做相应的处理，基本思路就是记录上一次生成主键的时间lastMilliseconds，和当前时间进行比较，如果lastMilliseconds大于当前时间就表示出现了时钟回拨，处理方式要么sleep()一段时间，要么直接抛异常。就比如ShardingSPhere的SnowFlake雪花算法就是sleep()，而cosID_SnowFlake就是抛异常

// 全类名 org.apache.shardingsphere.sharding.algorithm.keygen.SnowflakeKeyGenerateAlgorithm
@SneakyThrows(InterruptedException.class)
private boolean waitTolerateTimeDifferenceIfNeed(final long currentMilliseconds) {
    //  上一次生成主键的时间 和 当前时间进行比较
    if (lastMilliseconds <= currentMilliseconds) {
        return false;
    }
    long timeDifferenceMilliseconds = lastMilliseconds - currentMilliseconds;
    Preconditions.checkState(...);
    // 解决时钟回拨的方式采用sleep()
    Thread.sleep(timeDifferenceMilliseconds);
    return true;
}




// 全类名 me.ahoo.cosid.snowflake.AbstractSnowflakeId
public synchronized long generate() {
    long currentTimestamp = this.getCurrentTime();
    // 时钟回拨
    if (currentTimestamp < this.lastTimestamp) {
        // 抛异常
        throw new ClockBackwardsException(this.lastTimestamp, currentTimestamp);
    } else {
        // 序列号处理 不是同一个单位时间点&&值>2^12 就重置0
        if (currentTimestamp > this.lastTimestamp && this.sequence >= this.sequenceResetThreshold) {
            this.sequence = 0L;
        }
		// 序列号位自增
        this.sequence = this.sequence + 1L & this.maxSequence;
        if (this.sequence == 0L) {
            currentTimestamp = this.nextTime();
        }

        this.lastTimestamp = currentTimestamp;
        long diffTimestamp = currentTimestamp - this.epoch;
        if (diffTimestamp > this.maxTimestamp) {
            throw new TimestampOverflowException(this.epoch, diffTimestamp, this.maxTimestamp);
        } else {
            // 时间戳 | 进程号 | 序列位
            return diffTimestamp << (int)this.timestampLeft | this.machineId << (int)this.machineLeft | this.sequence;
        }
    }
}



上方只能处理单台服务器上的时钟回拨，如果是多台服务器一个集群，就无法保证时间戳的统一了。

可以为每个应用配置一个工作进程位来防止不同服务器之间的主键冲突。但是万一应用没有配置嘞？大部分应用不会为了一个雪花算法去单独考虑如何分配工作进程位。

也可以使用ntpd这样的时间同步服务来把多个服务器的时间同步一下。但同样的不会有人仅仅为了雪花算法去这么做

第三种方案是将时间戳从本地扔到第三方服务上去，比如zookeeper，这样多个服务就可以根据共同的时间戳往前推进，省了服务器之间同步时间的麻烦。美团的leaf就是这么做的。缺点是：给雪花算法添加强绑定；降低了效率，因为多了一个访问第三方的步骤。

这有变为了方案取舍、实现优化的头疼环节。就像整个分布式主键一样。



工作进程位问题

10bit的工作进程位标识服务器中运行的进程，而不是标识机器，需要应用自行扩展；它是分布式场景下，保证id不重复很重要的字段。

因为一台服务器上面可以运行多个进程实例，所以这个标识是工作进程的，而不能简单理解为标识机器。工作进程是需要各个应用自己设定值，所以这里就分为了手动指定和自动获取两种方式。

对于一些小集群，就可以简单使用手动指定的方式在配置文件中为当前应用指定一个工作进程。但如果是大型集群，上百个微服务肯定就不能手动指定了。

在这里插入图片描述

现在就有一个思路，把MachineId(比如ip+端口)当做一个短的并发不是很高的分布式主键来处理，用其他分布式主键生成的方式生成工作进程位。我们现在需要依赖于一个工作进程位来生成分布式唯一主键，然后现在又要依赖于一个分布式唯一主键生成策略来生成工作进程位，完美闭环！鸡生蛋 蛋生鸡问题。



首先工作进程位是不需要考虑高并发问题，通常工作进程位只需要在一个应用启动时分配一个就可以了，应用的运行过程中不需要什么变化。所以工程进程位每次单步推进，申请一次，分配一个就行

其次工程进程位有一个天然的就带有唯一性的因素，比如使用ip地址，如果服务器运行多个应用那么也可以使用ip+端口区分。所以工作进程位天生就有很多唯一性因素，不需要像雪花算法那样去设计复杂的结构。

最后工作进程位的分配需要保持稳定。工作进程要与一个应用建立绑定关系。给一个应用分配工作进程号位之后如果应用崩溃了，重启服务之后所生成的雪花算法还是需要保持一个稳定的区分度。所以可以使用一个本地缓存保存这个应用的工作进程位，应用重启后，还需要保持，那么这个缓存可以持久化到本地文件中。

其实把这几个方面想明白了，Cosid当中的工作进程位分配机制也就大致成型了。



序列号位问题

序列号位就是一个连续性问题。就比如上文中的结合分库分表的问题。

如果不是一个单位时间内，那么就将序列为重置为0，进而导致了我们使用取模分片策略使得数据分配不均匀。



根据雪花算法扩展基因分片法

业务场景，对User用户表进行分库分表，最简单的处理就是根据userId作为分片键，之后每次查询都根据userId这个分片键来进行查询。但用户登录这个场景嘞？此时只有一个用户名，你甚至都不知道这个用户名是否存在，难道就只能全路由查询？这肯定是不能接受的。

此时就可以使用基因法的分片算法来解决这个问题。它的基础思想是再给用户分配userId时，就把用户名当中的某种序列信息插入到userId当中。从而保证userId和用户名可以按照某一种对应规则分到同一个分片上。这样就可以根据用户名确定对应的用户信息在哪一个分片上

在这里插入图片描述



具体在实现时，可以参照雪花算法的实现。

@Test
public void testGene() {
    // 初始值
    Long userId = 1257458L;
    String userName = "testroy";
    // 基因序列位数
    int dataSize = 3;

    //掩码，二进制表述为全部是1.  111
    int mask = ((1 << dataSize) - 1);
    // 只取 datasize 个bit位
    long userGene = userName.hashCode() & mask;
    // 给ID添加用户名的基因片段后的新ID，保持了原id的一致性
    long newUserId = (userId << dataSize) | userGene;

    // 对新用户id对8取模进行数据分片
    long actualNode = newUserId % 8;
    System.out.println("用户信息实际保存的分片：" + actualNode);
    long userNode = (userName.hashCode() & mask) % 8;
    System.out.println("根据用户名判断，用户信息可能的分片：" + userNode);
}

用户信息实际保存的分片：2
根据用户名判断，用户信息可能的分片：2

标签：雪花,算法,详解,进程,currentMilliseconds,主键,序列号,分布式
From： https://blog.csdn.net/qq_44027353/article/details/140955500

相关文章

  • C语言：qsort详解
    在上一篇文章我们大致的了解了回调函数的用法和作用，在这一篇让我们来了解一下在回调函数qsort的使用吧。一.qsortqsort是一种用来排各种类型数据的函数，利用的是快速排序的方式。说到排序，我们就想到了之前学习的冒泡排序，但冒泡排序也有很明显的缺点：时间复杂度太高，效率慢，但qsor......
  • 【验证码逆向专栏】某安登录流程详解与验证码逆向分析与识别
    声明本文章中所有内容仅供学习交流使用，不用于其他任何目的，不提供完整代码，抓包内容、敏感网址、数据接口等均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关！本文章未经许可禁止转载，禁止任何修改后二次传播，擅自使用本文讲解的技术而导致的任何意外，作......
  • cudart64_90.dll缺失？一文详解CUDA运行时环境修复步骤
    cudart64_90.dll是一个与NVIDIACUDA（ComputeUnifiedDeviceArchitecture）框架相关的动态链接库（DynamicLinkLibrary，简称DLL）。CUDA是NVIDIA开发的一种并行计算平台和编程模型，它允许开发者利用NVIDIAGPU的并行处理能力来进行高性能计算。cudart64_90.dll是CUDA运行时库的一部......
  • Mipi SoundWire Spec 详解
    4技术概览（参考性） 4.1引言本规范描述了SoundWire接口，该接口用于传输通常与音频功能相关的数据。SoundWire促进了低成本、高效、高性能系统的开发，其特性包括：通过单一的双针脚接口（时钟和数据线）传输所有负载数据通道、控制信息和设置命令；时钟缩放和可选的多个数据通道，以提供......
  • C#:具体类=＞抽象类=＞接口的进化过程详解
    文章目录简单复习继承与多态具体类抽象类及成员使用语法接口抽象类到接口的进化简单复习继承与多态下面,我用一个交通工具的例子来快速复习一下.1.首先我定义一个基类Vehicle,代表交通工具的总称.里面定义了一个可被重写的成员方法Run.classVehicle{......
  • HTML5 WebSocket 详解及使用
    1.WebSocket是什么？WebSocket是HTML5提供的一种在单个TCP连接上进行全双工通讯的协议。（双向通信协议）2.WebSocket的作用？实现客户端与服务器之间的双向通信，允许服务端主动向客户端推送数据。在WebSocketAPI中，浏览器和服务器只需要完成一次握手，两者之间就直......
  • 【微信小程序实战教程】之微信小程序核心组件详解
    微信小程序核心组件组件化开发并不是小程序所特有的，一些其他编程语言中都有组件化的概念，准确来讲，只有UI视图层的展示，就必定要用到组件化。组件是UI视图层的最基本组成单元，组件中包含了一些基础功能和基础样式，一个组件就类似于一个自定义的标签。小程序框架为开发者提供了......
  • Mojo和Python中的类型详解
    调用Python方法时，Mojo需要在原生Python对象和原生Mojo对象之间来回转换。大多数转换都是自动进行的，但也有一些情况Mojo尚未处理。在这些情况下，您可能需要进行显式转换，或调用额外的方法。Python中的Mojo类型Mojo基本类型隐式转换为Python对象。目前支持的......
  • xpath详解
    什么是Xpath？Xpath是一种用在XML文档中定位元素的语言，同样也支持HTML元素的解析。所谓Xpath，是指XMLpathlanguage。path就是路径，那么Xpath主要是通过路径来查找元素。我们通过下面一张小图来了解一下HTML中的结构：HTML的结构就是树形结构，HTML是根节点，所有的......
  • IEC104初学者教程，第八章：总召唤流程详解
    第八章：总召唤流程详解平时学习规约或调试IEC104或IEC101设备，需要IEC104/101模拟器，推荐一款：主站下载地址：IEC104主站模拟器从站下载地址：IEC104从站模拟器IEC60870-5-104（简称IEC104）是一种用于远程控制和监控系统的通信协议。它广泛应用于电力系统和其他工业自动化系统中。总召......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99