新traceId格式
背景
当前端上使用一个long值的16进制的字符串作为traceId。目前存在两个问题:
1. 64位随机数的碰撞概率高,目前已经出现traceId碰撞的情况
2. 当前trace存储使用ClickHouse的Projection存储,其排序索引(主键)是traceId,即traceId在文件中是顺序的。当前traceId的生成规则是随机数,所以相近时间的traceId会分散在Data Part的不同部分,也就是要扫描的段比较多。如果让相近时间的traceId能处在一个局部,可以减少扫描的次数,从而减少负载和耗时。
目标
1. 降低traceId碰撞概率
2. 将时间相近的traceId尽可能存储在一起,从而减少扫描次数。
业内方案调研
UUID V1 (date-time and MAC address)
由3部分组成
● 时间:⾃1582-10-15 0点开始的第n个100nanoSecond
● 地址:机器mac地址
● 事件id(0-16383),单个tick⾥⾃增
单机每秒钟可以⽣成1638亿个id JDK中没有提供V1版本的UUID,需要参考开源的代码:
com.github.f4b6a3.uuid.factory.AbstTimeBasedFactory
**问题:**虽然使用了时间作为字段之一,但是把时间分成了三段,并把最低的32位移位到了最高的32位,破坏了时间的有序性,详见下面的代码:
UUID V4 random
使⽤java.util.UUID#randomUUID⽣成,底层是使用SecureRandom获取2个16byte(long)。
问题:
1. SecureRandom获取可能会block线程。
2. 生成的ID不具备顺序性。
snowflake分布式唯⼀ID⽣成
traceId最基础的能⼒就是分布式ID,snowflake是业界⽐较认可的分布式唯⼀ID⽣成算法。snowflake算法的输出是64bit的long型数字,输⼊是相对时间(41bit)、机器id(10bit)、同机器内事件序号(12位)、⾸位 保持0(1bit,使id保持为正数)。
这个算法单机每秒内理论上最多可以⽣成1000*(2^12),也就是409.6万。
问题:
● 机器id占⽤10bit,只能标识1024个机器。
● 虽然各字段的位数可以调整,但是总共只能使⽤63位,调整空间不⼤。机器id占⽤位数增加则时间戳或者序列号就不够⽤了。
● 使⽤时间作为id的⼀部分。分布式情况下时间是不可信的,时钟不同步或者**“时钟回拨”**会导致id重复。
UidGenerator
这是百度开源的分布式唯⼀ID⽣成算法,整体也是snowflake的思想,在各部分的含义和位数上做了微调:
1. 时间戳表示秒,最多可⽀持约8.7年。原⽣snowflake这部分表示毫秒。
2. workerId为22位。同⼀台机器每次重启都会从mysql获取新的workerId。可以承载420w次重启。
3. 事件号为13位,最⼤为8192。意味着⼀秒最多⽣成8192个id,在⼀些场景下不够⽤。
4. 为应对特点3带来的并发度不⾼问题,允许“借⽤未来时间”.
⼀些问题:
1. 420万次重启仍然不够,需要考虑机器Id的复⽤才⾏,但这会带来复杂度提升。
2. 虽然时间借⽤的思想可以⼀定程度上缓解并发度不⾜的问题,但是单个workerNodeId也只能有2^(28+13)个事件id。假设在单机10000qps下,也只能保证2545天不需要重启获得新的workId。
3. 从本质上讲,UidGenerator只是snowflake的改良版,有⼀些优势但也带来了复杂度的提升,并引⼊了额外依赖。
leaf分布式唯⼀ID⽣成算法
分为leaf-segment和leaf-snowflake。
leaf-segment是使⽤数据库⾃增id来获取分布式唯⼀id,采⽤分段获取id和数据库分库分表来突破单机性能瓶颈和⾼可⽤
leaf-snowflake仍然是snowflake的思想,有点在于引⼊zookeeper更新机器时间,探测“时间回拨”的发⽣并进⾏fail-fast。
leaf的⽅案都需要引⼊额外依赖。SDK不适合依赖mysql,也不适合依赖zookeeper,暂不考虑leaf⽅案
OpenTelemetry
SDK中默认的是RandomIdGenerator(也可以⾃定义IdGenerator),使⽤的都是伪随机数。
traceId使⽤两个随机long,最终产⽣⻓度为32的16进制字符串(例如4e9da3d2deda7aa20c433fd1dd6cb48d)
spanId使⽤⼀个随机long,最终产⽣⻓度为16的16进制字符串(例如7b335f26aed48e08)
问题:不具备顺序性
SOFATracer/鹰眼
TraceId:服务器 IP + ID 产⽣的时间 + ⾃增序列 + 当前进程号 ,⽐如:0ad1348f1403169275002100356696
前 8 位 0ad1348f 即产⽣ TraceId 的机器的 IP,这是⼀个⼗六进制的数字,每两位代表 IP 中的⼀段,我们把这个数字,按每两位转成 10 进制即可得到常⻅的 IP 地址表示⽅式。
后⾯的 13 位 1403169275002 是产⽣ TraceId 的时间。
之后的 4 位 1003 是⼀个⾃增的序列,从 1000 涨到 9000,到达 9000 后回到 1000 再开始往上涨。
最后的 5 位 进程ID。为了防止出现 TraceId 冲突的情况,所以在 TraceId 末尾添加了当前的进程 ID。
这个方案仍然是相关信息的拼接,不同于snowflake系的区别在于最终输出不是long,⽽是string。
SkyWalking TraceId/segmentId
使⽤ 应⽤实例Id+线程Id+时间戳(毫秒)+事件号(0-9999),使⽤英⽂句号分割。
仍然是相关信息的拼接,不同于snowflake系的区别在于最终输出不是long,⽽是string。
TraceId生成方案
总体设计上使用双long的16进制字符串作为traceId,这和opentelemetry保持一致。
双long的共128位中,保证41位表示时间戳(可使用69.7年)、23位表示序列号(每毫秒800万事件),剩余的64位用于保证唯一。
具体方案有以下三种:
方案一
41位时间戳(毫秒)+ 23位序列号+ 64位伪随机long
方案二
41bit时间戳(毫秒)+ 23位(自增id)+ 32bit IPv4 + 32位伪随机int,,每5000个trace生成一次随机int
方案三
41bit时间戳(毫秒)+ 23位(自增id)+ 由128位IPv6通过异或位运算折叠得到的32位 + 32位伪随机int,每5000个trace生成一次随机int
方案二和方案三需要使用IP地址来得到32位,使用局域网地址的意义不大,如何获取公网ip地址是一个待解决的问题。
方案评估
由于获取公网IP需要额外的依赖,并且针对IPv4和IPv6需要不同处理,增加了复杂度,最终选定方案一。
TraceId传输方案
IOS/Android/WEB当前使用Zipkin (B3) HTTP header传递traceId,相关header为X-B3-TraceId.
为避免兼容性问题,老的header不改动,新增一个header:x-trace-id来传递新的traceId。
参考资料
3. UUID
4. UUIDv1⽣成