diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go')
-rw-r--r-- | Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go | 258 |
1 files changed, 161 insertions, 97 deletions
diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go index 88a52f53e..50870ed83 100644 --- a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go +++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go @@ -7,6 +7,7 @@ package leveldb import ( + "fmt" "sync/atomic" "unsafe" @@ -23,7 +24,7 @@ type tSet struct { type version struct { s *session - tables []tFiles + levels []tFiles // Level that should be compacted next and its compaction score. // Score < 1 means compaction is not strictly needed. These fields @@ -39,7 +40,7 @@ type version struct { } func newVersion(s *session) *version { - return &version{s: s, tables: make([]tFiles, s.o.GetNumLevel())} + return &version{s: s} } func (v *version) releaseNB() { @@ -51,18 +52,18 @@ func (v *version) releaseNB() { panic("negative version ref") } - tables := make(map[uint64]bool) - for _, tt := range v.next.tables { + nextTables := make(map[int64]bool) + for _, tt := range v.next.levels { for _, t := range tt { - num := t.file.Num() - tables[num] = true + num := t.fd.Num + nextTables[num] = true } } - for _, tt := range v.tables { + for _, tt := range v.levels { for _, t := range tt { - num := t.file.Num() - if _, ok := tables[num]; !ok { + num := t.fd.Num + if _, ok := nextTables[num]; !ok { v.s.tops.remove(t) } } @@ -78,11 +79,26 @@ func (v *version) release() { v.s.vmu.Unlock() } -func (v *version) walkOverlapping(ikey iKey, f func(level int, t *tFile) bool, lf func(level int) bool) { +func (v *version) walkOverlapping(aux tFiles, ikey iKey, 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.tables { + for level, tables := range v.levels { if len(tables) == 0 { continue } @@ -114,7 +130,7 @@ func (v *version) walkOverlapping(ikey iKey, f func(level int, t *tFile) bool, l } } -func (v *version) get(ikey iKey, ro *opt.ReadOptions, noValue bool) (value []byte, tcomp bool, err error) { +func (v *version) get(aux tFiles, ikey iKey, ro *opt.ReadOptions, noValue bool) (value []byte, tcomp bool, err error) { ukey := ikey.ukey() var ( @@ -130,10 +146,10 @@ func (v *version) get(ikey iKey, ro *opt.ReadOptions, noValue bool) (value []byt err = ErrNotFound - // Since entries never hope across level, finding key/value + // Since entries never hop across level, finding key/value // in smaller level make later levels irrelevant. - v.walkOverlapping(ikey, func(level int, t *tFile) bool { - if !tseek { + v.walkOverlapping(aux, ikey, func(level int, t *tFile) bool { + if level >= 0 && !tseek { if tset == nil { tset = &tSet{level, t} } else { @@ -150,6 +166,7 @@ func (v *version) get(ikey iKey, ro *opt.ReadOptions, noValue bool) (value []byt } else { fikey, fval, ferr = v.s.tops.find(t, ikey, ro) } + switch ferr { case nil: case ErrNotFound: @@ -161,7 +178,8 @@ func (v *version) get(ikey iKey, ro *opt.ReadOptions, noValue bool) (value []byt if fukey, fseq, fkt, fkerr := parseIkey(fikey); fkerr == nil { if v.s.icmp.uCompare(ukey, fukey) == 0 { - if level == 0 { + // Level <= 0 may overlaps each-other. + if level <= 0 { if fseq >= zseq { zfound = true zseq = fseq @@ -212,7 +230,7 @@ func (v *version) get(ikey iKey, ro *opt.ReadOptions, noValue bool) (value []byt func (v *version) sampleSeek(ikey iKey) (tcomp bool) { var tset *tSet - v.walkOverlapping(ikey, func(level int, t *tFile) bool { + v.walkOverlapping(nil, ikey, func(level int, t *tFile) bool { if tset == nil { tset = &tSet{level, t} return true @@ -228,27 +246,22 @@ func (v *version) sampleSeek(ikey iKey) (tcomp bool) { } func (v *version) getIterators(slice *util.Range, ro *opt.ReadOptions) (its []iterator.Iterator) { - // Merge all level zero files together since they may overlap - for _, t := range v.tables[0] { - it := v.s.tops.newIterator(t, slice, ro) - its = append(its, it) - } - strict := opt.GetStrict(v.s.o.Options, ro, opt.StrictReader) - for _, tables := range v.tables[1:] { - if len(tables) == 0 { - continue + 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)) } - - it := iterator.NewIndexedIterator(tables.newIndexIterator(v.s.tops, v.s.icmp, slice, ro), strict) - its = append(its, it) } - return } func (v *version) newStaging() *versionStaging { - return &versionStaging{base: v, tables: make([]tablesScratch, v.s.o.GetNumLevel())} + return &versionStaging{base: v} } // Spawn a new version based on this version. @@ -259,23 +272,26 @@ func (v *version) spawn(r *sessionRecord) *version { } func (v *version) fillRecord(r *sessionRecord) { - for level, ts := range v.tables { - for _, t := range ts { + for level, tables := range v.levels { + for _, t := range tables { r.addTableFile(level, t) } } } func (v *version) tLen(level int) int { - return len(v.tables[level]) + if level < len(v.levels) { + return len(v.levels[level]) + } + return 0 } func (v *version) offsetOf(ikey iKey) (n uint64, err error) { - for level, tables := range v.tables { + 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 + n += uint64(t.size) } else if v.s.icmp.Compare(t.imin, ikey) > 0 { // Entire file is after "ikey", so ignore if level > 0 { @@ -300,37 +316,50 @@ func (v *version) offsetOf(ikey iKey) (n uint64, err error) { return } -func (v *version) pickLevel(umin, umax []byte) (level int) { - if !v.tables[0].overlaps(v.s.icmp, umin, umax, true) { - var overlaps tFiles - maxLevel := v.s.o.GetMaxMemCompationLevel() - for ; level < maxLevel; level++ { - if v.tables[level+1].overlaps(v.s.icmp, umin, umax, false) { - break - } - overlaps = v.tables[level+2].getOverlaps(overlaps, v.s.icmp, umin, umax, false) - if overlaps.size() > uint64(v.s.o.GetCompactionGPOverlaps(level)) { - break +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 - var bestLevel int = -1 - var bestScore float64 = -1 + bestLevel := int(-1) + bestScore := float64(-1) - for level, tables := range v.tables { + 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 compactions. + // 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 @@ -339,17 +368,24 @@ func (v *version) computeCompaction() { // overwrites/deletions). score = float64(len(tables)) / float64(v.s.o.GetCompactionL0Trigger()) } else { - score = float64(tables.size()) / float64(v.s.o.GetCompactionTotalSize(level)) + 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 { @@ -357,43 +393,48 @@ func (v *version) needCompaction() bool { } type tablesScratch struct { - added map[uint64]atRecord - deleted map[uint64]struct{} + added map[int64]atRecord + deleted map[int64]struct{} } type versionStaging struct { base *version - tables []tablesScratch + 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 { - tm := &(p.tables[r.level]) - - if len(p.base.tables[r.level]) > 0 { - if tm.deleted == nil { - tm.deleted = make(map[uint64]struct{}) + 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{}) } - tm.deleted[r.num] = struct{}{} + scratch.deleted[r.num] = struct{}{} } - - if tm.added != nil { - delete(tm.added, r.num) + if scratch.added != nil { + delete(scratch.added, r.num) } } // New tables. for _, r := range r.addedTables { - tm := &(p.tables[r.level]) - - if tm.added == nil { - tm.added = make(map[uint64]atRecord) + scratch := p.getScratch(r.level) + if scratch.added == nil { + scratch.added = make(map[int64]atRecord) } - tm.added[r.num] = r - - if tm.deleted != nil { - delete(tm.deleted, r.num) + scratch.added[r.num] = r + if scratch.deleted != nil { + delete(scratch.deleted, r.num) } } } @@ -401,40 +442,63 @@ func (p *versionStaging) commit(r *sessionRecord) { func (p *versionStaging) finish() *version { // Build new version. nv := newVersion(p.base.s) - for level, tm := range p.tables { - btables := p.base.tables[level] - - n := len(btables) + len(tm.added) - len(tm.deleted) - if n < 0 { - n = 0 + 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] } - nt := make(tFiles, 0, n) - // Base tables. - for _, t := range btables { - if _, ok := tm.deleted[t.file.Num()]; ok { - continue + 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) } - if _, ok := tm.added[t.file.Num()]; ok { - continue + + // 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) } - nt = append(nt, t) - } - // New tables. - for _, r := range tm.added { - nt = append(nt, p.base.s.tableFileFromRecord(r)) - } + // New tables. + for _, r := range scratch.added { + nt = append(nt, tableFileFromRecord(r)) + } - // Sort tables. - if level == 0 { - nt.sortByNum() + if len(nt) != 0 { + // Sort tables. + if level == 0 { + nt.sortByNum() + } else { + nt.sortByKey(p.base.s.icmp) + } + + nv.levels[level] = nt + } } else { - nt.sortByKey(p.base.s.icmp) + nv.levels[level] = baseTabels } - nv.tables[level] = nt } + // 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() |