Skip to content

storage-optimization.md

Latest commit

 

History

History
314 lines (233 loc) · 8.91 KB

storage-optimization.md

File metadata and controls

314 lines (233 loc) · 8.91 KB
Raw

Storage Optimization for Stellar-Save

Overview

This document describes the storage optimization strategies implemented in Stellar-Save to reduce costs for groups with many members. The optimizations focus on three key areas:

  1. Bitmap-based contribution tracking - Reduces per-cycle storage from O(n) to O(1)
  2. Compact member profiles - Reduces per-member storage through bit-packing
  3. Storage cost estimation - Provides tools to analyze and benchmark improvements

Problem Statement

Current Storage Usage

The original storage layout uses individual keys for each member's contribution per cycle:

CONTRIB_{group_id}_{cycle}_{address}  // One entry per member per cycle
MEMBER_CONTRIB_{group_id}_{address}   // One entry per member
MEMBER_PAYOUT_{group_id}_{address}    // One entry per member
MEMBER_TOTAL_CONTRIB_{group_id}_{address}  // One entry per member

Storage Cost Analysis:

For a group with 100 members and 10 cycles:

  • Contribution tracking: 100 × 10 = 1,000 entries
  • Member profiles: 100 × 4 = 400 entries
  • Total: ~1,400 entries

For a group with 1,000 members and 50 cycles:

  • Contribution tracking: 1,000 × 50 = 50,000 entries
  • Member profiles: 1,000 × 4 = 4,000 entries
  • Total: ~54,000 entries

This becomes prohibitively expensive on Soroban where storage is a primary cost factor.

Solution 1: Bitmap-Based Contribution Tracking

Design

Instead of storing individual contribution keys per member per cycle, we use a bitmap where each bit represents one member's contribution status:

pub struct ContributionBitmap {
    pub group_id: u64,
    pub cycle: u32,
    pub bitmap: Vec<u64>,           // Each u64 holds 64 bits
    pub member_count: u32,
    pub contributors_count: u32,    // Cached for O(1) access
    pub total_amount: i128,         // Cached for O(1) access
}

Storage Reduction

Bitmap approach:

  • One bitmap entry per cycle: ~1 entry
  • Cycle total: 1 entry
  • Cycle count: 1 entry
  • Total per cycle: 3 entries

Comparison:

Scenario Traditional Bitmap Savings
100 members, 10 cycles 1,000 30 97%
500 members, 25 cycles 12,500 75 99.4%
1,000 members, 50 cycles 50,000 150 99.7%

Implementation Details

Bit Layout:

  • Each u64 chunk holds 64 bits
  • Bit position = member_index % 64
  • Chunk index = member_index / 64
  • Bit value: 1 = contributed, 0 = not contributed

Example for 100 members:

  • Chunks needed: (100 + 63) / 64 = 2 u64 values
  • Chunk 0: bits 0-63 (members 0-63)
  • Chunk 1: bits 0-36 (members 64-99)

Operations:

// Set contribution for member at index 5
bitmap.set_contribution(5, 1_000_000)?;

// Check if member 5 contributed
let contributed = bitmap.has_contributed(5)?;

// Check cycle completion
let complete = bitmap.is_complete();

// Get remaining contributions needed
let remaining = bitmap.remaining_contributions();

Benefits

  1. Massive storage reduction - 97-99.7% savings for large groups
  2. O(1) operations - Bit operations are constant time
  3. Cached counters - No need to iterate to count contributors
  4. Backward compatible - Can coexist with traditional approach

Trade-offs

  1. Bit manipulation complexity - Requires careful index calculations
  2. Limited to 2^32 members - Practical limit is much lower anyway
  3. Requires migration - Existing data needs conversion

Solution 2: Compact Member Profiles

Design

Instead of storing separate entries for each member attribute, we pack multiple fields into a single structure using bit flags:

pub struct CompactMemberProfile {
    pub address: Address,
    pub group_id: u64,
    pub payout_position: u32,
    pub joined_at: u64,
    pub status_flags: u32,  // Bit-packed flags
}

Status Flags Layout:

Bit 0: has_contributed_current_cycle
Bit 1: is_eligible_for_payout
Bit 2: is_active
Bits 3-31: reserved for future use

Storage Reduction

Traditional approach:

  • Member profile: 1 entry
  • Contribution status: 1 entry
  • Payout eligibility: 1 entry
  • Total contributions: 1 entry
  • Total per member: 4 entries

