Repository: prometheus/tsdb
Pull request #595 (2019-05-01 16:25:33)

Simplify mergedPostings.Seek
The current implementation leads to very slow behaviour when there's
many lists, this at least is n log k, where k is the number of posting
lists.

Adjust benchmark to catch this.

Remove flattening of without lists, not needed anymore.

Benchmark versus 0.4.0 (used in Prometheus 2.7):
```
benchmark                                                            old ns/op      new ns/op      delta
BenchmarkHeadPostingForMatchers/n="1"-8                              189907976      188863880      -0.55%
BenchmarkHeadPostingForMatchers/n="1",j="foo"-8                      113950106      110791414      -2.77%
BenchmarkHeadPostingForMatchers/j="foo",n="1"-8                      104965646      102388760      -2.45%
BenchmarkHeadPostingForMatchers/n="1",j!="foo"-8                     138743592      104424250      -24.74%
BenchmarkHeadPostingForMatchers/i=~".*"-8                            5279594954     5206096267     -1.39%
BenchmarkHeadPostingForMatchers/i=~".+"-8                            8004610589     6184527719     -22.74%
BenchmarkHeadPostingForMatchers/i=~""-8                              2476042646     1003920432     -59.45%
BenchmarkHeadPostingForMatchers/i!=""-8                              7178244655     6059725323     -15.58%
BenchmarkHeadPostingForMatchers/n="1",i=~".*",j="foo"-8              199342649      166642946      -16.40%
BenchmarkHeadPostingForMatchers/n="1",i=~".*",i!="2",j="foo"-8       215774683      167515095      -22.37%
BenchmarkHeadPostingForMatchers/n="1",i!=""-8                        2214714769     392943663      -82.26%
BenchmarkHeadPostingForMatchers/n="1",i!="",j="foo"-8                2148727410     322289262      -85.00%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",j="foo"-8              2170658009     338458171      -84.41%
BenchmarkHeadPostingForMatchers/n="1",i=~"1.+",j="foo"-8             235720135      70597905       -70.05%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",i!="2",j="foo"-8       2190570590     343034307      -84.34%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",i!~"2.*",j="foo"-8     2373784439     387297908      -83.68%

benchmark                                                            old allocs     new allocs     delta
BenchmarkHeadPostingForMatchers/n="1"-8                              33             33             +0.00%
BenchmarkHeadPostingForMatchers/n="1",j="foo"-8                      33             33             +0.00%
BenchmarkHeadPostingForMatchers/j="foo",n="1"-8                      33             33             +0.00%
BenchmarkHeadPostingForMatchers/n="1",j!="foo"-8                     41             39             -4.88%
BenchmarkHeadPostingForMatchers/i=~".*"-8                            56             56             +0.00%
BenchmarkHeadPostingForMatchers/i=~".+"-8                            251577         100115         -60.21%
BenchmarkHeadPostingForMatchers/i=~""-8                              251123         100077         -60.15%
BenchmarkHeadPostingForMatchers/i!=""-8                              251525         100112         -60.20%
BenchmarkHeadPostingForMatchers/n="1",i=~".*",j="foo"-8              42             39             -7.14%
BenchmarkHeadPostingForMatchers/n="1",i=~".*",i!="2",j="foo"-8       52             42             -19.23%
BenchmarkHeadPostingForMatchers/n="1",i!=""-8                        251069         100101         -60.13%
BenchmarkHeadPostingForMatchers/n="1",i!="",j="foo"-8                251473         100101         -60.19%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",j="foo"-8              250914         100102         -60.11%
BenchmarkHeadPostingForMatchers/n="1",i=~"1.+",j="foo"-8             30038          11181          -62.78%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",i!="2",j="foo"-8       250813         100105         -60.09%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",i!~"2.*",j="foo"-8     281503         111260         -60.48%

benchmark                                                            old bytes     new bytes     delta
BenchmarkHeadPostingForMatchers/n="1"-8                              10887600      10887600      +0.00%
BenchmarkHeadPostingForMatchers/n="1",j="foo"-8                      5456416       5456416       +0.00%
BenchmarkHeadPostingForMatchers/j="foo",n="1"-8                      5456416       5456416       +0.00%
BenchmarkHeadPostingForMatchers/n="1",j!="foo"-8                     5456640       5456544       -0.00%
BenchmarkHeadPostingForMatchers/i=~".*"-8                            258254504     258254472     -0.00%
BenchmarkHeadPostingForMatchers/i=~".+"-8                            520126192     281554792     -45.87%
BenchmarkHeadPostingForMatchers/i=~""-8                              263446640     24908456      -90.55%
BenchmarkHeadPostingForMatchers/i!=""-8                              520121144     281553664     -45.87%
BenchmarkHeadPostingForMatchers/n="1",i=~".*",j="foo"-8              7062448       7062272       -0.00%
BenchmarkHeadPostingForMatchers/n="1",i=~".*",i!="2",j="foo"-8       7063473       7062384       -0.02%
BenchmarkHeadPostingForMatchers/n="1",i!=""-8                        274325656     35793776      -86.95%
BenchmarkHeadPostingForMatchers/n="1",i!="",j="foo"-8                268926824     30362624      -88.71%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",j="foo"-8              268882992     30363000      -88.71%
BenchmarkHeadPostingForMatchers/n="1",i=~"1.+",j="foo"-8             33193401      4269304       -87.14%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",i!="2",j="foo"-8       268875024     30363096      -88.71%
BenchmarkHeadPostingForMatchers/n="1",i=~".+",i!~"2.*",j="foo"-8     300589656     33099784      -88.99%
```
Benchmark against master is also good.


