| // Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com> |
| // All rights reserved. |
| // |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| package leveldb |
| |
| import ( |
| "fmt" |
| "sync/atomic" |
| "unsafe" |
| |
| "github.com/syndtr/goleveldb/leveldb/iterator" |
| "github.com/syndtr/goleveldb/leveldb/opt" |
| "github.com/syndtr/goleveldb/leveldb/util" |
| ) |
| |
| type tSet struct { |
| level int |
| table *tFile |
| } |
| |
| type version struct { |
| s *session |
| |
| levels []tFiles |
| |
| // Level that should be compacted next and its compaction score. |
| // Score < 1 means compaction is not strictly needed. These fields |
| // are initialized by computeCompaction() |
| cLevel int |
| cScore float64 |
| |
| cSeek unsafe.Pointer |
| |
| ref int |
| // Succeeding version. |
| next *version |
| } |
| |
| func newVersion(s *session) *version { |
| return &version{s: s} |
| } |
| |
| func (v *version) releaseNB() { |
| v.ref-- |
| if v.ref > 0 { |
| return |
| } |
| if v.ref < 0 { |
| panic("negative version ref") |
| } |
| |
| nextTables := make(map[int64]bool) |
| for _, tt := range v.next.levels { |
| for _, t := range tt { |
| num := t.fd.Num |
| nextTables[num] = true |
| } |
| } |
| |
| for _, tt := range v.levels { |
| for _, t := range tt { |
| num := t.fd.Num |
| if _, ok := nextTables[num]; !ok { |
| v.s.tops.remove(t) |
| } |
| } |
| } |
| |
| v.next.releaseNB() |
| v.next = nil |
| } |
| |
| func (v *version) release() { |
| v.s.vmu.Lock() |
| v.releaseNB() |
| v.s.vmu.Unlock() |
| } |
| |
| func (v *version) walkOverlapping(aux tFiles, ikey internalKey, f func(level int, t *tFile) bool, lf func(level int) bool) { |
| ukey := ikey.ukey() |
| |
| // Aux level. |
| if aux != nil { |
| for _, t := range aux { |
| if t.overlaps(v.s.icmp, ukey, ukey) { |
| if !f(-1, t) { |
| return |
| } |
| } |
| } |
| |
| if lf != nil && !lf(-1) { |
| return |
| } |
| } |
| |
| // Walk tables level-by-level. |
| for level, tables := range v.levels { |
| if len(tables) == 0 { |
| continue |
| } |
| |
| if level == 0 { |
| // Level-0 files may overlap each other. Find all files that |
| // overlap ukey. |
| for _, t := range tables { |
| if t.overlaps(v.s.icmp, ukey, ukey) { |
| if !f(level, t) { |
| return |
| } |
| } |
| } |
| } else { |
| if i := tables.searchMax(v.s.icmp, ikey); i < len(tables) { |
| t := tables[i] |
| if v.s.icmp.uCompare(ukey, t.imin.ukey()) >= 0 { |
| if !f(level, t) { |
| return |
| } |
| } |
| } |
| } |
| |
| if lf != nil && !lf(level) { |
| return |
| } |
| } |
| } |
| |
| func (v *version) get(aux tFiles, ikey internalKey, ro *opt.ReadOptions, noValue bool) (value []byte, tcomp bool, err error) { |
| ukey := ikey.ukey() |
| |
| var ( |
| tset *tSet |
| tseek bool |
| |
| // Level-0. |
| zfound bool |
| zseq uint64 |
| zkt keyType |
| zval []byte |
| ) |
| |
| err = ErrNotFound |
| |
| // Since entries never hop across level, finding key/value |
| // in smaller level make later levels irrelevant. |
| v.walkOverlapping(aux, ikey, func(level int, t *tFile) bool { |
| if level >= 0 && !tseek { |
| if tset == nil { |
| tset = &tSet{level, t} |
| } else { |
| tseek = true |
| } |
| } |
| |
| var ( |
| fikey, fval []byte |
| ferr error |
| ) |
| if noValue { |
| fikey, ferr = v.s.tops.findKey(t, ikey, ro) |
| } else { |
| fikey, fval, ferr = v.s.tops.find(t, ikey, ro) |
| } |
| |
| switch ferr { |
| case nil: |
| case ErrNotFound: |
| return true |
| default: |
| err = ferr |
| return false |
| } |
| |
| if fukey, fseq, fkt, fkerr := parseInternalKey(fikey); fkerr == nil { |
| if v.s.icmp.uCompare(ukey, fukey) == 0 { |
| // Level <= 0 may overlaps each-other. |
| if level <= 0 { |
| if fseq >= zseq { |
| zfound = true |
| zseq = fseq |
| zkt = fkt |
| zval = fval |
| } |
| } else { |
| switch fkt { |
| case keyTypeVal: |
| value = fval |
| err = nil |
| case keyTypeDel: |
| default: |
| panic("leveldb: invalid internalKey type") |
| } |
| return false |
| } |
| } |
| } else { |
| err = fkerr |
| return false |
| } |
| |
| return true |
| }, func(level int) bool { |
| if zfound { |
| switch zkt { |
| case keyTypeVal: |
| value = zval |
| err = nil |
| case keyTypeDel: |
| default: |
| panic("leveldb: invalid internalKey type") |
| } |
| return false |
| } |
| |
| return true |
| }) |
| |
| if tseek && tset.table.consumeSeek() <= 0 { |
| tcomp = atomic.CompareAndSwapPointer(&v.cSeek, nil, unsafe.Pointer(tset)) |
| } |
| |
| return |
| } |
| |
| func (v *version) sampleSeek(ikey internalKey) (tcomp bool) { |
| var tset *tSet |
| |
| v.walkOverlapping(nil, ikey, func(level int, t *tFile) bool { |
| if tset == nil { |
| tset = &tSet{level, t} |
| return true |
| } |
| if tset.table.consumeSeek() <= 0 { |
| tcomp = atomic.CompareAndSwapPointer(&v.cSeek, nil, unsafe.Pointer(tset)) |
| } |
| return false |
| }, nil) |
| |
| return |
| } |
| |
| func (v *version) getIterators(slice *util.Range, ro *opt.ReadOptions) (its []iterator.Iterator) { |
| strict := opt.GetStrict(v.s.o.Options, ro, opt.StrictReader) |
| for level, tables := range v.levels { |
| if level == 0 { |
| // Merge all level zero files together since they may overlap. |
| for _, t := range tables { |
| its = append(its, v.s.tops.newIterator(t, slice, ro)) |
| } |
| } else if len(tables) != 0 { |
| its = append(its, iterator.NewIndexedIterator(tables.newIndexIterator(v.s.tops, v.s.icmp, slice, ro), strict)) |
| } |
| } |
| return |
| } |
| |
| func (v *version) newStaging() *versionStaging { |
| return &versionStaging{base: v} |
| } |
| |
| // Spawn a new version based on this version. |
| func (v *version) spawn(r *sessionRecord) *version { |
| staging := v.newStaging() |
| staging.commit(r) |
| return staging.finish() |
| } |
| |
| func (v *version) fillRecord(r *sessionRecord) { |
| for level, tables := range v.levels { |
| for _, t := range tables { |
| r.addTableFile(level, t) |
| } |
| } |
| } |
| |
| func (v *version) tLen(level int) int { |
| if level < len(v.levels) { |
| return len(v.levels[level]) |
| } |
| return 0 |
| } |
| |
| func (v *version) offsetOf(ikey internalKey) (n int64, err error) { |
| for level, tables := range v.levels { |
| for _, t := range tables { |
| if v.s.icmp.Compare(t.imax, ikey) <= 0 { |
| // Entire file is before "ikey", so just add the file size |
| n += t.size |
| } else if v.s.icmp.Compare(t.imin, ikey) > 0 { |
| // Entire file is after "ikey", so ignore |
| if level > 0 { |
| // Files other than level 0 are sorted by meta->min, so |
| // no further files in this level will contain data for |
| // "ikey". |
| break |
| } |
| } else { |
| // "ikey" falls in the range for this table. Add the |
| // approximate offset of "ikey" within the table. |
| if m, err := v.s.tops.offsetOf(t, ikey); err == nil { |
| n += m |
| } else { |
| return 0, err |
| } |
| } |
| } |
| } |
| |
| return |
| } |
| |
| func (v *version) pickMemdbLevel(umin, umax []byte, maxLevel int) (level int) { |
| if maxLevel > 0 { |
| if len(v.levels) == 0 { |
| return maxLevel |
| } |
| if !v.levels[0].overlaps(v.s.icmp, umin, umax, true) { |
| var overlaps tFiles |
| for ; level < maxLevel; level++ { |
| if pLevel := level + 1; pLevel >= len(v.levels) { |
| return maxLevel |
| } else if v.levels[pLevel].overlaps(v.s.icmp, umin, umax, false) { |
| break |
| } |
| if gpLevel := level + 2; gpLevel < len(v.levels) { |
| overlaps = v.levels[gpLevel].getOverlaps(overlaps, v.s.icmp, umin, umax, false) |
| if overlaps.size() > int64(v.s.o.GetCompactionGPOverlaps(level)) { |
| break |
| } |
| } |
| } |
| } |
| } |
| return |
| } |
| |
| func (v *version) computeCompaction() { |
| // Precomputed best level for next compaction |
| bestLevel := int(-1) |
| bestScore := float64(-1) |
| |
| statFiles := make([]int, len(v.levels)) |
| statSizes := make([]string, len(v.levels)) |
| statScore := make([]string, len(v.levels)) |
| statTotSize := int64(0) |
| |
| for level, tables := range v.levels { |
| var score float64 |
| size := tables.size() |
| if level == 0 { |
| // We treat level-0 specially by bounding the number of files |
| // instead of number of bytes for two reasons: |
| // |
| // (1) With larger write-buffer sizes, it is nice not to do too |
| // many level-0 compaction. |
| // |
| // (2) The files in level-0 are merged on every read and |
| // therefore we wish to avoid too many files when the individual |
| // file size is small (perhaps because of a small write-buffer |
| // setting, or very high compression ratios, or lots of |
| // overwrites/deletions). |
| score = float64(len(tables)) / float64(v.s.o.GetCompactionL0Trigger()) |
| } else { |
| score = float64(size) / float64(v.s.o.GetCompactionTotalSize(level)) |
| } |
| |
| if score > bestScore { |
| bestLevel = level |
| bestScore = score |
| } |
| |
| statFiles[level] = len(tables) |
| statSizes[level] = shortenb(int(size)) |
| statScore[level] = fmt.Sprintf("%.2f", score) |
| statTotSize += size |
| } |
| |
| v.cLevel = bestLevel |
| v.cScore = bestScore |
| |
| v.s.logf("version@stat F·%v S·%s%v Sc·%v", statFiles, shortenb(int(statTotSize)), statSizes, statScore) |
| } |
| |
| func (v *version) needCompaction() bool { |
| return v.cScore >= 1 || atomic.LoadPointer(&v.cSeek) != nil |
| } |
| |
| type tablesScratch struct { |
| added map[int64]atRecord |
| deleted map[int64]struct{} |
| } |
| |
| type versionStaging struct { |
| base *version |
| levels []tablesScratch |
| } |
| |
| func (p *versionStaging) getScratch(level int) *tablesScratch { |
| if level >= len(p.levels) { |
| newLevels := make([]tablesScratch, level+1) |
| copy(newLevels, p.levels) |
| p.levels = newLevels |
| } |
| return &(p.levels[level]) |
| } |
| |
| func (p *versionStaging) commit(r *sessionRecord) { |
| // Deleted tables. |
| for _, r := range r.deletedTables { |
| scratch := p.getScratch(r.level) |
| if r.level < len(p.base.levels) && len(p.base.levels[r.level]) > 0 { |
| if scratch.deleted == nil { |
| scratch.deleted = make(map[int64]struct{}) |
| } |
| scratch.deleted[r.num] = struct{}{} |
| } |
| if scratch.added != nil { |
| delete(scratch.added, r.num) |
| } |
| } |
| |
| // New tables. |
| for _, r := range r.addedTables { |
| scratch := p.getScratch(r.level) |
| if scratch.added == nil { |
| scratch.added = make(map[int64]atRecord) |
| } |
| scratch.added[r.num] = r |
| if scratch.deleted != nil { |
| delete(scratch.deleted, r.num) |
| } |
| } |
| } |
| |
| func (p *versionStaging) finish() *version { |
| // Build new version. |
| nv := newVersion(p.base.s) |
| numLevel := len(p.levels) |
| if len(p.base.levels) > numLevel { |
| numLevel = len(p.base.levels) |
| } |
| nv.levels = make([]tFiles, numLevel) |
| for level := 0; level < numLevel; level++ { |
| var baseTabels tFiles |
| if level < len(p.base.levels) { |
| baseTabels = p.base.levels[level] |
| } |
| |
| if level < len(p.levels) { |
| scratch := p.levels[level] |
| |
| var nt tFiles |
| // Prealloc list if possible. |
| if n := len(baseTabels) + len(scratch.added) - len(scratch.deleted); n > 0 { |
| nt = make(tFiles, 0, n) |
| } |
| |
| // Base tables. |
| for _, t := range baseTabels { |
| if _, ok := scratch.deleted[t.fd.Num]; ok { |
| continue |
| } |
| if _, ok := scratch.added[t.fd.Num]; ok { |
| continue |
| } |
| nt = append(nt, t) |
| } |
| |
| // New tables. |
| for _, r := range scratch.added { |
| nt = append(nt, tableFileFromRecord(r)) |
| } |
| |
| if len(nt) != 0 { |
| // Sort tables. |
| if level == 0 { |
| nt.sortByNum() |
| } else { |
| nt.sortByKey(p.base.s.icmp) |
| } |
| |
| nv.levels[level] = nt |
| } |
| } else { |
| nv.levels[level] = baseTabels |
| } |
| } |
| |
| // Trim levels. |
| n := len(nv.levels) |
| for ; n > 0 && nv.levels[n-1] == nil; n-- { |
| } |
| nv.levels = nv.levels[:n] |
| |
| // Compute compaction score for new version. |
| nv.computeCompaction() |
| |
| return nv |
| } |
| |
| type versionReleaser struct { |
| v *version |
| once bool |
| } |
| |
| func (vr *versionReleaser) Release() { |
| v := vr.v |
| v.s.vmu.Lock() |
| if !vr.once { |
| v.releaseNB() |
| vr.once = true |
| } |
| v.s.vmu.Unlock() |
| } |