moon-latency

    Mergeable integer latency histograms with quantile and threshold bounds

    histogram
    latency
    quantiles
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    11 hours ago
    Downloads
    5

    No dependencies

    #MoonLatency

    MoonLatency 是纯 MoonBit 的整数延迟直方图。每个工作节点可以用单个直方图汇总请求耗时,随后合并节点结果,查询全局分位数以及满足延迟阈值的请求数。调用方统一时间单位,例如毫秒或微秒。

    moon run cmd/main --release moon test --release --deny-warn

    演示将两个节点的 200 条观测合并,得到 p99 区间 [400, 415] ms,以及不超过 400 ms 的请求数量区间 [194, 200]。如果业务要求至少 198 条请求达标,这个摘要只能判断证据不足,因为该阈值落在一个包含观测的桶内。

    #接口

    用 Histogram::new() 创建摘要。调用 record(value, count=...) 记录非负 Int64 延迟或一批相同延迟。用 merge 合并相同单位的摘要。非法值、非法权重或计数溢出返回 false,现有数据保留。

    quantile(p) 使用百万分比,990000 表示 p99。分位数按 nearest-rank 定义,0 返回最小值所在区间,1000000 返回最大值所在区间。空摘要或超出范围的参数返回 None。count_at_most(threshold) 返回包含真实计数的闭区间。

    #算法和边界

    0~31 逐值分桶。从 32 开始,每个二次幂区间均分为 16 桶,覆盖到 Int64 最大值。每个摘要有 960 个计数槽,桶界在模块内共享。录入用二分查找,合并和查询最多扫描 960 桶。合并逐桶相加,同一批观测的分桶结果与分片方式无关。

    对精确分位数,目标秩对应的所有候选值都在返回桶内,桶宽至多为下界的 1/16。对阈值,完全落在阈值内的桶构成计数下界,再加上跨越阈值的桶得到上界。在桶右边界上,计数为精确值。

    跨进程交换通过 snapshot() 和 Histogram::from_snapshot() 完成。MLH1 以四字节 ASCII 标识开头,随后每个非空桶以大端 u16 桶号和正 i64 计数组成十字节记录。桶号必须严格递增。空摘要四字节,最密摘要 9,604 字节。调用方需统一度量单位,并负责传输和数据完整性。

    assess_slo(threshold, target) 返回达标、未达标、证据不足或无样本。阈值使用原延迟单位,目标比例使用百万分比。分类依据通过计数的上下界,只有整个区间都满足目标时才标记达标。

    Window::new(width, slots) 汇总最近若干对齐的时间桶。以 merge_at(time, shard) 提交分片摘要,通过 advance(time) 推进空闲期,使用 summary() 取得独立快照。窗口允许同一时间桶多次汇入,拒绝更早的时间桶。过期桶从总摘要中扣除。调用方应在同一时间桶内汇总同批数据,并处理去重。

    Histogram::distribution() 为同一批数据一次性构建前缀计数。多个分位数与阈值查询可用这个不可变视图进行二分查找,也可查询闭区间内的计数上下界。

    Shard 携带延迟单位、来源编号、序号、时间戳及 MLH1 内容。采集器生成的 MLS2 还声明采集桶宽,接收时整片必须落在同一个接收桶内。旧 MLS1 仍按时间戳归桶,采集区间由发送方保证与接收配置相容。Collector 按来源与序号去重,校验单位与身份冲突,接受仍在窗口内的乱序分片。所有分片时间戳必须采用统一时间轴。

    moon build --target js --release --deny-warn node _build/js/release/build/cmd/collect/collect.js --help python scripts/check_collect.py

    文件汇总命令使用 Node.js。参数依次为延迟单位、时间桶宽度、桶数、延迟阈值、目标百万分比和 MLS1、MLS2 或 MLB1 文件路径。输出 JSON 中的 Int64 计数使用十进制字符串。

    #采集、批次和恢复

    Producer 按时间桶汇总一个来源的样本。时间戳必须非递减,可重复,跨桶时返回上一桶的 Shard。finish() 封存最后一桶。输入为文本时,SampleInput 支持分块读取 timestamp,latency[,weight] 整数记录,默认权重为 1。坏行报告物理行号,出错前已交付的分片保留。

    MLB1 批次以四字节标识和大端 u16 分片数开始,随后每片有大端 u16 长度和对应 MLS1 或 MLS2 字节。单批最多 1,024 片。receive_batch_bytes 按输入顺序处理,在全部接收成功后提交状态。批次中的单位、时间桶、身份或计数冲突会使整批回滚。

    Collector::checkpoint 导出 MLC1 检查点。恢复时重建窗口和当前去重状态,保留时间游标及汇总配置。检查点应保存在可信存储中,调用方负责完整性与原子写入。

    Collector::series 按时间顺序返回当前活动窗口中每桶的 SLO 结论,缺失的桶标记无样本。compare_quantile 对两个同单位的分布给出分位值变化的上下界。区间重叠时会返回不确定。

    #多服务和日志重放

    Registry 给各服务独立的单位、窗口和重试记录。receive_atomic 可跨服务一次提交多片数据。Registry::checkpoint 保存全部服务的状态。对累计监控计数,可用 Shard::delta 转为增量,并检测桶计数回退和序号错误。调用方需在桶边界采集累计快照,才能准确归属增量。

    多服务报告使用版本化 JSON 配置。下面是一个完整配置示例:

    {"version":"1","services":[{"service":"api","unit":"ms","width":"10","slots":3,"identities":256,"objectives":[{"name":"p99","threshold":"400","target":990000}]}]}

    moon build --target js --release --deny-warn node _build/js/release/build/cmd/produce/produce.js --help node _build/js/release/build/cmd/collect/collect.js fleet config.json api=api.mls node _build/js/release/build/cmd/collect/collect.js journal --help python scripts/check_collect.py

    produce 逐块读取 CSV,每行输出一片 MLS2 的十六进制表示。文件汇总器读取二进制 MLS1、MLS2 或 MLB1。日志打包用二进制标准输出,Windows 下使用支持二进制重定向的 shell。MLJ1 在标识后保存多个帧,每帧包含大端 u32 批次长度、批次内容和大端 u32 CRC-32。重放按帧提交,尾部截断或校验失败会报错,之前成功帧保留。CRC-32 用于发现意外损坏。

    运行 moon run cmd/bench --release 可生成窄分布、长尾分布和突发负载的 JSONL 基准。程序按相同输入对照排序真值,记录写入、合并、查询的实测耗时及快照字节数。

    快照、分片和日志的字段顺序及重放语义见 二进制格式。

    运行 moon run cmd/bench_ingest --release 可复测 1,024 槽窗口的单片接收和小批次处理。每组接收 192 片,并核对最终计数。

    项目独立实现,遵循 Apache-2.0。相关近似分位技术可参阅 Apache DataSketches KLL。

    BatchCollectError

    pub(all) enum BatchCollectError {
    MalformedBatch(BatchError)
    BatchTooLarge
    RejectedShard(Int, CollectError)
    }

    BatchError

    pub(all) enum BatchError {
    InvalidBatchSize
    InvalidBatchHeader
    InvalidBatchFrame(Int)
    InvalidBatchShard(Int, ShardError)
    }

    BatchReceipt

    pub(all) struct BatchReceipt {
    added : Int
    duplicates : Int
    }

    CheckpointError

    pub(all) enum CheckpointError {
    BadCheckpointHeader
    BadCheckpointConfiguration
    BadCheckpointFrame(Int)
    BadCheckpointShard(Int, ShardError)
    BadCheckpointState(Int, CollectError)
    }

    CollectError

    pub(all) enum CollectError {
    WindowFailure(WindowError)
    ShardFailure(ShardError)
    UnitMismatch
    IncompatibleTimeBucket
    ConflictingIdentity
    IdentityBudget
    }

    Collector

    pub struct Collector {
    // private fields
    }

    Collector::advance

    fn Collector::advance(self : Collector, timestamp : Int64) -> Result[Unit, CollectError]

    Collector::checkpoint

    fn Collector::checkpoint(self : Collector) -> Bytes

    MLC1 stores the collector configuration, epoch cursor, and active shards. The wire format is a snapshot of accepted reports, not a memory dump.

    Collector::new

    fn Collector::new(unit : LatencyUnit, width : Int64, slots : Int, identities? : Int) -> Result[Collector, CollectError]

    Collector::receive

    fn Collector::receive(self : Collector, shard : Shard) -> Result[Receipt, CollectError]

    Collector::receive_batch

    fn Collector::receive_batch(self : Collector, shards : Array[Shard]) -> Result[BatchReceipt, BatchCollectError]

    Process in input order and apply all changes only after success.

    Collector::receive_batch_bytes

    fn Collector::receive_batch_bytes(self : Collector, bytes : Bytes) -> Result[BatchReceipt, BatchCollectError]

    Collector::receive_bytes

    fn Collector::receive_bytes(self : Collector, bytes : Bytes) -> Result[Receipt, CollectError]

    Collector::restore

    fn Collector::restore(bytes : Bytes) -> Result[Collector, CheckpointError]

    Collector::series

    fn Collector::series(self : Collector, threshold : Int64, target : Int) -> Array[EpochReport]?

    Collector::summary

    fn Collector::summary(self : Collector) -> Histogram

    ConfigError

    pub(all) enum ConfigError {
    ConfigSize
    ConfigSyntax
    ConfigVersion
    InvalidServiceConfig(Int)
    ServiceRejected(Int, RegistryError)
    ObjectiveRejected(Int, PolicyError)
    }

    DeltaError

    pub(all) enum DeltaError {
    UnitChanged
    SourceChanged
    SequenceDidNotIncrease
    TimestampWentBackward
    BucketDecreased(Int)
    }

    Deployment

    pub struct Deployment {
    // private fields
    }

    Validated per-service configurations and policies for a collector deployment.

    Deployment::parse

    fn Deployment::parse(text : String) -> Result[Deployment, ConfigError]

    Deployment::registry

    fn Deployment::registry(self : Deployment) -> Registry

    Deployment::report

    Deployment::report_json

    fn Deployment::report_json(self : Deployment, registry : Registry) -> Result[String, RegistryError]

    Deployment::to_json

    fn Deployment::to_json(self : Deployment) -> String

    Distribution

    pub struct Distribution {
    // private fields
    }

    Immutable prefix counts for repeated queries over one observation set.

    Distribution::count

    fn Distribution::count(self : Distribution) -> Int64

    Distribution::count_at_most

    fn Distribution::count_at_most(self : Distribution, threshold : Int64) -> Interval

    Distribution::count_between

    fn Distribution::count_between(self : Distribution, lower : Int64, upper : Int64) -> Interval?

    Count observations in an inclusive interval without counting the same partially covered bucket twice in the upper bound.

    Distribution::quantile

    fn Distribution::quantile(self : Distribution, p : Int) -> Interval?

    EpochReport

    pub(all) struct EpochReport {
    epoch : Int64
    started_at : Int64
    result : SloReport
    }

    EpochReport::to_json

    Histogram

    pub struct Histogram {
    // private fields
    }

    Histogram::assess_slo

    fn Histogram::assess_slo(self : Histogram, threshold : Int64, target : Int) -> SloReport?

    Assess a latency threshold and required passing fraction in millionths.

    Histogram::count

    fn Histogram::count(self : Histogram) -> Int64

    Histogram::count_at_most

    fn Histogram::count_at_most(self : Histogram, threshold : Int64) -> Interval

    Return lower and upper bounds on the number of observations <= threshold.

    Histogram::delta

    fn Histogram::delta(self : Histogram, baseline : Histogram) -> Result[Histogram, DeltaError]

    Compute the increment between two cumulative snapshots of the same series. The first decreasing bucket is returned so callers can detect resets.

    Histogram::distribution

    fn Histogram::distribution(self : Histogram) -> Distribution

    Histogram::from_snapshot

    fn Histogram::from_snapshot(bytes : Bytes) -> Result[Histogram, SnapshotError]

    Histogram::merge

    fn Histogram::merge(self : Histogram, other : Histogram) -> Bool

    Histogram::new

    fn Histogram::new() -> Histogram

    Histogram::quantile

    fn Histogram::quantile(self : Histogram, p : Int) -> Interval?

    Nearest-rank quantile. p is in millionths, from 0 (minimum) to 1,000,000.

    Histogram::record

    fn Histogram::record(self : Histogram, value : Int64, count? : Int64) -> Bool

    Histogram::snapshot

    fn Histogram::snapshot(self : Histogram) -> Bytes

    InputError

    pub(all) enum InputError {
    InputClosed
    ChunkTooLarge
    LineTooLong(Int64)
    InvalidRow(Int64)
    InvalidReading(Int64, ProducerError)
    }

    Interval

    pub(all) struct Interval {
    lower : Int64
    upper : Int64
    }

    JournalError

    pub(all) enum JournalError {
    JournalClosed
    BadJournalMagic
    BadFrameLength(Int64)
    BadFrameChecksum(Int64)
    UnexpectedEnd(Int64)
    BadJournalBatch(Int64, BatchCollectError)
    OversizedChunk
    }

    JournalReader

    pub struct JournalReader {
    // private fields
    }

    Incremental MLJ1 reader. Completed batches are applied atomically. A bad frame seals the reader and preserves the accepted frame prefix.

    JournalReader::feed

    fn JournalReader::feed(self : JournalReader, chunk : BytesView, emit : (BatchReceipt) -> Unit) -> Result[Unit, JournalError]

    Reentrant reads and closes are rejected during callback delivery.

    JournalReader::finish

    fn JournalReader::finish(self : JournalReader) -> Result[Unit, JournalError]

    JournalReader::frames

    fn JournalReader::frames(self : JournalReader) -> Int64

    JournalReader::new

    fn JournalReader::new(collector : Collector) -> JournalReader

    JournalWriter

    pub struct JournalWriter {
    // private fields
    }

    Collect shards into bounded frames. An oversized next frame is split before accepting the next shard, without dropping it.

    JournalWriter::finish

    fn JournalWriter::finish(self : JournalWriter) -> Result[Bytes?, WriterError]

    JournalWriter::flush

    fn JournalWriter::flush(self : JournalWriter) -> Result[Bytes?, WriterError]

    JournalWriter::new

    fn JournalWriter::new(count_limit? : Int, bytes_limit? : Int) -> Result[JournalWriter, WriterError]

    JournalWriter::pending_count

    fn JournalWriter::pending_count(self : JournalWriter) -> Int

    JournalWriter::push

    fn JournalWriter::push(self : JournalWriter, shard : Shard) -> Result[Bytes?, WriterError]

    LatencyChange

    pub(all) enum LatencyChange {
    Slower
    Faster
    Uncertain
    ExactTie
    MissingSamples
    }

    LatencyUnit

    pub(all) enum LatencyUnit {
    Nanoseconds
    Microseconds
    Milliseconds
    }

    LatencyUnit::name

    fn LatencyUnit::name(self : LatencyUnit) -> String

    LatencyUnit::parse

    fn LatencyUnit::parse(name : String) -> LatencyUnit?

    Objective

    pub(all) struct Objective {
    name : String
    threshold : Int64
    target : Int
    }

    ObjectiveResult

    pub(all) struct ObjectiveResult {
    objective : Objective
    report : SloReport
    allowed_failures : Int64
    observed_failures : Interval
    }

    ObjectiveResult::to_json

    ObjectiveTransition

    pub(all) struct ObjectiveTransition {
    previous : ObjectiveResult
    current : ObjectiveResult
    }

    Aggregate evaluation across a before/after deployment without averaging the fractions from different sample sizes.

    Policy

    pub struct Policy {
    // private fields
    }

    Policy::compare

    fn Policy::compare(self : Policy, previous : Distribution, current : Distribution) -> Array[ObjectiveTransition]

    Policy::evaluate

    fn Policy::evaluate(self : Policy, distribution : Distribution) -> Array[ObjectiveResult]

    Policy::new

    fn Policy::new(objectives : Array[Objective]) -> Result[Policy, PolicyError]

    PolicyError

    pub(all) enum PolicyError {
    EmptyPolicy
    TooManyObjectives
    InvalidObjective(Int)
    DuplicateObjective(Int)
    }

    Producer

    pub struct Producer {
    // private fields
    }

    Producer::finish

    fn Producer::finish(self : Producer) -> Shard?

    Producer::new

    fn Producer::new(source : Int64, unit : LatencyUnit, width : Int64, sequence? : Int64) -> Result[Producer, ProducerError]

    Producer::pending_count

    fn Producer::pending_count(self : Producer) -> Int64

    Producer::record

    fn Producer::record(self : Producer, timestamp : Int64, latency : Int64, count? : Int64) -> Result[Shard?, ProducerError]

    Record a sample. Moving to a new epoch returns the preceding shard.

    ProducerError

    pub(all) enum ProducerError {
    InvalidProducer
    InvalidSample
    SampleOutOfOrder
    SampleCountOverflow
    SequenceExhausted
    ProducerFinished
    }

    QuantileComparison

    pub(all) struct QuantileComparison {
    baseline : Interval?
    current : Interval?
    change : LatencyChange
    difference : Interval?
    }

    Receipt

    pub(all) enum Receipt {
    Added
    Duplicate
    }

    Registry

    pub struct Registry {
    // private fields
    }

    Independent clocks and retry identities for named services.

    Registry::advance

    fn Registry::advance(self : Registry, service : String, timestamp : Int64) -> Result[Unit, RegistryError]

    Registry::checkpoint

    fn Registry::checkpoint(self : Registry) -> Bytes

    MLR1 serializes each configured service in name order.

    Registry::evaluate

    fn Registry::evaluate(self : Registry, service : String, policy : Policy) -> Result[ServiceReport, RegistryError]

    Evaluate objectives for a service without mixing incompatible units.

    Registry::names

    fn Registry::names(self : Registry) -> Array[String]

    Registry::new

    fn Registry::new(capacity? : Int) -> Result[Registry, RegistryError]

    Registry::receive_atomic

    fn Registry::receive_atomic(self : Registry, routes : Array[RoutedShard]) -> Result[BatchReceipt, RouteTransactionError]

    A transaction lazily clones only the named services it touches.

    Registry::receive_batch_bytes

    fn Registry::receive_batch_bytes(self : Registry, service : String, bytes : Bytes) -> Result[BatchReceipt, RegistryError]

    Registry::receive_bytes

    fn Registry::receive_bytes(self : Registry, service : String, bytes : Bytes) -> Result[Receipt, RegistryError]

    Registry::register

    fn Registry::register(self : Registry, config : ServiceConfig) -> Result[Unit, RegistryError]

    Registry::remove

    fn Registry::remove(self : Registry, service : String) -> Bool

    Registry::restore

    fn Registry::restore(bytes : Bytes) -> Result[Registry, RegistryCheckpointError]

    Registry::summary

    fn Registry::summary(self : Registry, service : String) -> Result[Histogram, RegistryError]

    RegistryCheckpointError

    pub(all) enum RegistryCheckpointError {
    RegistryHeader
    RegistryFrame(Int)
    RegistryName(Int)
    RegistryQuota(Int)
    ServiceCheckpoint(Int, CheckpointError)
    }

    RegistryError

    pub(all) enum RegistryError {
    InvalidService
    DuplicateService
    UnknownService
    ServiceBudget
    RoutedFailure(CollectError)
    RoutedBatchFailure(BatchCollectError)
    }

    ReplayError

    pub(all) enum ReplayError {
    BadReadSize
    ReadFailure(String)
    JournalFailure(JournalError)
    }

    ReplayStats

    pub(all) struct ReplayStats {
    frames : Int64
    added : Int64
    duplicates : Int64
    bytes : Int64
    }

    RouteTransactionError

    pub(all) enum RouteTransactionError {
    TooManyRoutes
    InvalidRoute(Int, RegistryError)
    }

    RoutedShard

    pub(all) struct RoutedShard {
    service : String
    shard : Shard
    }

    SampleInput

    pub struct SampleInput {
    // private fields
    }

    Incremental reader for integer timestamp,latency[,weight] rows.

    SampleInput::feed

    fn SampleInput::feed(self : SampleInput, chunk : String, emit : (Shard) -> Unit) -> Result[Unit, InputError]

    Completed shards are emitted before a later bad row is reported. Reentrant feed or finish calls are rejected while the callback is active.

    SampleInput::finish

    SampleInput::new

    fn SampleInput::new(producer : Producer) -> SampleInput

    ServiceConfig

    pub(all) struct ServiceConfig {
    service : String
    unit : LatencyUnit
    width : Int64
    slots : Int
    identities : Int
    }

    ServiceReport

    pub(all) struct ServiceReport {
    service : String
    unit : LatencyUnit
    objectives : Array[ObjectiveResult]
    }

    ServiceReport::to_json

    Shard

    pub struct Shard {
    // private fields
    }

    Identity is the pair (source, sequence). Producers must not reuse it while a previous report with that identity can still be retried.

    Shard::bucket_width

    fn Shard::bucket_width(self : Shard) -> Int64

    Zero denotes point data or an MLS1 shard without coverage metadata.

    Shard::decode

    fn Shard::decode(bytes : Bytes) -> Result[Shard, ShardError]

    Shard::delta

    fn Shard::delta(self : Shard, baseline : Shard) -> Result[Shard, DeltaError]

    Convert a cumulative report into an incremental shard for the collector. The caller must align collection with window epochs if exact attribution to those epochs is required.

    Shard::encode

    fn Shard::encode(self : Shard) -> Bytes

    MLS2 adds an aligned bucket width after the MLS1 timestamp.

    Shard::identity

    fn Shard::identity(self : Shard) -> (Int64, Int64)

    Shard::new

    fn Shard::new(source : Int64, sequence : Int64, timestamp : Int64, unit : LatencyUnit, histogram : Histogram, width? : Int64) -> Result[Shard, ShardError]

    Shard::timestamp

    fn Shard::timestamp(self : Shard) -> Int64

    Shard::unit

    fn Shard::unit(self : Shard) -> LatencyUnit

    ShardError

    pub(all) enum ShardError {
    InvalidMetadata
    InvalidEncoding
    InvalidHistogram(SnapshotError)
    }

    SloReport

    pub(all) struct SloReport {
    total : Int64
    passing : Interval
    required : Int64
    status : SloStatus
    }

    SloReport::to_json

    SloStatus

    pub(all) enum SloStatus {
    Met
    Missed
    Indeterminate
    NoSamples
    }

    SloStatus::name

    fn SloStatus::name(self : SloStatus) -> String

    SnapshotError

    pub(all) enum SnapshotError {
    InvalidSize
    InvalidHeader
    InvalidBucketOrder
    InvalidCount
    }

    Window

    pub struct Window {
    // private fields
    }

    A rolling histogram over a fixed number of aligned time buckets.

    Window::advance

    fn Window::advance(self : Window, time : Int64) -> Result[Unit, WindowError]

    Window::merge_at

    fn Window::merge_at(self : Window, time : Int64, shard : Histogram) -> Result[Unit, WindowError]

    Insert a shard summary. Timestamps identify aligned time buckets. Rejection leaves both the contents and the time cursor unchanged.

    Window::new

    fn Window::new(width : Int64, slots : Int) -> Result[Window, WindowError]

    Window::series

    fn Window::series(self : Window, threshold : Int64, target : Int) -> Array[EpochReport]?

    Report all live epochs, including gaps with no samples. Results are ordered oldest first. The final epoch can still accept shard updates.

    Window::summary

    fn Window::summary(self : Window) -> Histogram

    WindowError

    pub(all) enum WindowError {
    InvalidConfiguration
    InvalidObservation
    ClockWentBackward
    CountOverflow
    }

    WriterError

    pub(all) enum WriterError {
    WriterClosed
    FrameRejected(BatchError)
    InvalidWriterLimit
    ShardExceedsFrameLimit
    }

    compare_quantile

    fn compare_quantile(baseline : Distribution, current : Distribution, percentile : Int) -> QuantileComparison?

    Compare nearest-rank latency intervals without assuming an ordering when the two sets admit overlapping quantile values.

    decode_batch

    fn decode_batch(bytes : Bytes) -> Result[Array[Shard], BatchError]

    encode_batch

    fn encode_batch(shards : Array[Shard]) -> Result[Bytes, BatchError]

    Portable batch with a fixed header, a count, and length-prefixed shards.

    journal_frame

    fn journal_frame(shards : Array[Shard]) -> Result[Bytes, BatchError]

    Append a single frame following the MLJ1 header (or another frame).

    journal_header

    fn journal_header() -> Bytes

    replay_journal

    fn replay_journal(collector : Collector, read : () -> Result[Bytes?, String]) -> Result[ReplayStats, ReplayError]

    Pull one chunk at a time from the host. The callback returns None at EOF. A nonempty chunk is required so each successful read makes progress.