I'm pretty sure I tried this approach originally, but it came out as slower at the time. Other improvements have likely helped.

Fixes https://github.com/prometheus/prometheus/issues/5424


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 50276ed..87b6420 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,5 +1,6 @@
 ## master / unreleased
  - [BUGFIX] Calling `Close` more than once on a querier returns an error instead of a panic.
+ - [ENHANCEMENT] Add (again) FromData function to easily create a chunk from bytes.
 
 
 ## 0.7.1
diff --git a/Makefile.common b/Makefile.common
index 73052b3..4f18ea5 100644
--- a/Makefile.common
+++ b/Makefile.common
@@ -73,6 +73,7 @@ PROMU_VERSION ?= 0.3.0
 PROMU_URL     := https://github.com/prometheus/promu/releases/download/v$(PROMU_VERSION)/promu-$(PROMU_VERSION).$(GO_BUILD_PLATFORM).tar.gz
 
 GOLANGCI_LINT :=
+GOLANGCI_LINT_OPTS ?=
 GOLANGCI_LINT_VERSION ?= v1.16.0
 # golangci-lint only supports linux, darwin and windows platforms on i386/amd64.
 # windows isn't included here because of the path separator being different.
@@ -166,7 +167,7 @@ ifdef GO111MODULE
 # 'go list' needs to be executed before staticcheck to prepopulate the modules cache.
 # Otherwise staticcheck might fail randomly for some reason not yet explained.
 	GO111MODULE=$(GO111MODULE) $(GO) list -e -compiled -test=true -export=false -deps=true -find=false -tags= -- ./... > /dev/null
-	GO111MODULE=$(GO111MODULE) $(GOLANGCI_LINT) run $(pkgs)
+	GO111MODULE=$(GO111MODULE) $(GOLANGCI_LINT) run $(GOLANGCI_LINT_OPTS) $(pkgs)
 else
 	$(GOLANGCI_LINT) run $(pkgs)
 endif
