全局ID生成方式

目录

• 1. 全局唯一id介绍
  • 1.1 特点
• 2. 常见的全局唯一id生成策略
  • 2.1 利用数据库自增字段生成id
  • 2.2 UUID
  • 2.3 Redis生成id
  • 2.4 zookeeper生成ID
  • 2.5 Twitter的snowflake算法
• 3. 面试题目：实现一个全局的ID生成器，注意线程安全
  • 3.1 单例模式分类
  • 3.2 普通懒汉模式单例（线程不安全）
  • 3.3 线程安全懒汉模式单例
  • 3.4 饿汉模式单例

本文章中前面两个章节转载自：

https://cloud.tencent.com/developer/article/1884037

1. 全局唯一id介绍

在复杂的分布式系统中，需要对大量的数据和消息进行唯一标识，在设计的初期就要考虑到日后的数据量的级别，如果需要对数据库进行分库分表，就需要有一个全局唯一id来标识一条数据或记录。

1.1 特点

全局唯一id主要有以下几个特点

• 全局唯一性
• 趋势递增：MySQL InnoDB默认使用的是聚簇索引，底层使用B+ tree的数据结构来存储索引数据，在主键选择上尽量使用有序的主键保证写入性能
• 单调递增：保证下一个ID一定大于上一个ID，例如事务版本号、**IM**增量消息、排序等特殊需求
• 信息安全：如果ID是连续的，恶意用户的爬取工作就非常容易做了，在一些应用场景下，需要ID无规则、不规则。
• 高可用性：同时除了对ID号码自身的要求，业务还对ID号生成系统的可用性要求极高，如果ID系统瘫痪，会带来一场灾难，所以不能有单点故障。
• 分片支持
• 长度适中

2. 常见的全局唯一id生成策略

2.1 利用数据库自增字段生成id

优点

• 简单：成本小，代码简单，性能可以接收
• ID号单调递增，可以实现一些对ID有特殊要求的业务，比如分页或排序等

缺点

• 强依赖DB。数据库迁移、多数据库版本支持、或分库分表时需要处理，比较麻烦
• 单点故障。单个数据库或读写分离或一主多从的情况下，只有一个主库可以生成，有单点故障的风险
• 数据一致性问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。
• 难于扩展。在新能达不到要求的情况下，难以扩展

部分优化方案

对于主库单点，如果有多个Master库，则每个Master库设置的起始数字不一样，步长一样，可以是Master的个数。例如:Master 1生成的是1，4，7，10；Master 2生成的是2，5，8，11；Master 3生成的是3，6，9，12。这样就可以有效生成集群的唯一ID，也可以大大降低ID生成数据库操作的负载

2.2 UUID

常见的id生成方式，利用程序生成

UUID的目的是让分布式系统中的所有元素，都能有唯一的辨识咨询，而不需要透过中央控制端来做辨识资讯的指定。

UUID的标准形式包含32个16进制数字，以‘-’分为5段，示例：550e8400-e29b-41d4-a716-446655440000

C++中使用boost生成uuid的示例

#include <boost/uuid/uuid.hpp>
#include <boost/uuid/uuid_io.hpp>
#include <boost/uuid/uuid_generators.hpp>int main() {boost::uuids::uuid a_uuid = boost:uuids::random_generator();string uuid_string = boost::uuids::to_string(a_uuid);return 0;
}

优点

• 非常简单，本地生成，可以调用API
• 性能很高，没有网络消耗，基本不会有性能问题
• 全球唯一，在数据迁移、系统数据合并等情况下可以从容应对

缺点

• 存储成本高。16字节128位，通常用36长度的字符串表示，海量数据场景下，需要考虑存储量的问题
• 信息不安全。基于MAC地址生成UUID的算法可能造成MAC地址泄漏
• 不适用作为主键
• UUID是无序的
• 传输数据量大
• 不可读

部分优化方案

• 为了解决UUID不可读，可以使用UUID to Int64方法
• 为了解决UUID无序的问题， NHibernate在其主键生成方式中提供了Comb算法（combined guid/timestamp）。保留GUID的10个字节，用另6个字节表示GUID生成的时间（DateTime）。

2.3 Redis生成id

当使用数据库生成ID性能不够要求的时候，可以尝试使用Redis来生成ID，这主要依赖于Redis是单线程的，所以也可以用于生成全局唯一的ID。可以使用Redis的原子操作**INCR和INCRBY**来实现。

可以使用Redis集群来获取更高的吞吐量。假如一个集群中有5台Redis。可以初始化每台Redis的值分别是1,2,3,4,5，然后步长都是5。

优点

• 不依赖数据库，灵活方便，且性能优于数据库
• 数字ID天然排序，对分页或需要排序的结果很有帮助

缺点

• 如果系统中没有Redis，还需要引入新的组件，增加系统的复杂度
• 需要编码和配置的工作量比较大
• Redis单点故障，影响序列服务的可用性

2.4 zookeeper生成ID

zookeeper主要通过其中znode数据版本来生成序列号，可以生成32位和64位的数据版本号，客户端可以使用这个版本号来作为唯一的序列号。

很少会使用zookeeper来生成唯一ID。主要是由于需要依赖zookeeper，并且是多步调用API，如果在竞争较大的情况下，需要考虑分布式锁。因此，性能在高并发的分布式环境下，也不是很理想。

2.5 Twitter的snowflake算法

