Implement SearchByID Algorithm (Algorithm 1 from Skip Graph Paper)

[thep2p]

Implement SearchByID Algorithm (Algorithm 1 from Skip Graph Paper)

Overview

Implement the SearchByID method for Skip Graph nodes, corresponding to Algorithm 1: search for node v from the Skip Graph paper. This implementation must achieve 100% parity with the reference Rust implementation in skipgraph-rust.

Reference Implementation:

• Rust: src/node/base_node.rs:66-146
• Tests: src/node/search_by_id_test.rs

---

Algorithm Description

Purpose

Searches for an identifier in the node's lookup table by scanning through levels up to a specified maximum level in a given direction (Left or Right). Returns either the best matching identifier or falls back to the node's own identifier.

Input: IdSearchReq

type IdSearchReq struct {
    target    model.Identifier  // The target identifier to search for
    level     core.Level        // Maximum level to search (inclusive, 0-indexed)
    direction core.Direction    // Search direction (Left or Right)
}

Output: IdSearchRes

type IdSearchRes struct {
    target           model.Identifier  // Copy of the target identifier (for traceability)
    terminationLevel core.Level        // Level where the match was found
    result           model.Identifier  // The matched identifier (or fallback)
}

Algorithm Steps

1. Collect Candidates

   • Iterate through levels 0 to req.Level() (inclusive)
   • For each level, call lookupTable.GetEntry(req.Direction(), level)
   • Collect all non-nil neighbors as candidates: (identity.Identifier, level)
   • If GetEntry returns an error at any level, propagate error immediately
   • Skip nil entries (no neighbor at that level/direction)

2. Filter Candidates by Direction

   Left Direction:

   • Goal: Find the smallest identifier ≥ target
   • Filter: Keep only candidates where candidate.ID >= target
   • Select: Minimum by identifier among filtered candidates

   Right Direction:

   • Goal: Find the greatest identifier ≤ target
   • Filter: Keep only candidates where candidate.ID <= target
   • Select: Maximum by identifier among filtered candidates

3. Return Result

   • If a candidate is found: Return IdSearchRes{target, candidateLevel, candidateID}
   • If no candidate is found: Fallback to IdSearchRes{target, 0, node.OwnIdentifier}

Pseudocode

function SearchByID(req: IdSearchReq) -> Result<IdSearchRes>:
    candidates = []
    
    // Step 1: Collect candidates from levels 0 to req.level
    for level in 0..=req.level:
        entry = lookupTable.GetEntry(req.direction, level)
        if entry is Error:
            return Error("error while searching by id in level {level}: {error}")
        if entry is Some(identity):
            candidates.append((identity.id, level))
    
    // Step 2: Filter candidates based on direction
    filtered = match req.direction:
        Left:
            candidates.filter(id >= req.target).min_by_key(id)
        Right:
            candidates.filter(id <= req.target).max_by_key(id)
    
    // Step 3: Return result or fallback
    if filtered is Some((id, level)):
        return Ok(IdSearchRes{target: req.target, level: level, result: id})
    else:
        return Ok(IdSearchRes{target: req.target, level: 0, result: node.own_id})

Implementation Details

1. New Types to Create

File: core/model/search.go

package model

// IdSearchReq represents a request to search for an identifier in the lookup table
type IdSearchReq struct {
    target    Identifier
    level     core.Level  // Note: Import cycle - may need to use int64 directly
    direction core.Direction  // Note: Import cycle - may need to use string
}

func NewIdSearchReq(target Identifier, level core.Level, direction core.Direction) IdSearchReq {
    return IdSearchReq{
        target:    target,
        level:     level,
        direction: direction,
    }
}

func (r IdSearchReq) Target() Identifier {
    return r.target
}

func (r IdSearchReq) Level() core.Level {
    return r.level
}

func (r IdSearchReq) Direction() core.Direction {
    return r.direction
}

// IdSearchRes represents the result of an identifier search
type IdSearchRes struct {
    target           Identifier  // The target identifier that was searched for
    terminationLevel core.Level  // The level where the search terminated
    result           Identifier  // The identifier found (or own ID as fallback)
}

