Debian Codegraph @

tsdb/index/tsi1/tsi1.go

raw
1 package tsi1
2
3 import (
4 "bytes"
5 "encoding/binary"
6 "fmt"
7 "io"
8
9 "github.com/influxdata/influxdb/tsdb"
10 )
11
12 // LoadFactor is the fill percent for RHH indexes.
13 const LoadFactor = 80
14
15 // MeasurementElem represents a generic measurement element.
16 type MeasurementElem interface {
17 Name() []byte
18 Deleted() bool
19 // HasSeries() bool
20 }
21
22 // MeasurementElems represents a list of MeasurementElem.
23 type MeasurementElems []MeasurementElem
24
25 func (a MeasurementElems) Len() int { return len(a) }
26 func (a MeasurementElems) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
27 func (a MeasurementElems) Less(i, j int) bool { return bytes.Compare(a[i].Name(), a[j].Name()) == -1 }
28
29 // MeasurementIterator represents a iterator over a list of measurements.
30 type MeasurementIterator interface {
31 Next() MeasurementElem
32 }
33
34 // MergeMeasurementIterators returns an iterator that merges a set of iterators.
35 // Iterators that are first in the list take precendence and a deletion by those
36 // early iterators will invalidate elements by later iterators.
37 func MergeMeasurementIterators(itrs ...MeasurementIterator) MeasurementIterator {
38 if len(itrs) == 0 {
39 return nil
40 }
41
42 return &measurementMergeIterator{
43 e: make(measurementMergeElem, 0, len(itrs)),
44 buf: make([]MeasurementElem, len(itrs)),
45 itrs: itrs,
46 }
47 }
48
49 type measurementMergeIterator struct {
50 e measurementMergeElem
51 buf []MeasurementElem
52 itrs []MeasurementIterator
53 }
54
55 // Next returns the element with the next lowest name across the iterators.
56 //
57 // If multiple iterators contain the same name then the first is returned
58 // and the remaining ones are skipped.
59 func (itr *measurementMergeIterator) Next() MeasurementElem {
60 // Find next lowest name amongst the buffers.
61 var name []byte
62 for i, buf := range itr.buf {
63 // Fill buffer if empty.
64 if buf == nil {
65 if buf = itr.itrs[i].Next(); buf != nil {
66 itr.buf[i] = buf
67 } else {
68 continue
69 }
70 }
71
72 // Find next lowest name.
73 if name == nil || bytes.Compare(itr.buf[i].Name(), name) == -1 {
74 name = itr.buf[i].Name()
75 }
76 }
77
78 // Return nil if no elements remaining.
79 if name == nil {
80 return nil
81 }
82
83 // Merge all elements together and clear buffers.
84 itr.e = itr.e[:0]
85 for i, buf := range itr.buf {
86 if buf == nil || !bytes.Equal(buf.Name(), name) {
87 continue
88 }
89 itr.e = append(itr.e, buf)
90 itr.buf[i] = nil
91 }
92 return itr.e
93 }
94
95 // measurementMergeElem represents a merged measurement element.
96 type measurementMergeElem []MeasurementElem
97
98 // Name returns the name of the first element.
99 func (p measurementMergeElem) Name() []byte {
100 if len(p) == 0 {
101 return nil
102 }
103 return p[0].Name()
104 }
105
106 // Deleted returns the deleted flag of the first element.
107 func (p measurementMergeElem) Deleted() bool {
108 if len(p) == 0 {
109 return false
110 }
111 return p[0].Deleted()
112 }
113
114 // tsdbMeasurementIteratorAdapter wraps MeasurementIterator to match the TSDB interface.
115 // This is needed because TSDB doesn't have a concept of "deleted" measurements.
116 type tsdbMeasurementIteratorAdapter struct {
117 itr MeasurementIterator
118 }
119
120 // NewTSDBMeasurementIteratorAdapter return an iterator which implements tsdb.MeasurementIterator.
121 func NewTSDBMeasurementIteratorAdapter(itr MeasurementIterator) tsdb.MeasurementIterator {
122 if itr == nil {
123 return nil
124 }
125 return &tsdbMeasurementIteratorAdapter{itr: itr}
126 }
127
128 func (itr *tsdbMeasurementIteratorAdapter) Close() error { return nil }
129
130 func (itr *tsdbMeasurementIteratorAdapter) Next() ([]byte, error) {
131 for {
132 e := itr.itr.Next()
133 if e == nil {
134 return nil, nil
135 } else if e.Deleted() {
136 continue
137 }
138 return e.Name(), nil
139 }
140 }
141
142 // TagKeyElem represents a generic tag key element.
143 type TagKeyElem interface {
144 Key() []byte
145 Deleted() bool
146 TagValueIterator() TagValueIterator
147 }
148
149 // TagKeyIterator represents a iterator over a list of tag keys.
150 type TagKeyIterator interface {
151 Next() TagKeyElem
152 }
153
154 // tsdbTagKeyIteratorAdapter wraps TagKeyIterator to match the TSDB interface.
155 // This is needed because TSDB doesn't have a concept of "deleted" tag keys.
156 type tsdbTagKeyIteratorAdapter struct {
157 itr TagKeyIterator
158 }
159
160 // NewTSDBTagKeyIteratorAdapter return an iterator which implements tsdb.TagKeyIterator.
161 func NewTSDBTagKeyIteratorAdapter(itr TagKeyIterator) tsdb.TagKeyIterator {
162 if itr == nil {
163 return nil
164 }
165 return &tsdbTagKeyIteratorAdapter{itr: itr}
166 }
167
168 func (itr *tsdbTagKeyIteratorAdapter) Close() error { return nil }
169
170 func (itr *tsdbTagKeyIteratorAdapter) Next() ([]byte, error) {
171 for {
172 e := itr.itr.Next()
173 if e == nil {
174 return nil, nil
175 } else if e.Deleted() {
176 continue
177 }
178 return e.Key(), nil
179 }
180 }
181
182 // MergeTagKeyIterators returns an iterator that merges a set of iterators.
183 // Iterators that are first in the list take precendence and a deletion by those
184 // early iterators will invalidate elements by later iterators.
185 func MergeTagKeyIterators(itrs ...TagKeyIterator) TagKeyIterator {
186 if len(itrs) == 0 {
187 return nil
188 }
189
190 return &tagKeyMergeIterator{
191 e: make(tagKeyMergeElem, 0, len(itrs)),
192 buf: make([]TagKeyElem, len(itrs)),
193 itrs: itrs,
194 }
195 }
196
197 type tagKeyMergeIterator struct {
198 e tagKeyMergeElem
199 buf []TagKeyElem
200 itrs []TagKeyIterator
201 }
202
203 // Next returns the element with the next lowest key across the iterators.
204 //
205 // If multiple iterators contain the same key then the first is returned
206 // and the remaining ones are skipped.
207 func (itr *tagKeyMergeIterator) Next() TagKeyElem {
208 // Find next lowest key amongst the buffers.
209 var key []byte
210 for i, buf := range itr.buf {
211 // Fill buffer.
212 if buf == nil {
213 if buf = itr.itrs[i].Next(); buf != nil {
214 itr.buf[i] = buf
215 } else {
216 continue
217 }
218 }
219
220 // Find next lowest key.
221 if key == nil || bytes.Compare(buf.Key(), key) == -1 {
222 key = buf.Key()
223 }
224 }
225
226 // Return nil if no elements remaining.
227 if key == nil {
228 return nil
229 }
230
231 // Merge elements together & clear buffer.
232 itr.e = itr.e[:0]
233 for i, buf := range itr.buf {
234 if buf == nil || !bytes.Equal(buf.Key(), key) {
235 continue
236 }
237 itr.e = append(itr.e, buf)
238 itr.buf[i] = nil
239 }
240
241 return itr.e
242 }
243
244 // tagKeyMergeElem represents a merged tag key element.
245 type tagKeyMergeElem []TagKeyElem
246
247 // Key returns the key of the first element.
248 func (p tagKeyMergeElem) Key() []byte {
249 if len(p) == 0 {
250 return nil
251 }
252 return p[0].Key()
253 }
254
255 // Deleted returns the deleted flag of the first element.
256 func (p tagKeyMergeElem) Deleted() bool {
257 if len(p) == 0 {
258 return false
259 }
260 return p[0].Deleted()
261 }
262
263 // TagValueIterator returns a merge iterator for all elements until a tombstone occurs.
264 func (p tagKeyMergeElem) TagValueIterator() TagValueIterator {
265 if len(p) == 0 {
266 return nil
267 }
268
269 a := make([]TagValueIterator, 0, len(p))
270 for _, e := range p {
271 itr := e.TagValueIterator()
272
273 a = append(a, itr)
274 if e.Deleted() {
275 break
276 }
277 }
278 return MergeTagValueIterators(a...)
279 }
280
281 // TagValueElem represents a generic tag value element.
282 type TagValueElem interface {
283 Value() []byte
284 Deleted() bool
285 }
286
287 // TagValueIterator represents a iterator over a list of tag values.
288 type TagValueIterator interface {
289 Next() TagValueElem
290 }
291
292 // tsdbTagValueIteratorAdapter wraps TagValueIterator to match the TSDB interface.
293 // This is needed because TSDB doesn't have a concept of "deleted" tag values.
294 type tsdbTagValueIteratorAdapter struct {
295 itr TagValueIterator
296 }
297
298 // NewTSDBTagValueIteratorAdapter return an iterator which implements tsdb.TagValueIterator.
299 func NewTSDBTagValueIteratorAdapter(itr TagValueIterator) tsdb.TagValueIterator {
300 if itr == nil {
301 return nil
302 }
303 return &tsdbTagValueIteratorAdapter{itr: itr}
304 }
305
306 func (itr *tsdbTagValueIteratorAdapter) Close() error { return nil }
307
308 func (itr *tsdbTagValueIteratorAdapter) Next() ([]byte, error) {
309 for {
310 e := itr.itr.Next()
311 if e == nil {
312 return nil, nil
313 } else if e.Deleted() {
314 continue
315 }
316 return e.Value(), nil
317 }
318 }
319
320 // MergeTagValueIterators returns an iterator that merges a set of iterators.
321 // Iterators that are first in the list take precendence and a deletion by those
322 // early iterators will invalidate elements by later iterators.
323 func MergeTagValueIterators(itrs ...TagValueIterator) TagValueIterator {
324 if len(itrs) == 0 {
325 return nil
326 }
327
328 return &tagValueMergeIterator{
329 e: make(tagValueMergeElem, 0, len(itrs)),
330 buf: make([]TagValueElem, len(itrs)),
331 itrs: itrs,
332 }
333 }
334
335 type tagValueMergeIterator struct {
336 e tagValueMergeElem
337 buf []TagValueElem
338 itrs []TagValueIterator
339 }
340
341 // Next returns the element with the next lowest value across the iterators.
342 //
343 // If multiple iterators contain the same value then the first is returned
344 // and the remaining ones are skipped.
345 func (itr *tagValueMergeIterator) Next() TagValueElem {
346 // Find next lowest value amongst the buffers.
347 var value []byte
348 for i, buf := range itr.buf {
349 // Fill buffer.
350 if buf == nil {
351 if buf = itr.itrs[i].Next(); buf != nil {
352 itr.buf[i] = buf
353 } else {
354 continue
355 }
356 }
357
358 // Find next lowest value.
359 if value == nil || bytes.Compare(buf.Value(), value) == -1 {
360 value = buf.Value()
361 }
362 }
363
364 // Return nil if no elements remaining.
365 if value == nil {
366 return nil
367 }
368
369 // Merge elements and clear buffers.
370 itr.e = itr.e[:0]
371 for i, buf := range itr.buf {
372 if buf == nil || !bytes.Equal(buf.Value(), value) {
373 continue
374 }
375 itr.e = append(itr.e, buf)
376 itr.buf[i] = nil
377 }
378 return itr.e
379 }
380
381 // tagValueMergeElem represents a merged tag value element.
382 type tagValueMergeElem []TagValueElem
383
384 // Name returns the value of the first element.
385 func (p tagValueMergeElem) Value() []byte {
386 if len(p) == 0 {
387 return nil
388 }
389 return p[0].Value()
390 }
391
392 // Deleted returns the deleted flag of the first element.
393 func (p tagValueMergeElem) Deleted() bool {
394 if len(p) == 0 {
395 return false
396 }
397 return p[0].Deleted()
398 }
399
400 /*
401 type SeriesPointMergeIterator interface {
402 Next() (*query.FloatPoint, error)
403 Close() error
404 Stats() query.IteratorStats
405 }
406
407 func MergeSeriesPointIterators(itrs ...*seriesPointIterator) SeriesPointMergeIterator {
408 if n := len(itrs); n == 0 {
409 return nil
410 } else if n == 1 {
411 return itrs[0]
412 }
413
414 return &seriesPointMergeIterator{
415 buf: make([]*query.FloatPoint, len(itrs)),
416 itrs: itrs,
417 }
418 }
419
420 type seriesPointMergeIterator struct {
421 buf []*query.FloatPoint
422 itrs []*seriesPointIterator
423 }
424
425 func (itr *seriesPointMergeIterator) Close() error {
426 for i := range itr.itrs {
427 itr.itrs[i].Close()
428 }
429 return nil
430 }
431 func (itr *seriesPointMergeIterator) Stats() query.IteratorStats {
432 return query.IteratorStats{}
433 }
434
435 func (itr *seriesPointMergeIterator) Next() (_ *query.FloatPoint, err error) {
436 // Find next lowest point amongst the buffers.
437 var key []byte
438 for i, buf := range itr.buf {
439 // Fill buffer.
440 if buf == nil {
441 if buf, err = itr.itrs[i].Next(); err != nil {
442 return nil, err
443 } else if buf != nil {
444 itr.buf[i] = buf
445 } else {
446 continue
447 }
448 }
449
450 // Find next lowest key.
451 if key == nil || bytes.Compare(buf.Key(), key) == -1 {
452 key = buf.Key()
453 }
454 }
455
456 // Return nil if no elements remaining.
457 if key == nil {
458 return nil, nil
459 }
460
461 // Merge elements together & clear buffer.
462 itr.e = itr.e[:0]
463 for i, buf := range itr.buf {
464 if buf == nil || !bytes.Equal(buf.Key(), key) {
465 continue
466 }
467 itr.e = append(itr.e, buf)
468 itr.buf[i] = nil
469 }
470
471 return itr.e, nil
472 }
473 */
474
475 // writeTo writes write v into w. Updates n.
476 func writeTo(w io.Writer, v []byte, n *int64) error {
477 nn, err := w.Write(v)
478 *n += int64(nn)
479 return err
480 }
481
482 // writeUint8To writes write v into w. Updates n.
483 func writeUint8To(w io.Writer, v uint8, n *int64) error {
484 nn, err := w.Write([]byte{v})
485 *n += int64(nn)
486 return err
487 }
488
489 // writeUint16To writes write v into w using big endian encoding. Updates n.
490 func writeUint16To(w io.Writer, v uint16, n *int64) error {
491 var buf [2]byte
492 binary.BigEndian.PutUint16(buf[:], v)
493 nn, err := w.Write(buf[:])
494 *n += int64(nn)
495 return err
496 }
497
498 // writeUint64To writes write v into w using big endian encoding. Updates n.
499 func writeUint64To(w io.Writer, v uint64, n *int64) error {
500 var buf [8]byte
501 binary.BigEndian.PutUint64(buf[:], v)
502 nn, err := w.Write(buf[:])
503 *n += int64(nn)
504 return err
505 }
506
507 // writeUvarintTo writes write v into w using variable length encoding. Updates n.
508 func writeUvarintTo(w io.Writer, v uint64, n *int64) error {
509 var buf [binary.MaxVarintLen64]byte
510 i := binary.PutUvarint(buf[:], v)
511 nn, err := w.Write(buf[:i])
512 *n += int64(nn)
513 return err
514 }
515
516 type uint64Slice []uint64
517
518 func (a uint64Slice) Len() int { return len(a) }
519 func (a uint64Slice) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
520 func (a uint64Slice) Less(i, j int) bool { return a[i] < a[j] }
521
522 type byteSlices [][]byte
523
524 func (a byteSlices) Len() int { return len(a) }
525 func (a byteSlices) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
526 func (a byteSlices) Less(i, j int) bool { return bytes.Compare(a[i], a[j]) == -1 }
527
528 // assert will panic with a given formatted message if the given condition is false.
529 func assert(condition bool, msg string, v ...interface{}) {
530 if !condition {
531 panic(fmt.Sprintf("assert failed: "+msg, v...))
532 }
533 }
534
535 // uvarint is a wrapper around binary.Uvarint.
536 // Returns a non-nil error when binary.Uvarint returns n <= 0 or n > len(data).
537 func uvarint(data []byte) (value uint64, n int, err error) {
538 if len(data) < 1 {
539 err = io.ErrShortBuffer
540 } else if value, n = binary.Uvarint(data); n == 0 || n > len(data) {
541 err = io.ErrShortBuffer
542 } else if n < 0 {
543 err = fmt.Errorf("parsing binary-encoded uint64 value failed; binary.Uvarint() returned %d", n)
544 }
545 return
546 }
547
548 // hexdump is a helper for dumping binary data to stderr.
549 // func hexdump(data []byte) { os.Stderr.Write([]byte(hex.Dump(data))) }
550
551 // stack is a helper for dumping a stack trace.
552 // func stack() string {
553 // return "------------------------\n" + string(debug.Stack()) + "------------------------\n\n"
554 // }