cover_image

说说唯一ID与CAS｜得物技术

预子 得物技术
2024年07月24日 10:54

图片

目录

一、从数据的唯一标识开讲

    1. 数据区分与标识表现

    2. 标识的生成与组织

    3. 标识唯一性保证与核验

二、唯一索引到分布式锁

    1. 唯一索引的业务契合度

    2. 前置校验的方式选择

    3. 分布式锁的必要性

三、锁的共性问题

    1. 分布式锁的正确性保障

    2. 数据库主键唯一性保障

    3. 进程内协同之一：互斥

    4. 分布式锁与进程内锁的共性

    5. 唯一标识与CAS的联系

四、同类场景延伸

    1. 分布式ID生成原理

    2. 接口幂等与MQ消费幂等

    3. 操作系统进程间通信与互斥

    4. CAS原理的其他应用场景

五、总结

    1. 唯一标识与CAS与多对一模型

    2. 学会抽象归纳

一

从数据的唯一标识开讲

数据区分与标识表现

数据和算法组成了我们现有的应用软件，当然互联网应用也不例外。为了区分应用系统收集和运行所必要的这些数据，我们通过各种方法，来组织其存储形式，方便其为我们所用。从数据结构、文件、到专业数据库等工具，无一不是方便数据存储和访问的利器。
但无论如何，我们对数据存储，都要通过唯一的标识来对其进行区分，以确保我们根据这个标识来定位到它。
在不同的系统中，这个标识的表现也各不相同：
  • 在编程语言中，它表现为变量名称、常量名称等；
  • 在文件系统中，它表现为目录以及目录下的文件名等；
  • 在数据库表中，它表现为库名、表名、主键或唯一索引；
  • 在网络通信中，它表现为IP地址、MAC地址等；
  • 在计算机内存中，它表现为物理内存地址等。

标识的生成与组织

客观现实要求我们必须要做每一份数据的唯一性区分，在数据量少的时候，我们尚可以简单的命名方式来实现，但是当存在海量数据的时候，我们若想要将其区分标记出来，除了命名，还要相应地进行组织结构的变更，来降低命名的复杂度，否则海量杂乱的数据名称会加大我们管理和获取的难度。
最常见的几种区分方式通常有如下几类：
  • 全随机（可读性差，文字组合其实也可以当成一种全随机的特殊情况）
    • 例如UUID（结构示例如下：6B29FC40-CA47-1067-B31D-00DD010662DA）
    • 该方式经常用于小范围数据区分
    • 该方式通常不会单独使用，一般会结合树形结构来实现一些目录区分
  • 顺序递增的数值结构
    • 该方式形式简单，索引方便
    • 例如：数据库的自增主键、计算机内存的物理地址、Excel表的序号
  • 树形结构区分
    • 组织方式方便直观，便于索引
    • 例如：文件目录结构、关系型数据库数据组织方式、编程语言的多层结构体
  • 分布式ID生成方式
    • 例如雪花算法，该算法的分段标记其实有点树形结构的结合，但其增长方式又有数值的使用便利
  • 其他：以上方式的结合
    • 很多其他的唯一性区分通常都表现成以上方式的结合
    • 例如：URL
      • URL的域名以及Path，本身就存在树形结构的引子（虽然其本身指向的资源存储不一定是该方式）；
      • Path中的每一小段，都是区分性命名，世界范围内看，都是随机和不确定的。
几种形式标识的结构表现图例：
图片

全部随机形式以及递增数值

图片

树形结构区分的目录

图片
分布式ID之雪花算法的二进制结构（实际转换为10进制就是个长串的数值）

标识唯一性保证与核验

虽然我们已经有了唯一性生成的方式，人工确认数据的唯一性是一方面，但是在我们的软件系统中，存储唯一性数据的时候，如何保证其唯一性呢？
想必大家在使用计算机文件系统存储文件的时候会发现，在文件改名时，如果当前文件的新名字和同一目录下存在的文件名称冲突，那么系统可能会给出冲突提示，这是一种前置检测。
而且在数据库表设置了唯一索引的时候，如果唯一索引字段存在冲突，那么系统也会给出相应的提示。
另外一些情况下，不同的软件系统，通过自身的规则设计，保证了其生成的数据唯一性，例如数据库自增主键。
全局分布式ID生成算法中的雪花算法，一般也保证其生成数据的唯一性，但是在极端情况下，却也可能存在冲突。
一些软件唯一值冲突提示信息展示：
图片

文件系统命名冲突

图片

数据库唯一索引冲突

图片

编程语言变量重复命名

以上的例子其实提示了我们，在使用唯一标识生成的时候，一定要确认该标识是否在你的系统中能保证唯一，如果不能，那么有可能存在无法预期的风险。这些风险，需要我们提前识别并预设方案来解决，例如：
  • 同一个文件夹下如果来了重名文件，是要选择丢弃操作还是进行文件覆盖？
  • 唯一ID重复导致数据写入失败，是要丢弃数据还是通过其他方法来补偿？
笔者曾经遇到过这样的场景：历史项目中使用到了一个封装的随机字符串生成库，该库在低并发下生成的字符串无异常，但是在高并发状态下，其生成结果有重复项。而生成的目标字符在使用时未做唯一性校验，这就导致了一些异常的发生。
根据如上分析，我们需要通过如下两个方式来处理这个问题：
  • 切换离散性更高的的唯一字符串生成方式
    • 这个可以通过UUID算法来实现
  • 增加唯一性校验
    • 理论上在UUID算法下，几乎不会出现重复，但在防御性编程的考量下，我们依然引入校验做双重保障。

二

唯一索引到分布式锁

唯一索引的业务契合度

在未说明更详细信息的情况下，一定有人会问：既然你的数据要入库，为什么不使用唯一索引来保证数据不会冲突呢？
通常情况下，如果数据满足了全局唯一这个条件，我们确实可以使用唯一索引在保证数据入库数据关键字段唯一，但还存在一些例外的业务场景。
例如：
  • 数据字符较长，同时又不作为索引字段。
  • 应用数据软删除的要求，系统中可能存在某个唯一字段的多条数据。
这种情况下，就不得不放弃数据库的校验，将数据唯一性检验的过程纳入到自己的系统中。

前置校验的方式选择

我们考虑到要在系统中加入唯一性校验，那么在数据INSERT场景下，首先就要查询数据库以判断其是否存在，不存在再写入。
到了这一步，有以下几个问题需要考虑：
  • 这一步一定要查询数据库才能确认是否存在重复吗？
  • 你确定自己要查询的这个字段是索引字段吗？如果不是，查询性能太差，要怎么办？
  • 你查询数据库就一定能保证不重复吗？高并发下检测存在并发与时差怎么处理？
这里我们拆开来一个一个地讲：

是否必须查询数据库验证

数据库作为我们最终数据的存储载体，它所承载的数据总体来说体量是比较大的，即便我们有索引，但在索引查询以及查询数据库时候的网络交互开销一直不低。所以我们是否必须要从数据库来查询这些内容，存在一定的可选择性。
我们可以适当地通过唯一标识生成的规则，来做一些基本的数据隔离。
例如以时间段作为前缀，再追加上随机字符来区分数据：
  • 这样的标识自带时间区分度，我们只要在这个前缀的时间粒度上保证唯一，那么就可以确认整个数据在整个系统的唯一性。
  • 随机数据的生成，通常习惯于用系统时间作为种子值，所以高并发下的冲突不能依赖前缀来解决。
  • 时间的颗粒度按照数据的量来确认，通常需要自行平衡其同级以及下级的数据量。
例如如下的一串字符串 “foo_bar_20240616_randStr”，我们以foo、bar作为一二级前缀，时间日期作为第三级前缀，在这种情况下，我们可以不用关注历史数据的情况，直接校验单日维度的数据是否有重复即可，如果怕并发时间差影响，可以适当扩充延长校验的范围。
多级前缀或者类树形数据隔离后需要校验的数据量漏斗：
图片
再比如UUID算法，根据理论分析，UUID版本4（随机生成的UUID）的冲突概率可以被认为是忽略不计的。这种情况下，我们可以根据业务的需求来确认是否需要前置校验。
由此我们知道，只要我们确认数据重复性的可能是不存在的，或者有其他更简洁的替代方法，那么我们确实不需要去数据库查询核验。

非索引字段怎么验证处理

在不确认数据唯一性的情况下，或者查询数据库不是最合适的解决方案的情况下，我们该用什么方法来解决这个问题呢？通常选择的一种方法是增加分布式锁来进行校验。
依然针对我们提到的字符串“foo_bar_20240616_randStr”，经过前缀隔离之后，我们判断下来，只要校验按日维度的数据不存在重复即可。
这样我们选择分布式锁的时候，需要保证锁的时间维度在一天或者稍多就能满足需求。

高并发下如何保证正确性

如果我们确实要走数据库查询核验，那么在高并发场景下，查询到存储的间隙，有其他进程或线程触发同样的逻辑造成冲突了怎么办？其他机器上部署的业务也同样触发相同的逻辑又该如何？
这种情况下，我们自然而然地也想到了分布式锁。
内存级分布式锁工具的高性能可以弥补直接查询数据库判断比对的处理时间差。

