GoldFlake：详细解读本地持久化功能 GRF！

分布式 分布式id生成
分布式算法
发布日期:   2022-05-20
文章字数:   959
阅读次数:  

GoldFlake：详细解读本地持久化功能 GRF！

前言：

  本来上一次更新完API文章之后，我已经认为GoldFlake已经没有什么需要再改的了。但是我在上课的路上突然想到了一个严重的问题！因为GoldFlake是有记录时间偏移量的，如果机器宕机重启了那么这个内存中的变量不就丢失了吗？这是一个严重的问题，如果丢失了 timeOffset 数据，如果重启后直接继续生成id，可能会因为还在之前的偏移时间内而发生id重复无法入库，就算选择等待一段时间再继续使用重启的机器，我们将无法确定到底该什么时候开始继续使用。因为偏移量完全就是随机的，可能很大也可能很小。所以…很遗憾，金毛的GoldFlake居然生成个id还需要做持久化。（本来就不会有人用这个玩意生成id了，这下不就更没人用了吗！）既然是自己造出来的GoldFlake，跪着也要做到让它能用！所以…金毛目前已经为GoldFlake提供了本地的持久化功能——GRF！这下估计是史上最复杂的分布式id生成算法诞生了！！！

1. 一些可行的持久化方案：

  1. 生成id的机器进行本地持久化，将毫秒时间戳偏移量本地保存。重启恢复的时候最为快速，但会降低生成id性能。
  2. 重启恢复的时候通过数据库查表，找出最大（最新）的id，计算取出前42位毫秒时间戳部分，通过与当前毫秒时间戳相减，得出需要的偏移量。
    但是这个方法还要注意其它因素，如果id是异步入库的，那么最新的id可能会在消息队列中，需要考虑这种情况做出调整。
  3. 将最大（最新）的id放到缓存层中（如Redis），通过缓存查找id比数据库查表的速度通常要快得多。不过要注意更新顺序，如果id先在缓存上更新再到数据库更新，
    这个方法才比较安全。

  第二个和第三个方案是利用GoldFlake之外的介质进行持久化，不会导致GoldFlake的性能降低，如果有条件的话是推荐使用的持久化方案。第一个是由GoldFlake的内部代码提供的本地持久化，也是金毛需要创造的持久化功能！

2. GRF 原理

  金毛为GoldFlake提供了持久化功能GRF(GoldFlake Recovery File)，GRF又分有两种持久化策略和两种持久化文件格式，本节就来介绍一下什么是GRF：

2.1 GRF 策略：FSync/TSync

  GRF 提供的第一个策略为 FSync(FullSync)，即完全同步。

  在FSync策略下，每一个 GoldFlake 节点的 timeoffset 更新时都进行持久化。

  GRF 提供的第二个策略为 TSync(ThresholdSync)，即阈值式同步。

  在TSync策略下，每一个 GoldFlake 节点的 timeoffset 超过阈值（tSyncThreshold）的倍数时进行持久化（默认阈值为10000）。在 TSync 策略下重启恢复时，恢复的 timeoffset 为本地保存的 timeoffset 再加上 tSyncThreshold（阈值），这样做一定不会比之前的id小，以确保生成的id可用（顺序更大且不重复）。

  源码部分：

if RVStack.top > 0 {
        RVStack.top--
        gf.timeOffset += RVStack.randVal[RVStack.top]

        // 如果开启了GRF，在 timeOffset 被更新后则调用 
        // GRFUpdateTimeOffset 进行持久化
        if GrfEnable == GRFEnable {
            GRFUpdateTimeOffset(gf.workerId, gf.timeOffset)
        }
    }

func GRFUpdateTimeOffset(workerId uint32, timeOffset uint64) {
    // TSync 策略下，当 timeOffset 超过之前保存的 timeOffset 加上阈值时
    // 进行本地GRF文件的写入
    if GrfStrategy == TSync {
        if GrfLastupdatedtimeoffset[workerId]+tSyncThreshold <= timeOffset {
            GrfLastupdatedtimeoffset[workerId] = timeOffset
            writeTimeOffsetInGRF(workerId, timeOffset)
        }
    // FSync 策略下一定写入本地GRF文件
    } else if GrfStrategy == FSync {
        writeTimeOffsetInGRF(workerId, timeOffset)
    } else {
        panic("GRF error: unknown 'strategy'")
    }
}

2.2 GRF 格式：ALL/MAX

  GRF 还提供了两种持久化格式： ALL 和 MAX.

  首先两种持久化格式都需要在最开头存储策略（Strategy）和格式（Format）信息，示例如下：

S: // Strategy
TSYNC
F: // Format
MAX

Format ALL：

  ALL 格式会存储所有不同 GoldFlake 节点的 workerid 与 timeoffset 信息，格式如下：

S:
FSYNC
F:
ALL
W:1 T:6 // workerid:1 timeoffset:6
W:2 T:2

Format MAX（默认）：

MAX 格式只存储所有 GoldFlake 节点中最大的 timeoffset 信息，所有 GoldFlake 节点恢复时 timeoffset 将都恢复成保存的最大值（TSync 下还要加上阈值），格式如下：

S:
TSYNC
F:
MAX
T:446 // timeoffset:446

  Format ALL 和 FSync 共同的优点是能够利用更多的可用id数量，缺陷都在于性能开销更大。

  而 Format MAX 和 TSync 共同的优点都是开销较少，缺陷都是能够利用的id数量更少。因为 TSync 的恢复方式将可能跳过一定数量的可用id，MAX 格式的恢复也可能会跳过其他 GoldFlake 节点的可用id。

  详细解释一下这个跳过可用id是什么意思：举个明显的例子，在TSync策略下，假如阈值为20000(20s)，worker1在timeoffset到达20001时第一次超过20000，被保存了下来。而它在生成id到timeoffset为21000时宕机重启。按照我们的TSync恢复策略，它的timeoffset会被恢复成保存下来的timeoffset(20001) + tSyncThreshold(20000) = 40001。如果重启时间花了9s,那么将有大约10s的可用id会被直接跳过，无法被利用。（tSyncThreshold 过小影响性能，过大则能够利用的可用id数量越少，但是42位毫秒时间戳可用id数量是极多的，建议可以调大一些）

  我们默认是选择了性能优先的组合方案：TSync + Format MAX.

  此外为了兼容不同系统，所以默认路径直接选用了当前路径，默认持久化文件名为”GoldRecovery.grf”。(本来是叫”dump.grf”，但是还是有特色点比较好嘻嘻！)

3. GRF 部分源码解读

GRFSetStrategy：

func GRFSetStrategy(strategy uint8) error {
    if strategy != FSync && strategy != TSync {
        return errors.New("GRFSetStrategy error: unknown 'strategy'.")
    }
    if GrfStrategy == FSync && strategy == TSync {
        RemakeGrfLastupdatedtimeoffset()
    }
    GrfStrategy = strategy
    writeStrategyInGRF()
    return nil
}

  这个函数有个细节要说，在第二个if上：这个处理的是从 FSync 转换为 TSync 的情况，这里调用了个 RemakeGrfLastupdatedtimeoffset()，重新生成了 GrfLastupdatedtimeoffset，目的是将 GrfLastupdatedtimeoffset 全部清零，这是为了防止之前 TSync 用了一段时间，GrfLastupdatedtimeoffset 有遗留下一些 timeoffset 数据影响之后的持久化。

writeTimeOffsetInGRF:

func writeTimeOffsetInGRF(workerId uint32, timeOffset uint64) {
    for GrfCasLock() {
    }
    defer GrfCasUnLock()
    wid := Uint32ToString(workerId)
    timeoffset := Uint64ToString(timeOffset)
    lineBytes, err := ioutil.ReadFile(GrfPath)
    var lines []string
    if err != nil {
        fmt.Println(err)
    } else {
        contents := string(lineBytes)
        lines = strings.Split(contents, "\n")
    }
    var newLines []string
    var Updated bool = false
    for _, line := range lines {
        if GrfFormat == FormatMAX {
            isIn, err := regexp.MatchString("^"+timeOffsetDecl+".*", line)
            if err != nil {
                panic(err)
            }
            if isIn {
                oldtimeOffset, err := strconv.ParseUint(line[2:], 10, 64)
                if err != nil {
                    panic(err)
                }
                if oldtimeOffset < timeOffset {
                    newLines = append(newLines, timeOffsetDecl+timeoffset)
                    Updated = true
                    continue
                }
            }
        } else if GrfFormat == FormatALL {
            isIn, err := regexp.MatchString("^"+workeridDecl+wid+".*", line)
            if err != nil {
                panic(err)
            }
            if isIn {
                newContent := workeridDecl + wid + " " + timeOffsetDecl + timeoffset
                newLines = append(newLines, newContent)
                Updated = true
                continue
            }
        } else {
            panic("GRF error: unknown GRF format.")
        }
        newLines = append(newLines, line)
    }

    if !Updated && GrfFormat == FormatALL {
        newContent := workeridDecl + wid + " " + timeOffsetDecl + timeoffset
        newLines = append(newLines, newContent)
    }

    file, err := os.OpenFile(GrfPath, os.O_WRONLY, 0666)
    if err != nil {
        panic(err)
    }
    defer file.Close()
    _, err = file.WriteString(strings.Join(newLines, "\n"))
    if err != nil {
        panic(err)
    }
}

  我们写入的方法是先读取文件的所有内容到字符串 lineBytes 中，然后按换行符分割成多个字符串，并使用字符串切片 lines 引用这些字符串。之后我们遍历 lines，并使用新的字符串切片 newlines 记录更新后的文件内容，最后会将 newlines 的内容写回文件。遍历 lines 时我们根据不同的格式来使用正则表达式进行匹配，如果是 ALL 格式则需要找对应的 workerid 所在的一行，找到后更新当前行的内容，即向 newlines 追加更新过的内容，最后如果找不到匹配的 workerid 记录的话，会在尾部追加一条该 workerid 的新记录；而如果是 MAX 格式则找到 timeoffset 所在的一行，之后将保存的 oldtimeoffset 和要更新的 timeoffset 进行比较，若更新后 timeoffset 更大则进行更新。

4. 当 timeoffset 很大时 GRF 会发生什么？

  想一想，如果 timeoffset 已经累积很大时，比如达到了1个小时的偏移量会发生什么？

  当我们的 timeoffset 有1个小时的时候，假如机器关机了2个小时重启了，timeoffset 恢复为之前的值，按理来说 timeoffset 此时为 0 也依然大于先前生成的id，而这么恢复我们会损失掉1个小时这么多的可用id数量！那么有办法解决这个问题吗？

  其实之前提到第二，第三种持久化方案就可以做到，取出最大id的前42位毫秒时间戳部分，为了更多利用可用id可以再取中间的机器id部分判断是否是当前要恢复的机器生成的，从而取出该机器生成过的最大id前42位毫秒时间戳部分。我们通过当前时间和上一次生成id的时间做减法即可获得准确需要的偏移量（注意结果为负值时要恒等于0）。

  那么本地持久化可以做到吗？答案是可以的，在每次生成id的时候都做持久化即可，但是这样做性能开销就太大了！所以金毛并不打算提供这样的持久化策略，另外 timeoffset 累积几个小时我认为还是能容忍的，而如果累积到了以天数来计的大小，能有这样的规模我认为也可以用得了第二或第三种持久化吧？

5. 杂谈

  GoldFlake + GRF 已经有700多行代码了(单元测试代码量不计算），这下真要成“史上最复杂的分布式id生成算法”了呜呜呜！

  不过呢，因为复杂，所以创造 GoldFlake 的过程中感觉也用来Go练手很不错，而且也学到了不少东西，嘻嘻！希望这下 GoldFlake 真的足够了吧。🍭🍭

文章作者: 金毛败犬
文章链接: http://eririspace.cn/2022/05/20/GoldFlake_3/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 金毛败犬 !
分布式 分布式id生成
赏
评论
  目录