分布式算法

发布日期: 2022-05-12

文章字数: 7.8k

阅读次数:

GoldFlake：与竞争对手斗智斗勇！金毛突发奇想的非连续时间戳雪花算法版本！

1. 前言：

金毛在看雪花算法(Snowflake)的原理的时候，发现它用的主要是毫秒时间戳和当前毫秒内生成的 id 数量来保持有序性。雪花算法在时间上仍然具有连续性，所以我想着如果我要分析使用雪花算法生成 id 的竞争对手的业务规模，那么我其实是可以通过获取一个或多个范围内毫秒时间戳的 id，进而来分析他们的业务规模的。所以金毛就打算改造一下雪花算法，令毫秒时间戳并非一定连续，从而降低竞争对手的分析准确率。

咱给这个算法小命名一下，叫作 GoldFlake。为什么是Gold呢？因为如果你的业务是“金子”做的（形容很重要），不想被竞争对手准确分析的前提下才有必要使用。🍭🍭

2. 雪花算法

这是金毛要改造的雪花算法原型生成 id 示意图：

可能与网上大部分说的不一样，网上说第一位是0，后41位才是毫秒时间戳。那是因为第一位0用来当符号位，0表示正数。但我使用的是 uint64 类型来存储 id，也就是无符号的，所以不需要保留第一位做符号位。

具体雪花算法就不细讲了，实际上很简单，看图也能猜到：uint64 型数值的前42位保存毫秒时间戳，中间10位是机器id号（10位最多可以表示1024台机器，如果有更大的集群可以将机器 id 所占位数调大一些），最后12位是序列号，即在当前毫秒内该机器生成了第几个 id，12位最大可以表示4096个 id，也就是一个毫秒内单台机器最多能生成4096个 id。

雪花算法的源码就不在这里细说，可以到 https://github.com/ncghost1/snowflake-go 仓库查看（Go语言实现）。

3. 传统雪花算法测试

首先写了1s生成id的Test，以及一个go benchmark测试一下传统雪花算法的性能，代码如下：

func TestGenerateId(t *testing.T) {
    count := 0
    var prev uint64 = 0
    Sf, err := snowflake.New(1)
    if err != nil {
        t.Errorf("create snowflake error:%s", err)
        return
    }
    go func() {
        for {
            cur, err := GenerateId(Sf, 1)
            if err != nil {
                t.Errorf("generate id failed,error:%s", err)
                return
            }
            if prev >= cur {
                t.Errorf("invalid id. prev:%d,cur:%d,count:%d", prev, cur, count)
                return
            }
            prev = cur
            count++
        }
    }()
    time.Sleep(time.Second)
    fmt.Println("generate id count:", count)
}
func BenchmarkGenerateId(b *testing.B) {
    Sf, err := snowflake.New(1)
    if err != nil {
        return
    }
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        GenerateId(Sf, 1)
    }
}

以下是运行结果：

generate id count: 266717 // Test 运行结果，计数26W个id
goos: windows
goarch: amd64
pkg: GoldFlake
cpu: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx
// benchmark 测试出来迭代次数约100W次
BenchmarkGenerateId-8            1000000              3738 ns/op
PASS
ok      GoldFlake       5.568s

可以看到 Test 的计数为 26W，用 1s 除以 benchmark 的结果（3738 ns/op）也能得到 26w op/s，所以在我的笔记本电脑上传统雪花算法差不多是每秒能生成 26W 个 id。

但是传统雪花算法在时间上是连续的，而且算法是开源的，如果使用传统的算法容易被对手通过搜集一定范围内的 id 进行业务规模的分析。以下我们来做一个连续生成并输出 id 的测试，看看输出的 id 都是什么样的。（new millisecond 输出表示当前时间到了一个新的毫秒）以下是部分生成的 id 结果：

PS D:\GoldFlake> go test
new Millisecond:
527715426747027456
new Millisecond:
527715426751221760
527715426751221761
527715426751221762
527715426751221763
527715426751221764
527715426751221765
527715426751221766
527715426751221767
527715426751221768
527715426751221769
527715426751221770
527715426751221771
new Millisecond:
527715426755416064
527715426755416065
527715426755416066
527715426755416067
new Millisecond:
527715426759610368
527715426759610369
527715426759610370
527715426759610371
527715426759610372
527715426759610373
527715426759610374
527715426759610375
527715426759610376
527715426759610377

