diff options
Diffstat (limited to 'docs/design/fractional-indexing.md')
| -rw-r--r-- | docs/design/fractional-indexing.md | 396 |
1 files changed, 0 insertions, 396 deletions
diff --git a/docs/design/fractional-indexing.md b/docs/design/fractional-indexing.md deleted file mode 100644 index 287e719..0000000 --- a/docs/design/fractional-indexing.md +++ /dev/null @@ -1,396 +0,0 @@ -# Fractional Indexing for Stable Cell Positions - -**Last Updated:** 2025-11-13 - -## Overview - -Fractional indexing provides stable, immutable identifiers for cell positions in an ordered sequence, enabling concurrent insertions without the coordination problems of array indices. - -## The Problem with Array Indices - -Consider this scenario with traditional array indices: - -``` -Initial state: -[0: A, 1: B, 2: C, 3: D] - -Alice subdivides cells 1-2 (B, C) -Bob subdivides cells 2-3 (C, D) - -After Alice's operation: -[0: A, 1: T1, 2: T2, 3: T3, 4: D] -Now "cell 2" means T2 - -After Bob's operation (he thinks "cell 2" is C): -[0: A, 1: T1, 2: T2, 3: T3, 4: Q1, 5: Q2, 6: Q3, 7: D] -But C is gone! Bob's operation is invalid. -``` - -**The problem:** Indices are relative positions that change when the array is modified. Concurrent operations reference different cells by the same index. - -## Fractional Indexing Solution - -Instead of indices, each cell has a **position string** that never changes: - -``` -Initial state: -Cell A: position="a0" -Cell B: position="a1" -Cell C: position="a2" -Cell D: position="a3" - -Alice subdivides [B, C] (position="a1" and "a2") -Bob subdivides [C, D] (position="a2" and "a3") - -Alice creates: - T1: position="a1.2" (between a1 and a2) - T2: position="a1.5" - T3: position="a1.8" - -Bob creates: - Q1: position="a2.2" (between a2 and a3) - Q2: position="a2.5" - Q3: position="a2.8" - -Merged result (sorted by position): -a0 (A), a1 (B, deleted), a1.2 (T1), a1.5 (T2), a1.8 (T3), -a2 (C, deleted), a2.2 (Q1), a2.5 (Q2), a2.8 (Q3), a3 (D, deleted) -``` - -**Key insight:** Position strings are immutable. Operations reference cells by their stable position, not their current index in the array. - -## Position String Format - -Positions are lexicographically sortable strings: - -``` -"a0" < "a0.5" < "a1" < "a1.25" < "a2" -``` - -### Base Structure - -``` -[prefix][integer].[fractional] -``` - -- **Prefix:** Letter(s) for global ordering (e.g., "a", "b", "z") -- **Integer:** Whole number part -- **Fractional:** Optional decimal part for insertions - -### Generating Positions - -```rust -pub struct FractionalIndex(String); - -impl FractionalIndex { - /// Create initial positions for a sequence - pub fn initial_sequence(count: usize) -> Vec<Self> { - (0..count) - .map(|i| FractionalIndex(format!("a{}", i))) - .collect() - } - - /// Generate position between two existing positions - pub fn between(before: &str, after: &str) -> Self { - // Simplified version - production needs more robust logic - let before_val = parse_position(before); - let after_val = parse_position(after); - let middle = (before_val + after_val) / 2.0; - - FractionalIndex(format_position(middle)) - } - - /// Generate position before the first element - pub fn before_first(first: &str) -> Self { - // e.g., "a0" → "a-1" - let val = parse_position(first); - FractionalIndex(format_position(val - 1.0)) - } - - /// Generate position after the last element - pub fn after_last(last: &str) -> Self { - // e.g., "a5" → "a6" - let val = parse_position(last); - FractionalIndex(format_position(val + 1.0)) - } -} - -fn parse_position(pos: &str) -> f64 { - // Strip prefix, parse number - let num_part = pos.trim_start_matches(|c: char| c.is_alphabetic()); - num_part.parse().unwrap_or(0.0) -} - -fn format_position(val: f64) -> String { - if val.fract() == 0.0 { - format!("a{}", val as i64) - } else { - format!("a{}", val) - } -} -``` - -### Insertion Examples - -```rust -// Insert between a0 and a1 -FractionalIndex::between("a0", "a1") // → "a0.5" - -// Insert between a0.5 and a1 -FractionalIndex::between("a0.5", "a1") // → "a0.75" - -// Insert between a0.75 and a1 -FractionalIndex::between("a0.75", "a1") // → "a0.875" - -// Insert at beginning -FractionalIndex::before_first("a0") // → "a-1" - -// Insert at end -FractionalIndex::after_last("a3") // → "a4" -``` - -## Subdivision Operation with Positions - -```rust -pub struct Subdivide { - pub deleted_cell_ids: Vec<Uuid>, - pub new_cells: Vec<NewCell>, -} - -pub struct NewCell { - pub id: Uuid, - pub position: String, // Fractional position - pub duration: f64, -} - -impl Subdivide { - /// Create a subdivide operation - pub fn new( - target_cells: &[Cell], - new_durations: Vec<f64>, - ) -> Self { - // Find position range for new cells - let first_pos = &target_cells.first().unwrap().position; - let last_pos = &target_cells.last().unwrap().position; - - // Generate evenly spaced positions between first and last - let new_cells = distribute_positions( - first_pos, - last_pos, - new_durations.len(), - ) - .into_iter() - .zip(new_durations) - .map(|(position, duration)| NewCell { - id: Uuid::new_v7(), - position, - duration, - }) - .collect(); - - Subdivide { - deleted_cell_ids: target_cells.iter().map(|c| c.id).collect(), - new_cells, - } - } -} - -fn distribute_positions( - first: &str, - last: &str, - count: usize, -) -> Vec<String> { - let start = parse_position(first); - let end = parse_position(last); - let step = (end - start) / (count as f64 + 1.0); - - (1..=count) - .map(|i| format_position(start + step * i as f64)) - .collect() -} -``` - -**Example:** -```rust -// Subdivide cells at positions a1, a2, a3 into 5 new cells - -// Position range: a1 to a3 -// Generate 5 positions between them: -// a1.33, a1.67, a2.0, a2.33, a2.67 - -let subdivide = Subdivide { - deleted_cell_ids: [id_a1, id_a2, id_a3], - new_cells: [ - NewCell { id: new_id_1, position: "a1.33", duration: 0.15 }, - NewCell { id: new_id_2, position: "a1.67", duration: 0.15 }, - NewCell { id: new_id_3, position: "a2.0", duration: 0.15 }, - NewCell { id: new_id_4, position: "a2.33", duration: 0.15 }, - NewCell { id: new_id_5, position: "a2.67", duration: 0.15 }, - ], -}; -``` - -## Applying Operations - -```rust -impl Op { - fn apply(&self, realized: &mut RealizedDoc) { - match &self.payload { - OpPayload::Subdivide { new_cells, deleted_cell_ids, .. } => { - let row = realized.get_row_mut(self.row_id); - - // Mark deleted cells (tombstone) - for cell_id in deleted_cell_ids { - if let Some(cell) = row.cells.iter_mut().find(|c| c.id == *cell_id) { - cell.deleted = true; - } - } - - // Insert new cells - for new_cell in new_cells { - row.cells.push(Cell { - id: new_cell.id, - position: new_cell.position.clone(), - duration: new_cell.duration, - created_by: self.id, - deleted: false, - }); - } - - // Sort by position for display - row.cells.sort_by(|a, b| a.position.cmp(&b.position)); - } - _ => {} - } - } -} -``` - -## Handling Concurrent Insertions - -Fractional indexing ensures deterministic ordering even with concurrent insertions: - -``` -Initial: [a0: A, a1: B, a2: C] - -Alice inserts between A and B: position = "a0.5" -Bob inserts between A and B: position = "a0.5" - -Both generate the same position! -``` - -**Solution 1: Add randomness** -```rust -fn between_with_jitter(before: &str, after: &str, actor_id: &Uuid) -> String { - let base = between(before, after); - // Add tiny actor-specific offset - let offset = (actor_id.as_bytes()[0] as f64) / 1000000.0; - adjust_position(&base, offset) -} -``` - -**Solution 2: Use timestamp in position** -```rust -fn between_with_timestamp(before: &str, after: &str, timestamp: u64) -> String { - let middle = between(before, after); - format!("{}.{}", middle, timestamp % 1000) -} -``` - -**Solution 3: Accept ties (rely on cell ID for final ordering)** -```rust -impl Cell { - fn compare_for_display(&self, other: &Cell) -> Ordering { - // Primary: position - match self.position.cmp(&other.position) { - Ordering::Equal => { - // Tie-breaker: cell ID (lexicographic) - self.id.cmp(&other.id) - } - other => other, - } - } -} -``` - -## Position Space Exhaustion - -**Problem:** Repeatedly inserting between two positions eventually runs out of precision: - -``` -a0, a0.5, a0.75, a0.875, a0.9375, a0.96875, ... -``` - -**Solutions:** - -### 1. Rebalancing (Offline) -Periodically regenerate positions with even spacing: -```rust -fn rebalance_positions(cells: &mut [Cell]) { - let count = cells.len(); - for (i, cell) in cells.iter_mut().enumerate() { - cell.position = format!("a{}", i); - } -} -``` - -### 2. Multi-level Positions -Use hierarchical structure: -``` -"a0", "a0|b0", "a0|b1", "a1" -``` - -### 3. Arbitrary Precision -Use strings that can grow indefinitely: -``` -"a0", "a0.5", "a0.5.5", "a0.5.5.5", ... -``` - -## Production Implementation - -Consider using existing libraries: - -- **fractional-index** (Rust) - Figma-style implementation -- **string-ordering** - Lexicographic ordering primitives - -Example with `fractional-index`: -```rust -use fractional_index::{FractionalIndex, generate_key_between}; - -// Generate position between two cells -let pos = generate_key_between( - Some(&cell_a.position), - Some(&cell_b.position), -); -``` - -## Key Properties - -1. **Immutable** - Positions never change after creation -2. **Lexicographic** - String comparison gives correct order -3. **Dense** - Can always insert between any two positions -4. **Deterministic** - Same inputs produce same outputs -5. **Conflict-Free** - Concurrent insertions at same position are handled gracefully - -## Trade-offs - -**Pros:** -- No coordination needed for insertions -- Stable references across replicas -- Simple to reason about - -**Cons:** -- Positions can become long strings over time -- Requires periodic rebalancing in heavy-edit scenarios -- Slightly more complex than array indices - -## References - -- [Figma's Blog: Realtime Editing of Ordered Sequences](https://www.figma.com/blog/realtime-editing-of-ordered-sequences/) -- [fractional-index crate](https://crates.io/crates/fractional-index) -- [LSEQ CRDT](https://hal.archives-ouvertes.fr/hal-00921633/document) - -## Related Documents - -- See `crdt-design.md` for overall CRDT architecture -- See `branch-based-merge.md` for conflict detection and resolution |