objectstore/packed: Optimize pack candidate lookup and locking

3 files changed, 116 insertions, 40 deletions

diff --git a/objectstore/packed/idx_lookup_candidates.go b/objectstore/packed/idx_lookup_candidates.go
index 95323238..23ac9a61 100644
--- a/objectstore/packed/idx_lookup_candidates.go
+++ b/objectstore/packed/idx_lookup_candidates.go
@@ -23,24 +23,50 @@ type packCandidate struct {
 	mtime int64
 }
 
+// packCandidateNode is one node in the candidate MRU order list.
+type packCandidateNode struct {
+	candidate packCandidate
+	prev      *packCandidateNode
+	next      *packCandidateNode
+}
+
 // ensureCandidates discovers pack/index pairs once.
 func (store *Store) ensureCandidates() error {
 	store.discoverOnce.Do(func() {
 		candidates, err := store.discoverCandidates()
 		candidateByPack := make(map[string]packCandidate, len(candidates))
+		nodeByPack := make(map[string]*packCandidateNode, len(candidates))
+
+		var head *packCandidateNode
+		var tail *packCandidateNode
 		for _, candidate := range candidates {
+			node := &packCandidateNode{
+				candidate: candidate,
+				prev:      tail,
+			}
+			if tail != nil {
+				tail.next = node
+			}
+			if head == nil {
+				head = node
+			}
+			tail = node
 			candidateByPack[candidate.packName] = candidate
+			nodeByPack[candidate.packName] = node
 		}
-		store.stateMu.Lock()
-		store.candidates = candidates
+
+		store.candidatesMu.Lock()
+		store.candidateHead = head
+		store.candidateTail = tail
 		store.candidateByPack = candidateByPack
+		store.candidateNodeByPack = nodeByPack
 		store.discoverErr = err
-		store.stateMu.Unlock()
+		store.candidatesMu.Unlock()
 	})
 
-	store.stateMu.RLock()
+	store.candidatesMu.RLock()
 	err := store.discoverErr
-	store.stateMu.RUnlock()
+	store.candidatesMu.RUnlock()
 	return err
 }
 