func NewIdSearchRes(target Identifier, terminationLevel core.Level, result Identifier) IdSearchRes {
    return IdSearchRes{
        target:           target,
        terminationLevel: terminationLevel,
        result:           result,
    }
}

func (r IdSearchRes) Target() Identifier {
    return r.target
}

func (r IdSearchRes) TerminationLevel() core.Level {
    return r.terminationLevel
}

func (r IdSearchRes) Result() Identifier {
    return r.result
}

Note on Import Cycles: If core and model create import cycles, consider:

• Moving Direction and Level to model package
• Using basic types (int64, string) in model/search.go
• Creating a separate search package

2. Node Interface Extension

File: node/node.go

Add the SearchByID method to the node:

// SearchByID searches for an identifier in the lookup table in the given direction up to the given level.
// 
// Algorithm (corresponds to Algorithm 1 from Skip Graph paper):
// 1. Collects neighbors from levels 0 to req.Level() in req.Direction()
// 2. Filters candidates based on direction:
//    - Left: smallest identifier >= target
//    - Right: greatest identifier <= target
// 3. Returns the best match, or falls back to own identifier at level 0 if no match found
//
// Returns error if lookup table access fails at any level.
func (n *SkipGraphNode) SearchByID(req model.IdSearchReq) (model.IdSearchRes, error) {
    // Implementation goes here
}

3. Implementation Logic (Go)

func (n *SkipGraphNode) SearchByID(req model.IdSearchReq) (model.IdSearchRes, error) {
    // Step 1: Collect candidates from levels 0 to req.Level()
    type candidate struct {
        id    model.Identifier
        level core.Level
    }
    
    var candidates []candidate
    
    for level := core.Level(0); level <= req.Level(); level++ {
        identity, err := n.lt.GetEntry(req.Direction(), level)
        if err != nil {
            return model.IdSearchRes{}, fmt.Errorf("error while searching by id in level %d: %w", level, err)
        }
        if identity != nil {
            candidates = append(candidates, candidate{
                id:    identity.GetIdentifier(),
                level: level,
            })
        }
    }
    
    // Step 2: Filter candidates based on direction
    var bestCandidate *candidate
    
    switch req.Direction() {
    case core.LeftDirection:
        // Left: find smallest ID >= target
        for i := range candidates {
            c := &candidates[i]
            cmp := c.id.Compare(&req.Target())
            if cmp.GetComparisonResult() == model.CompareGreater || cmp.GetComparisonResult() == model.CompareEqual {
                if bestCandidate == nil {
                    bestCandidate = c
                } else {
                    bestCmp := c.id.Compare(&bestCandidate.id)
                    if bestCmp.GetComparisonResult() == model.CompareLess {
                        bestCandidate = c
                    }
                }
            }
        }
        
    case core.RightDirection:
        // Right: find greatest ID <= target
        for i := range candidates {
            c := &candidates[i]
            cmp := c.id.Compare(&req.Target())
            if cmp.GetComparisonResult() == model.CompareLess || cmp.GetComparisonResult() == model.CompareEqual {
                if bestCandidate == nil {
                    bestCandidate = c
                } else {
                    bestCmp := c.id.Compare(&bestCandidate.id)
                    if bestCmp.GetComparisonResult() == model.CompareGreater {
                        bestCandidate = c
                    }
                }
            }
        }
    }
    
    // Step 3: Return result or fallback
    if bestCandidate != nil {
        return model.NewIdSearchRes(req.Target(), bestCandidate.level, bestCandidate.id), nil
    }
    
    // Fallback: return own identifier at level 0
    return model.NewIdSearchRes(req.Target(), 0, n.Identifier()), nil
}

Test Scenarios (100% Parity with Rust)

All tests should be in node/search_by_id_test.go

Test 1: Singleton Fallback

Function: TestSearchByIDSingletonFallback

Purpose: Tests fallback behavior when no neighbors exist (empty lookup table)

Test Matrix:

• Node ID: 10 (hex 0A)
• Target IDs: 5 (hex 05), 15 (hex 0F)
• Directions: Left, Right
• Max Level: 3

Expected Results (all 4 combinations):

