moon-distinct-sketch | MoonBit 流式基数估计与多维指标统计库

moon-distinct-sketch 是基于 MoonBit 原生构建的高性能流式基数估计（Streaming Cardinality Estimation）与多维指标统计库。本项目实现了 HyperLogLog（稀疏模式/稠密模式）、HyperLogLog++、Linear Counting、滑动/翻转多窗口统计、时间衰减加权 Sketch、多租户 Active Device / UV 统计引擎、MinHash 集合相似度估计、Count-Min Frequency Sketch 频次统计、紧凑二进制序列化以及分布式树状规约聚合引擎。

---

核心特性 (Features)

1. HyperLogLog & HLL++ 引擎

   • 动态稀疏模式 (Sparse Mode) 与稠密模式 (Dense Mode, 4-bit / 6-bit packed) 自动升阶转换。
   • 包含 Flajolet 2007 经验偏差修正 (Empirical Bias Correction) 表与分段线性插值。
   • 支持跨 Sketch 寄存器合并、降采样与理论误差界计算 ($1.04\mathrm{/}\sqrt{m}1.04\; /\; \backslash sqrt\{m\}$)。
   • 基于 64 位哈希值的 HyperLogLog++，消除海量数据下的哈希碰撞瓶颈。

2. 多窗口与时间衰减统计 (Multi-Window & Time-Decay)

   • 翻转窗口 (Tumbling Window) 与 环形缓冲区滑动窗口 (Sliding Window) 实时 UV 计算。
   • 指数衰减 (Exponential Decay) 时间加权基数估计，贴合动态热度退化场景。

3. 多租户 UV 与集合重叠引擎 (Multi-Tenant & Set Operations)

   • 支持多租户隔离的实时设备数/活跃用户数追踪 (Unique Visitors / Active Devices)。
   • 基于容斥原理 ($\mathrm{\mid }A\cup B\mathrm{\mid }=\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }-\mathrm{\mid }A\cap B\mathrm{\mid }|A\; \backslash cup\; B|\; =\; |A|\; +\; |B|\; -\; |A\; \backslash cap\; B|$) 实现交集、并集与 Jaccard 相似度估计。

4. 频次与集合相似度 (MinHash & Count-Min Sketch)

   • MinHash 签名矩阵 estimate Jaccard Similarity。
   • Bottom-K Sketch 实现 Top-K/Heavy Hitters 元素过滤。
   • Count-Min Sketch 用于加权流式计数与频次上界估计。

5. 紧凑二进制序列化 (Compact SerDe)

   • 自研 ByteBuffer 位流读写器。
   • 高度压缩的二进制 Wire Format，单 Sketch 占用空间仅数 KB，极利于网络传输与 DB 存储。

6. 分布式树状规约聚合 (Distributed Tree Reduction)

   • $O(\log N)O(\backslash log\; N)$ 层级二叉树并行规约合并引擎，适用于多节点分布式流处理引擎。

---

目录结构 (Directory Layout)

moon-distinct-sketch/
├── .github/workflows/ci.yml       # 跨平台 GitHub Actions CI
├── moon.mod                        # MoonBit 模块配置
├── README.md                        # 项目主文档
├── LICENSE                          # Apache 2.0 开源协议
├── cmd/main/                        # CLI 主程序与 Benchmark
│   ├── main.mbt
│   └── moon.pkg
└── src/
    ├── utils/                       # 位运算(clz, popcount)、数学与稀疏数组
    ├── hash/                        # MurmurHash3, XXHash64, SipHash24, FNV1a
    ├── hll/                         # HyperLogLog 核心 (Sparse/Dense/Merge/Bias)
    ├── hllplus/                     # HyperLogLog++ 扩展
    ├── linear/                      # Linear Counting 位图 Counters
    ├── window/                      # Tumbling, Sliding & Exponential Window
    ├── multitenant/                 # 多租户 active metric & Jaccard
    ├── minhash/                     # MinHash & Bottom-K Sketch
    ├── countmin/                    # Count-Min Frequency Sketch
    ├── serde/                       # 二进制位流 Wire Format 编解码
    └── distributed/                 # 节点树状规约合并引擎

---

快速上手 (Quick Start)

1. 基础 HyperLogLog 使用

let hll = @hll.HyperLogLog::new(14) // 2^14 = 16384 registers

// 添加元素
let mut i = 0
while i < 100000 {
  hll.add_string("user_device_" + i.to_string())
  i = i + 1
}

// 获取基数估计值
let estimate = hll.cardinality()
println("Estimated Unique Count: " + estimate.to_string())

2. 多租户 UV 引擎与集合合并

let engine = @multitenant.TenantMetricsEngine::new(14)

// 记录租户日志
engine.record("tenant_app_a", "device_1001")
engine.record("tenant_app_a", "device_1002")
engine.record("tenant_app_b", "device_1002")

let tenant_a_uv = engine.get_tenant_uv("tenant_app_a")
let global_uv = engine.get_global_uv()

3. 二进制序列化与还原

// 序列化为字节数组
let bytes = @serde.serialize_hll(hll)

// 从字节数组还原 Sketch
let restored_hll = @serde.deserialize_hll(bytes)

---

编译与测试 (Build & Test)

确保已安装最新版 MoonBit 工具链 (0.10.4+)：

# 格式化检查
moon fmt --check

# 更新接口声明
moon info

# 运行全套单元测试
moon test

# 运行主程序基准测试 CLI
moon run cmd/main

---

贡献声明与版权 (License & Source)

本项目由 yhsrtty 独立设计与开发，为开源代码竞赛（OSC2026）参赛作品。 代码严格遵循 Apache-2.0 开源协议。所有 MoonBit 源码均由作者编写与测试，无任何第三方代码侵权。