2949

Committed 09 Oct 2019 03:04PM UTC coverage: 77.122% (-0.4%) from 77.548%

Build # 2949

Build Type

push

travis-ci

Committed by

web-flow

Commit Message

<a href="https://github.com/dgraph-io/badger/commit/<a class=hub.com/dgraph-io/badger/commit/6da9aac1feb4ed1533f9957959489223de436838">6da9aac1f<a href="https://github.com/dgraph-io/badger/commit/6da9aac1feb4ed1533f9957959489223de436838">&quot;&gt;Change badger version in manifest version FAQ (#1074)

The badger version mentioned in manifest version mismatch FAQ has an
unsupported backup format. This commit changes the badger version in FAQ
from v1.5.5 to v1.6.0. v1.6.0 has the new backup format.
The backup format was changed in
https://github.com/dgraph-io/badger/commit/</a><a class="double-link" href="https://github.com/dgraph-io/badger/commit/<a class="double-link" href="https://github.com/dgraph-io/badger/commit/4e5cbcc8574b8258c0146d4d01539b6d48212f4a">4e5cbcc85</a>">4e5cbcc85</a><a href="https://github.com/dgraph-io/badger/commit/6da9aac1feb4ed1533f9957959489223de436838">
commit.

Run Details

18207 of 23608 relevant lines covered (77.12%)

132651.3 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.68

/compaction.go

/*
 * Copyright 2017 Dgraph Labs, Inc. and Contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package badger

import (
        "bytes"
        "fmt"
        "log"
        "math"
        "sync"

        "golang.org/x/net/trace"

        "github.com/dgraph-io/badger/table"
        "github.com/dgraph-io/badger/y"
)

type keyRange struct {
        left  []byte
        right []byte
        inf   bool
}

var infRange = keyRange{inf: true}

func (r keyRange) String() string {
        return fmt.Sprintf("[left=%x, right=%x, inf=%v]", r.left, r.right, r.inf)
}

func (r keyRange) equals(dst keyRange) bool {
        return bytes.Equal(r.left, dst.left) &&
                bytes.Equal(r.right, dst.right) &&
                r.inf == dst.inf
}

func (r keyRange) overlapsWith(dst keyRange) bool {
        if r.inf || dst.inf {
                return true
        }

        // If my left is greater than dst right, we have no overlap.
        if y.CompareKeys(r.left, dst.right) > 0 {
                return false
        }
        // If my right is less than dst left, we have no overlap.
        if y.CompareKeys(r.right, dst.left) < 0 {
                return false
        }
        // We have overlap.
        return true
}

func getKeyRange(tables ...*table.Table) keyRange {
        if len(tables) == 0 {
                return keyRange{}
        }
        smallest := tables[0].Smallest()
        biggest := tables[0].Biggest()
        for i := 1; i < len(tables); i++ {
                if y.CompareKeys(tables[i].Smallest(), smallest) < 0 {
                        smallest = tables[i].Smallest()
                }
                if y.CompareKeys(tables[i].Biggest(), biggest) > 0 {
                        biggest = tables[i].Biggest()
                }
        }

        // We pick all the versions of the smallest and the biggest key. Note that version zero would
        // be the rightmost key, considering versions are default sorted in descending order.
        return keyRange{
                left:  y.KeyWithTs(y.ParseKey(smallest), math.MaxUint64),
                right: y.KeyWithTs(y.ParseKey(biggest), 0),
        }
}

type levelCompactStatus struct {
        ranges  []keyRange
        delSize int64
}

func (lcs *levelCompactStatus) debug() string {
        var b bytes.Buffer
        for _, r := range lcs.ranges {
                b.WriteString(r.String())
        }
        return b.String()
}

func (lcs *levelCompactStatus) overlapsWith(dst keyRange) bool {
        for _, r := range lcs.ranges {
                if r.overlapsWith(dst) {
                        return true
                }
        }
        return false
}

func (lcs *levelCompactStatus) remove(dst keyRange) bool {
        final := lcs.ranges[:0]
        var found bool
        for _, r := range lcs.ranges {
                if !r.equals(dst) {
                        final = append(final, r)
                } else {
                        found = true
                }
        }
        lcs.ranges = final
        return found
}

type compactStatus struct {
        sync.RWMutex
        levels []*levelCompactStatus
}

func (cs *compactStatus) toLog(tr trace.Trace) {
        cs.RLock()
        defer cs.RUnlock()

        tr.LazyPrintf("Compaction status:")
        for i, l := range cs.levels {
                if l.debug() == "" {
                        continue
                }
                tr.LazyPrintf("[%d] %s", i, l.debug())
        }
}

func (cs *compactStatus) overlapsWith(level int, this keyRange) bool {
        cs.RLock()
        defer cs.RUnlock()

        thisLevel := cs.levels[level]
        return thisLevel.overlapsWith(this)
}

func (cs *compactStatus) delSize(l int) int64 {
        cs.RLock()
        defer cs.RUnlock()
        return cs.levels[l].delSize
}

type thisAndNextLevelRLocked struct{}

// compareAndAdd will check whether we can run this compactDef. That it doesn't overlap with any
// other running compaction. If it can be run, it would store this run in the compactStatus state.
func (cs *compactStatus) compareAndAdd(_ thisAndNextLevelRLocked, cd compactDef) bool {
        cs.Lock()
        defer cs.Unlock()

        level := cd.thisLevel.level

        y.AssertTruef(level < len(cs.levels)-1, "Got level %d. Max levels: %d", level, len(cs.levels))
        thisLevel := cs.levels[level]
        nextLevel := cs.levels[level+1]

        if thisLevel.overlapsWith(cd.thisRange) {
                return false
        }
        if nextLevel.overlapsWith(cd.nextRange) {
                return false
        }
        // Check whether this level really needs compaction or not. Otherwise, we'll end up
        // running parallel compactions for the same level.
        // Update: We should not be checking size here. Compaction priority already did the size checks.
        // Here we should just be executing the wish of others.

        thisLevel.ranges = append(thisLevel.ranges, cd.thisRange)
        nextLevel.ranges = append(nextLevel.ranges, cd.nextRange)
        thisLevel.delSize += cd.thisSize
        return true
}

func (cs *compactStatus) delete(cd compactDef) {
        cs.Lock()
        defer cs.Unlock()

        level := cd.thisLevel.level
        y.AssertTruef(level < len(cs.levels)-1, "Got level %d. Max levels: %d", level, len(cs.levels))

        thisLevel := cs.levels[level]
        nextLevel := cs.levels[level+1]

        thisLevel.delSize -= cd.thisSize
        found := thisLevel.remove(cd.thisRange)
        found = nextLevel.remove(cd.nextRange) && found

        if !found {
                this := cd.thisRange
                next := cd.nextRange
                fmt.Printf("Looking for: [%q, %q, %v] in this level.\n", this.left, this.right, this.inf)
                fmt.Printf("This Level:\n%s\n", thisLevel.debug())
                fmt.Println()
                fmt.Printf("Looking for: [%q, %q, %v] in next level.\n", next.left, next.right, next.inf)
                fmt.Printf("Next Level:\n%s\n", nextLevel.debug())
                log.Fatal("keyRange not found")
        }
}

1	/*
2	* Copyright 2017 Dgraph Labs, Inc. and Contributors
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16
17	package badger
18
19	import (
20	"bytes"
21	"fmt"
22	"log"
23	"math"
24	"sync"
25
26	"golang.org/x/net/trace"
27
28	"github.com/dgraph-io/badger/table"
29	"github.com/dgraph-io/badger/y"
30	)
31
32	type keyRange struct {
33	left []byte
34	right []byte
35	inf bool
36	}
37
38	var infRange = keyRange{inf: true}
39
40	func (r keyRange) String() string {	3,706✔
41	return fmt.Sprintf("[left=%x, right=%x, inf=%v]", r.left, r.right, r.inf)	3,706✔
42	}	3,706✔
43
44	func (r keyRange) equals(dst keyRange) bool {	926✔
45	return bytes.Equal(r.left, dst.left) &&	926✔
46	bytes.Equal(r.right, dst.right) &&	926✔
47	r.inf == dst.inf	926✔
48	}	926✔
49
50	func (r keyRange) overlapsWith(dst keyRange) bool {	14✔
51	if r.inf \|\| dst.inf {	24✔
52	return true	10✔
53	}	10✔
54
55	// If my left is greater than dst right, we have no overlap.
56	if y.CompareKeys(r.left, dst.right) > 0 {	4✔
57	return false	×
58	}	×
59	// If my right is less than dst left, we have no overlap.
60	if y.CompareKeys(r.right, dst.left) < 0 {	7✔
61	return false	3✔
62	}	3✔
63	// We have overlap.
64	return true	1✔
65	}
66
67	func getKeyRange(tables ...*table.Table) keyRange {	1,437✔
68	if len(tables) == 0 {	1,479✔
69	return keyRange{}	42✔
70	}	42✔
71	smallest := tables[0].Smallest()	1,395✔
72	biggest := tables[0].Biggest()	1,395✔
73	for i := 1; i < len(tables); i++ {	4,553✔
74	if y.CompareKeys(tables[i].Smallest(), smallest) < 0 {	4,584✔
75	smallest = tables[i].Smallest()	1,426✔
76	}	1,426✔
77	if y.CompareKeys(tables[i].Biggest(), biggest) > 0 {	5,112✔
78	biggest = tables[i].Biggest()	1,954✔
79	}	1,954✔
80	}
81
82	// We pick all the versions of the smallest and the biggest key. Note that version zero would
83	// be the rightmost key, considering versions are default sorted in descending order.
84	return keyRange{	1,395✔
85	left: y.KeyWithTs(y.ParseKey(smallest), math.MaxUint64),	1,395✔
86	right: y.KeyWithTs(y.ParseKey(biggest), 0),	1,395✔
87	}	1,395✔
88	}
89
90	type levelCompactStatus struct {
91	ranges []keyRange
92	delSize int64
93	}
94
95	func (lcs *levelCompactStatus) debug() string {	9,135✔
96	var b bytes.Buffer	9,135✔
97	for _, r := range lcs.ranges {	12,841✔
98	b.WriteString(r.String())	3,706✔
99	}	3,706✔
100	return b.String()	9,135✔
101	}
102
103	func (lcs *levelCompactStatus) overlapsWith(dst keyRange) bool {	6,407✔
104	for _, r := range lcs.ranges {	6,421✔
105	if r.overlapsWith(dst) {	25✔
106	return true	11✔
107	}	11✔
108	}
109	return false	6,396✔
110	}
111
112	func (lcs *levelCompactStatus) remove(dst keyRange) bool {	924✔
113	final := lcs.ranges[:0]	924✔
114	var found bool	924✔
115	for _, r := range lcs.ranges {	1,850✔
116	if !r.equals(dst) {	928✔
117	final = append(final, r)	2✔
118	} else {	926✔
119	found = true	924✔
120	}	924✔
121	}
122	lcs.ranges = final	924✔
123	return found	924✔
124	}
125
126	type compactStatus struct {
127	sync.RWMutex
128	levels []*levelCompactStatus
129	}
130
131	func (cs *compactStatus) toLog(tr trace.Trace) {	924✔
132	cs.RLock()	924✔
133	defer cs.RUnlock()	924✔
134		924✔
135	tr.LazyPrintf("Compaction status:")	924✔
136	for i, l := range cs.levels {	7,392✔
137	if l.debug() == "" {	11,088✔
138	continue	4,620✔
139	}
140	tr.LazyPrintf("[%d] %s", i, l.debug())	1,848✔
141	}
142	}
143
144	func (cs *compactStatus) overlapsWith(level int, this keyRange) bool {	5,473✔
145	cs.RLock()	5,473✔
146	defer cs.RUnlock()	5,473✔
147		5,473✔
148	thisLevel := cs.levels[level]	5,473✔
149	return thisLevel.overlapsWith(this)	5,473✔
150	}	5,473✔
151
152	func (cs *compactStatus) delSize(l int) int64 {	32,502✔
153	cs.RLock()	32,502✔
154	defer cs.RUnlock()	32,502✔
155	return cs.levels[l].delSize	32,502✔
156	}	32,502✔
157
158	type thisAndNextLevelRLocked struct{}
159
160	// compareAndAdd will check whether we can run this compactDef. That it doesn't overlap with any
161	// other running compaction. If it can be run, it would store this run in the compactStatus state.
162	func (cs *compactStatus) compareAndAdd(_ thisAndNextLevelRLocked, cd compactDef) bool {	470✔
163	cs.Lock()	470✔
164	defer cs.Unlock()	470✔
165		470✔
166	level := cd.thisLevel.level	470✔
167		470✔
168	y.AssertTruef(level < len(cs.levels)-1, "Got level %d. Max levels: %d", level, len(cs.levels))	470✔
169	thisLevel := cs.levels[level]	470✔
170	nextLevel := cs.levels[level+1]	470✔
171		470✔
172	if thisLevel.overlapsWith(cd.thisRange) {	476✔
173	return false	6✔
174	}	6✔
175	if nextLevel.overlapsWith(cd.nextRange) {	464✔
176	return false	×
177	}	×
178	// Check whether this level really needs compaction or not. Otherwise, we'll end up
179	// running parallel compactions for the same level.
180	// Update: We should not be checking size here. Compaction priority already did the size checks.
181	// Here we should just be executing the wish of others.
182
183	thisLevel.ranges = append(thisLevel.ranges, cd.thisRange)	464✔
184	nextLevel.ranges = append(nextLevel.ranges, cd.nextRange)	464✔
185	thisLevel.delSize += cd.thisSize	464✔
186	return true	464✔
187	}
188
189	func (cs *compactStatus) delete(cd compactDef) {	462✔
190	cs.Lock()	462✔
191	defer cs.Unlock()	462✔
192		462✔
193	level := cd.thisLevel.level	462✔
194	y.AssertTruef(level < len(cs.levels)-1, "Got level %d. Max levels: %d", level, len(cs.levels))	462✔
195		462✔
196	thisLevel := cs.levels[level]	462✔
197	nextLevel := cs.levels[level+1]	462✔
198		462✔
199	thisLevel.delSize -= cd.thisSize	462✔
200	found := thisLevel.remove(cd.thisRange)	462✔
201	found = nextLevel.remove(cd.nextRange) && found	462✔
202		462✔
203	if !found {	462✔
204	this := cd.thisRange	×
205	next := cd.nextRange	×
206	fmt.Printf("Looking for: [%q, %q, %v] in this level.\n", this.left, this.right, this.inf)	×
207	fmt.Printf("This Level:\n%s\n", thisLevel.debug())	×
208	fmt.Println()	×
209	fmt.Printf("Looking for: [%q, %q, %v] in next level.\n", next.left, next.right, next.inf)	×
210	fmt.Printf("Next Level:\n%s\n", nextLevel.debug())	×
211	log.Fatal("keyRange not found")	×
212	}	×
213	}

dgraph-io / badger / 2949

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous