分布式系统唯一主键标识符ID生成机制比较 - Encore


在构建任何分布式或非分布式系统时,您最终会处理许多数据ID标识符,从数据库行一直到生产系统版本的ID标识符。
决定如何生成标识符有时非常简单;例如,您可能只是将一个自动递增ID的数字作为您的数据库中的主键。

然而,在分布式系统中,让一个数字从 1 开始并缓慢增加要困难得多。您可以构建一个选举领导者的系统,并且该领导者负责增加数量 - 但这会给您的系统设计增加很多复杂性,它不会无限扩展,因为您仍然会受到吞吐量的限制领导。您仍然可能会遇到脑裂问题,即相同的数字由两个不同的“领导者”生成两次
在项目的早期做出正确的决定总是很重要的,因为一旦投入生产,这是系统中最难改变的事情之一。
 
现有选项
如果我们暂时忽略类型安全和人类可读性要求,那么我们所要求的已经解决了一千次了,我们不需要在这里重新发明轮子。让我们看看一些现有的久经考验的选项。

  • 数据库的自动递增键

大多数人的第一反应是自动递增的主键。这解决了可排序的问题,并且没有碰撞的风险。然而,它只能扩展到你的数据库服务器所能处理的写入量的程度。它还增加了一个新的要求,即你生成的每个标识符都必须有一个匹配的数据库行。鉴于我们想把这个系统用于我们不存储在数据库中的东西,我们很快就排除了这个要求。
 
  • UUIDs

有各种版本的UUIDs,它们都是128位;乍一看,从可扩展性、零配置和碰撞风险的角度来看,版本1、2、4似乎很完美。然而,当你深入挖掘时,不同版本的UUIDs开始显示出疣状。

版本1和2,尽管它们每秒可以生成大约1600亿个标识符,但它们使用机器的MAC地址,这意味着同一台机器上的两个进程如果同时调用,可能会生成相同的标识符。
第4版生成完全随机的标识符,具有2122比特的随机性。这意味着我们非常不可能发生碰撞,并且可以无限扩展而不会出现瓶颈。然而,我们失去了按时间顺序排列标识符的能力。
  

  • Snowflake 

Snowflake标识符是由Twitter首先开发的,通常是64位(尽管有些变种使用128位)。这个方案将ID产生的时间编码为前41位,然后将实例ID编码为后10位,最后将序列号编码为最后的12位。

这给了我们很好的可扩展性,因为实例的比特集允许我们同时运行1024个不同的进程,同时知道它们不能产生相同的标识符,因为进程自己的标识符是在里面编码的 它给我们提供了我们的k-排序,因为上面的位是ID产生的时间。最后,我们在进程内有一个序列号,这使我们能够在每个进程中每秒产生4096个标识符。

然而,Snowflake 不符合我们需要零配置的要求,因为实例 ID 必须在每个进程中进行配置。
 


KSUID有点像UUID第四版和Snowflake之间的交叉。它们是160位,其中前32位是标识符产生的时间(到第二位),然后是128位的随机数据。这使得它们对我们来说几乎是理想的;它们是k-排序的,不需要配置,而且没有碰撞的风险,因为ID的随机部分有大量的熵。
然而,我们在研究KSUID的过程中发现了一些有趣的事情;KSUID的字符串编码使用BASE-62编码,因此有大写和小写字母;这意味着根据你的字符串排序,你可能会对标识符进行不同的排序--也就是说,我们失去了根据系统进行排序的要求。例如,Postgres将小写字母排序在大写字母之前,而大多数算法将大写字母排序在小写字母之前,这可能会导致一些非常讨厌的和难以识别的错误。(值得注意的是,这对任何同时使用大写和小写字母的编码方案都有影响,所以它不仅仅限于KSUID。)
 

XID的是96位。前32位是时间,这意味着我们可以立即得到我们的k-排序。接下来的40位是机器标识符和进程标识符;然而,与其他系统不同的是,这些是使用库自动计算的,不需要我们自己配置什么。最后的24位是一个序列号,它允许一个进程每秒产生16,777,216个标识符!

XID给了我们所有的核心要求,它的字符串编码使用32进制(没有大写字母来破坏我们的排序!)。这个字符串编码始终是20个字符,这意味着我们可以在任何marshalling代码中使用这一事实进行验证(例如Postgres对数据库类型的CHECK约束)。
 
Encore公司的选择要求

  • 可排序

我们希望能够对标识符进行排序,例如当A先被创建时,A<B。然而,我们不需要完全的排序;可以接受的是k-sortable。可排序可以使我们在数据库中获得更好的索引性能,使我们能够轻松地按顺序遍历记录,并提高我们的调试能力,因为事件的顺序可以通过事件标识符来确定。
  • 可扩展性

我们希望有一个能与我们一起扩展的系统,没有瓶颈。我们将使用这个系统来生成痕迹和跨度的标识符,我们将在其中创建大量的标识符。
  • 无碰撞风险:

因为我们运行的是一个分布式系统,我们不希望有两个进程创建相同标识符的风险。
  • 零配置:

在使用这个系统时,我们不希望在每台机器或每个进程层面上做任何级别的配置。
  • 类型安全:

我们想要一个系统,其中一个资源的标识符不能意外地作为另一种类型的资源的标识符被传递或返回。
我们还希望标识符是。
  1. 合理地小:无论是在内存中还是在传输过程上。
  2. 人类可读性。这与类型安全有关;然而,我们希望字符串的表示能够让人类理解标识符的创建目的。

 

我们决定选择的标识符ID方案
一旦我们决定使用XID作为我们的ID类型的基础,我们就把重点转回到我们最后的两个要求上:类型安全和人类可读性。

对于前一个要求,我们可以简单地解决这个问题:

import "github.com/rs/xid"

type AppID xid.ID
type TraceID xid.ID

func NewAppID() AppID { return AppID(xid.New()) }
func NewTraceID() TraceID { return TraceID(xid.New()) }

由于 Go 的类型系统,AppID和TraceID两者都是不同的类型,因此以下将成为编译错误:

var app AppID = NewTraceID() // this won't compile

这本来是可行的;但是,我们必须为每个具体类型(如AppID)实现所有的marshalling函数(encoding.TextMarshaler, json.Marshaler, sql.Scanner等)。为了尽量减少我们团队的模板编写,这将意味着使用代码生成器来为我们编写。

这里的另一个缺点是我们的系统不仅仅是Go。我们还有一个Typescript前台和一个Postgres数据库。这意味着一旦我们将ID编码成线格式,我们就失去了对类型安全的所有保证,现在在另一个系统中,有可能错误地将一种形式的ID用于另一种。

在Go 1.18之前,我们可以通过添加一个包含类型信息的包装结构来解决这个问题。

import (
    "fmt"
   
"github.com/rs/xid"
)

type EncoreID struct {
    ResourceType string
    ID           xid.ID
}

type AppID *EncoreID
type TraceID *EncoreID

func NewAppID() AppID { return &EncoreID{
"app", xid.New() } }
func NewTraceID() TraceID { return &EncoreID{
"trace", xid.New() } }

 
进入Go泛型
在Go 1.18中,我们可以创建一个抽象的ID类型,然后基于ResourceType创建不同的具体类型,但实际上只是xid。所以从概念上讲,我们是这样开始的。

import (
    "fmt"
   
"github.com/rs/xid"
)

type ResourceType struct{}
type App ResourceType
type Trace ResourceType

type ID[T ResourceType] xid.ID

func New[T ResourceType]() ID[T] { return ID[T](xid.New()) }

更多点击标题