kvid : Global Unique ID Generator Based on Redis/Kvrocks

Introduction
Usage
Design and Implementation
Tech Stack
Directory Structure
Competitors
Comparison of ID Generation Algorithms
History

Introduction

kvid is a distributed unique ID generator based on Redis or Kvrocks. It guarantees globally unique IDs that are trend-increasing. It is designed to be robust, high-performance, and easy to integrate into Rust projects.

Key features include:

Global Uniqueness: Ensures no duplicate IDs are generated across the distributed system.
Trend Increasing: IDs are generated in an increasing order, which is beneficial for database indexing.
High Performance: Utilizes batch fetching (step-based) to minimize network round-trips to Redis/Kvrocks.
Dynamic Step Adjustment: Automatically adjusts the batch size based on consumption rate to balance performance and ID continuity.
Static Global Variable Support: Can be directly declared as a static global variable in Rust, simplifying usage across the application.

Usage

Add kvid to Cargo.toml.

Basic Example

kvid allows declaring the generator as a static global variable, making it accessible throughout the application without passing instances around.

use std::time::Duration;
use aok::{OK, Void};
use kvid::KvId;
use log::info;

// Initialize logger (optional, depending on your setup)
#[static_init::constructor(0)]
extern "C" fn _log_init() {
  log_init::init();
}

// Declare as a static global variable
pub static KVID_TEST: KvId = KvId::new("test");

#[tokio::test]
async fn test() -> Void {
  // Initialize global Redis/Kvrocks connection (Required for xkv to connect to Redis/Kvrocks)
  xboot::init().await?;

  for i in 0..300 {
    // Generate next ID
    let id = KVID_TEST.next().await?;
    info!("{}", id);

    if i > 5 {
      tokio::time::sleep(Duration::from_secs(1)).await;
    }
  }
  OK
}

Design and Implementation

Configuration & Constants

The following constants are defined in src/lib.rs and control the behavior of the generator:

FETCH_DURATION (Default: 600s / 10 minutes): The target duration for a batch of IDs to last. The algorithm tries to adjust the step (batch size) so that a fetch request happens approximately every 10 minutes.
- If IDs are consumed faster than this duration, the step size doubles (up to STEP_MAX) to reduce network frequency.
- If IDs are consumed slower than this duration, the step size halves to prevent holding too many unused IDs during low traffic periods.
STEP_MAX (Default: 1,000,000): The maximum number of IDs that can be fetched in a single request. This prevents the step size from growing indefinitely.

Core Logic

The core logic resides in the KvId struct. It maintains a local range of IDs and fetches a new range (step) from the Redis/Kvrocks backend when the local range is exhausted.

Initialization: KvId is initialized with a name (key).
ID Generation (next):
- Checks if there are available IDs in the local buffer (id < max).
- If yes, increments the local id and returns it.
- If no, it triggers a fetch operation.
Fetching from Backend:
- Uses HINCRBY command on Redis/Kvrocks to atomically increment the maximum ID for the given key by step.
- Updates local max and id based on the response.
Dynamic Step Adjustment:
- The system calculates the time elapsed (cost) since the last fetch.
- Increase Step: If cost <= FETCH_DURATION (high load), step = step * 2.
- Decrease Step: If cost > FETCH_DURATION (low load), step = max(1, step / 2).
- This self-tuning mechanism ensures high performance under load while minimizing waste during idle times.

Data Structures (`lib.rs`)

KvId: The main struct exposed to the user.
- name: The key name used in Redis.
- inner: A Mutex protected Inner state.
Inner: Internal state of the generator.
- id: Current ID available for distribution.
- max: The maximum ID in the current allocated range.
- step: Current batch size to fetch from backend.
- ts: Timestamp of the last fetch.

Tech Stack

Rust: Core language.
Redis / Kvrocks: Backend storage for atomic counters.
fred: Async Redis client.
parking_lot: Efficient Mutex implementation.
tokio: Async runtime.

Directory Structure