分布式锁的必要性

我们知道，编程语言中也到处有锁的身影，例如Go语言的互斥锁、读写锁，但是其作用是在单应用进程内提供的协程并发访问互斥机制，无法作用到多进程或者多节点部署的情况。
而分布式锁，正好可以帮助多节点部署的业务服务来解决并发访问共享资源时的一致性问题。

三

锁的共性问题

分布式锁的正确性保障

相信对分布式锁感兴趣的小伙伴，或多或少都知道常用的两种分布式锁应用方式：Redis、Zookeeper。
通常使用分布式锁时候要考量如下的问题：
  • 加锁成功之后，后续对该锁的所有操作，能否确认该锁是当前线程持有
    • 当前线程释放锁是否有可能释放了不是本线程持有的锁？
    • 我加了锁，锁的时间不够我业务执行，后面我再操作锁，这个锁还是本线程的锁吗？
  • 加锁的时间问题
    • 当前线程持有的锁时间内，任务还没完成锁就过期了该怎么办？
    • 当前线程持有的锁还有很长时间才自动释放，但是任务已经结束，并发上不来阻塞了怎么办？
  • 锁的释放问题
    • 你确定当前线程加的锁在程序正确执行或者异常之后都释放了吗？
  • 你如何知道Redis或者Zookeeper给你保证的锁是唯一的呢？
    • Redis的单线程模型保证锁操作的正确性，如果你的Redis是主从版或者集群版又正好节点异常切换了呢？
    • Zookeeper的强CP原则，牺牲了A（可用性），但是也可能存在宕机等问题，如何处理？
针对业务上的前面几个问题，我们通常可以通过下面的几个方法来解决，但依然存在局限性。
对于最常见的基于Redis实现的分布式锁：
  • 获取锁的时候给锁value设置随机唯一标识，该标识可以用来判断接下来的锁持有方；
  • 给锁一个合适的初始有效时长，并在锁即将到期的时候续期；
  • 在程序执行的正常区间和异常区间都要释放锁；
  • 如果有自旋场景，那么一定要给自旋场景一个最大过期时间防止死锁；
  • 对于每一个操作，最好使用lua脚本实现操作的原子性；
  • 针对集群版或者主从版本的Redis，需要根据业务权衡是否需要采用redlock或者单节点的Redis来作为锁载体。
    • redlock算法较重而且极端情况下也可能存在问题；
    • 单节点显然存在单点问题，但是肯定可以保证强一致性。
而基于Zookeeper实现的分布式锁：
  • Zookeeper基于其临时有序节点的“申请-未获取-监听-申请-获取-操作-释放”的循环来实现分布式锁；
  • 因为临时节点的释放是基于会话级别的，所以在会话关闭或者异常中断的情况下，也都会自动释放，所以避免了死锁的问题，心跳的存在我们也不用手动续期。
Redis使用自身单线程操作内存的机制、Zookeeper使用ZAB协议，其实都存在一些共同点，它们的共同点就在于要保证我设置的key或者节点的次序是首次。
它们要保证的是，无论你的业务系统分布式程度多高，基于它们所获取到锁数据，都是唯一的和最先的。
以上我们讲了那么多，其实都绕不开一个概念，那就是多个线程的访问，经过层层传递收缩，最终都指向到同一份数据上或者同一个数据标识上（因为对于分布式缓存而言，数据可能存有多份，并通过半数以上同意的协议形式来确定其一致性）。
业务线程锁逻辑访问收缩示例：
图片
能支持分布式锁的，不只有Redis和Zookeeper。理论上，其他满足CAP理论中CP（一致性和分区容忍性）的分布式系统，在一定程度上都能满足支持分布式锁的条件。

数据库主键唯一性保障

在MySQL数据库中，我们知道，主键一定是唯一的，唯一索引却不一定是主键。虽然上面提到的场景，我们引入了分布式锁来保障数据的唯一性，但是MySQL自身的自增主键机制，也是我们所离不开的。
在MySQL中，自增主键通过“AUTO_INCREMENT控制”的机制来确保主键值的唯一性和自增，AUTO_INCREMENT控制主要通过数据库的内部机制来实现。
具体来说，当表中的某个列被指定为AUTO_INCREMENT主键时，MySQL会自动维护一个用于该列的自增计数器，并确保每次对表的插入操作都会使这个计数器递增。
具体实现的方式包括以下几个方面：
  • 内部计数器：MySQL内部会维护一个计数器，用来记录下一个可用的自增值。这个计数器通常保存在系统表中，跟踪每个表，以及每个表的AUTO_INCREMENT列的当前值。
  • 锁机制：在插入新记录时，MySQL会使用锁机制来确保自增值的唯一性。在插入操作之前，会对计数器或相关数据进行锁定，以避免多个客户端同时尝试获取相同的自增值。
  • 事务支持：对于使用事务的情况，MySQL也会确保在事务失败时（例如回滚），已分配的自增值不会被使用，以维护自增值的连续性和唯一性。