• All searches should return terminationLevel = 0, result = node's own ID (10)

Implementation:

func TestSearchByIDSingletonFallback(t *testing.T) {
    // Create node with ID 10 and empty lookup table
    nodeID, _ := model.ByteToId([]byte{10})
    memVec := unittest.MembershipVectorFixture()
    node := node.NewSkipGraphNode(
        model.NewIdentity(nodeID, memVec, model.NewAddress("localhost", "8000")),
        &lookup.Table{},
    )
    
    testCases := []struct {
        targetBytes []byte
        direction   core.Direction
    }{
        {[]byte{5}, core.LeftDirection},
        {[]byte{15}, core.LeftDirection},
        {[]byte{5}, core.RightDirection},
        {[]byte{15}, core.RightDirection},
    }
    
    for _, tc := range testCases {
        target, _ := model.ByteToId(tc.targetBytes)
        req := model.NewIdSearchReq(target, 3, tc.direction)
        res, err := node.SearchByID(req)
        
        require.NoError(t, err)
        require.Equal(t, core.Level(0), res.TerminationLevel())
        require.Equal(t, nodeID, res.Result())
    }
}

Test 2: Found Left Direction

Function: TestSearchByIDFoundLeftDirection

Purpose: Verify correct candidate selection in left direction (smallest ID >= target)

Test Strategy:

• For each level 0 to MaxLookupTableLevel-1:
  • Create lookup table with random neighbors
  • Generate random target
  • Ensure at least one neighbor >= target exists (add "safe_neighbor" at level 0 if needed)
  • Call SearchByID
  • Manually compute expected result (smallest ID >= target from all left neighbors at levels <= req.level)
  • Assert: res.TerminationLevel() == expectedLevel, res.Result() == expectedID

Key Logic:

// Compute expected result
expectedLevel, expectedID := computeExpectedLeftResult(lookupTable, target, maxLevel)
// Compare with actual
require.Equal(t, expectedLevel, res.TerminationLevel())
require.Equal(t, expectedID, res.Result())

Test 3: Found Right Direction

Function: TestSearchByIDFoundRightDirection

Purpose: Verify correct candidate selection in right direction (greatest ID <= target)

Test Strategy: Mirror of Test 2, but:

• Filter: ID <= target
• Select: Maximum ID
• Ensure at least one neighbor <= target exists

Test 4: Not Found Left Direction

Function: TestSearchByIDNotFoundLeftDirection

Purpose: Verify fallback when no valid candidates exist in left direction

Test Strategy:

• For each level 0 to MaxLookupTableLevel-1:
  • Generate random target
  • Populate ALL left neighbors with IDs less than target
  • Call SearchByID with left direction
  • Assert: res.TerminationLevel() == 0, res.Result() == node.OwnID

Key Setup:
```go
for level := core.Level(0); level < core.MaxLookupTableLevel; level++ {
neighborID := unittest.IdentifierLessThan(target) // All neighbors < target
lt.AddEntry(core.LeftDirection, level, unittest.IdentityFixture(neighborID))
}
```

Test 5: Not Found Right Direction

Function: TestSearchByIDNotFoundRightDirection

Purpose: Verify fallback when no valid candidates exist in right direction

Test Strategy: Mirror of Test 4, but:

• Populate ALL right neighbors with IDs greater than target
• Assert fallback to own ID

Test 6: Exact Result

Function: TestSearchByIDExactResult

Purpose: Verify exact match when target exists in lookup table

Test Strategy:

• Create lookup table with random neighbors at all levels
• For each level and each direction:
  • Get the neighbor at (level, direction)
  • Use that neighbor's ID as the target
  • Call SearchByID(target, level, direction)
  • Assert: res.TerminationLevel() == level, res.Result() == target

Test 7: Concurrent Left Direction

Function: TestSearchByIDConcurrentFoundLeftDirection

Purpose: Test thread safety with concurrent searches in left direction

Test Strategy:

• Create node with populated lookup table
• Spawn 20 goroutines
• Use sync.WaitGroup and barrier (sync.Cond or channels)
• Each goroutine:
  • Picks random level
  • Calls SearchByID with left direction
  • Computes expected result independently
  • Asserts result matches expected
