C++实现雪花算法(SnowFlake)产生唯一ID

SnowFlake雪花算法简介

SnowFlake 中文意思为雪花，故称为雪花算法。最早是 Twitter 公司在其内部用于分布式环境下生成唯一 ID。在2014年开源 scala 语言版本。

雪花算法的原理就是生成一个的 64 位比特位的 long 类型的唯一ID。

• 最高 1 位固定值 0，因为生成的ID是正整数，如果是 1 就是负数了。
• 接下来 41 位存储毫秒级时间戳，2^41/(1000*60*60*24*365)=69，大概可以使用 69 年。
• 再接下 10 位存储机器码，包括 5 位 datacenterId 和 5 位 workerId。最多可以部署 2^10=1024 台机器。
• 最后 12 位存储序列号。同一毫秒时间戳时，通过这个递增的序列号来区分。即对于同一台机器而言，同一毫秒时间戳下，可以生成 2^12=4096 个不重复 ID。

总的来说就是一个机房，一台机器,在同一号毫秒时产生的ID，可能在同一秒钟产生不同的ID，最后12bit序列号可以区分在同一秒钟的不同ID。

算法优点

雪花算法有以下几个优点：

• 高并发分布式环境下生成不重复 id，每秒可生成百万个不重复 id。
• 基于时间戳，以及同一时间戳下序列号自增，基本保证 id 有序递增。
• 不依赖第三方库或者中间件。
• 算法简单，在内存中进行，效率高。

SnowFlake雪花算法C++实现

使用VS2015创建一个名为“SnowFlakeTest”Win32工程，并编写测试代码：

// SnowFlakeTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "SnowFlake.h"
#include <iostream>
using namespace std;

int main(int argc, char const *argv[])
{
	SnowFlake snow;
	snow.SetMechine(1024);
	for (int i = 0; i < 1000; ++i)
	{
		cout << snow.UniqueId() << endl;
	}
	return 0;
}

SnowFlake.h文件：

class SnowFlake
{
public:
	SnowFlake()
	{
		m_seqMask = ~(-1L << 10);
		m_lasttm = TimeMs();
	}
	virtual ~SnowFlake() {}

	int64_t UniqueId();
	int64_t TimeMs();
	int64_t PId();

	void SetMechine(int64_t mechine)
	{
		m_mechine = mechine;
	}
	int64_t NextMs(int64_t now);

private:
	int64_t m_seq{ 0 };
	int64_t m_mechine;
	int64_t m_lasttm{ -1L };
	int64_t m_seqMask;
	int64_t m_epoch{ 1546272000000L }; // 起始时间戳 2019-01-01
};

核心算法代码：

int64_t SnowFlake::UniqueId()
{
	int64_t now = TimeMs();
	if (now == m_lasttm)
	{
		m_seq = (m_seq + 1) & m_seqMask;
		if (m_seq == 0)
		{
			now = NextMs(now);
		}
	}
	else
	{
		m_seq = 0; //最大为1024
	}
	m_lasttm = now;
	int64_t pid = PId();
	int64_t uid = (now - m_epoch) << 22 | m_mechine << 16 | pid << 10 | m_seq;
	return uid;
}

运行结果：