leaf

README

leaf 分布式唯一 id 生成器

当前版本为开发 demo，仅供参考。

依赖

etcd 服务

算法

核心算法采用 snowflake 模式，即用一个带符号的长整型数，切分二进制位分配不同类型数据来产生唯一 ID。

如图：
将带符号的64位整型的二进制位，划分成4段。
第一段1位，作为符号位不使用，主要为了兼容其它语言，如：java。
第二段41位，作为时间戳，表示毫秒数，最长可使用 1<<41 / (1000 * 3600 * 24 * 365) ≈ 69年。
第三段10位，作为工作进程，表示机器id。10位可以标识1024台机器。
最四端12位，作为序列号，标识每个时间戳（毫秒）内可生成的序列号。12位每毫秒最大可产生4096个序列号。
所以该算法理论上最大可支持每秒生成 1024 * 4096 ≈ 400万 个递增且不重复的id。

第三段10位表示机器数，一般机房用不到这么多机器，所以将该段数据分为两段， 前5位表示数据中心数，后5位表示机器数。这样就可以支持32个数据中心，每个数据中心支持32台机器。 整个算法的二进制位分配应视具体情况而定。

架构

简单架构图如下：

接口

http RESTful API:

url：http://leafid-host:port/id
method：GET

http get http://leafid-host:port/id

gRPC:

数据格式采用 protobuf 协议，leaf_grpc.proto 内容:

syntax = "proto3";
package leafgrpc;

service Leaf {
    rpc GenId (request) returns (reply) {
    }
}

message request {
}

message reply {
    string message = 1;
}

执行 protoc 命令生成 grpc 服务相关代码，Golang 版本如下：

protoc -I leaf-grpc/ leaf-grpc/leaf_grpc.proto --go_out=plugins=grpc:leaf-grpc

时间回溯

时间回溯解决方法：
1.当第一台服务结点启动时会要求校验当前服务结点时间是否正确，且需要手动输入确认指令后才能正常启动。
2.启动后的结点注册进 etcd 集群。并定时刷新自身结点时间和集群共同维护时间(假设为：cluster_time 每个结点更新自身时间时同时把自身时间更新到 cluster_time 字段下)。
2.定时刷新自己结点时间时会比较当前时间和上一次的时间是否有偏差，如有偏差，则释放 etcd 注册，并中断当前服务。
3.后续启动的结点会自动校验当前结点时间与集群中已注册的结点（比较数：n/2 + 1）时间是否一致，如果时间在设置的时间偏差内则视当前服务结点时间准确。
4.新加入的结点校验时间阶段会监控集群的 cluster_time，该值有变更时就能感知到，并做处理。 因为每个结点都会把自身时间更新到 cluster_time，所以新加入的结点只需要比较 cluster_time 和自身时间即可，比较多次即可确认时间是否准确。

基准测试

TODO

License

遵循 MIT 协议，查看 MIT。

TODO

1.支持生成多种类型id。 2.性能优化 3.日志输出优化 4.配置动态更新 5.基准测试 6.docker容器化