@@ -99,18 +125,54 @@ func (store *Store) discoverCandidates() ([]packCandidate, error) {
 
 // touchCandidate moves one candidate to the front of the lookup order.
 func (store *Store) touchCandidate(packName string) {
-	store.stateMu.Lock()
-	defer store.stateMu.Unlock()
-	for i := range store.candidates {
-		if store.candidates[i].packName != packName {
-			continue
-		}
-		if i == 0 {
-			return
-		}
-		candidate := store.candidates[i]
-		copy(store.candidates[1:i+1], store.candidates[0:i])
-		store.candidates[0] = candidate
+	store.candidatesMu.Lock()
+	defer store.candidatesMu.Unlock()
+
+	node := store.candidateNodeByPack[packName]
+	if node == nil || node == store.candidateHead {
 		return
 	}
+
+	if node.prev != nil {
+		node.prev.next = node.next
+	}
+	if node.next != nil {
+		node.next.prev = node.prev
+	}
+	if store.candidateTail == node {
+		store.candidateTail = node.prev
+	}
+
+	node.prev = nil
+	node.next = store.candidateHead
+	if store.candidateHead != nil {
+		store.candidateHead.prev = node
+	}
+	store.candidateHead = node
+	if store.candidateTail == nil {
+		store.candidateTail = node
+	}
+}
+
+// firstCandidatePackName returns the current head pack name, or "" when none
+// are available.
+func (store *Store) firstCandidatePackName() string {
+	store.candidatesMu.RLock()
+	defer store.candidatesMu.RUnlock()
+	if store.candidateHead == nil {
+		return ""
+	}
+	return store.candidateHead.candidate.packName
+}
+
+// nextCandidatePackName returns the pack name after currentPack in current MRU
+// order, or "" at end / when currentPack is not present.
+func (store *Store) nextCandidatePackName(currentPack string) string {
+	store.candidatesMu.RLock()
+	defer store.candidatesMu.RUnlock()
+	node := store.candidateNodeByPack[currentPack]
+	if node == nil || node.next == nil {
+		return ""
+	}
+	return node.next.candidate.packName
 }
diff --git a/objectstore/packed/idx_open.go b/objectstore/packed/idx_open.go
index 45f0f83d..c00a7bac 100644
--- a/objectstore/packed/idx_open.go
+++ b/objectstore/packed/idx_open.go
@@ -40,34 +40,34 @@ type idxFile struct {
 
 // candidateForPack returns one discovered candidate for a pack basename.
 func (store *Store) candidateForPack(packName string) (packCandidate, bool) {
-	store.stateMu.RLock()
+	store.candidatesMu.RLock()
 	candidate, ok := store.candidateByPack[packName]
-	store.stateMu.RUnlock()
+	store.candidatesMu.RUnlock()
 	return candidate, ok
 }
 
 // openIndex returns one opened and parsed index, caching it by pack basename.
 func (store *Store) openIndex(candidate packCandidate) (*idxFile, error) {
-	store.stateMu.RLock()
+	store.idxMu.RLock()
 	if index, ok := store.idxByPack[candidate.packName]; ok {
-		store.stateMu.RUnlock()
+		store.idxMu.RUnlock()
 		return index, nil
 	}
-	store.stateMu.RUnlock()
+	store.idxMu.RUnlock()
 
 	index, err := openIdxFile(store.root, candidate.idxName, candidate.packName, store.algo)
 	if err != nil {
 		return nil, err
 	}
 
-	store.stateMu.Lock()
+	store.idxMu.Lock()
 	if existing, ok := store.idxByPack[candidate.packName]; ok {
-		store.stateMu.Unlock()
+		store.idxMu.Unlock()
 		_ = index.close()
 		return existing, nil
 	}
 	store.idxByPack[candidate.packName] = index
-	store.stateMu.Unlock()
+	store.idxMu.Unlock()
 	return index, nil
 }
 
diff --git a/objectstore/packed/store.go b/objectstore/packed/store.go
index 00b8c962..bb6936ea 100644
--- a/objectstore/packed/store.go
+++ b/objectstore/packed/store.go
@@ -25,15 +25,23 @@ type Store struct {
 	discoverOnce sync.Once
 	// discoverErr stores candidate discovery failures.
 	discoverErr error
-	// candidates stores known pack/index pairs in lookup priority order.
-	candidates []packCandidate
+	// candidateHead is the first candidate in lookup priority order.
+	candidateHead *packCandidateNode
+	// candidateTail is the last candidate in lookup priority order.
+	candidateTail *packCandidateNode
 	// candidateByPack maps pack basename to discovered candidate.
 	candidateByPack map[string]packCandidate
+	// candidateNodeByPack maps pack basename to linked-list node.
+	candidateNodeByPack map[string]*packCandidateNode
 	// idxByPack caches opened and parsed indexes by pack basename.
 	idxByPack map[string]*idxFile
 
-	// stateMu guards index publication, pack cache, and close state.
+	// stateMu guards pack cache and close state.
 	stateMu sync.RWMutex
+	// candidatesMu guards discovered candidates and MRU order.
+	candidatesMu sync.RWMutex
+	// idxMu guards parsed index cache.
+	idxMu sync.RWMutex
 	// cacheMu guards delta cache operations.
 	cacheMu sync.RWMutex
 	// packs caches opened .pack handles by basename.
@@ -54,12 +62,13 @@ func New(root *os.Root, algo objectid.Algorithm) (*Store, error) {
 		return nil, objectid.ErrInvalidAlgorithm
 	}
 	return &Store{
-		root:            root,
-		algo:            algo,
-		candidateByPack: make(map[string]packCandidate),
-		idxByPack:       make(map[string]*idxFile),
-		packs:           make(map[string]*packFile),
-		deltaCache:      newDeltaCache(defaultDeltaCacheMaxBytes),
+		root:                root,
+		algo:                algo,
+		candidateByPack:     make(map[string]packCandidate),
+		candidateNodeByPack: make(map[string]*packCandidateNode),
+		idxByPack:           make(map[string]*idxFile),
+		packs:               make(map[string]*packFile),
+		deltaCache:          newDeltaCache(defaultDeltaCacheMaxBytes),
 	}, nil
 }
 
@@ -73,8 +82,10 @@ func (store *Store) Close() error {
 	store.closed = true
 	root := store.root
 	packs := store.packs
-	indexes := store.idxByPack
 	store.stateMu.Unlock()
+	store.idxMu.RLock()
+	indexes := store.idxByPack
+	store.idxMu.RUnlock()
 
 	var closeErr error
 	for _, pack := range packs {
@@ -107,11 +118,14 @@ func (store *Store) lookup(id objectid.ObjectID) (location, error) {
 		return zero, err
 	}
 
-	store.stateMu.RLock()
-	candidates := append([]packCandidate(nil), store.candidates...)
-	store.stateMu.RUnlock()
-
-	for _, candidate := range candidates {
+	nextPackName := store.firstCandidatePackName()
+	for nextPackName != "" {
+		candidate, ok := store.candidateForPack(nextPackName)
+		if !ok {
+			nextPackName = store.firstCandidatePackName()
+			continue
+		}
+		nextPackName = store.nextCandidatePackName(candidate.packName)
 		index, err := store.openIndex(candidate)
 		if err != nil {
 			return zero, err