• Main goroutine waits for all to complete within 1 second timeout

Concurrency Pattern:

const numGoroutines = 20
var wg sync.WaitGroup
barrier := make(chan struct{})

for i := 0; i < numGoroutines; i++ {
    wg.Add(1)
    go func() {
        defer wg.Done()
        <-barrier  // Wait for all goroutines to be ready
        
        level := rand.Intn(int(core.MaxLookupTableLevel))
        req := model.NewIdSearchReq(target, core.Level(level), core.LeftDirection)
        res, err := node.SearchByID(req)
        
        // Compute expected and assert
        expectedLevel, expectedID := computeExpectedLeftResult(lt, target, level)
        require.NoError(t, err)
        require.Equal(t, expectedLevel, res.TerminationLevel())
        require.Equal(t, expectedID, res.Result())
    }()
}

close(barrier)  // Release all goroutines at once
unittest.RequireReturnsBefore(t, wg.Wait, 1*time.Second, "searches should complete within 1s")

Test 8: Concurrent Right Direction

Function: TestSearchByIDConcurrentRightDirection

Purpose: Test thread safety with concurrent searches in right direction

Test Strategy: Mirror of Test 7, but with right direction

Test 9: Error Propagation

Function: TestSearchByIDErrorPropagation

Purpose: Verify errors from lookup table are propagated correctly

Test Strategy:

• Create mock lookup table that returns error from GetEntry at a specific level
• Call SearchByID
• Assert: error is returned and contains expected message format

Mock Implementation:

type mockErrorLookupTable struct{}

func (m *mockErrorLookupTable) GetEntry(dir core.Direction, level core.Level) (*model.Identity, error) {
    return nil, fmt.Errorf("simulated lookup table error")
}

func (m *mockErrorLookupTable) AddEntry(dir core.Direction, level core.Level, identity model.Identity) error {
    return nil
}

Assertion:

_, err := node.SearchByID(req)
require.Error(t, err)
require.Contains(t, err.Error(), "error while searching by id in level")
require.Contains(t, err.Error(), "simulated lookup table error")

Test 10: Networking Integration (Future)

Function: TestSearchByIDNetworkingIntegration

Purpose: Integration test verifying search_by_id through event processing

Note: This test depends on the network layer and message processing infrastructure, which may not exist yet. Mark as TODO or skip if network layer is not implemented.

Test Strategy (when network layer is ready):

• Create node with mock network
• Register node as event processor
• Send IdSearchRequest event to node
• Verify node responds with IdSearchResponse event
• Assert response contains correct result

---

Test Utilities Needed

Create unittest/identifier.go with these helper functions:

package unittest

import (
    "github.com/thep2p/skipgraph-go/core/model"
)

// IdentifierGreaterThan returns a random identifier greater than the given target
func IdentifierGreaterThan(target model.Identifier) model.Identifier {
    bytes := target.Bytes()
    // Increment from the right until we find a byte < 0xFF
    for i := len(bytes) - 1; i >= 0; i-- {
        if bytes[i] < 0xFF {
            bytes[i]++
            break
        }
    }
    id, _ := model.ByteToId(bytes)
    return id
}

// IdentifierLessThan returns a random identifier less than the given target
func IdentifierLessThan(target model.Identifier) model.Identifier {
    bytes := target.Bytes()
    // Decrement from the left until we find a byte > 0x00
    for i := 0; i < len(bytes); i++ {
        if bytes[i] > 0x00 {
            bytes[i]--
            break
        }
    }
    id, _ := model.ByteToId(bytes)
    return id
}

// LeftNeighbors returns all left neighbors from the lookup table as (level, identity) tuples
func LeftNeighbors(lt core.ImmutableLookupTable) ([]struct{ Level core.Level; Identity model.Identity }, error) {
    var result []struct{ Level core.Level; Identity model.Identity }
    for level := core.Level(0); level < core.MaxLookupTableLevel; level++ {
        identity, err := lt.GetEntry(core.LeftDirection, level)
        if err != nil {
            return nil, err
        }
        if identity != nil {
            result = append(result, struct{ Level core.Level; Identity model.Identity }{level, *identity})
        }
    }
    return result, nil
}

