Skip to content
This repository was archived by the owner on Apr 21, 2026. It is now read-only.

crdt-optimization.md

Latest commit

 

History

History
208 lines (150 loc) · 6.48 KB

crdt-optimization.md

File metadata and controls

208 lines (150 loc) · 6.48 KB

CRDT Optimization in Ditto CoT

This document describes the advanced CRDT (Conflict-free Replicated Data Type) optimization techniques implemented in the Ditto CoT library to handle duplicate XML elements and enable efficient P2P synchronization.

Quick Navigation: Architecture Overview | Performance Benchmarks | Schema Reference | Integration Guide

Table of Contents

Overview

The Ditto CoT library employs advanced CRDT optimization to handle CoT XML processing efficiently, preserving all duplicate elements while enabling differential updates in P2P networks.

Key Achievements

Metric Legacy Systems Ditto CoT Solution Improvement
Data Preservation 6/13 elements (46%) 13/13 elements (100%) +54%
P2P Sync Efficiency Full document sync Differential field sync ~70% bandwidth savings
Metadata Size Large keys + redundant data Base64 optimized keys ~74% reduction
CRDT Compatibility ❌ Arrays break updates ✅ Stable keys enable granular updates ✅

The Challenge

CoT XML often contains duplicate elements that are critical for tactical operations:

<detail>
  <sensor type="optical" id="sensor-1"/>
  <sensor type="thermal" id="sensor-2"/>  
  <sensor type="radar" id="sensor-3"/>
  <contact callsign="ALPHA-1"/>
  <contact callsign="BRAVO-2"/>
  <!-- Legacy systems: Only 6/13 elements preserved -->
  <!-- Ditto CoT: ALL 13 elements preserved -->
</detail>

Traditional approaches using arrays break CRDT differential updates, requiring full document synchronization across P2P networks.

Solution Architecture

Stable Key Generation

The library uses a size-optimized stable key format that enables CRDT differential updates:

Format: base64(hash(documentId + elementName))_index
Example: "aG1k_0", "aG1k_1", "aG1k_2"

Before vs After

Before: Array-based (breaks differential updates)

details: [
  {"name": "sensor", "type": "optical"},
  {"name": "sensor", "type": "thermal"}
]

After: Stable key storage (enables differential updates)

details: {
  "aG1k_0": {"type": "optical", "_tag": "sensor"},
  "aG1k_1": {"type": "thermal", "_tag": "sensor"}
}

Implementation Details

Two-Pass Algorithm

  1. First Pass: Detect duplicate elements and count occurrences
  2. Second Pass: Assign stable keys to all elements

Key Generation Process

// Rust implementation
let key = format!("{}_{}_{}", document_id, element_name, index);
let hash = calculate_hash(&key);
let stable_key = format!("{}_{}", base64_encode(hash), index);
// Java implementation
String key = String.format("%s_%s_%d", documentId, elementName, index);
String hash = calculateHash(key);
String stableKey = String.format("%s_%d", base64Encode(hash), index);

Metadata Optimization

  • Original Format: 27 bytes per key (e.g., "complex-detail-test_sensor_0")
  • Optimized Format: 7 bytes per key (e.g., "aG1k_0")
  • Savings: ~74% reduction per key

Performance Benefits

P2P Network Scenario

Node A: Updates sensor_1.zoom = "20x"     // Only this field syncs
Node B: Removes contact_0                 // Only this removal syncs  
Node C: Adds new sensor_4                 // Only this addition syncs

Result: All nodes converge efficiently without full document sync

Bandwidth Savings

  • Traditional approach: Entire document syncs on any change
  • CRDT-optimized approach: Only changed fields sync
  • Typical savings: 70% reduction in sync payload size

Cross-Language Compatibility

Both Java and Rust implementations use identical algorithms ensuring:

  • ✅ Identical stable key generation
  • ✅ Compatible data structures
  • ✅ Consistent P2P convergence behavior
  • ✅ Unified index management

Key Components

Java

  • CRDTOptimizedDetailConverter.java - Core implementation
  • Full integration with existing CoT converter infrastructure

Rust

  • crdt_detail_parser.rs - Core implementation
  • Zero-copy XML parsing with quick_xml

P2P Network Behavior

Convergence Example

Consider three peers making concurrent modifications:

  1. Peer A modifies an existing sensor's zoom level
  2. Peer B removes a contact element
  3. Peer C adds a new sensor element

With CRDT optimization:

  • Each peer's change creates a minimal diff
  • Changes merge without conflicts
  • Final state preserves all non-conflicting changes

Conflict Resolution

The stable key approach enables last-write-wins semantics at the field level rather than document level, providing more granular conflict resolution.

Integration

With CoT Conversion

// Rust
let detail_map = parse_detail_section_with_stable_keys(&detail_xml, &event.uid);
// Java
Map<String, Object> detailMap = crdtConverter.convertDetailElementToMapWithStableKeys(
    event.getDetail(), event.getUid()
);

With Ditto Storage

The optimized format integrates seamlessly with Ditto's CRDT engine:

{
  "id": "complex-detail-test",
  "detail": {
    "status": {"operational": true},
    "aG1k_0": {"type": "optical", "_tag": "sensor"},
    "aG1k_1": {"type": "thermal", "_tag": "sensor"}
  }
}

Summary

The CRDT optimization in Ditto CoT successfully addresses the challenge of preserving duplicate XML elements while enabling efficient P2P synchronization. This solution provides:

  • 100% data preservation of all CoT XML elements
  • 70% bandwidth savings through differential updates
  • Cross-language compatibility between Java and Rust
  • Production-ready implementation with comprehensive testing

See Also