Compact approach:

  • Compact profile: 1 entry
  • Total contributions: 1 entry
  • Total per member: 2 entries

Savings: 50% per member

For 1,000 members: 4,000 → 2,000 entries saved

Implementation

// Create profile
let mut profile = CompactMemberProfile::new(address, group_id, payout_pos, joined_at);

// Set flags
profile.set_contributed(true);
profile.set_eligible_for_payout(true);
profile.set_active(true);

// Read flags
if profile.has_contributed() { /* ... */ }
if profile.is_eligible_for_payout() { /* ... */ }
if profile.is_active() { /* ... */ }

Benefits

  1. 50% storage reduction for member data
  2. Extensible - 29 bits reserved for future flags
  3. Type-safe - Compiler checks flag operations
  4. Fast access - Single storage read for all member state

Solution 3: Storage Cost Estimation

API

The StorageCostAnalyzer provides functions to estimate and compare storage costs:

// Estimate traditional approach
let traditional = StorageCostAnalyzer::estimate_traditional_contribution_storage(100, 10);
// Returns: 1000

// Estimate bitmap approach
let bitmap = StorageCostAnalyzer::estimate_bitmap_contribution_storage(100, 10);
// Returns: 30

// Calculate savings
let (trad, opt, savings_pct) = StorageCostAnalyzer::calculate_bitmap_savings(100, 10);
// Returns: (1000, 30, 97)

// Estimate total group storage
let total = StorageCostAnalyzer::estimate_total_group_storage(
    100,    // members
    10,     // cycles
    true,   // use_bitmap
    true,   // use_compact_profiles
);

// Generate detailed report
let report = StorageCostAnalyzer::generate_storage_report(100, 10);

Report Example

Storage Analysis Report
========================
Members: 100
Cycles: 10

Traditional Approach: 1405 entries
Optimized Approach: 235 entries
Savings: 83%

Integration Strategy

Phase 1: Parallel Implementation

  • Implement bitmap and compact profiles alongside existing code
  • Use feature flags to enable/disable optimizations
  • Maintain backward compatibility

Phase 2: Migration

  • Provide migration functions to convert existing data
  • Support both old and new formats during transition
  • Gradual rollout to existing groups

Phase 3: Deprecation

  • Mark old storage keys as deprecated
  • Encourage migration to new format
  • Eventually remove old code

Benchmarking Results

Contribution Tracking

Members Cycles Traditional Bitmap Reduction
10 5 50 15 70%
50 10 500 30 94%
100 10 1,000 30 97%
500 25 12,500 75 99.4%
1,000 50 50,000 150 99.7%

Member Storage

Members Traditional Compact Reduction
10 40 20 50%
100 400 200 50%
1,000 4,000 2,000 50%

Total Group Storage

Members Cycles Traditional Optimized Reduction
100 10 1,435 265 81.5%
500 25 16,935 1,075 93.6%
1,000 50 58,435 2,150 96.3%

Cost Implications

Soroban Storage Costs

Assuming Soroban storage costs of ~0.00001 XLM per entry per ledger:

100-member group, 10 cycles:

  • Traditional: 1,435 entries × 0.00001 = 0.01435 XLM
  • Optimized: 265 entries × 0.00001 = 0.00265 XLM
  • Savings: 0.0117 XLM per ledger

1,000-member group, 50 cycles:

  • Traditional: 58,435 entries × 0.00001 = 0.58435 XLM
  • Optimized: 2,150 entries × 0.00001 = 0.02150 XLM
  • Savings: 0.56285 XLM per ledger

Over a year (52,560 ledgers):

  • 100-member group: ~615 XLM saved
  • 1,000-member group: ~29,600 XLM saved

Implementation Checklist

  • Implement ContributionBitmap structure
  • Implement CompactMemberProfile structure
  • Implement StorageCostAnalyzer with estimation functions
  • Add comprehensive tests for all components
  • Create storage optimization module
  • Document storage layout and optimization strategies
  • Implement migration utilities
  • Add feature flags for gradual rollout
  • Create benchmarking suite
  • Update contract to use optimized structures
  • Add integration tests with real scenarios

Future Optimizations

  1. Contribution amount packing - Store amounts in compact format
  2. Address compression - Use member indices instead of full addresses
  3. Timestamp compression - Store relative timestamps instead of absolute
  4. Cycle batching - Group multiple cycles in single storage entry
  5. Lazy evaluation - Compute values on-demand instead of caching

References