moon-sketch-kit

    MoonBit streaming sketch toolkit for approximate analytics, drift checks, and compact data reports.

    sketch
    streaming
    analytics
    bloom-filter
    count-min
    moonbit
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    2 months ago
    Downloads
    16

    #Moon Sketch Kit

    Moon Sketch Kit 是一个用 MoonBit 实现的流式近似分析工具箱,目标是让 MoonBit 项目可以用很小的内存对事件流、日志 token、埋点数据或简单业务流水做快速画像。

    它不是 CSV 解析器,也不是 Web 展示项目,而是偏“基础算法 + 应用生态”的可复用库:把 Count-Min Sketch、Bloom Filter、HyperLogLog-lite、MinHash、Space-Saving Top-K、Reservoir Sampling、直方图、分位数、窗口漂移和质量门组合成一套可运行的分析工具。

    当前仓库上传后请替换:

    • GitHub: https://github.com/cauchyQ/moon-sketch-kit
    • GitLink: https://www.gitlink.org.cn/cauchyQ/moon-sketch-kit

    #适用场景

    • 日志或埋点流:统计高频事件、估算唯一用户数、抽样查看代表性 token。
    • 数据质量检查:比较两段流是否发生漂移,输出质量门和建议。
    • 浏览器或 CLI 小工具:用较小内存生成 Markdown / JSON 报告。
    • MoonBit 生态基础库:给上层可视化、CI 检查、监控示例提供可复用组件。

    #核心功能

    • Count-Min Sketch:近似频率统计,支持加权更新和误差报告。
    • Space-Saving Top-K:在线高频项发现。
    • HyperLogLog-lite:唯一值数量估算。
    • MinHash:集合相似度估算。
    • Bloom Filter:成员关系判断和误判率估计。
    • Reservoir Sampling:确定性抽样,便于测试和报告复现。
    • Histogram / Quantile:数值分布、P50/P90/P99 预览。
    • Windowed Stream:用 |; 分隔窗口,查看趋势、尖峰和 Top-K 时间线。
    • Quality Gate:比较 baseline / candidate,输出 pass/fail、问题列表和修复建议。
    • Token Profile:分析 token 类型、长度分布和前缀 Top-K。
    • Budget Planner:根据样本流推荐 sketch 参数。

    #安装和检查

    需要先安装 MoonBit 工具链。

    cd C:\Users\Lenovo\Desktop\Hot100\moon-sketch-kit moon update moon check moon test

    一键验证:

    .\scripts\verify.ps1

    当前测试覆盖核心路径:哈希稳定性、事件解析、Count-Min、Bloom、Top-K、HLL-lite、MinHash、Reservoir、Histogram、Quantile、Drift、Quality Gate、Weighted Stream、Windowed Stream、Token Profile 和 Budget Planner。

    #CLI 示例

    整体事件流报告:

    moon run cmd/main -- report "login view login cart checkout login"

    JSON 报告:

    moon run cmd/main -- json "login view login cart checkout login"

    窗口漂移报告:

    moon run cmd/main -- windows "login login view | view cart cart checkout | checkout refund refund"

    加权事件报告:

    moon run cmd/main -- weighted "login:12 view:7 checkout:3 refund:1"

    数值分布:

    moon run cmd/main -- histogram "12 18 21 21 35 89" 0 100 10 moon run cmd/main -- quantile "12 18 21 21 35 89"

    质量门:

    moon run cmd/main -- gate "login view login cart" "login login checkout refund"

    参数建议:

    moon run cmd/main -- budget "login view login cart checkout refund user42 user43" 6

    运行完整演示:

    .\scripts\demo.ps1

    #MoonBit API 示例

    ///|
    fn main {
    let report = @sketch.windowed_report_from_text(
    "login login view | view cart checkout | refund refund checkout",
    )
    println(@sketch.windowed_report_markdown(report))
    }

    可运行示例:

    moon run examples/basic moon run examples/windowed moon run examples/budget

    #测试集说明

    仓库内置 fixtures/ 目录,包含四类小样本:

    • fixtures/events.txt:普通事件流,用于整体报告、Top-K、Bloom、Token Profile。
    • fixtures/windowed.txt:带窗口分隔符的事件流,用于漂移报告和时间线。
    • fixtures/weighted.txtkey:weight 加权事件,用于加权 Count-Min。
    • fixtures/numbers.txt:数值序列,用于 Histogram 和 Quantile。

    这些测试集不追求大数据量,而是追求可读、可复现、便于验收时手工检查。

    #项目性质

    本项目为原创 MoonBit 实现。算法思想参考公开通用算法资料和业界常见 sketch 结构,但没有移植某个特定开源库,也没有复制第三方实现代码。

    许可证:Apache-2.0。

    #参赛交付清单

    • MoonBit 主要实现语言:核心库、CLI、示例和测试均为 MoonBit。
    • README:包含项目目标、安装、使用、示例、测试集说明。
    • CI:.github/workflows/ci.yml 覆盖 format、check、test、example run。
    • 测试:覆盖核心算法和报告输出。
    • 可运行示例:cmd/mainexamples/*
    • 开源许可证:LICENSE
    • mooncakes.io:上传仓库后再执行 moon register / moon login / moon publish

    BloomFilter

    pub(all) struct BloomFilter {
    size : Int
    hashes : Int
    inserted : Int
    bits : Array[Bool]
    } derive(Eq,
    Debug
    )

    Compact membership sketch with deterministic hashes.

    BloomStats

    pub(all) struct BloomStats {
    size : Int
    hashes : Int
    inserted : Int
    set_bits : Int
    fill_ratio : Double
    estimated_false_positive_rate : Double
    } derive(Eq,
    Debug
    )

    CountMinError

    pub(all) struct CountMinError {
    key : String
    exact : Int
    estimated : Int
    overestimate : Int
    } derive(Eq,
    Debug
    )

    CountMinErrorReport

    pub(all) struct CountMinErrorReport {
    total : Int
    max_overestimate : Int
    average_overestimate : Double
    rows : Array[CountMinError]
    } derive(Eq,
    Debug
    )

    CountMinSketch

    pub(all) struct CountMinSketch {
    width : Int
    depth : Int
    total : Int
    cells : Array[Int]
    } derive(Eq,
    Debug
    )

    EventWindow

    pub(all) struct EventWindow {
    index : Int
    label : String
    events : Array[String]
    } derive(Eq,
    Debug
    )

    A logical batch inside a stream. Window text uses | or ; as separators.

    ExactCounter

    pub(all) struct ExactCounter {
    keys : Array[String]
    counts : Array[Int]
    total : Int
    } derive(Eq,
    Debug
    )

    HistogramBucket

    pub(all) struct HistogramBucket {
    index : Int
    start : Int
    end : Int
    count : Int
    } derive(Eq,
    Debug
    )

    HistogramStats

    pub(all) struct HistogramStats {
    total : Int
    underflow : Int
    overflow : Int
    non_empty_buckets : Int
    mode_bucket : Int
    mode_count : Int
    } derive(Eq,
    Debug
    )

    HyperLogLogLite

    pub(all) struct HyperLogLogLite {
    buckets : Int
    registers : Array[Int]
    } derive(Eq,
    Debug
    )

    IntHistogram

    pub(all) struct IntHistogram {
    min : Int
    max : Int
    buckets : Int
    counts : Array[Int]
    underflow : Int
    overflow : Int
    total : Int
    } derive(Eq,
    Debug
    )

    Fixed-width integer histogram for quick distribution previews.

    MinHashSignature

    pub(all) struct MinHashSignature {
    seeds : Int
    values : Array[Int]
    } derive(Eq,
    Debug
    )

    NumericSummary

    pub(all) struct NumericSummary {
    count : Int
    min : Int?
    max : Int?
    sum : Int
    mean : Double?
    p50 : Int?
    p90 : Int?
    p99 : Int?
    } derive(Eq,
    Debug
    )

    QuantileSummary

    pub(all) struct QuantileSummary {
    values : Array[Int]
    sorted : Bool
    } derive(Eq,
    Debug
    )

    Exact-backed quantile summary for small to medium samples.

    It uses the same reporting interface that a future approximate quantile sketch can keep, so examples and CI workflows do not need to change.

    ReservoirSampler

    pub(all) struct ReservoirSampler {
    capacity : Int
    seen : Int
    samples : Array[String]
    } derive(Eq,
    Debug
    )

    SketchBudgetPlan

    pub(all) struct SketchBudgetPlan {
    expected_events : Int
    expected_unique : Int
    accuracy_level : Int
    count_min_width : Int
    count_min_depth : Int
    bloom_bits : Int
    bloom_hashes : Int
    hll_buckets : Int
    topk_capacity : Int
    reservoir_size : Int
    estimated_cells : Int
    } derive(Eq,
    Debug
    )

    SketchGateIssue

    pub(all) struct SketchGateIssue {
    severity : String
    rule : String
    metric : String
    message : String
    } derive(Eq,
    Debug
    )

    SketchGateReport

    pub(all) struct SketchGateReport {
    passed : Bool
    policy : SketchQualityPolicy
    drift : StreamDrift
    issues : Array[SketchGateIssue]
    } derive(Eq,
    Debug
    )

    SketchQualityPolicy

    pub(all) struct SketchQualityPolicy {
    max_event_delta : Int
    max_unique_delta : Int
    min_top_overlap : Double
    min_minhash_similarity : Double
    max_bloom_false_positive_rate : Double
    } derive(Eq,
    Debug
    )

    SketchRecommendation

    pub(all) struct SketchRecommendation {
    severity : String
    code : String
    title : String
    detail : String
    action : String
    } derive(Eq,
    Debug
    )

    SketchReport

    pub(all) struct SketchReport {
    item_count : Int
    unique_count : Int
    hll_estimate : Double
    topk : SpaceSavingTopK
    sampler : ReservoirSampler
    } derive(Eq,
    Debug
    )

    SpaceSavingTopK

    pub(all) struct SpaceSavingTopK {
    capacity : Int
    total : Int
    items : Array[TopKItem]
    } derive(Eq,
    Debug
    )

    StreamDrift

    pub(all) struct StreamDrift {
    baseline : StreamSnapshot
    candidate : StreamSnapshot
    event_delta : Int
    unique_delta : Int
    top_overlap : Double
    minhash_similarity : Double
    } derive(Eq,
    Debug
    )

    StreamSnapshot

    pub(all) struct StreamSnapshot {
    name : String
    events : Int
    exact_unique : Int
    hll_unique : Double
    topk : Array[TopKItem]
    sample : Array[String]
    bloom : BloomStats
    } derive(Eq,
    Debug
    )

    Compact snapshot of one stream for release notes, CI checks, and demos.

    TokenProfile

    pub(all) struct TokenProfile {
    total : Int
    unique : Int
    numeric : Int
    alphabetic : Int
    alphanumeric : Int
    mixed : Int
    min_length : Int
    max_length : Int
    average_length : Double
    length_histogram : IntHistogram
    prefix_topk : Array[TopKItem]
    } derive(Eq,
    Debug
    )

    TopKItem

    pub(all) struct TopKItem {
    key : String
    count : Int
    error : Int
    } derive(Eq,
    Debug
    )

    WeightedEvent

    pub(all) struct WeightedEvent {
    key : String
    weight : Int
    } derive(Eq,
    Debug
    )

    WeightedStreamSummary

    pub(all) struct WeightedStreamSummary {
    event_rows : Int
    total_weight : Int
    unique_keys : Int
    count_min : CountMinSketch
    exact : ExactCounter
    topk : Array[TopKItem]
    } derive(Eq,
    Debug
    )

    WindowChange

    pub(all) struct WindowChange {
    index : Int
    previous_label : String
    current_label : String
    event_delta : Int
    unique_delta : Int
    top_overlap : Double
    minhash_similarity : Double
    dominant_key : String
    dominant_count : Int
    } derive(Eq,
    Debug
    )

    WindowSnapshot

    pub(all) struct WindowSnapshot {
    index : Int
    label : String
    events : Int
    exact_unique : Int
    hll_unique : Double
    bloom_false_positive_rate : Double
    dominant_key : String
    dominant_count : Int
    topk : Array[TopKItem]
    } derive(Eq,
    Debug
    )

    WindowedStreamReport

    pub(all) struct WindowedStreamReport {
    windows : Array[WindowSnapshot]
    changes : Array[WindowChange]
    total_events : Int
    max_event_spike : Int
    min_similarity : Double
    } derive(Eq,
    Debug
    )

    bloom_add

    fn bloom_add(filter : BloomFilter, value : String) -> BloomFilter

    bloom_add_many

    fn bloom_add_many(filter : BloomFilter, values : Array[String]) -> BloomFilter

    bloom_from_items

    fn bloom_from_items(values : Array[String], size : Int, hashes : Int) -> BloomFilter

    bloom_json

    fn bloom_json(filter : BloomFilter) -> String

    bloom_markdown

    fn bloom_markdown(filter : BloomFilter, probes : Array[String]) -> String

    bloom_might_contain

    fn bloom_might_contain(filter : BloomFilter, value : String) -> Bool

    bloom_new

    fn bloom_new(size : Int, hashes : Int) -> BloomFilter

    bloom_set_bits

    fn bloom_set_bits(filter : BloomFilter) -> Int

    bloom_stats

    fn bloom_stats(filter : BloomFilter) -> BloomStats

    count_min_add

    fn count_min_add(sketch : CountMinSketch, key : String) -> CountMinSketch

    count_min_add_count

    fn count_min_add_count(sketch : CountMinSketch, key : String, count : Int) -> CountMinSketch

    count_min_error_markdown

    fn count_min_error_markdown(report : CountMinErrorReport) -> String

    count_min_error_report

    fn count_min_error_report(items : Array[String], probes : Array[String], width : Int, depth : Int) -> CountMinErrorReport

    count_min_estimate

    fn count_min_estimate(sketch : CountMinSketch, key : String) -> Int

    count_min_from_items

    fn count_min_from_items(items : Array[String], width : Int, depth : Int) -> CountMinSketch

    count_min_new

    fn count_min_new(width : Int, depth : Int) -> CountMinSketch

    count_min_summary_markdown

    fn count_min_summary_markdown(sketch : CountMinSketch, keys : Array[String]) -> String

    evaluate_stream_gate

    fn evaluate_stream_gate(baseline_name : String, baseline_input : String, candidate_name : String, candidate_input : String, policy : SketchQualityPolicy) -> SketchGateReport

    evaluate_stream_gate_default

    fn evaluate_stream_gate_default(baseline_input : String, candidate_input : String) -> SketchGateReport

    exact_counter_add

    fn exact_counter_add(counter : ExactCounter, key : String) -> ExactCounter

    exact_counter_count

    fn exact_counter_count(counter : ExactCounter, key : String) -> Int

    exact_counter_from_items

    fn exact_counter_from_items(items : Array[String]) -> ExactCounter

    exact_counter_markdown

    fn exact_counter_markdown(counter : ExactCounter, k : Int) -> String

    exact_counter_new

    fn exact_counter_new() -> ExactCounter

    exact_counter_topk

    fn exact_counter_topk(counter : ExactCounter, k : Int) -> Array[TopKItem]

    exact_counter_unique

    fn exact_counter_unique(counter : ExactCounter) -> Int

    exact_jaccard

    fn exact_jaccard(left : Array[String], right : Array[String]) -> Double

    histogram_add

    fn histogram_add(histogram : IntHistogram, value : Int) -> IntHistogram

    histogram_approx_percentile

    fn histogram_approx_percentile(histogram : IntHistogram, percentile : Int) -> Int?

    histogram_bucket_width

    fn histogram_bucket_width(histogram : IntHistogram) -> Int

    histogram_buckets

    fn histogram_buckets(histogram : IntHistogram) -> Array[HistogramBucket]

    histogram_from_text

    fn histogram_from_text(input : String, min : Int, max : Int, buckets : Int) -> IntHistogram

    histogram_from_values

    fn histogram_from_values(values : Array[Int], min : Int, max : Int, buckets : Int) -> IntHistogram

    histogram_index

    fn histogram_index(histogram : IntHistogram, value : Int) -> Int

    histogram_json

    fn histogram_json(histogram : IntHistogram) -> String

    histogram_markdown

    fn histogram_markdown(histogram : IntHistogram) -> String

    histogram_new

    fn histogram_new(min : Int, max : Int, buckets : Int) -> IntHistogram

    histogram_stats

    fn histogram_stats(histogram : IntHistogram) -> HistogramStats

    hll_add

    fn hll_add(hll : HyperLogLogLite, value : String) -> HyperLogLogLite

    hll_estimate

    fn hll_estimate(hll : HyperLogLogLite) -> Double

    hll_from_items

    fn hll_from_items(items : Array[String], buckets : Int) -> HyperLogLogLite

    hll_new

    fn hll_new(buckets : Int) -> HyperLogLogLite

    jaccard_report

    fn jaccard_report(left_input : String, right_input : String) -> String

    minhash_add

    fn minhash_add(signature : MinHashSignature, value : String) -> MinHashSignature

    minhash_from_items

    fn minhash_from_items(items : Array[String], seeds : Int) -> MinHashSignature

    minhash_new

    fn minhash_new(seeds : Int) -> MinHashSignature

    minhash_similarity

    fn minhash_similarity(left : MinHashSignature, right : MinHashSignature) -> Double

    numeric_summary

    fn numeric_summary(summary : QuantileSummary) -> NumericSummary

    numeric_summary_json

    fn numeric_summary_json(summary : QuantileSummary) -> String

    numeric_summary_markdown

    fn numeric_summary_markdown(summary : QuantileSummary) -> String

    parse_event_windows

    fn parse_event_windows(input : String) -> Array[EventWindow]

    parse_events

    fn parse_events(input : String) -> Array[String]

    parse_weighted_events

    fn parse_weighted_events(input : String) -> Array[WeightedEvent]

    parse_weighted_token

    fn parse_weighted_token(token : String) -> WeightedEvent?

    quantile_add

    fn quantile_add(summary : QuantileSummary, value : Int) -> QuantileSummary

    quantile_compare_markdown

    fn quantile_compare_markdown(baseline : QuantileSummary, candidate : QuantileSummary) -> String

    quantile_from_text

    fn quantile_from_text(input : String) -> QuantileSummary

    quantile_from_values

    fn quantile_from_values(values : Array[Int]) -> QuantileSummary

    quantile_new

    fn quantile_new() -> QuantileSummary

    quantile_sorted

    fn quantile_sorted(summary : QuantileSummary) -> QuantileSummary

    quantile_value

    fn quantile_value(summary : QuantileSummary, percentile : Int) -> Int?

    recommendations_from_gate

    fn recommendations_from_gate(report : SketchGateReport) -> Array[SketchRecommendation]

    recommendations_from_weighted

    fn recommendations_from_weighted(summary : WeightedStreamSummary) -> Array[SketchRecommendation]

    recommendations_from_windowed

    fn recommendations_from_windowed(report : WindowedStreamReport) -> Array[SketchRecommendation]

    recommendations_json

    fn recommendations_json(items : Array[SketchRecommendation]) -> String

    recommendations_markdown

    fn recommendations_markdown(items : Array[SketchRecommendation]) -> String

    reservoir_add

    fn reservoir_add(sampler : ReservoirSampler, value : String) -> ReservoirSampler

    reservoir_from_items

    fn reservoir_from_items(items : Array[String], capacity : Int) -> ReservoirSampler

    reservoir_markdown

    fn reservoir_markdown(sampler : ReservoirSampler) -> String

    reservoir_new

    fn reservoir_new(capacity : Int) -> ReservoirSampler

    sketch_budget_from_text

    fn sketch_budget_from_text(input : String, accuracy_level : Int) -> SketchBudgetPlan

    sketch_budget_json

    fn sketch_budget_json(plan : SketchBudgetPlan) -> String

    sketch_budget_markdown

    fn sketch_budget_markdown(plan : SketchBudgetPlan) -> String

    sketch_budget_plan

    fn sketch_budget_plan(expected_events : Int, expected_unique : Int, accuracy_level : Int) -> SketchBudgetPlan

    sketch_budget_recommendations

    fn sketch_budget_recommendations(plan : SketchBudgetPlan) -> Array[SketchRecommendation]

    sketch_gate_issue

    fn sketch_gate_issue(severity : String, rule : String, metric : String, message : String) -> SketchGateIssue

    sketch_gate_json

    fn sketch_gate_json(report : SketchGateReport) -> String

    sketch_gate_markdown

    fn sketch_gate_markdown(report : SketchGateReport) -> String

    sketch_hash

    fn sketch_hash(value : String, seed : Int) -> Int

    Stable hash used by all sketches in this package.

    The implementation is intentionally deterministic across targets. It is not cryptographic; it is meant for repeatable sketch indexing, examples, and tests.

    sketch_quality_policy_default

    fn sketch_quality_policy_default() -> SketchQualityPolicy

    sketch_quality_policy_strict

    fn sketch_quality_policy_strict() -> SketchQualityPolicy

    sketch_recommendation

    fn sketch_recommendation(severity : String, code : String, title : String, detail : String, action : String) -> SketchRecommendation

    sketch_report

    fn sketch_report(items : Array[String], topk_size : Int, sample_size : Int) -> SketchReport

    sketch_report_json

    fn sketch_report_json(input : String) -> String

    sketch_report_markdown

    fn sketch_report_markdown(input : String) -> String

    stream_drift

    fn stream_drift(baseline_name : String, baseline_input : String, candidate_name : String, candidate_input : String) -> StreamDrift

    stream_drift_json

    fn stream_drift_json(baseline_name : String, baseline_input : String, candidate_name : String, candidate_input : String) -> String

    stream_drift_markdown

    fn stream_drift_markdown(baseline_name : String, baseline_input : String, candidate_name : String, candidate_input : String) -> String

    stream_snapshot

    fn stream_snapshot(name : String, input : String) -> StreamSnapshot

    stream_snapshot_json

    fn stream_snapshot_json(snapshot : StreamSnapshot) -> String

    stream_snapshot_markdown

    fn stream_snapshot_markdown(snapshot : StreamSnapshot) -> String

    token_profile

    fn token_profile(items : Array[String], prefix_length : Int) -> TokenProfile

    token_profile_from_text

    fn token_profile_from_text(input : String, prefix_length : Int) -> TokenProfile

    token_profile_json

    fn token_profile_json(profile : TokenProfile) -> String

    token_profile_markdown

    fn token_profile_markdown(profile : TokenProfile) -> String

    token_profile_recommendations

    fn token_profile_recommendations(profile : TokenProfile) -> Array[SketchRecommendation]

    topk_add

    fn topk_add(topk : SpaceSavingTopK, key : String) -> SpaceSavingTopK

    topk_from_items

    fn topk_from_items(items : Array[String], capacity : Int) -> SpaceSavingTopK

    topk_markdown

    fn topk_markdown(topk : SpaceSavingTopK) -> String

    topk_new

    fn topk_new(capacity : Int) -> SpaceSavingTopK

    weighted_compare_markdown

    fn weighted_compare_markdown(baseline : WeightedStreamSummary, candidate : WeightedStreamSummary) -> String

    weighted_estimate

    fn weighted_estimate(summary : WeightedStreamSummary, key : String) -> Int

    weighted_event

    fn weighted_event(key : String, weight : Int) -> WeightedEvent

    weighted_summary

    fn weighted_summary(events : Array[WeightedEvent], width : Int, depth : Int, k : Int) -> WeightedStreamSummary

    weighted_summary_from_text

    fn weighted_summary_from_text(input : String) -> WeightedStreamSummary

    weighted_summary_json

    fn weighted_summary_json(summary : WeightedStreamSummary) -> String

    weighted_summary_markdown

    fn weighted_summary_markdown(summary : WeightedStreamSummary) -> String

    window_change

    fn window_change(previous : WindowSnapshot, current : WindowSnapshot) -> WindowChange

    window_snapshot

    fn window_snapshot(window : EventWindow) -> WindowSnapshot

    windowed_report

    fn windowed_report(windows : Array[EventWindow]) -> WindowedStreamReport

    windowed_report_from_text

    fn windowed_report_from_text(input : String) -> WindowedStreamReport

    windowed_report_json

    fn windowed_report_json(report : WindowedStreamReport) -> String

    windowed_report_markdown

    fn windowed_report_markdown(report : WindowedStreamReport) -> String

    windowed_topk_timeline_markdown

    fn windowed_topk_timeline_markdown(report : WindowedStreamReport) -> String