Sign in

    moontxnwitness

    Offline transactional history analysis with independently verifiable dependency-cycle witnesses

    transactions
    serializability
    witness
    consistency
    offline
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    2 hours ago
    Downloads
    25

    #MoonTxnWitness v0.1.0

    用 MoonBit 把事务并发日志变成可解释、可缩减、可回放的反例。 面向数据库与后端开发者,连接真实采集、异常解释、反例缩减、证据复现和修复回归。分析在本地完成。

    English: An offline MoonBit transaction-history checker with shortest cycle witnesses, bounded serial completion, transaction reduction and reproducible database examples.

    #先运行完整演示

    下载 portable ZIP,解压后运行。需要 Node.js ≥20,本机验证使用 24.13.0:

    node dist/moontxnwitness.mjs --version node dist/demo.mjs

    Windows 也可双击 run-demo.cmd。演示使用推荐的 balanced 入口,在新的 moontxnwitness-demo-* 目录保存中文报告、7→2 事务缩减、模型对照和 schema-2 复现包。先打开 report.md。演示使用合成案例;真实数据库流程见下文。

    #检查、缩减、复现

    node dist/moontxnwitness.mjs check examples/write-skew.json --profile balanced node dist/moontxnwitness.mjs check examples/fractured-observation.json --profile balanced --format json node dist/moontxnwitness.mjs shrink examples/noisy-write-skew.json --profile balanced --output reduction.json --history mini.json node dist/moontxnwitness.mjs check mini.json --profile balanced --format markdown --output report.md --capsule case.capsule.json node dist/moontxnwitness.mjs replay case.capsule.json node dist/moontxnwitness.mjs compare-models examples/strict-realtime.json

    导出拒绝覆盖已有文件。check 支持 text/json/markdown/dot;异常返回 1 是预期结果。

    状态退出码含义
    consistent0当前模型与约束内有可行串行执行,无未解决缺失
    violation1有直接读写异常、依赖环或完整搜索无解
    invalid2输入或约束不合法
    inconclusive3缺少观察或计算预算不足

    complete 不认证采集真实性或采集窗口完整。oneMinimal 只表示当前分析规则与预算下,删除任何一个剩余事务都不能保留确定异常;它不表示全局最少事务或最少操作。

    #真实 PostgreSQL 18 闭环

    按照 PostgreSQL 采集说明 安装可选 Python 驱动、配置测试数据库,然后运行:

    node dist/postgres-demo.mjs

    同一入口连续执行 20 轮 Repeatable Read 写偏斜和 20 轮 Serializable 回滚/全新事务重试对照,分析两份真实历史,把异常缩成两事务,并回放三个 v2 复现包。保存 SQL 结果、提交确认、40001 回滚、JSONL 日志和摘要。两连接先点读,再经同步屏障写入;不从自增序号或线程返回时间推断提交顺序。

    缺少 Python、驱动或连接配置时明确返回 not-executed、passed:false 和退出码 3;实际运行失败保留失败记录。每次只创建和清理自己的随机测试 schema,输出放在新目录。源码另有临时实例辅助入口和独立 Linux PostgreSQL CI。

    SQLite 顺序与真实 WAL 并发案例使用 Python 标准库。这些实验检查所捕获的执行,不认证整个数据库,也不将隔离级别允许的现象称作漏洞。

    #输入与判断依据

    每次同键写入必须有唯一版本身份;业务值相同的两次写入也使用不同标记。

    { "schemaVersion": 1, "model": "serializable", "initial": {"x": "x0", "y": "y0"}, "transactions": [ {"id": "A", "status": "committed", "ops": [ {"type": "read", "key": "x", "version": "x0"}, {"type": "write", "key": "y", "version": "y1"} ]}, {"id": "B", "status": "committed", "ops": [ {"type": "read", "key": "y", "version": "y0"}, {"type": "write", "key": "x", "version": "x1"} ]} ] }

    这份日志要求 A 在 B 前、B 又在 A 前,形成两事务环。报告保留依赖的键、操作下标、版本和来源,并寻找图中全局最短的有向环。

    • serializable 检查整个事务的串行执行;strict-serializable 再尊重共同单调观察时钟中明确先完成、后开始的约束。
    • 事务状态为 committed/aborted/unknown;缺少结果、来源或共同时间时明确指出。
    • versionOrders 是可选的采集事实。缺少多写者顺序时,只在其余观察充分且规模允许时搜索补全。
    • searched 只证明某个可能执行成立,不能变成已观察到的数据库顺序。缩减只裁剪原始声明。

    详见 输入格式、JSON Schema、算法设计 和 独特性范围。范围/谓词查询、自动 SQL 插桩、append/list 模型及完整隔离级别分类尚未实现。

    #API 与预算约定

    保留 analyze、reduce_history、JS analyze/shrink 和 CLI 默认行为。推荐显式使用高级入口:

    import {analyzeWithOptions, shrinkWithOptions, replayReport} from './dist/sdk.mjs'; const report = analyzeWithOptions(history, { maxAttempts: 100000, maxOperationChecks: 1000000, maxCachedStates: 50000 }); console.log(report.status, report.search, report.metrics); const reduced = shrinkWithOptions(history, {maxChecks: 256}); console.log(reduced.oneMinimal, replayReport(reduced.reducedHistory, reduced.report));

    MoonBit 使用 analysis_options / analyze_with_options / analysis_result_json 和 reduction_options / reduce_with_options / reduction_result_json。类型见 src/pkg.generated.mbti。

    moon add HhWw96/moontxnwitness@0.1.0

    范围默认兼容入口balanced 入口
    图分析512 事务 / 10,000 操作 / 50,000 依赖相同
    完整串行补全8 个已提交事务12 个已提交事务
    补全操作 / 初始键512 / 128相同
    候选前缀 / 操作检查100,000 / 1,000,000相同,可调低
    失败状态缓存无最多 50,000 项,可关闭
    缩减64 事务 / 2,048 操作 / 128 次检查512 事务 / 10,000 操作 / 256 次检查

    核心 JSON 限 1,048,576 UTF-16 单元,CLI 历史限 2 MiB UTF-8,深度 64。缓存满后停止新增缓存;预算耗尽不会被当作穷举无解。

    v2 记录算法、模型、有效预算和版本来源,把运行计数与判断证据分开;v1 保留原搜索顺序、预算和计数比较规则。回放重算语义,SHA-256 仅保证完整性,不认证采集者。verify 使用 schema-1 紧凑环证书;完整 v2 报告使用 replayReport 或 CLI replay。详见 高级分析与证据。

    #构建与可重复验收

    源码需要 MoonBit、Node 和 Python,无需 npm install。工具链见 开发说明。

    npm run build npm test npm run benchmark npm run postgres:verify npm run package

    benchmark 自动重建,缺少基线时下载并核对公开 v0.0.6 核心的固定摘要。完整报告与完整报告比较:每场景预热 5 次、测量 30 次、分 3 批交替复测;独立进程记录峰值 RSS、冷启动、P95 和输出大小。固定输入、原始样本和失败记录均保留。--quick 只作烟雾检查。详见 路线与协议 和 性能报告。

    v0.0.10 的完整负载组相对 v0.0.6:图分析 2.67 倍、搜索 5.02 倍、缩减 2.18 倍,图分析峰值内存下降约 30.3%。这是工程测量,不是官方评分权重;当前冻结版本的结果见性能报告。

    验证保留每后端 94 项核心测试、10,320 份独立串行重放、6,373 份环证据、2,542 份解析差分和独立缩减检查。Windows/Linux CI 检查便携交付;Linux 另执行 Native 和独立 PostgreSQL 流程。每版实际 CI、公开下载、摘要、Mooncakes 字节和全新注册表安装结果见 verification/releases/VERSION/publication.json。

    #开源与参赛状态

    Apache-2.0;依赖、概念来源、AI 使用与复核方式见 THIRD_PARTY.md。分析算法全部使用 MoonBit;JS 处理文件与传输,Python 可选采集数据库,JS 后端有一个字符串片段拼接原语。

    v0.0.7–v0.0.11 的实质提交、变更、失败尝试和发布记录保留。参赛者本人仍须完成 安装与解释验收,并独立确认报名、入群及组织方回执。公开发布或自动检查通过不表示官方接受或获奖。

    AnalysisOptions

    pub(all) struct AnalysisOptions {
    max_attempts : Int
    max_operation_checks : Int
    max_cached_states : Int
    } derive(Eq)

    AnalysisOptions::equal

    AnalysisOptions::not_equal

    fn AnalysisOptions::not_equal(x : AnalysisOptions, y : AnalysisOptions) -> Bool

    AnalysisResult

    pub(all) struct AnalysisResult {
    report : Report
    options : AnalysisOptions
    cache_hits : Int
    cached_states : Int
    } derive(Eq)

    AnalysisResult::equal

    AnalysisResult::not_equal

    fn AnalysisResult::not_equal(x : AnalysisResult, y : AnalysisResult) -> Bool

    Dependency

    pub(all) enum Dependency {
    WR
    WW
    RW
    RT
    } derive(Eq, Hash)

    Dependency::equal

    fn Dependency::equal(Dependency, Dependency) -> Bool

    Dependency::hash

    fn Dependency::hash(self : Dependency) -> Int

    Dependency::hash_combine

    fn Dependency::hash_combine(Dependency, Hasher) -> Unit

    Dependency::not_equal

    fn Dependency::not_equal(x : Dependency, y : Dependency) -> Bool

    Edge

    pub(all) struct Edge {
    from : String
    to : String
    kind : Dependency
    key : String?
    from_op : Int?
    to_op : Int?
    from_version : String?
    to_version : String?
    reason : String
    } derive(Eq, Hash)

    Operation indexes are zero-based. Initial versions have no transaction.

    Edge::equal

    fn Edge::equal(Edge, Edge) -> Bool

    Edge::hash

    fn Edge::hash(self : Edge) -> Int

    Edge::hash_combine

    fn Edge::hash_combine(Edge, Hasher) -> Unit

    Edge::not_equal

    fn Edge::not_equal(x : Edge, y : Edge) -> Bool

    Finding

    pub(all) struct Finding {
    code : String
    severity : String
    message : String
    transactions : Array[String]
    key : String?
    ops : Array[Int]
    } derive(Eq)

    Finding::equal

    fn Finding::equal(Finding, Finding) -> Bool

    Finding::not_equal

    fn Finding::not_equal(x : Finding, y : Finding) -> Bool

    GraphInfo

    pub(all) struct GraphInfo {
    analyzed : Bool
    components : Int
    cyclic_components : Int
    cyclic_transactions : Int
    bfs_roots : Int
    edge_budget_exceeded : Bool
    } derive(Eq)

    GraphInfo::equal

    fn GraphInfo::equal(GraphInfo, GraphInfo) -> Bool

    GraphInfo::not_equal

    fn GraphInfo::not_equal(x : GraphInfo, y : GraphInfo) -> Bool

    History

    pub(all) struct History {
    model : Model
    initial : Map[String, String]
    version_orders : Map[String, Array[String]]
    transactions : Array[Transaction]
    } derive(Eq)

    Version orders contain the initial version followed by all committed final writes.

    History::equal

    fn History::equal(History, History) -> Bool

    History::not_equal

    fn History::not_equal(x : History, y : History) -> Bool

    KeyCoverage

    pub(all) struct KeyCoverage {
    key : String
    committed_reads : Int
    committed_final_writes : Int
    unresolved_reads : Int
    } derive(Eq)

    KeyCoverage::equal

    fn KeyCoverage::equal(KeyCoverage, KeyCoverage) -> Bool

    KeyCoverage::not_equal

    fn KeyCoverage::not_equal(x : KeyCoverage, y : KeyCoverage) -> Bool

    Model

    pub(all) enum Model {
    Serializable
    StrictSerializable
    } derive(Eq)

    Model::equal

    fn Model::equal(Model, Model) -> Bool

    Model::not_equal

    fn Model::not_equal(x : Model, y : Model) -> Bool

    OpKind

    pub(all) enum OpKind {
    Read
    Write
    } derive(Eq)

    The supported workload is a versioned, point-read register workload.

    OpKind::equal

    fn OpKind::equal(OpKind, OpKind) -> Bool

    OpKind::not_equal

    fn OpKind::not_equal(x : OpKind, y : OpKind) -> Bool

    Operation

    pub(all) struct Operation {
    kind : OpKind
    key : String
    version : String
    } derive(Eq)

    Operation::equal

    fn Operation::equal(Operation, Operation) -> Bool

    Operation::not_equal

    fn Operation::not_equal(x : Operation, y : Operation) -> Bool

    Outcome

    pub(all) enum Outcome {
    Consistent
    Violation
    Inconclusive
    Invalid
    } derive(Eq)

    Outcome::equal

    fn Outcome::equal(Outcome, Outcome) -> Bool

    Outcome::not_equal

    fn Outcome::not_equal(x : Outcome, y : Outcome) -> Bool

    Reduction

    pub(all) struct Reduction {
    history : History
    report : Report
    status : String
    removed : Array[String]
    checks : Int
    one_minimal : Bool
    reason : String
    } derive(Eq)

    Reduction::equal

    fn Reduction::equal(Reduction, Reduction) -> Bool

    Reduction::not_equal

    fn Reduction::not_equal(x : Reduction, y : Reduction) -> Bool

    ReductionOptions

    pub(all) struct ReductionOptions {
    max_checks : Int
    analysis : AnalysisOptions
    } derive(Eq)

    ReductionOptions::equal

    ReductionOptions::not_equal

    fn ReductionOptions::not_equal(x : ReductionOptions, y : ReductionOptions) -> Bool

    ReductionResult

    pub(all) struct ReductionResult {
    reduction : Reduction
    analysis : AnalysisResult
    cached_checks : Int
    max_checks : Int
    } derive(Eq)

    ReductionResult::equal

    ReductionResult::not_equal

    fn ReductionResult::not_equal(x : ReductionResult, y : ReductionResult) -> Bool

    Report

    pub(all) struct Report {
    outcome : Outcome
    model : Model
    findings : Array[Finding]
    edges : Array[Edge]
    witness : Array[Edge]
    serial_order : Array[String]
    transaction_count : Int
    committed_count : Int
    operation_count : Int
    inferred_orders : Map[String, Array[String]]
    order_sources : Map[String, String]
    search : SearchInfo
    graph : GraphInfo
    coverage : Array[KeyCoverage]
    } derive(Eq)

    Consistent is a claim about the supplied complete history and asserted version orders.

    Report::equal

    fn Report::equal(Report, Report) -> Bool

    Report::not_equal

    fn Report::not_equal(x : Report, y : Report) -> Bool

    SearchInfo

    pub(all) struct SearchInfo {
    status : String
    attempts : Int
    operation_checks : Int
    reason : String
    blockers : Array[Finding]
    } derive(Eq)

    SearchInfo::equal

    fn SearchInfo::equal(SearchInfo, SearchInfo) -> Bool

    SearchInfo::not_equal

    fn SearchInfo::not_equal(x : SearchInfo, y : SearchInfo) -> Bool

    Transaction

    pub(all) struct Transaction {
    id : String
    status : TxStatus
    ops : Array[Operation]
    start : Int64?
    end : Int64?
    } derive(Eq)

    Transaction::equal

    fn Transaction::equal(Transaction, Transaction) -> Bool

    Transaction::not_equal

    fn Transaction::not_equal(x : Transaction, y : Transaction) -> Bool

    TxStatus

    pub(all) enum TxStatus {
    Committed
    Aborted
    Unknown
    } derive(Eq)

    TxStatus::equal

    fn TxStatus::equal(TxStatus, TxStatus) -> Bool

    TxStatus::not_equal

    fn TxStatus::not_equal(x : TxStatus, y : TxStatus) -> Bool

    analysis_options

    fn analysis_options(max_attempts? : Int, max_operation_checks? : Int, max_cached_states? : Int) -> AnalysisOptions

    analysis_result_json

    fn analysis_result_json(result : AnalysisResult) -> Json

    analyze

    fn analyze(h : History) -> Report

    Analyze point reads and unique versioned writes. No arrival/commit order is invented.

    analyze_json

    fn analyze_json(text : String) -> String

    Main portable host entry. Syntax/schema errors have the same report envelope.

    analyze_options_json

    fn analyze_options_json(text : String, options_text : String) -> String

    analyze_with_options

    fn analyze_with_options(h : History, options? : AnalysisOptions) -> AnalysisResult

    benchmark_cycle

    fn benchmark_cycle(h : History, r : Report) -> Int

    benchmark_infer

    fn benchmark_infer(h : History) -> Report

    Development-only phase hooks. Timers live in the host, not the analyzer.

    benchmark_parser_agreement

    fn benchmark_parser_agreement(text : String) -> String

    benchmark_reduce_balanced

    fn benchmark_reduce_balanced(h : History) -> ReductionResult

    benchmark_render

    fn benchmark_render(r : Report) -> String

    fn benchmark_search(h : History, r : Report) -> Int

    benchmark_search_balanced

    fn benchmark_search_balanced(h : History, r : Report) -> Int

    capsule_content_json

    fn capsule_content_json(text : String) -> String

    Parse a capsule with duplicate-key/depth limits. Cryptographic hashes belong to the host.

    compare_models

    fn compare_models(h : History) -> Json

    compare_models_json

    fn compare_models_json(text : String) -> String

    history_json

    fn history_json(h : History) -> Json

    Explicit history export is useful to library consumers and retains all recorded operations.

    parse_history

    fn parse_history(text : String) -> Result[History, String]

    Parse the versioned-register input schema. Unknown fields are rejected.

    parse_history_optimized

    fn parse_history_optimized(text : String) -> Result[History, String]

    Valid-input fast path; legacy decoding retains exact errors and uncommon cases.

    reduce_history

    fn reduce_history(h : History, max_checks? : Int) -> Reduction

    Delta debugging followed by a complete singleton pass proves one-minimality. The predicate is a definite Violation from this analyzer, not absence of a serial replay with unknown sources.

    reduce_with_options

    fn reduce_with_options(h : History, options? : ReductionOptions) -> ReductionResult

    reduction_json

    fn reduction_json(r : Reduction) -> Json

    reduction_options

    fn reduction_options(max_checks? : Int, analysis? : AnalysisOptions) -> ReductionOptions

    reduction_result_json

    fn reduction_result_json(result : ReductionResult) -> Json

    render_report

    fn render_report(r : Report, format : String) -> String

    Render local text, Markdown, JSON or Graphviz DOT. No external renderer is required.

    replay_report_json

    fn replay_report_json(history_text : String, report_text : String) -> String

    Recompute semantic fields. Supplemental presentation/coverage fields are not authenticated.

    report_json

    fn report_json(r : Report) -> Json

    run_json

    fn run_json(text : String, format : String) -> String

    Host transport combines a structured result and its MoonBit-rendered presentation.

    run_options_json

    fn run_options_json(text : String, format : String) -> String

    shrink_json

    fn shrink_json(text : String) -> String

    shrink_options_json

    fn shrink_options_json(text : String, options_text : String) -> String

    verify_certificate_json

    fn verify_certificate_json(history_text : String, certificate_text : String) -> String

    verify_cycle

    fn verify_cycle(h : History, witness : Array[Edge]) -> Bool

    Verify edge provenance and cycle closure without running cycle search again.

    version

    fn version() -> String