.
├── Cargo.toml      # Project configuration
├── README.mdt      # README template
├── readme/         # Documentation files
│   ├── en.md       # English README
│   └── zh.md       # Chinese README
├── src/            # Source code
│   └── lib.rs      # Library entry point
└── tests/          # Integration tests
    └── main.rs     # Usage demonstration

Competitors

Distributed ID generation is a common requirement. Here are some similar projects:

Baidu Uidgenerator: Java-based, Snowflake algorithm variant. High performance but relies on Snowflake's time-dependency.
Meituan Leaf: Supports both Segment mode (database) and Snowflake mode (ZooKeeper). Segment mode is similar to kvid's approach.
Didi TinyID: Java-based, Segment mode only. Focuses on high availability and multi-db support.

kvid distinguishes itself by being written in Rust, offering high performance with low footprint, and specifically optimizing for ease of use with static global variables.

Comparison of ID Generation Algorithms

To better understand kvid's position, here is a comparison of common distributed ID generation algorithms:

1. UUID (Universally Unique Identifier)

Principle: 128-bit identifier generated based on timestamp, random numbers, or MAC address.
Pros:
- Simple to implement, no network interaction needed.
- Globally unique without coordination.
Cons:
- Too long: 128 bits (32 hex chars) is inefficient for storage and indexing.
- Not sortable: Randomness (v4) causes page splitting in B+Tree indexes, hurting database performance.
- Information leakage: v1 contains MAC address.

2. Database Auto-increment

Principle: Rely on database's AUTO_INCREMENT feature.
Pros:
- Simple, strictly increasing.
Cons:
- Single point of failure: Database becomes the bottleneck.
- Hard to scale: Difficult to merge data from multiple databases later.

3. Snowflake (Twitter)

Principle: 64-bit integer: 1 bit sign + 41 bits timestamp + 10 bits machine ID + 12 bits sequence.
Pros:
- High performance (millions of IDs/sec).
- Time-ordered (roughly).
- No network overhead (generated locally).
Cons:
- Clock dependency: Strongly relies on system clock. Clock rollback can cause duplicate IDs or service unavailability.
- Machine ID management: Requires a mechanism (like ZooKeeper) to assign unique machine IDs.

4. Segment Mode (kvid / Meituan Leaf)

Principle: Pre-allocate a range (step) of IDs from a central store (Redis/DB) and issue them from memory.
Pros:
- High Performance: Database is accessed only once per step (e.g., every 1000 IDs).
- No Clock Dependency: Immune to clock rollback issues.
- Trend Increasing: Friendly to database indexing.
Cons:
- ID Gaps: If the service restarts, unused IDs in the current step are lost (but uniqueness is preserved).
- Central Dependency: Relies on the availability of the central store (Redis/Kvrocks), though load is very low.

History

The need for distributed unique IDs arose with the explosion of web-scale applications. Traditional database auto-increment keys became a bottleneck in sharded databases. Twitter's Snowflake (2010) was a pioneer, using time-based bit manipulation to generate IDs without coordination. However, Snowflake depends heavily on system clocks. Database-based "Segment" approaches (like Flickr's ticket server and later Meituan Leaf's segment mode) emerged to solve clock dependency issues by allocating blocks of IDs. kvid follows the Segment pattern, leveraging modern Redis/Kvrocks for speed and atomicity, combined with Rust's safety and concurrency features.

About

This project is an open-source component of js0.site ⋅ Refactoring the Internet Plan.

We are redefining the development paradigm of the Internet in a componentized way. Welcome to follow us:

kvid : 基于 Redis/Kvrocks 的全局唯一 ID 生成器

项目介绍
使用演示
设计思路
技术堆栈
目录结构
竞品对比
主流 ID 生成算法对比
历史背景

项目介绍

kvid 是基于 Redis 或 Kvrocks 的分布式全局唯一 ID 生成器。保证生成的 ID 全局唯一且整体呈递增趋势。设计目标是稳健、高性能，并易于集成到 Rust 项目中。

主要特性：

全局唯一：确保在分布式系统中不会生成重复 ID。
趋势递增：ID 按序生成，有利于数据库索引性能。
高性能：采用号段模式（Batch Fetching），极大减少对 Redis/Kvrocks 的网络请求频率。
动态步长：根据 ID 消费速率自动调整步长，平衡性能与 ID 连续性。
支持静态全局变量：Rust 中可直接声明为 static 全局变量，无需在函数间传递实例，使用极其便捷。

使用演示

在 Cargo.toml 中添加 kvid。

基础示例

kvid 支持声明为静态全局变量，可在应用任意位置直接调用。

use std::time::Duration;
use aok::{OK, Void};
use kvid::KvId;
use log::info;

// 初始化日志（可选）
#[static_init::constructor(0)]
extern "C" fn _log_init() {
  log_init::init();
}

// 声明静态全局变量
pub static KVID_TEST: KvId = KvId::new("test");

#[tokio::test]
async fn test() -> Void {
  // 初始化全局 Redis/Kvrocks 连接(使用xkv连接redis/kvrocks数据库必须先这样初始化)
  xboot::init().await?;

  for i in 0..300 {
    // 生成下一个 ID
    let id = KVID_TEST.next().await?;
    info!("{}", id);

    if i > 5 {
      tokio::time::sleep(Duration::from_secs(1)).await;
    }
  }
  OK
}

设计思路

配置与常量

以下常量定义在 src/lib.rs 中，用于控制生成器的行为：

FETCH_DURATION (默认: 600秒 / 10分钟)：一个号段（Batch）预期的持续时间。算法会尝试调整 step（步长），使得大约每 10 分钟进行一次网络请求。
- 如果 ID 消费速度快于此时间，步长翻倍（上限为 STEP_MAX），以减少网络交互频率。
- 如果 ID 消费速度慢于此时间，步长减半，以防止在低流量期间持有过多未使用的 ID。
STEP_MAX (默认: 1,000,000)：单次请求获取的最大 ID 数量。防止步长无限增长。

核心逻辑

核心逻辑封装于 KvId 结构体。其内部维护一段本地 ID 缓存，当缓存耗尽时，从 Redis/Kvrocks 后端获取新的号段（Step）。

初始化：使用名称（Key）初始化 KvId。
ID 生成 (next)：
- 检查本地缓存是否有可用 ID (id < max)。
- 若有，递增本地 id 并返回。
- 若无，触发远程获取操作。
后端获取：
- 使用 Redis/Kvrocks 的 HINCRBY 命令，原子性地增加对应 Key 的最大值。
- 根据返回值更新本地 max 和 id。
动态步长调整：
- 系统计算距离上次获取的时间间隔 (cost)。
- 增加步长：若 cost <= FETCH_DURATION（高负载），则 step = step * 2。
- 减小步长：若 cost > FETCH_DURATION（低负载），则 step = max(1, step / 2)。
- 这种自适应机制确保了在高负载下的高性能，同时在空闲时减少 ID 浪费。

数据结构 (`lib.rs`)

KvId：对外暴露的主结构体。
- name: Redis 中使用的 Key 名称。
- inner: Mutex 保护的内部状态 Inner。
Inner：生成器内部状态。
- id: 当前可分配的 ID。
- max: 当前号段的最大 ID。
- step: 当前从后端获取的步长。
- ts: 上次获取的时间戳。

技术堆栈

Rust: 核心开发语言。
Redis / Kvrocks: 用于原子计数器的后端存储。
fred: 异步 Redis 客户端。
parking_lot: 高效 Mutex 实现。
tokio: 异步运行时。

目录结构

.
├── Cargo.toml      # 项目配置
├── README.mdt      # README 模板
├── readme/         # 文档目录
│   ├── en.md       # 英文文档
│   └── zh.md       # 中文文档
├── src/            # 源代码
│   └── lib.rs      # 库入口
└── tests/          # 集成测试
    └── main.rs     # 使用演示

竞品对比

分布式 ID 生成是常见需求，类似项目包括：

