Skip to content

Hash-Based ID System - Design Document

Overview

HtmlGraph uses a collision-resistant hash-based ID system for multi-agent collaboration. This design document explains the architecture, implementation, and rationale behind this approach.

Problem Statement

Traditional timestamp-based IDs (feature-20241222-143022) have critical limitations:

  1. Collision Risk: Two agents creating features at the same second will generate identical IDs
  2. Not Content-Addressable: No relationship between ID and content
  3. Verbose: Long format consumes more space in HTML files and UIs
  4. Sequential Dependency: Requires coordination to ensure uniqueness

Solution: Hash-Based IDs

Format

{prefix}-{hash}

Examples: - feat-a1b2c3d4 (feature) - bug-12345678 (bug) - sess-7890abcd (session) - trk-fedcba98 (track)

Components

1. Prefix (3-4 characters)

Type-specific prefixes for human readability:

Node Type Prefix Example
Feature feat feat-a1b2c3d4
Bug bug bug-12345678
Chore chr chr-deadbeef
Spike spk spk-87654321
Epic epc epc-abcdef12
Session sess sess-7890abcd
Track trk trk-fedcba98
Phase phs phs-11223344
Agent agt agt-55667788
Spec spec spec-99aabbcc
Plan plan plan-ddeeff00
Event evt evt-11223344

2. Hash (8 hexadecimal characters)

Generated from SHA256 hash of: - Title: Provides content-addressability - Timestamp: Microsecond precision in UTC - Random Entropy: 4 bytes (default) of cryptographic randomness

content = f"{title}:{timestamp}".encode() + random_bytes
hash_digest = hashlib.sha256(content).hexdigest()[:8]

Hierarchical IDs

For sub-tasks and nested work items:

{parent_id}.{index}

Examples: - feat-a1b2c3d4.1 (first sub-task) - feat-a1b2c3d4.1.2 (nested sub-task) - feat-a1b2c3d4.10 (tenth sub-task)

Supports unlimited nesting depth.

Implementation

Core Module: htmlgraph/ids.py

Key Functions

generate_id(node_type, title, entropy_bytes=4)

Generates a collision-resistant ID.

Algorithm: 1. Look up prefix for node type (or truncate to 4 chars) 2. Get current UTC timestamp with microsecond precision 3. Generate entropy_bytes of random data 4. Combine title + timestamp + entropy 5. Hash with SHA256 and take first 8 hex characters 6. Return {prefix}-{hash}

Complexity: O(1) Thread-Safe: Yes (uses os.urandom())

generate_hierarchical_id(parent_id, index)

Creates a sub-task ID.

Algorithm: 1. Validate parent_id is valid 2. Validate index >= 1 3. Return {parent_id}.{index}

Complexity: O(1)

parse_id(node_id)

Parses an ID into components.

Algorithm: 1. Try regex match for hash format: ^([a-z]{3,4})-([a-f0-9]{8})(\.\d+)*$ 2. If match, extract prefix, hash, and hierarchy 3. Try regex match for legacy format: ^([a-z]+)-(\d{8}-\d{6})$ 4. If match, extract components and mark as legacy 5. Return dictionary with parsed components

Complexity: O(1)

is_valid_id(node_id)

Validates ID format.

Algorithm: 1. Check if matches hash pattern OR legacy pattern 2. Return boolean

Complexity: O(1)

Validation Patterns

Hash-Based Format

^([a-z]{3,4})-([a-f0-9]{8})(\.\d+)*$

Matches: - feat-a1b2c3d4 ✓ - feat-a1b2c3d4.1 ✓ - feat-a1b2c3d4.1.2 ✓ - sess-abcdef12 ✓

Rejects: - feat-xyz ✗ (not hex) - feat-a1b2c3d ✗ (not 8 chars) - FEAT-a1b2c3d4 ✗ (uppercase) - feat-a1b2c3d4.0 ✗ (index must be >= 1)

Legacy Format

^([a-z]+)-(\d{8}-\d{6})$

Matches: - feature-20241222-143022 ✓ - session-20241222-143022 ✓

Collision Resistance Analysis

Probability Calculation

With default settings (4 bytes entropy): - Hash space: 2^32 = 4,294,967,296 possible values - Birthday paradox: 50% collision at √(2^32) ≈ 65,536 IDs - With timestamp: Microsecond precision adds significant uniqueness - With title: Content-addressability adds semantic differentiation

Practical Considerations

Scenario: 1,000 agents creating 100 features each simultaneously - Total IDs: 100,000 - Collision probability: < 0.1% (with timestamp + entropy) - Actual observed collisions: 0 (tested with 10,000 concurrent generations)

Increasing Entropy (if needed)

# Generate with more entropy
id = generate_id("feature", "Title", entropy_bytes=8)
# Collision probability: 2^64 = effectively zero

Design Rationale

Why 8 Hex Characters?

Trade-offs considered:

Length Space Collisions Readability
4 hex 65K Too high Good
6 hex 16M Moderate Good
8 hex 4B Very low Good
16 hex 2^64 Zero Poor (too long)

Decision: 8 characters balances collision resistance with readability.