// RightNeighbors returns all right neighbors from the lookup table as (level, identity) tuples
func RightNeighbors(lt core.ImmutableLookupTable) ([]struct{ Level core.Level; Identity model.Identity }, error) {
    var result []struct{ Level core.Level; Identity model.Identity }
    for level := core.Level(0); level < core.MaxLookupTableLevel; level++ {
        identity, err := lt.GetEntry(core.RightDirection, level)
        if err != nil {
            return nil, err
        }
        if identity != nil {
            result = append(result, struct{ Level core.Level; Identity model.Identity }{level, *identity})
        }
    }
    return result, nil
}

// RandomLookupTableWithExtremes creates a lookup table with random entries plus extreme values (0x00...00 left, 0xFF...FF right) at level 0
func RandomLookupTableWithExtremes() *lookup.Table {
    lt := &lookup.Table{}
    
    // Add random neighbors at all levels
    for level := core.Level(0); level < core.MaxLookupTableLevel; level++ {
        lt.AddEntry(core.LeftDirection, level, IdentityFixture())
        lt.AddEntry(core.RightDirection, level, IdentityFixture())
    }
    
    // Add extreme values at level 0
    zeroID, _ := model.ByteToId(make([]byte, model.IdentifierSizeBytes))  // All zeros
    maxID, _ := model.ByteToId(bytes.Repeat([]byte{0xFF}, model.IdentifierSizeBytes))  // All 0xFF
    
    lt.AddEntry(core.LeftDirection, 0, NewIdentity(zeroID, MembershipVectorFixture(), AddressFixture()))
    lt.AddEntry(core.RightDirection, 0, NewIdentity(maxID, MembershipVectorFixture(), AddressFixture()))
    
    return lt
}

---

Acceptance Criteria

• All types (IdSearchReq, IdSearchRes) implemented with proper encapsulation
• SearchByID method implemented on SkipGraphNode following the exact algorithm
• All 10 test scenarios pass (or 9 if network integration is deferred)
• Test coverage >= 95% for SearchByID method
• Concurrent tests verify thread safety with 20 goroutines
• Error propagation works correctly
• Code follows Go idioms (error handling, naming conventions)
• Godoc comments on all public types and methods
• Logger injection pattern followed (if logging is added)
• Tests use unittest package helpers (no raw goroutine waits, use RequireReturnsBefore)

---

Implementation Checklist

• Create core/model/search.go with IdSearchReq and IdSearchRes types
• Add SearchByID method to node/node.go
• Create unittest/identifier.go with test helper functions
• Create node/search_by_id_test.go with all 10 test scenarios
• Ensure all tests pass: `make test`
• Run linter: `make lint`
• Verify test coverage: `go test -cover ./node/...`
• Update godoc comments
• Create pull request with all changes

---

Notes

1. Import Cycles: If core and model packages create import cycles when adding Direction and Level to IdSearchReq, consider:

   • Moving Direction and Level types to model package
   • Creating a separate search package
   • Using primitive types in model/search.go

2. Comparison Logic: The Rust implementation uses >= and <= operators. Go's Identifier.Compare() returns comparison results. Ensure the filtering logic correctly handles equality.

3. Thread Safety: The Rust implementation's lookup table uses Arc<RwLock<_>>. Go's lookup.Table uses sync.RWMutex. Ensure the concurrent tests verify this works correctly.

4. Zero Values: Go's zero value for Identity is all zeros. The GetEntry method should return nil for empty entries (already implemented in lookup.Table).

5. Error Messages: Match error message format from Rust: `"error while searching by id in level {level}: {error}"`

6. Network Integration Test: This test requires event processing infrastructure. If not available, mark as TODO/skip and implement later.

---

Reference Links

• Skip Graph Paper (docs/skip-graphs-journal.pdf)
• Rust Implementation - search_by_id
• Rust Tests - search_by_id_test.rs
• CLAUDE.md - Project Guidelines
• AGENTS.md - Code Standards

---

Estimated Effort: 8-12 hours
Priority: High
Labels: feature, skip-graph-algorithm, testing, cross-language-parity