仔细观察你会发现它的变化是比较有规律的，且接近于定长增加的。比如从右到左第6位与第7位，可以看到每到下一个毫秒，它们几乎是以定长增加的（第7位+4，第6位+2），最右边剩下5位虽然也有变化，但是对整体影响不大，实际上我们就只要看变动明显的最高位（第7位）就可以了。从这个可以看出每一个毫秒第7位的平均变化步长为4（少数情况下可能达到5），所以可以利用这个步长大致断定某个时间生成 id 的时间戳部分，然后用爬虫之类的技术获取一个时间范围内的所有 id。收集多个时间段的 id 数量后，就可以对业务规模进行推断了。当然如果用传统雪花算法，还可以被更精确地分析时间戳范围（从算法上反推），总之传统雪花算法生成 id 是会有被准确分析的风险存在的。

4. GoldFlake

4.1 引出

GoldFlake 是金毛睡前躺在床上突发奇想想出来的一个改造传统雪花算法的方法（那晚上金毛想得兴奋只睡了1小时，第二天还精神得神…）。

从上面的分析得知，因为雪花算法源码公开且生成有规律的原因，是能被准确分析的。所以金毛想到，如果要把算法开源而且知道了也不能被准确分析，那么需要给算法增加随机性，即要让 id 做到非连续性。

那么这个非连续性要对雪花算法生成的 id 哪个部分进行下手呢？我刚开始是想着对最末尾的部分——序列号下手，但是后来换位思考了一下，如果我来做分析，肯定是按毫秒时间戳的范围来搜集 id 数量的，序列号就算做到了非连续性对分析的迷惑程度也是几乎没有的！所以最终金毛打算对毫秒时间戳的部分下手！

4.2 GoldFlake 方案一：随机时间戳偏移量

这是一个最简单的方法，我们只需要对 SnowFlake 生成 id 时给毫秒加上一个随机偏移量，如下方代码所示：

// 单节点 SnowFlake
type SingleSnowFlake struct {
    lastTimestamp uint64 // 最后一次生成的毫秒时间戳
    sequence      uint32 // 序列号
    workerId      uint32 // 机器id
    timeOffset       uint64 // 毫秒时间戳偏移量
    maxTimeOffset uint64 // 最大毫秒时间戳偏移量增量
    lock          sync.Mutex // mutex锁
}

func (sf *SingleSnowFlake) Generate() (uint64, error) {
    // 需要使用 mutex 保证并发安全性
    sf.lock.Lock()
    defer sf.lock.Unlock()

    // 获取当前毫秒时间戳
    t := timestamp()

    // 设置随机种子
    rand.Seed(time.Now().UnixNano())

    // 使用随机数，这里是有 1/3 的概率需要增加随机偏移量
    if rand.Intn(3) == 0 {
        
        // 随机获取偏移量增量，范围为 1~maxTimeOffset，本例中maxTimeOffset = 5
        sf.timeOffset += rand.Uint64()%sf.maxTimeOffset+1
    }

    // ts 为生成id的毫秒时间戳，为实际时间戳 t 加上 timeOffset
    ts := t + sf.timeOffset
    if ts == sf.lastTimestamp {
        sf.sequence = (sf.sequence + 1) & MaxSequence
        if sf.sequence == 0 {
            ts = sf.waitNextMilli(ts) + sf.timeOffset
        }
    } else {
        sf.sequence = 0
    }

    if ts < sf.lastTimestamp {
        return 0, errors.New("invalid system clock")
    }
    sf.lastTimestamp = ts
    return sf.pack(), nil
}

这个实现方法很简单，增加了 timeOffset 一个字段，让生成 id 真正使用的毫秒时间戳为当前毫秒时间戳加上 timeOffset，而 timeOffset 是不确定的值，每次随机决定是否要增加 timeOffset，并且再通过随机决定增量。接下来我们测试一下它的性能：

generate id count: 118099
goos: windows
goarch: amd64
pkg: GoldFlake
cpu: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx
BenchmarkGenerateId-8              56720             19493 ns/op
PASS
ok      GoldFlake       3.149s

可以看到改动后，每秒生成id数从26W降到了11W，性能降了一倍多！（不过我个人认为11W/s也是够支撑大部分业务了的）。接下来我们再看看连续使用它输出的 id：

new Millisecond:
527735818723266560
527735818723266561
527735818723266562
new Millisecond:
527735818731655168
new Millisecond:
527735818735849472
new Millisecond:
527735818740043776
new Millisecond:
527735818744238080
new Millisecond:
527735818756820992 
new Millisecond:
527735818769403904 
new Millisecond:
527735818781986816
new Millisecond:
527735818790375424
new Millisecond:
527735818794569728

我们观察每个 new Millisecond 的第一个 id 与前一个毫秒下的 id，可以发现到这回的增量是不定的，有多有少。这样的随机性会令对手想要获取一个时间段的 id 时，这个时间段往往不是实际的时间段，这样就能做到令对手无法准确判断你的业务规模了。

这样的改造方法很简单，它适用于单台机器单线程生成 id 10w左右即可的需求场景（当然服务器生成 id 一般要比我的笔记本快很多），并且能在即使生成算法公开的情况下，竞争对手也无法正确分析。当然它的槽点也是挺多的，为了防分析竟然损失了这么多的性能，还有因为时间戳正偏移的原因，能使用的 id 也减少了，这个减少量和可以自定义设置的增加时间戳概率和时间戳最大增量有关。还好传统雪花算法的基础很好，所以即使性能和可用 id 数量衰减后也是能适用于大多数业务的。

我知道大家都会觉得，为了防止不太可能存在的竞争对手分析就损失一倍以上的性能，同时大大降低可用 id 数量可太逊了！不需要达到原本的性能或更好性能的话，这种规模的业务也没多大可能会被竞争对手当作主要目标吧！那么还有让性能和可用 id 比本方案更多点的方案吗？当然是有滴辣！🍭🍭

4.3 GoldFlake 方案二引出：分割随机偏移过程+并发/并行计算+模拟栈

在方案一中无论如何，生成 id 的例程在生成 id 前都需要“抽奖”决定自己是否需要偏移时间戳，每次都要经历一个：放随机种子->生成随机数决定需要偏移->生成随机数决定偏移增量 这么一个过程。然而实际上我们不需要每次生成 id 前都进行一个这样的过程。想想如果我们想要一个非连续时间戳的雪花算法版本应该满足什么条件：

每个毫秒的最大生成 id 数是稳定的
在方案一中，每次生成 id 前都要决定是否将毫秒时间戳向后跳跃，所以我们几乎是不可能利用完所有序列号的，在示例用的 1/3 概率下，每个毫秒能够生成的 id 数基本不超过3个，这样会大大降低可用 id 数量，这种损失我们基本上是无法接受的。

性能应接近传统雪花算法
在方案一中，性能被砍了比1倍还多，这样可能已经把分布式 id 生成算法的重要条件之一：“高QPS” 给砍掉了，想让一个团队采用你的分布式 id 生成算法几乎是不可能了，想想自己是架构师也不会选择这样的”垃圾“算法😥😥，不说超过传统雪花算法的性能，至少要接近吧。
或者我们简单可以形容一下我们应该想要的版本是什么样的：

在轮到下一个毫秒的时候，在我们所定义的最大毫秒时间戳偏移量内随机进行偏移（或不偏移）即可。
我认为一般需求就是这样，我们并不需要频繁地进行偏移，只需要每毫秒考虑一次是否偏移就足够了，我们应该优先保证高性能和高可用，然后才是所谓的”迷惑性“。接下来我们再重新改造一下方案一：

4.4 GoldFlake 方案二设计与实现

首先再来看看我们的需求：在轮到下一个毫秒的时候，在我们所定义的最大毫秒时间戳偏移量内随机进行偏移（或不偏移）。

我们在方案一中是每次生成 id 时都要执行一次随机偏移过程，每次生成 id 都有可能发生偏移。而我们的需求只是每毫秒执行一次随机偏移过程就够了。那么我们就将这个过程分割出来吧，然后咱让服务端机器给它一个 goroutine 与生成 id 分割开来执行，并且使用 Sleep 函数每毫秒执行一次，伪代码如下：

go func(){
    RandProcess() // 随机偏移过程
    time.Sleep(time.Millisecond) // 睡眠1毫秒
}()

这样我们就做到了分割随机偏移过程 ，其次如果是单核机器或者设置了 runtime.GOMAXPROCS(1)，那么我们这里是并发计算 。而如果是多核且 GOMAXPROCS 设置大于1,即使用了多核心这里就是并行计算 。实际上因为我们在这里每次睡眠了1毫秒，即使在单核心情况下也和多线程性能相差不大，所以单核也可以放心使用。

那么我们将随机偏移过程分割之后还有一个问题，用什么方法将随机偏移量结果通知给生成 id 的执行函数？我们可以设置一个全局变量，执行选择随机偏移量的函数负责设置它，生成 id 的函数去获取它。那么这个全局变量该是什么类型呢？如果只是单个变量，那么就只能满足单个线程下的生成 id 函数使用，如果是采用多线程来生成 id 呢？所以金毛的方案就这么出来了：

我们使用一个全局的能够容纳多个随机偏移量的容器，然后我们对获取顺序没有硬性要求，所以我们既可以使用栈也可以使用队列做容器。因为模拟栈的实现要更简单一些，所以金毛使用了模拟栈，以下是关于该容器的结构体定义：

type RandValStack struct{
    RandVal []uint64 // uint64切片，存储随机偏移量
    top uint32 // 栈顶索引
    Size uint32 // 栈的大小
    lock sync.Mutex // 互斥锁，用于栈的并发安全
}
var RVStack RandValStack // 全局变量

我们再具体设计并实现一下相关的函数，首先我们需要一个栈的初始化函数：

func InitRandValStack(Size uint32){
    RVStack.lock.Lock() // 加锁
    defer RVStack.lock.Unlock() // 延迟释放锁（函数退出前释放）
    RVStack.RandVal = make([]uint64,Size) // 初始化切片空间
    RVStack.top = 0 // 栈顶索引初始化为 0
    RVStack.Size = Size // 栈大小设置为入参
}

还要设计并实现最重要的随机偏移量选取的过程执行函数，实际上就是一个随机决定是否向栈中填充元素的函数，金毛做了一个简单实现，如下：

/* 参数说明:
 * chanceNumerator 概率分子 
 * chanceDenominator 概率分母 
 * 我们这里决定是否要填充栈的概率用分数表示
 * maxxTimeOffset 最大毫秒时间偏移量 */
func FillWithRandValStack(chanceNumerator,chanceDenominator,maxTimeOffset uint64){
    rand.Seed(time.Now().UnixNano()) // 设置随机种子
    RVStack.lock.Lock() // 加锁
    defer RVStack.lock.Unlock() //延迟释放锁（函数退出前释放）

    // 当栈空间不满 且 随机结果满足概率范围之内 则填充栈
    if     RVStack.top  < RVStack.Size && rand.Uint64() % chanceDenominator < chanceNumerator {
        // 随机在 1 ~ maxTimeOffset 范围内取偏移量
        offset := rand.Uint64() % maxTimeOffset + 1
        RVStack.RandVal[RVStack.top] = offset 
        RVStack.top  ++
    }
}

与此同时，用于生成 id 的函数逻辑也需要修改，我们需要加一个取栈顶的逻辑，如下：

// 注意这里结构体名称 Snowflake 改成了 GoldFlake
func (gf *GoldFlake) Generate() (uint64, error) {
    gf.lock.Lock() // GoldFlake 加锁
    defer gf.lock.Unlock() // GoldFlake 延迟释放锁
    RVStack.lock.Lock() // 栈加锁

    // 栈顶大于0时表示栈内有随机偏移量，需要发生偏移
    if RVStack.top  > 0 {
        // 令总偏移量 timeOffset 加上栈顶的偏移量
        gf.timeOffset += RVStack.RandVal[RVStack.top-1]
        RVStack.top -- // 栈顶位置 -1
    }
    RVStack.lock.Unlock() // 栈释放锁
    ts := timestamp() + gf.timeOffset // 计算生成 id 用的时间戳（逻辑时间戳）

    // 与上一次生成的逻辑毫秒时间戳相同（在同一毫秒内）
    if ts == gf.lastTimestamp {
        gf.sequence = (gf.sequence + 1) & MaxSequence // 序列号+1
        
        // 如果序列号 +1 后等于0，说明超出最大序列号范围
        if gf.sequence == 0 {
            // 等待至下一毫秒生成 id
            ts = gf.waitNextMilli(ts)+gf.timeOffset
        }
    
    // 与上一次生成的毫秒时间戳不相同（到了下一个毫秒）
    } else {
        gf.sequence = 0 // 序列号清零
    }

    // 当前逻辑毫秒时间戳小于上次的逻辑毫秒时间戳，发生了时钟跳跃，报错
    if ts < gf.lastTimestamp {
        return 0, errors.New("invalid system clock")
    }
    gf.lastTimestamp = ts // 更新上一次生成 id 的逻辑时间戳为本次的逻辑时间戳

    // 调用 pack 将时间戳，机器id，序列号三部分打包成 id 并返回
    return gf.pack(), nil 
}

这下大功告成啦！咱们写一个测试看看性能，看看它每秒能生成多少个 id！

// 并行测试
func TestGenerateId(t *testing.T) {
    count := 0 // 生成id计数值
    var workerid uint32 = 1 // 机器id
    var maxtimeoffset uint64 = 5 // 最大随机毫秒时间偏移量
    var stacksize uint32 = 5 // 栈空间大小，这里空间设置得对于单个生成线程有些冗余
    Sf, err := Goldflake.New(workerid, maxtimeoffset)
    if err != nil {
        t.Errorf("create goldflake error:%s", err)
        return
    }
    runtime.GOMAXPROCS(2) // 设置可用CPU核心数为 2
    Goldflake.InitRandValStack(stacksize)
    go func() {
        for {
            snowflake.FillWithRandValStack(1, 2, maxtimeoffset)
            time.Sleep(time.Millisecond)
        }
    }()
    go func() {
        for {
            _, err := GenerateId(Sf, 1)
            if err != nil {
                t.Errorf("generate id failed,error:%s", err)
                return
            }
            count++
        }
    }()
    time.Sleep(time.Second) // 测试时间为 1s
    fmt.Println("generate id count:", count)
}

// Benchmark
func BenchmarkGenerateId(b *testing.B) {
    var workerid uint32 = 1
    var maxtimeoffset uint64 = 5
    var stacksize uint32 = 5
    runtime.GOMAXPROCS(2)
    Sf, err := Goldflake.New(workerid, maxtimeoffset)
    if err != nil {
        return
    }
    Goldflake.InitRandValStack(stacksize)
    b.ResetTimer()
    go func() {
        for {
            Goldflake.FillWithRandValStack(1, 2, maxtimeoffset)
            time.Sleep(time.Millisecond)
        }
    }()
    for i := 0; i < b.N; i++ {
        GenerateId(Sf, 1)
    }
}

以下是测试结果：

PS D:\GoldFlake> go test -bench.
generate id count: 289629
goos: windows
goarch: amd64
pkg: GoldFlake
cpu: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx
BenchmarkGenerateId-8            1000000              3430 ns/op
testing: BenchmarkGenerateId-8 left GOMAXPROCS set to 2
PASS
ok      GoldFlake       4.524s

Wow!看到了吗？每秒生成 id 数大约29W ，benchmark 的 3430 ns/op 可以换算成每秒生成 291545 个 id，竟然恢复到了原来的性能水平左右！甚至还比咱之前测试的26W多3W，不过我认为这是有误差所以不能说是比原来还要快，但是可以说已经几乎相同了！💪💪

我们再将GOMAXPROCS 设为1，进行单核测试看看测试结果：

PS D:\GoldFlake> go test -bench.
generate id count: 272702
goarch: amd64
pkg: GoldFlake
cpu: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx
BenchmarkGenerateId-8            1000000              3685 ns/op
testing: BenchmarkGenerateId-8 left GOMAXPROCS set to 1
PASS
ok      GoldFlake       4.794s

Wow!单核情况下每秒生成 id 计数是 272702，3685 ns/op 换算成每秒生成271,370 个 id，可以看到该测试结果也说明了即使在单核情况下，它的性能依然几乎等同于传统雪花算法！

除了性能之外，我们还需要检查它生成的 id 在毫秒时间戳部分的跨度是否随机，还有每毫秒下连续生成 id 数是否足够多，我们打印看看它生成的 id 。

new Millisecond:
59392691015680
59392691015681
59392691015682
59392691015683
59392691015684
59392691015685
59392691015686
59392691015687
59392691015688
59392691015689
59392691015690
59392691015691
new Millisecond:
59392695209984
59392695209985
59392695209986
59392695209987
59392695209988
59392695209989
59392695209990
59392695209991
59392695209992
59392695209993
59392695209994
59392695209995
59392695209996
new Millisecond:
59392699404288
59392699404289
59392699404290
59392699404291
59392699404292
59392699404293
new Millisecond:
59392703598592
59392703598593
59392703598594
59392703598595
59392703598596
59392703598597

这是金毛随便截的一部分结果，同毫秒连续生成 id 是有了，但是好像时间戳跨度都一样了？我们在栈 push 和 pop 的时候输出一下，看看到底一秒有多少次发生了 push 和 pop，以下是测试结果：

// 双核情况下测试
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [1 0 0 0 0]
pop: [1 0 0 0 0]
Push: [1 0 0 0 0]
pop: [1 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [1 0 0 0 0]
pop: [1 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [1 0 0 0 0]
pop: [1 0 0 0 0]
Push: [1 0 0 0 0]
pop: [1 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [5 0 0 0 0]
pop: [5 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [1 0 0 0 0]
pop: [1 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [4 0 0 0 0]
pop: [4 0 0 0 0]
Push: [3 0 0 0 0]
pop: [3 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]
Push: [2 0 0 0 0]
pop: [2 0 0 0 0]

金毛大概数了数在35个左右，1000ms 里竟然只有35个随机偏移量被压栈？这和我们原本设想的不一样啊，1000ms 内执行1000次，二分之一的概率平均500个压栈左右吧！为什么会只有35个呢？我上网搜索了一下，总结出以下原因：

（1）Sleep 不够准确，和OS调度有关。

（2）金毛是在win下测试的，网上有人说 win 最少 sleep 时间间隔在 10~13 ms，按这个原因来就能解释 1000 ms 内为什么只有35个随机偏移量被压栈了。

这样的话，原来性能能与传统雪花算法几乎相同的原因就是随机次数少啊！有点尴尬…我们来测试一下我的win10在1秒内，每次执行睡眠 1ms 能执行多少次。

func main() {
    var cnt uint64 = 0
    go func() {
        for {
            cnt++
            time.Sleep(time.Millisecond)
        }
    }()
    time.Sleep(time.Second)
    fmt.Println(cnt)
}

测试结果（4次）：

我真是无语了…才执行了66次左右，不知道为什么我的 win10 这么垃圾…当然也许也是因为我的后台进程太多，所以我把这个代码放到了 ubuntu 云服务器上再做个测试：

// ubuntu 测试结果（5次）
root@iZj6c7ajkft5134m4zbf3vZ:~# go run main.go 
883
root@iZj6c7ajkft5134m4zbf3vZ:~# go run main.go 
915
root@iZj6c7ajkft5134m4zbf3vZ:~# go run main.go 
914
root@iZj6c7ajkft5134m4zbf3vZ:~# go run main.go 
886
root@iZj6c7ajkft5134m4zbf3vZ:~# go run main.go 
914

还是Ubuntu正常一点啊！平均执行了900次左右，已经接近 1ms 1次了。服务端大多数都是 Linux 系统，所以接下来我们再用 Ubuntu 做个正经的算法改造测试！

4.5 Ubuntu 测试

首先还是测试传统雪花算法性能：

root@iZj6c7ajkft5134m4zbf3vZ:~/go/src/GoldFlake# go test -bench=.
generate id count: 4030792
goos: linux
goarch: amd64
pkg: GoldFlake
BenchmarkGenerateId-2        4933039           273 ns/op
testing: BenchmarkGenerateId-2 left GOMAXPROCS set to 1
PASS
ok      GoldFlake    2.598s

可以看到 1s 生成了400W个 id！273 ns/op 换算下来是一秒生成了 3663003个 id ，好家伙，这可只是双核轻量级云服务器啊，可见我的win笔记本太垃圾了啊！！！

好吧，接下来我们再测试方案一：

root@iZj6c7ajkft5134m4zbf3vZ:~/go/src/GoldFlake# go test -bench=.
generate id count: 100887
cnt: 0
goos: linux
goarch: amd64
pkg: GoldFlake
BenchmarkGenerateId-2          58946         21278 ns/op
testing: BenchmarkGenerateId-2 left GOMAXPROCS set to 1
PASS
ok      GoldFlake    3.421s

震惊，原来方案一和我的笔记本都一样慢！21278 ns/op 也太夸张了，看来真不能整每次生成 id 时都生成随机数啊！不过我也挺奇怪为什么运行速度差这么巨大的两台机器，在这个方案会结果差不多呢？emm…还是先测方案二吧：

// 单核情况
root@iZj6c7ajkft5134m4zbf3vZ:~/go/src/GoldFlake# go test -bench=.
generate id count: 5403977
Rand process cnt: 652
goos: linux
goarch: amd64
pkg: GoldFlake
BenchmarkGenerateId-2        3814839           290 ns/op

这里增加了一条输出：”Rand process cnt: 652“，监测 1s 内执行了多少次随机过程函数，单核这里显示的是652，1/2的概率平均下来应该会有 326 个左右的随机数满足概率，这样的数量还是可以接受的。这回生成了 5403977 个 id？比传统雪花算法多了一些，再看看 benchmark 测试的结果为 290 ns/op，比传统雪花算法测试时出现的 273 ns/op 慢了一些些，其实这些都在误差允许的范围之内，应该说它们的性能依然是差不多的。接下来我们再看看双核情况的测试：

// 双核情况
generate id count: 5812648
Rand process cnt: 804
goos: linux
goarch: amd64
pkg: GoldFlake
BenchmarkGenerateId-2        3805255           314 ns/op
testing: BenchmarkGenerateId-2 left GOMAXPROCS set to 1
PASS
ok      GoldFlake    2.522s

可以看到双核下 “Rand process cnt：804” 比单核增多了，我们这回只考虑 benchmark 的数据，314 ns/op 还是与单核与传统雪花差不多的。

4.6 GoldFlake 方案三：使用信号量改造方案二

金毛想到就算在 linux 系统上，Sleep 1ms 还是很难做到很精确的，我们应该放弃使用 Sleep 的方法。那么我们可以使用一个信号量，在每到一个新毫秒的时候就可以执行获取随机偏移量的函数。我决定将它加在存储随机偏移量的栈中：

// Random Value(TimeOffset) Stack
type RandValStack struct {
    RandVal []uint64
    top     uint32
    Size    uint32
    Sign    int8 // 信号量，为 1 时可以执行获取随机偏移量操作
    lock    sync.Mutex
}

我们规定 Sign 为1时可以执行获取随机偏移量操作，接下来我们先在初始化栈的函数中增加对 Sign 的初始化：

func InitRandValStack(Size uint32) {
    RVStack.lock.Lock()
    defer RVStack.lock.Unlock()
    RVStack.RandVal = make([]uint64, Size)
    RVStack.top = 0
    RVStack.Size = Size
    RVStack.Sign = 1
}

我们在 FillWithRandValStack 函数中首先判断 Sign 是否等于 1，如果等于1则说明到了新毫秒，做一次随机数生成操作。

func FillWithRandValStack(chanceNumerator, chanceDenominator, maxTimeOffset uint64) {
    rand.Seed(time.Now().UnixNano())
    RVStack.lock.Lock()
    defer RVStack.lock.Unlock()
    if RVStack.Sign == 1 {
        if RVStack.top < RVStack.Size && rand.Uint64()%chanceDenominator < chanceNumerator {
            offset := rand.Uint64()%maxTimeOffset + 1
            RVStack.RandVal[RVStack.top] = offset
            RVStack.top++
            RVStack.Sign = 0
        } else {
            RVStack.Sign = 0
        }
    }
}

最后我们在 Generate 函数也要增加 Sign 的更改，在 ts != gf.lastTimestamp 时，说明到达了新毫秒（排除发生时间跳跃），那我们就可以将 Sign 设为 1。

func (gf *GoldFlake) Generate() (uint64, error) {
    gf.lock.Lock()
    defer gf.lock.Unlock()
    RVStack.lock.Lock()
    if RVStack.top > 0 {
        gf.timeOffset += RVStack.RandVal[RVStack.top-1]
        RVStack.top--
    }
    RVStack.lock.Unlock()
    ts := timestamp() + gf.timeOffset
    if ts == gf.lastTimestamp {
        gf.sequence = (gf.sequence + 1) & MaxSequence
        if gf.sequence == 0 {
            ts = gf.waitNextMilli(ts) + gf.timeOffset
        }
    } else {
        RVStack.Sign = 1 // 到达新时间戳，设为1
        gf.sequence = 0
    }

    if ts < gf.lastTimestamp {
        return 0, errors.New("invalid system clock")
    }
    gf.lastTimestamp = ts
    return gf.pack(), nil
}

这样就改造完啦，我们首先来测试 Ubuntu 单核情况下的算法性能：

root@iZj6c7ajkft5134m4zbf3vZ:~/go/src/GoldFlake# go test -bench=.
generate id count: 136822
Rand process cnt: 95968
goos: linux
goarch: amd64
pkg: GoldFlake
BenchmarkGenerateId-2         291802          6718 ns/op

可以看到单核性能还是很差，6718 ns/op 换算下来是每秒 14W，不过对比方案一夸张的 21278 ns/op 还是好很多，因为每个新毫秒时间戳只用生成一回随机数。但是！与原来的每秒 400W 相比还是远远不够啊！不过不用担心，我们这回因为把获取随机偏移量的函数分割开来了，所以双核能够很好的派上用场，让我们看看双核下的测试：

generate id count: 6078560
Rand process cnt: 92944
goos: linux
goarch: amd64
pkg: GoldFlake
BenchmarkGenerateId-2        3619393           326 ns/op
PASS
ok      GoldFlake    2.527s

在双核情况下我们可以看到性能有很大的提升，326 ns/op 已经说明很接近原来的雪花算法性能了！接下来我们再打印生成的 id，看看它的非连续性，以下是金毛截的部分：

188985234165792
188985234165793
188985234165794
188985234165795
188985234165796
188985234165797
188985234165798
188985234165799
188985234165800
188985234165801
188985234165802
188985234165803
188985234165804
188985234165805
188985238360064 // new Millisec
188985246748672 // new Millisec
188985263525888 // new Millisec
188985276108800 // new Millisec
188985284497408 // new Millisec
188985284497409
188985284497410
188985284497411
188985284497412
188985284497413
188985284497414

咱们可以看到上面的部分发生了连续的偏移，并且连续偏移中每次的偏移值都不同。在方案三中由于每到一个新的毫秒时间戳就做一次随机决定是否偏移，所以发生的偏移次数还是能够贴近我们设定的概率的（本例中设定的是 1/2，上面连续偏移多次属于比较罕见了）。

5. GoldFlake 方案总结

金毛在设计与实现 GoldFlake 的过程中一共想了三种方案，以上已经讲完这三种方案的具体内容以及测试结果，接下来做个总结：

方案一：
是最简单的方案，简单粗暴容易实现，但是也是最惨的方案，生成id数和性能双双被大砍，极不推荐！

方案二：
是一种相对来说比较节省 CPU 资源的一种方案，性能与传统雪花算法相差无几。但是使用前需要测一测获取随机偏移量的函数在 sleep 的情况下能在1s内大概能跑多少次，并且根据自身需求来考虑是否该执行次数是否足够0。

方案三：
在双核以上情况下能够发挥最好的性能，与传统雪花算法相差无几，并且能够做到（几乎）考虑了每一个新毫秒时间戳的随机偏移量，是最接近原先设想需求的方案，若机器能够为生成id分配双核以上，推荐使用该方案。

6. 杂谈

虽然做了那么多研究，但是估计还是不会有人用的吧。实际上只要服务端将id加密后传给前端，接受前端的加密id时再解密就可以完美防竞对分析了。不过如果加密解密要比生成分布式id慢很多的话，需要传递加密id和解密id的QPS又很高，不妨试试咱们的GoldFlake，非连续的分布式id生成方案！🍭🍭

本篇文章中金毛实现的代码还是比较简陋且不够标准，等有时间了金毛会把方案二和方案三完善一些，然后放到 github 上开源让大家吐槽吐槽的🍦🍦

金毛败犬

http://eririspace.cn/2022/05/12/GoldFlake/