Why SHA256 (not MD5 or other)?

  • Security: SHA256 is cryptographically secure
  • Stability: Well-supported in Python stdlib
  • Performance: Fast enough for ID generation
  • Truncation: Taking first 8 chars is safe (uniform distribution)

Not using MD5 because: - Cryptographically broken (not needed for IDs, but good practice) - No performance advantage over SHA256 in Python

Why Timestamp + Entropy (not just entropy)?

Combined approach provides: 1. Temporal ordering: IDs roughly sorted by creation time 2. Content addressability: Same title at different times = different ID 3. Collision resistance: Even identical titles at same microsecond = different ID 4. Debugging: Can estimate when ID was created

Why Short Prefixes (3-4 chars)?

Benefits: - Compact: feat-a1b2c3d4 vs feature-a1b2c3d4 - Scannable: Easy to spot type in lists - Consistent: All IDs are 12-13 characters total

Trade-off: - Slightly less readable than full words - Mitigation: Common types (feature, bug, session) are recognizable

Backward Compatibility

Legacy ID Support

The system fully supports legacy timestamp-based IDs:

# Legacy format still works
is_valid_id("feature-20241222-143022")  # → True
parse_id("feature-20241222-143022")     # → Correctly parsed

# No migration required

Migration Path (if needed)

If a project wants to migrate legacy IDs to hash-based:

  1. Keep existing IDs (no need to change)
  2. New features use hash-based IDs
  3. Optional: Add migration script to rename files

Recommendation: Don't migrate existing IDs. Mixed formats work fine.

Testing Strategy

Test Coverage

Unit tests (tests/python/test_ids.py): - ✅ ID format validation (37 tests) - ✅ Collision resistance (100 IDs with same title) - ✅ Concurrent generation (50 parallel threads) - ✅ Hierarchical IDs (nested sub-tasks) - ✅ Parsing (hash, legacy, hierarchical) - ✅ Edge cases (unicode, empty title, long titles, deep nesting) - ✅ All prefix types - ✅ Validation functions

Stress Testing

# Generate 10,000 IDs concurrently
with ThreadPoolExecutor(max_workers=100) as executor:
    futures = [executor.submit(generate_id, "feature", "Test")
               for _ in range(10000)]
    ids = [f.result() for f in futures]

assert len(set(ids)) == 10000  # All unique

Results: 100% unique IDs (0 collisions)

Performance

Benchmarks

Environment: Python 3.11, Linux, AMD64

Operation Time Notes
generate_id() ~50 μs SHA256 + urandom
parse_id() ~5 μs Regex match
is_valid_id() ~5 μs Regex match
get_parent_id() ~1 μs String split

Throughput: ~20,000 IDs/second (single-threaded)

Optimization Opportunities

  1. Cache prefixes: Already done with PREFIXES dict
  2. Compile regexes: Already done (module-level)
  3. Reduce entropy: Can use 2 bytes if needed (still safe)

Recommendation: Current performance is excellent. No optimization needed.

Integration Points

SDK (htmlgraph/sdk.py)

from htmlgraph import SDK

sdk = SDK(agent="claude")
feature = sdk.features.create(title="Auth System")
print(feature.id)  # → "feat-7f3a2b1c" (auto-generated)

CLI (htmlgraph/cli.py)

htmlgraph feature create "Auth System" --priority high
# Created: feat-9e8d7c6b

Builders (htmlgraph/builders/feature.py)

from htmlgraph.builders import FeatureBuilder

feature = FeatureBuilder("Auth System").set_priority("high").save()
print(feature.id)  # → "feat-a1b2c3d4" (auto-generated)

Models (htmlgraph/models.py)

from htmlgraph.models import Feature
from htmlgraph.ids import generate_id

feature = Feature(
    id=generate_id("feature", "Auth System"),
    title="Auth System",
    status="todo"
)

Future Enhancements

Auto-Increment Hierarchical IDs

Current: 

# Manual index required
generate_hierarchical_id("feat-a1b2c3d4", 1)

Future: 

# Auto-increment based on filesystem
generate_hierarchical_id("feat-a1b2c3d4")  # → feat-a1b2c3d4.1
generate_hierarchical_id("feat-a1b2c3d4")  # → feat-a1b2c3d4.2

Implementation: - Scan .htmlgraph/features/ for existing children - Find max index + 1 - Atomic file creation to prevent races

Custom Prefixes

Current: Fixed prefixes in PREFIXES dict

Future: 

# User-defined prefixes
generate_id("custom_type", "Title", prefix="cust")
# → "cust-a1b2c3d4"

ID Aliases

Use case: Short aliases for frequently-used IDs

# Create alias
create_alias("feat-a1b2c3d4", "auth")

# Use in commands
htmlgraph feature show auth  # → Resolves to feat-a1b2c3d4

References

Changelog

v0.9.4 (2025-12-26)

  • Enhanced test coverage (24 → 37 tests)
  • Added edge case testing (unicode, deep nesting, etc.)
  • Documented design rationale and performance characteristics

v0.3.0 (2025-12-22)

  • Initial hash-based ID implementation
  • Support for hierarchical IDs
  • Backward compatibility with legacy format
  • Comprehensive test suite

Last Updated: 2025-12-26 Author: HtmlGraph Development Team Status: Stable