百度 Uidgenerator：基于 Java，Snowflake 算法变种。高性能，但依赖机器时钟。
美团 Leaf：支持号段模式（数据库）和 Snowflake 模式（ZooKeeper）。其号段模式与 kvid 思路类似。
滴滴 TinyID：基于 Java，仅支持号段模式。侧重高可用和多 DB 支持。

kvid 的优势在于使用 Rust 编写，资源占用低，性能卓越，且专门针对 Rust 开发习惯优化，支持静态全局变量调用。

主流 ID 生成算法对比

为了更好地理解 kvid 的定位，以下是常见分布式 ID 生成算法的对比：

1. UUID (Universally Unique Identifier)

原理：基于时间戳、随机数或 MAC 地址生成的 128 位标识符。
优点：
- 实现简单，无需网络交互。
- 全球唯一，无需协调。
缺点：
- 太长：128 位（32 个十六进制字符），存储和索引效率低。
- 无序：随机性（v4）导致 B+Tree 索引频繁分裂，严重影响数据库性能。
- 信息泄露：v1 版本包含 MAC 地址。

2. 数据库自增 ID

原理：依赖数据库的 AUTO_INCREMENT 特性。
优点：
- 简单，严格递增。
缺点：
- 单点故障：数据库成为性能瓶颈。
- 难以扩展：分库分表后难以合并数据。

3. Snowflake (Twitter 雪花算法)

原理：64 位整数：1 位符号 + 41 位时间戳 + 10 位机器 ID + 12 位序列号。
优点：
- 高性能（百万级 QPS）。
- 趋势递增（基于时间）。
- 无网络开销（本地生成）。
缺点：
- 强依赖时钟：系统时钟回拨会导致 ID 重复或服务不可用。
- 机器 ID 管理：需要额外的机制（如 ZooKeeper）来分配唯一的机器 ID。

4. 号段模式 (kvid / 美团 Leaf)

原理：从中心存储（Redis/DB）预申请一段 ID（步长），然后在内存中分配。
优点：
- 高性能：每个步长（如 1000 个 ID）仅访问一次数据库。
- 无时钟依赖：完全免疫时钟回拨问题。
- 趋势递增：对数据库索引友好。
缺点：
- ID 空洞：服务重启时，当前步长内未使用的 ID 会丢失（但保证唯一性）。
- 依赖中心：依赖中心存储（Redis/Kvrocks）的高可用，但负载极低。

历史背景

随着互联网应用规模爆发，分布式唯一 ID 需求应运而生。传统数据库自增主键在分库分表场景下成为瓶颈。Twitter 的 Snowflake (2010) 开创性地利用时间戳位运算生成 ID，无需中心化协调，但强依赖系统时钟。基于数据库的“号段模式”（如 Flickr 的 Ticket Server 及后来的美团 Leaf）通过预分配 ID 块解决了时钟依赖问题。kvid 沿用号段模式，利用现代 Redis/Kvrocks 的原子性与速度，结合 Rust 的安全并发特性，提供更优解决方案。

关于

本项目为 js0.site ⋅ 重构互联网计划的开源组件。

我们正在以组件化的方式重新定义互联网的开发范式，欢迎关注：

kvid 0.1.1

kvid : Global Unique ID Generator Based on Redis/Kvrocks

Introduction

Usage

Basic Example

Design and Implementation

Configuration & Constants

Core Logic

Data Structures (lib.rs)

Tech Stack

Directory Structure

Competitors

Comparison of ID Generation Algorithms

1. UUID (Universally Unique Identifier)

2. Database Auto-increment

3. Snowflake (Twitter)

4. Segment Mode (kvid / Meituan Leaf)

History

About

kvid : 基于 Redis/Kvrocks 的全局唯一 ID 生成器

项目介绍

使用演示

基础示例

设计思路

配置与常量

核心逻辑

数据结构 (lib.rs)

技术堆栈

目录结构

竞品对比

主流 ID 生成算法对比

1. UUID (Universally Unique Identifier)

2. 数据库自增 ID

3. Snowflake (Twitter 雪花算法)

4. 号段模式 (kvid / 美团 Leaf)

历史背景

关于

Data Structures (`lib.rs`)

数据结构 (`lib.rs`)