snowflake（雪花算法）是Twitter开源的分布式ID生成算法，结果是一个long型的ID。这种方案把64-bit分别划分成多段，分开来标识机器、时间等。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sI2XDQmC-1692772460124)(image/image_OUDNHYGCkP.png)]

其核心思想是：使用41bit作为毫秒数，10bit作为机器的ID（5个bit是数据中心，5个bit的机器ID），12bit作为毫秒内的流水号（意味着每个节点在每毫秒可以产生 4096 个 ID），最后还有一个符号位，永远是0。具体实现的代码可以参看github。

snowflake算法可以根据自身项目的需要进行一定的修改。比如估算未来的数据中心个数，每个数据中心的机器数以及统一毫秒可以能的并发数来调整在算法中所需要的bit数。

优点

• 稳定性高，不依赖于数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
• 灵活方便，可以根据自身业务特性分配bit位。
• 单机上ID单调自增，毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。

缺点

• 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。
• ID可能不是全局递增。在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，也许有时候也会出现不是全局递增的情况。

3. 面试题目：实现一个全局的ID生成器，注意线程安全

这是我在最近面试过程中遇到的一道代码题目，个人思路是考察设计模式中的单例模式，考虑线程安全的话需要使用饿汉模式，或者双重检查锁的懒汉模式。

3.1 单例模式分类

单例模式可以分为懒汉和饿汉，两者之间的区别在于创建实例的时间不同

• 懒汉：系统运行时，实例并不存在，只有当需要使用该实例时，才会去创建并使用实例（这种方式需要考虑线程安全）
• 饿汉：指系统一运行，就初始化创建实例，当需要时，直接调用即可（本身就线程安全，没有多线程的问题）

3.2 普通懒汉模式单例（线程不安全）

#include <iostream>
#include <mutex>
#include <pthread.h>using namespace std;class IdGenerator {
public:// 获取单例对象 static IdGenerator* getInstance();// 释放单例，进程退出时调用static void deleteInstance();// 获取唯一IDint getID();
private:IdGenerator();~IdGenerator();// 将拷贝构造函数设为私有，禁止外部拷贝IdGenerator(const IdGenerator& rhs);const IdGenerator& operator=(const IdGenerator& rhs);// 唯一单例对象指针static IdGenerator* m_IdGenerator;// 全局唯一IDint id;
};// 初始化静态成员变量
IdGenerator* IdGenerator::m_IdGenerator = NULL;int IdGenerator::getID() {return id ++;
}IdGenerator* IdGenerator::getInstance() {if (m_IdGenerator == nullptr) {m_IdGenerator = new IdGenerator();}return m_IdGenerator;
}void IdGenerator::deleteInstance() {if (m_IdGenerator) {delete m_IdGenerator;m_IdGenerator = nullptr;}
}IdGenerator::IdGenerator() : id(0) {}
IdGenerator::~IdGenerator() {}

3.3 线程安全懒汉模式单例

双重检查锁

#include <iostream>
#include <mutex>
#include <pthread.h>using namespace std;// 锁对象
std::mutex g_lock;class IdGenerator {
public:// 获取单例对象 static IdGenerator* getInstance();// 释放单例，进程退出时调用static void deleteInstance();// 获取唯一IDint getID();
private:IdGenerator();~IdGenerator();// 将拷贝构造函数设为私有，禁止外部拷贝IdGenerator(const IdGenerator& rhs);const IdGenerator& operator=(const IdGenerator& rhs);// 唯一单例对象指针static IdGenerator* m_IdGenerator;// 全局唯一IDint id;
};// 初始化静态成员变量
IdGenerator* IdGenerator::m_IdGenerator = NULL;int IdGenerator::getID() {return id ++;
}IdGenerator* IdGenerator::getInstance() {if (m_IdGenerator == nullptr) { // 第一重检查std::lock_guard<std::mutex> lock(g_lock);if (m_IdGenerator == nullptr) { // 第二重检查m_IdGenerator = new IdGenerator(); }}return m_IdGenerator;
}void IdGenerator::deleteInstance() {if (m_IdGenerator) {delete m_IdGenerator;m_IdGenerator = nullptr;}
}IdGenerator::IdGenerator() : id(0) {}
IdGenerator::~IdGenerator() {}

3.4 饿汉模式单例

#include <iostream>
#include <pthread.h>using namespace std;class IdGenerator {
public:// 获取单例对象 static IdGenerator* getInstance();// 释放单例，进程退出时调用static void deleteInstance();// 获取唯一IDint getID();
private:IdGenerator();~IdGenerator();// 将拷贝构造函数设为私有，禁止外部拷贝IdGenerator(const IdGenerator& rhs);const IdGenerator& operator=(const IdGenerator& rhs);// 唯一单例对象指针static IdGenerator* m_IdGenerator;// 全局唯一IDint id;
};// 初始化静态成员变量
IdGenerator* IdGenerator::m_IdGenerator = new IdGenerator();int IdGenerator::getID() {return id ++;
}IdGenerator* IdGenerator::getInstance() {return m_IdGenerator;
}void IdGenerator::deleteInstance() {if (m_IdGenerator) {delete m_IdGenerator;m_IdGenerator = nullptr;}
}IdGenerator::IdGenerator() : id(0) {}
IdGenerator::~IdGenerator() {}

参考：

https://blog.csdn.net/fly910905/article/details/79286680