🥮 mooncakes.io

moon-frequency-sketch

A pure MoonBit streaming analytics library with frequency, heavy-hitter, cardinality, quantile, sliding-window, telemetry, and serialization components.

sketch
frequency
count-min
heavy-hitters
probabilistic
streaming
moon add Hhsqoo/moon-frequency-sketch@0.2.0
Download zip
Author
Version
0.2.0
License
Apache-2.0
Repository
Last updated
12 hours ago
Downloads
3
README

#moon-frequency-sketch

纯 MoonBit 实现的高吞吐流式频率、基数、重频项和分位数估计库，面向 API 监控、网络流量分析和边缘/Wasm 场景。

CI Acceptance Check License: Apache-2.0

本项目参加 2026 年 8 月官方 MoonBit 黑客松，目标是提供可以被其他 MoonBit 应用直接复用的流式统计基础组件，而不是一次性演示程序。

#能力概览

模块用途主要保证
Count-Min Sketch频率估计只高估，误差由 ε/δ 控制
Count Sketch有符号频率估计基于中位数的无偏近似
Space-Saving / Misra-GriesTop-K 重频项亚线性空间、误差界
Bloom / Counting Bloom成员判断与删除无假阴性；Counting 支持删除
HyperLogLog独立用户/API/设备数固定寄存器空间、可合并
T-Digest延迟/大小 P50/P95/P99增量摘要、CDF、可合并
Sliding Window / Decay时间窗口与衰减桶轮换或指数衰减
Binary CodecCMS 快照与合并Magic 校验、差异比对
Telemetry MonitorAPI 监控组合门面请求量、错误率、Top-K、基数、分位数

#快速开始

# 编译与测试
moon check --target all
moon test --target all

# 运行完整 CLI 示例
moon run cli

# 运行确定性基准
moon run bench

作为依赖使用：

moon add Hhsqoo/moon-frequency-sketch

#示例

#HyperLogLog 与 T-Digest

let users = @cardinality.HyperLogLog::new(12).unwrap()
users.add_str("user:alice")
users.add_str("user:bob")
println(users.estimate().to_string())

let latency = @quantile.TDigest::new(100).unwrap()
latency.add(12.5).unwrap()
latency.add(80.0).unwrap()
match latency.quantile(0.95) {
  Some(p95) => println("p95=" + p95.to_string())
  None => println("empty digest")
}

#统一 API 监控

let monitor = @telemetry.Monitor::new(20, 10, 5, 1000, 12, 100).unwrap()
monitor.observe(
  @telemetry.Event::new("/api/users", "user:alice", 200, 18.0, 512L),
).unwrap()
let report = monitor.report()
println("events=" + report.total_events.to_string())
println("unique=" + report.unique_entities.to_string())

Monitor 将 CMS、Space-Saving、HyperLogLog、T-Digest 和 SlidingWindow 组合起来；底层摘要仍可单独使用，便于在流处理管线中替换参数或算法。

#模块结构

moon-frequency-sketch/
├── hash/                       # MurmurHash3, FNV-1a, xxHash32
├── sketch/
│   ├── cms/                    # Count-Min Sketch 与合并
│   ├── countsketch/            # Count Sketch 与统计估计器
│   ├── topk/                   # Space-Saving, Misra-Gries
│   ├── bloomfilter/            # Bloom 与 Counting Bloom
│   ├── cardinality/            # HyperLogLog
│   └── quantile/               # T-Digest
├── window/                     # RingBuffer, SlidingWindow, Decay
├── telemetry/                  # API 监控应用门面
├── codec/                      # 二进制快照、合并与差异
├── bench/                      # 确定性 workload 与真实计时
└── cli/                        # 可运行 API 监控示例

#基准样例

运行 moon run bench 会生成固定事件流，并在运行时测量耗时；基准同时维护精确 ground truth，不把理论数字当作实测结果。以下是 2026-08-17 在 Windows、MoonBit moon 0.1.20260807 / moonc v0.10.7 上的一次输出摘录：

events=10000 distinct_entities=1000
measured_ms=56 throughput_events_per_sec=178571.42857142858
unique_estimate=987 relative_error=0.013
latency_p95_estimate=104.98969072164948 exact=104.0
latency_p99_estimate=108.98969072164948 exact=108.0
error_events=104 error_rate=0.0104

耗时和吞吐会随机器变化；数据规模、输入分布和精确参考值固定，因此误差结果可以复核。

#测试与 CI

当前测试覆盖 CMS、Count Sketch、Top-K、Bloom、窗口、codec、HyperLogLog、T-Digest 和 telemetry 边界路径，包括空输入、非法参数、重复数据、极端值、不可兼容合并、NaN、窗口过期和零事件错误率。

moon version --all
moon update
moon fmt
moon info
moon check --target all
moon test --target all
moon build --target all
moon run cli
moon run bench

GitHub Actions 使用稳定版工具链，覆盖 Linux/macOS/Windows，并执行格式、接口、构建、测试、覆盖率摘要和 CLI/benchmark smoke test。Windows native 使用 MSVC developer environment；本地若只有 MinGW，可能遇到 Moon runtime rand_s 头文件兼容问题，这属于工具链环境而非本项目源码错误。

#算法来源与原创性

实现参考公开论文和经典算法定义：Count-Min Sketch、Space-Saving、Misra-Gries、Count Sketch、Bloom Filter、HyperLogLog 和 T-Digest。代码、测试、CLI 与 benchmark 均为本项目的 MoonBit 实现；没有复制其他仓库的源代码。算法来源和工程设计边界见 project_proposal.md 与 CHANGELOG.md。

#仓库与发布

Mooncakes 发布工作流只允许手动触发，发布前会再次执行 check/test；凭据只来自 CI secret 或经过确认的本地 moon login，不会进入仓库。

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io