From 8600b32050fa21d63baf4b21e75f8fc71fcfc610 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Sat, 21 Feb 2026 19:51:40 +0800 Subject: objectstore/packed: Optimize pack candidate lookup and locking --- objectstore/packed/idx_lookup_candidates.go | 96 ++++++++++++++++++++++++----- objectstore/packed/idx_open.go | 16 ++--- objectstore/packed/store.go | 44 ++++++++----- 3 files changed, 116 insertions(+), 40 deletions(-) (limited to 'objectstore/packed') 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 -- cgit v1.3.1-10-gc9f91