diff --git a/chunkenc/chunk.go b/chunkenc/chunk.go
index 6c1b8b7..dc56660 100644
--- a/chunkenc/chunk.go
+++ b/chunkenc/chunk.go
@@ -14,6 +14,7 @@
 package chunkenc
 
 import (
+	"fmt"
 	"sync"
 
 	"github.com/pkg/errors"
@@ -70,16 +71,18 @@ func (nopIterator) At() (int64, float64) { return 0, 0 }
 func (nopIterator) Next() bool           { return false }
 func (nopIterator) Err() error           { return nil }
 
+// Pool is used to create and reuse chunk references to avoid allocations.
 type Pool interface {
 	Put(Chunk) error
 	Get(e Encoding, b []byte) (Chunk, error)
 }
 
-// Pool is a memory pool of chunk objects.
+// pool is a memory pool of chunk objects.
 type pool struct {
 	xor sync.Pool
 }
 
+// NewPool returns a new pool.
 func NewPool() Pool {
 	return &pool{
 		xor: sync.Pool{
@@ -119,3 +122,14 @@ func (p *pool) Put(c Chunk) error {
 	}
 	return nil
 }
+
+// FromData returns a chunk from a byte slice of chunk data.
+// This is there so that users of the library can easily create chunks from
+// bytes.
+func FromData(e Encoding, d []byte) (Chunk, error) {
+	switch e {
+	case EncXOR:
+		return &XORChunk{b: bstream{count: 0, stream: d}}, nil
+	}
+	return nil, fmt.Errorf("unknown chunk encoding: %d", e)
+}
diff --git a/docs/format/index.md b/docs/format/index.md
index 1ec3c21..e5fa05e 100644
--- a/docs/format/index.md
+++ b/docs/format/index.md
@@ -153,7 +153,7 @@ For instance, a single label name with 4 different values will be encoded as:
 └────┴───┴───┴──────────────┴──────────────┴──────────────┴──────────────┴───────┘
 ```
 
-The sequence of label index sections is finalized by an [offset table](#offset-table) pointing to the beginning of each label index section for a given set of label names.
+The sequence of label index sections is finalized by a [label offset table](#label-offset-table) containing label offset entries that points to the beginning of each label index section for a given label name.
 
 ### Postings
 
@@ -175,24 +175,48 @@ Postings sections store monotonically increasing lists of series references that
 └─────────────────────────────────────────┘
 ```
 
-The sequence of postings sections is finalized by an [offset table](#offset-table) pointing to the beginning of each postings section for a given set of label names.
+The sequence of postings sections is finalized by a [postings offset table](#postings-offset-table) containing postings offset entries that points to the beginning of each postings section for a given label pair.
 
-### Offset Table
+### Label Offset Table
 
-An offset table stores a sequence of entries that maps a list of strings to an offset. They are used to track label index and postings sections. They are read into memory when an index file is loaded.
+A label offset table stores a sequence of label offset entries.
+Every label offset entry holds the label name and the offset to its values in the label index section.
+They are used to track label index sections. They are read into memory when an index file is loaded.
 
 ```
 ┌─────────────────────┬──────────────────────┐
 │ len <4b>            │ #entries <4b>        │
 ├─────────────────────┴──────────────────────┤
 │ ┌────────────────────────────────────────┐ │
-│ │  n = #strs <uvarint>                   │ │
+│ │  n = 1 <1b>                            │ │
 │ ├──────────────────────┬─────────────────┤ │
-│ │ len(str_1) <uvarint> │ str_1 <bytes>   │ │
+│ │ len(name) <uvarint>  │ name <bytes>    │ │
 │ ├──────────────────────┴─────────────────┤ │
-│ │  ...                                   │ │
+│ │  offset <uvarint64>                    │ │
+│ └────────────────────────────────────────┘ │
+│                    . . .                   │
+├────────────────────────────────────────────┤
+│  CRC32 <4b>                                │
+└────────────────────────────────────────────┘
+```
+
+
+### Postings Offset Table
+
+A postings offset table stores a sequence of postings offset entries.
+Every postings offset entry holds the lable name/value pair and the offset to its series list in the postings section.
+They are used to track postings sections. They are read into memory when an index file is loaded.
+
+```
+┌─────────────────────┬──────────────────────┐
+│ len <4b>            │ #entries <4b>        │
+├─────────────────────┴──────────────────────┤
+│ ┌────────────────────────────────────────┐ │
+│ │  n = 2 <1b>                            │ │
 │ ├──────────────────────┬─────────────────┤ │
-│ │ len(str_n) <uvarint> │ str_n <bytes>   │ │
+│ │ len(name) <uvarint>  │ name <bytes>    │ │
+│ ├──────────────────────┼─────────────────┤ │
+│ │ len(value) <uvarint> │ value <bytes>   │ │
 │ ├──────────────────────┴─────────────────┤ │
 │ │  offset <uvarint64>                    │ │
 │ └────────────────────────────────────────┘ │
@@ -216,11 +240,11 @@ If a reference is zero, it indicates the respective section does not exist and e
 ├─────────────────────────────────────────┤
 │ ref(label indices start) <8b>           │
 ├─────────────────────────────────────────┤
-│ ref(label indices table) <8b>           │
+│ ref(label offset table) <8b>            │
 ├─────────────────────────────────────────┤
 │ ref(postings start) <8b>                │
 ├─────────────────────────────────────────┤
-│ ref(postings table) <8b>                │
+│ ref(postings offset table) <8b>         │
 ├─────────────────────────────────────────┤
 │ CRC32 <4b>                              │
 └─────────────────────────────────────────┘
diff --git a/head.go b/head.go
index cfb7cb8..30cbe61 100644
--- a/head.go
+++ b/head.go
@@ -755,6 +755,9 @@ func (a *headAppender) Add(lset labels.Labels, t int64, v float64) (uint64, erro
 		return 0, ErrOutOfBounds
 	}
 
+	// Ensure no empty labels have gotten through.
+	lset = lset.WithoutEmpty()
+
 	s, created := a.head.getOrCreate(lset.Hash(), lset)
 	if created {
 		a.series = append(a.series, RefSeries{
diff --git a/index/postings.go b/index/postings.go
index cdad939..bb7b583 100644
--- a/index/postings.go
+++ b/index/postings.go
@@ -404,7 +404,6 @@ func (h *postingsHeap) Pop() interface{} {
 type mergedPostings struct {
 	h          postingsHeap
 	initilized bool
-	heaped     bool
 	cur        uint64
 	err        error
 }
@@ -434,12 +433,9 @@ func (it *mergedPostings) Next() bool {
 		return false
 	}
 
-	if !it.heaped {
-		heap.Init(&it.h)
-		it.heaped = true
-	}
 	// The user must issue an initial Next.
 	if !it.initilized {
+		heap.Init(&it.h)
 		it.cur = it.h[0].At()
 		it.initilized = true
 		return true
@@ -477,33 +473,24 @@ func (it *mergedPostings) Seek(id uint64) bool {
 			return false
 		}
 	}
-	if it.cur >= id {
-		return true
-	}
-	// Heapifying when there is lots of Seeks is inefficient,
-	// mark to be re-heapified on the Next() call.
-	it.heaped = false
-	lowest := ^uint64(0)
-	n := 0
-	for _, i := range it.h {
-		if i.Seek(id) {
-			it.h[n] = i
-			n++
-			if i.At() < lowest {
-				lowest = i.At()
+	for it.cur < id {
+		cur := it.h[0]
+		if !cur.Seek(id) {
+			heap.Pop(&it.h)
+			if cur.Err() != nil {
+				it.err = cur.Err()
+				return false
 			}
-		} else {
-			if i.Err() != nil {
-				it.err = i.Err()
+			if it.h.Len() == 0 {
 				return false
 			}
+		} else {
+			// Value of top of heap has changed, re-heapify.
+			heap.Fix(&it.h, 0)
 		}
+
+		it.cur = it.h[0].At()
 	}
-	it.h = it.h[:n]
-	if len(it.h) == 0 {
-		return false
-	}
-	it.cur = lowest
 	return true
 }
 
diff --git a/labels/labels.go b/labels/labels.go
index 35a230f..aab8e42 100644
--- a/labels/labels.go
+++ b/labels/labels.go
@@ -103,6 +103,23 @@ func (ls Labels) Map() map[string]string {
 	return m
 }
 
+// WithoutEmpty returns the labelset without empty labels.
+// May return the same labelset.
+func (ls Labels) WithoutEmpty() Labels {
+	for _, v := range ls {
+		if v.Value == "" {
+			els := make(Labels, 0, len(ls)-1)
+			for _, v := range ls {
+				if v.Value != "" {
+					els = append(els, v)
+				}
+			}
+			return els
+		}
+	}
+	return ls
+}
+
 // New returns a sorted Labels from the given labels.
 // The caller has to guarantee that all label names are unique.
 func New(ls ...Label) Labels {
@@ -119,7 +136,9 @@ func New(ls ...Label) Labels {
 func FromMap(m map[string]string) Labels {
 	l := make(Labels, 0, len(m))
 	for k, v := range m {
-		l = append(l, Label{Name: k, Value: v})
+		if v != "" {
+			l = append(l, Label{Name: k, Value: v})
+		}
 	}
 	sort.Sort(l)
 
@@ -133,7 +152,9 @@ func FromStrings(ss ...string) Labels {
 	}
 	var res Labels
 	for i := 0; i < len(ss); i += 2 {
-		res = append(res, Label{Name: ss[i], Value: ss[i+1]})
+		if ss[i+1] != "" {
+			res = append(res, Label{Name: ss[i], Value: ss[i+1]})
+		}
 	}
 
 	sort.Sort(res)
diff --git a/querier.go b/querier.go
index b7116c2..9d99de0 100644
--- a/querier.go
+++ b/querier.go
@@ -332,15 +332,6 @@ func PostingsForMatchers(ix IndexReader, ms ...labels.Matcher) (index.Postings,
 	it := index.Intersect(its...)
 
 	for _, n := range notIts {
-		if _, ok := n.(*index.ListPostings); !ok {
-			// Best to pre-calculate the merged lists via next rather than have a ton
-			// of seeks in Without.
-			pl, err := index.ExpandPostings(n)
-			if err != nil {
-				return nil, err
-			}
-			n = index.NewListPostings(pl)
-		}
 		it = index.Without(it, n)
 	}
 


Test patch:
diff --git a/db_test.go b/db_test.go
index 54197df..6014a1d 100644
--- a/db_test.go
+++ b/db_test.go
@@ -219,6 +219,29 @@ func TestDBAppenderAddRef(t *testing.T) {
 	}, res)
 }
 
+func TestAppendEmptyLabelsIgnored(t *testing.T) {
+	db, delete := openTestDB(t, nil)
+	defer func() {
+		testutil.Ok(t, db.Close())
+		delete()
+	}()
+
+	app1 := db.Appender()
+
+	ref1, err := app1.Add(labels.FromStrings("a", "b"), 123, 0)
+	testutil.Ok(t, err)
+
+	// Construct labels manually so there is an empty label.
+	ref2, err := app1.Add(labels.Labels{labels.Label{"a", "b"}, labels.Label{"c", ""}}, 124, 0)
+	testutil.Ok(t, err)
+
+	// Should be the same series.
+	testutil.Equals(t, ref1, ref2)
+
+	err = app1.Commit()
+	testutil.Ok(t, err)
+}
+
 func TestDeleteSimple(t *testing.T) {
 	numSamples := int64(10)
 
@@ -1580,26 +1603,26 @@ func TestDB_LabelNames(t *testing.T) {
 	}{
 		{
 			sampleLabels1: [][2]string{
-				[2]string{"name1", ""},
-				[2]string{"name3", ""},
-				[2]string{"name2", ""},
+				[2]string{"name1", "1"},
+				[2]string{"name3", "3"},
+				[2]string{"name2", "2"},
 			},
 			sampleLabels2: [][2]string{
-				[2]string{"name4", ""},
-				[2]string{"name1", ""},
+				[2]string{"name4", "4"},
+				[2]string{"name1", "1"},
 			},
 			exp1: []string{"name1", "name2", "name3"},
 			exp2: []string{"name1", "name2", "name3", "name4"},
 		},
 		{
 			sampleLabels1: [][2]string{
-				[2]string{"name2", ""},
-				[2]string{"name1", ""},
-				[2]string{"name2", ""},
+				[2]string{"name2", "2"},
+				[2]string{"name1", "1"},
+				[2]string{"name2", "2"},
 			},
 			sampleLabels2: [][2]string{
-				[2]string{"name6", ""},
-				[2]string{"name0", ""},
+				[2]string{"name6", "6"},
+				[2]string{"name0", "0"},
 			},
 			exp1: []string{"name1", "name2"},
 			exp2: []string{"name0", "name1", "name2", "name6"},
diff --git a/head_bench_test.go b/head_bench_test.go
index 68505ea..0b0391e 100644
--- a/head_bench_test.go
+++ b/head_bench_test.go
@@ -56,20 +56,21 @@ func BenchmarkHeadPostingForMatchers(b *testing.B) {
 		testutil.Ok(b, h.Close())
 	}()
 
-	var hash uint64
+	var ref uint64
+
+	addSeries := func(l labels.Labels) {
+		ref++
+		h.getOrCreateWithID(ref, l.Hash(), l)
+	}
+
 	for n := 0; n < 10; n++ {
 		for i := 0; i < 100000; i++ {
-			h.getOrCreate(hash, labels.FromStrings("i", strconv.Itoa(i), "n", strconv.Itoa(i), "j", "foo"))
-			hash++
+			addSeries(labels.FromStrings("i", strconv.Itoa(i), "n", strconv.Itoa(n), "j", "foo"))
 			// Have some series that won't be matched, to properly test inverted matches.
-			h.getOrCreate(hash, labels.FromStrings("i", strconv.Itoa(i), "n", strconv.Itoa(i), "j", "bar"))
-			hash++
-			h.getOrCreate(hash, labels.FromStrings("i", strconv.Itoa(i), "n", "0_"+strconv.Itoa(i), "j", "bar"))
-			hash++
-			h.getOrCreate(hash, labels.FromStrings("i", strconv.Itoa(i), "n", "1_"+strconv.Itoa(i), "j", "bar"))
-			hash++
-			h.getOrCreate(hash, labels.FromStrings("i", strconv.Itoa(i), "n", "2_"+strconv.Itoa(i), "j", "bar"))
-			hash++
+			addSeries(labels.FromStrings("i", strconv.Itoa(i), "n", strconv.Itoa(n), "j", "bar"))
+			addSeries(labels.FromStrings("i", strconv.Itoa(i), "n", "0_"+strconv.Itoa(n), "j", "bar"))
+			addSeries(labels.FromStrings("i", strconv.Itoa(i), "n", "1_"+strconv.Itoa(n), "j", "bar"))
+			addSeries(labels.FromStrings("i", strconv.Itoa(i), "n", "2_"+strconv.Itoa(n), "j", "foo"))
 		}
 	}
 
@@ -100,6 +101,7 @@ func BenchmarkHeadPostingForMatchers(b *testing.B) {
 		{`i!=""`, []labels.Matcher{iNotEmpty}},
 		{`n="1",i=~".*",j="foo"`, []labels.Matcher{n1, iStar, jFoo}},
 		{`n="1",i=~".*",i!="2",j="foo"`, []labels.Matcher{n1, iStar, iNot2, jFoo}},
+		{`n="1",i!=""`, []labels.Matcher{n1, iNotEmpty}},
 		{`n="1",i!="",j="foo"`, []labels.Matcher{n1, iNotEmpty, jFoo}},
 		{`n="1",i=~".+",j="foo"`, []labels.Matcher{n1, iPlus, jFoo}},
 		{`n="1",i=~"1.+",j="foo"`, []labels.Matcher{n1, i1Plus, jFoo}},