总的来说，MySQL的AUTO_INCREMENT控制主要依靠内部的自增计数器和相应的锁机制来实现。这种机制有效地确保了主键的自增属性，并保证了主键的唯一性。

进程内协同之一：互斥

以上说到的是分布式锁，但是在单机系统中，也存在不同线程或协程数据交互与执行互斥的问题。例如操作系统多应用互访、单进程应用配置数据的多线程访问和变更、下游访问的并发抑制操作等。
编程语言给我们提供了一系列进程内协同的方式：同步、互斥与通信。这里的进程内互斥体，其实也就是称为锁。
Go语言提供的互斥锁功能，其底层依赖有如下一些机制：
  • 原子操作
    • 原子操作是CPU提供的功能，由CPU保证执行的原子性
    • Go语言互斥锁所依赖的主要原子操作是CAS（ Compare and Swap ）
  • 自旋模式与阻塞模式
    • 自旋+CAS 、阻塞/唤醒双模式
    • 协程与锁的多对一状态，锁的自旋等待显得尤为必要
    • 但对于长CPU时间片的操作，自旋等待过程所消耗的资源其实也不低
    • Go语言通过自旋模式到阻塞模式的切换，来缓解锁竞争激烈场景下的CPU消耗
  • 均衡调度
    • 普通模式：普通模式下，老协程相比新的协程，在正常锁竞争下缺乏优势，可能导致长时间无法获得执行权限
    • 饥饿模式：饥饿模式会使未得到执行的协程获得更高的执行优先级，以摆脱长时间获取不到锁无法执行的困境
其他的编程语言一般也提供相应的锁机制，来保证系统中多线程执行互斥的问题。

分布式锁与进程内锁的共性

从上面的信息，我们看的出来，无论是分布式锁，还是进程内的互斥锁，都存在下面的一些共性：
  • 使用唯一标识来识别锁的当前归属；
  • 通常使用CAS方式来实现变更操作的原子性；
  • 要考虑获得锁的失败自旋以及时间问题；
  • 根据需要来确定是自旋等待还是失败结束。

唯一标识与CAS的联系

编程语言提供的互斥锁功能，在底层上依赖CPU提供的原子操作功能CAS 。
我们在使用Redis分布式锁的时候，如果使用lua脚本，其比对该锁的value是否是本线程持有的时候，也有个比对后再更改的过程。
Zookeeper实现分布式锁的时候，我们也是获取到临时顺序节点的最小序号（有个比对过程），才能确定获取到锁。
另外在数据库数据更新的时候，我们也经常用该方式保证数据变更条件的准确性。
当然，CAS这个操作概念，其C（compare），所依赖的依然是某个数值在当前场景下的唯一性。这也是我为什么从数据唯一性引申到这里的原因，而且CAS也是我在这里要重点说的思想。
看到这里，不知道大家有没有发现，这里存在一个很有意思的情况：
  • 数据唯一性检验可以使用锁来解决
  • 而锁的获取，又依赖一个小范围的唯一数据
所以这也是一个将大范围唯一性校验，通过一定方式转换为小范围唯一性校验的方法。而小范围唯一性的标记，甚至可以深入简化到底层二进制的0和1两个状态来完成。

四

同类场景延伸

分布式ID生成原理

我们在前面提到了唯一标识的生成组织方式，其中分布式ID生成算法之一的雪花算法，就使用了时间前缀区分、分片标识、节点数据自增的方式，将大范围唯一标识生成缩小成小范围的数据自增，还兼顾了按时间增长与高并发等性能优势。
常用的分布式ID生成算法，各有其特点：
  • 雪花算法：雪花算法是Twitter开源的分布式ID生成算法，它可以在分布式系统中生成全局唯一的、递增有序的ID。Snowflake算法的ID由时间戳、机器ID和序列号组成。
  • 数据库自增ID：在分布式系统中，可以使用单独的数据库服务器生成自增ID。不同的服务器会有不同的起始值和步长，从而避免冲突。
  • 使用Redis的INCR命令：Redis的INCR命令可以用来原子递增一个key的值，因此可以利用这个特性来生成全局唯一ID。
但是无论使用哪种方案，都需要考虑ID的唯一性、性能、可用性以及分布式环境下的并发安全性，选择合适的方案应根据具体需求以及系统架构来进行权衡和决策。

接口幂等与MQ消费幂等

业务数据接口幂等操作与消费队列消费的幂等操作，幂等性保证其实是一样的原理。
幂等性是指针对同一个操作，多次执行的结果和一次执行的结果是一致的。在计算机科学和网络编程中，幂等性是一个重要的概念，特别是在分布式系统和网络通信中。
针对幂等性处理，我们要记住的唯一思想其实也是CAS。对于存在数据变动的场景，CAS的原则可以保证数据只在指定条件下才发生变化。
以下几种保证MQ消费幂等的方式中，CAS的思想其实是一致的：
  • 基于数据库中唯一ID以及某个状态的值做前置判断，符合条件才执行；
  • 使用消息ID作为Redis分布式锁的key来判断当前消息是否消费成功；
  • 使用消息ID入库以及成功后状态变更来判断消息消费是否已经执行过。

操作系统进程间通信与互斥

对于进程间协同来说，主流操作系统支持了锁（Mutex）和信号量（Semaphore）。Windows还额外支持了事件（Event）同步原语。
进程间的锁（Mutex），语义上和进程内没有什么区别，只不过标识互斥资源的方法不同。Windows最简单，用名称（Name）标识资源，iOS用路径（Path），Linux 则用共享内存。
从使用接口看，Windows和iOS更为合理，虽然大家背后实现上可能都是基于共享内存（对用户进程来说，操作系统内核对象都是共享的），但是没必要把实现机理暴露给用户。

CAS原理的其他应用场景

  • 无锁数据结构：CAS原理通常与无锁数据结构结合使用，以实现高效的并发数据访问。由于CAS原子操作的特性，可以在不使用锁的情况下对共享数据进行操作，从而提高并发性能。
  • 分布式系统：CAS原理的思想可以应用于分布式系统中的数据同步和一致性问题。在分布式环境中，类似CAS的原子操作除了可以用于实现分布式锁，还可以用来实现分布式事务以及一致性算法，确保全局状态的一致性和可靠性。
  • 数据库事务：在数据库系统中，CAS原理的思想可以用于乐观锁和并发控制。通过比较数据版本或标记位，并进行更新的原子操作，实现数据库事务的并发控制和一致性。
  • 业务流程控制：CAS原理的思想也可以应用于业务系统中的流程控制，例如利用乐观锁的机制来处理并发访问下的业务逻辑一致性问题。（上面提到的幂等实现其实也是该大类下的）

五

总结

唯一标识与CAS与多对一模型

到这里，我们发现，上面提到的基于唯一标识与CAS原理来解决问题的方式，其本质都是多对一模型下，实现多线程同步互斥，以及并发收缩问题的基础依赖。
所以我们遇到的多对少或者多对一模型下的，数据访问或修改的收缩问题，其实都可以通过类似的思想来尝试寻找解决方案。

学会抽象归纳

唯一ID与CAS这两个点，乍一看好像并无联系，但是经过关联梳理，我们依然能发现它们在多对一模型下的关联。
当我们在工作学习中，遇到的比较相似的问题多了，只要愿意深入思考，就能发现其中的共性，并且总结提炼出来，在下一次遇到类似的情况时，自然而然就能想到它。
熟能生巧之外，我们也可以主动使用一些通用的思路和方法，配合工具来提升自己的抽象归纳能力。具体来说，抽象归纳有以下思路和方法：观察和辨识共性、提炼概念、泛化思维、归纳推理、应用验证等，可以使用的工具则有：思维导图、数据分析工具、逻辑推理工具或游戏等。
希望这些方法思路和工具，可以带大家直击问题本质，提升大家面对问题的分析能力和解决能力。

往期回顾


1. 前端打包工具Mako架构解析｜得物技术
2. 基于Rspack实现大仓应用构建提效实践｜得物技术
3. 星愿森林的互动玩法揭秘｜得物技术
4. StarRocks跨集群迁移最佳实践｜得物技术
5. Apache Flink类型及序列化研读&生产应用｜得物技术


文 / 预子


关注得物技术，每周一、三、五更新技术干货

要是觉得文章对你有帮助的话，欢迎评论转发点赞～

未经得物技术许可严禁转载，否则依法追究法律责任。

“

扫码添加小助手微信

如有任何疑问，或想要了解更多技术资讯，请添加小助手微信：

图片

后端18
无锁1
一致性1
分布式锁2
cas1
继续滑动看下一个
得物技术
向上滑动看下一个