Debian Codegraph @

tsdb/index/inmem/inmem.go

raw
1 /*
2 Package inmem implements a shared, in-memory index for each database.
3
4 The in-memory index is the original index implementation and provides fast
5 access to index data. However, it also forces high memory usage for large
6 datasets and can cause OOM errors.
7
8 Index is the shared index structure that provides most of the functionality.
9 However, ShardIndex is a light per-shard wrapper that adapts this original
10 shared index format to the new per-shard format.
11 */
12 package inmem
13
14 import (
15 "errors"
16 "fmt"
17 "regexp"
18 "sort"
19 "sync"
20 "unsafe"
21
22 "github.com/influxdata/influxdb/models"
23 "github.com/influxdata/influxdb/pkg/bytesutil"
24 "github.com/influxdata/influxdb/pkg/escape"
25 "github.com/influxdata/influxdb/pkg/estimator"
26 "github.com/influxdata/influxdb/pkg/estimator/hll"
27 "github.com/influxdata/influxdb/query"
28 "github.com/influxdata/influxdb/tsdb"
29 "github.com/influxdata/influxql"
30 "go.uber.org/zap"
31 )
32
33 // IndexName is the name of this index.
34 const IndexName = tsdb.InmemIndexName
35
36 func init() {
37 tsdb.NewInmemIndex = func(name string, sfile *tsdb.SeriesFile) (interface{}, error) { return NewIndex(name, sfile), nil }
38
39 tsdb.RegisterIndex(IndexName, func(id uint64, database, path string, seriesIDSet *tsdb.SeriesIDSet, sfile *tsdb.SeriesFile, opt tsdb.EngineOptions) tsdb.Index {
40 return NewShardIndex(id, seriesIDSet, opt)
41 })
42 }
43
44 // Index is the in memory index of a collection of measurements, time
45 // series, and their tags. Exported functions are goroutine safe while
46 // un-exported functions assume the caller will use the appropriate locks.
47 type Index struct {
48 mu sync.RWMutex
49
50 database string
51 sfile *tsdb.SeriesFile
52 fieldset *tsdb.MeasurementFieldSet
53
54 // In-memory metadata index, built on load and updated when new series come in
55 measurements map[string]*measurement // measurement name to object and index
56 series map[string]*series // map series key to the Series object
57
58 seriesSketch, seriesTSSketch estimator.Sketch
59 measurementsSketch, measurementsTSSketch estimator.Sketch
60
61 // Mutex to control rebuilds of the index
62 rebuildQueue sync.Mutex
63 }
64
65 // NewIndex returns a new initialized Index.
66 func NewIndex(database string, sfile *tsdb.SeriesFile) *Index {
67 index := &Index{
68 database: database,
69 sfile: sfile,
70 measurements: make(map[string]*measurement),
71 series: make(map[string]*series),
72 }
73
74 index.seriesSketch = hll.NewDefaultPlus()
75 index.seriesTSSketch = hll.NewDefaultPlus()
76 index.measurementsSketch = hll.NewDefaultPlus()
77 index.measurementsTSSketch = hll.NewDefaultPlus()
78
79 return index
80 }
81
82 func (i *Index) UniqueReferenceID() uintptr {
83 return uintptr(unsafe.Pointer(i))
84 }
85
86 // Bytes estimates the memory footprint of this Index, in bytes.
87 func (i *Index) Bytes() int {
88 var b int
89 i.mu.RLock()
90 b += 24 // mu RWMutex is 24 bytes
91 b += int(unsafe.Sizeof(i.database)) + len(i.database)
92 // Do not count SeriesFile because it belongs to the code that constructed this Index.
93 if i.fieldset != nil {
94 b += int(unsafe.Sizeof(i.fieldset)) + i.fieldset.Bytes()
95 }
96 b += int(unsafe.Sizeof(i.fieldset))
97 for k, v := range i.measurements {
98 b += int(unsafe.Sizeof(k)) + len(k)
99 b += int(unsafe.Sizeof(v)) + v.bytes()
100 }
101 b += int(unsafe.Sizeof(i.measurements))
102 for k, v := range i.series {
103 b += int(unsafe.Sizeof(k)) + len(k)
104 b += int(unsafe.Sizeof(v)) + v.bytes()
105 }
106 b += int(unsafe.Sizeof(i.series))
107 b += int(unsafe.Sizeof(i.seriesSketch)) + i.seriesSketch.Bytes()
108 b += int(unsafe.Sizeof(i.seriesTSSketch)) + i.seriesTSSketch.Bytes()
109 b += int(unsafe.Sizeof(i.measurementsSketch)) + i.measurementsSketch.Bytes()
110 b += int(unsafe.Sizeof(i.measurementsTSSketch)) + i.measurementsTSSketch.Bytes()
111 b += 8 // rebuildQueue Mutex is 8 bytes
112 i.mu.RUnlock()
113 return b
114 }
115
116 func (i *Index) Type() string { return IndexName }
117 func (i *Index) Open() (err error) { return nil }
118 func (i *Index) Close() error { return nil }
119
120 func (i *Index) WithLogger(*zap.Logger) {}
121
122 // Database returns the name of the database the index was initialized with.
123 func (i *Index) Database() string {
124 return i.database
125 }
126
127 // Series returns a series by key.
128 func (i *Index) Series(key []byte) (*series, error) {
129 i.mu.RLock()
130 s := i.series[string(key)]
131 i.mu.RUnlock()
132 return s, nil
133 }
134
135 // SeriesSketches returns the sketches for the series.
136 func (i *Index) SeriesSketches() (estimator.Sketch, estimator.Sketch, error) {
137 i.mu.RLock()
138 defer i.mu.RUnlock()
139 return i.seriesSketch.Clone(), i.seriesTSSketch.Clone(), nil
140 }
141
142 // Measurement returns the measurement object from the index by the name
143 func (i *Index) Measurement(name []byte) (*measurement, error) {
144 i.mu.RLock()
145 defer i.mu.RUnlock()
146 return i.measurements[string(name)], nil
147 }
148
149 // MeasurementExists returns true if the measurement exists.
150 func (i *Index) MeasurementExists(name []byte) (bool, error) {
151 i.mu.RLock()
152 defer i.mu.RUnlock()
153 return i.measurements[string(name)] != nil, nil
154 }
155
156 // MeasurementsSketches returns the sketches for the measurements.
157 func (i *Index) MeasurementsSketches() (estimator.Sketch, estimator.Sketch, error) {
158 i.mu.RLock()
159 defer i.mu.RUnlock()
160 return i.measurementsSketch.Clone(), i.measurementsTSSketch.Clone(), nil
161 }
162
163 // MeasurementsByName returns a list of measurements.
164 func (i *Index) MeasurementsByName(names [][]byte) ([]*measurement, error) {
165 i.mu.RLock()
166 defer i.mu.RUnlock()
167
168 a := make([]*measurement, 0, len(names))
169 for _, name := range names {
170 if m := i.measurements[string(name)]; m != nil {
171 a = append(a, m)
172 }
173 }
174 return a, nil
175 }
176
177 // MeasurementIterator returns an iterator over all measurements in the index.
178 // MeasurementIterator does not support authorization.
179 func (i *Index) MeasurementIterator() (tsdb.MeasurementIterator, error) {
180 names, err := i.MeasurementNamesByExpr(nil, nil)
181 if err != nil {
182 return nil, err
183 }
184 return tsdb.NewMeasurementSliceIterator(names), nil
185 }
186
187 // CreateSeriesListIfNotExists adds the series for the given measurement to the
188 // index and sets its ID or returns the existing series object
189 func (i *Index) CreateSeriesListIfNotExists(seriesIDSet *tsdb.SeriesIDSet, keys, names [][]byte, tagsSlice []models.Tags, opt *tsdb.EngineOptions, ignoreLimits bool) error {
190 seriesIDs, err := i.sfile.CreateSeriesListIfNotExists(names, tagsSlice)
191 if err != nil {
192 return err
193 }
194
195 i.mu.RLock()
196 // if there is a series for this ids, it's already been added
197 seriesList := make([]*series, len(seriesIDs))
198 for j, key := range keys {
199 seriesList[j] = i.series[string(key)]
200 }
201 i.mu.RUnlock()
202
203 var hasNewSeries bool
204 for _, ss := range seriesList {
205 if ss == nil {
206 hasNewSeries = true
207 continue
208 }
209
210 // This series might need to be added to the local bitset, if the series
211 // was created on another shard.
212 seriesIDSet.Lock()
213 if !seriesIDSet.ContainsNoLock(ss.ID) {
214 seriesIDSet.AddNoLock(ss.ID)
215 }
216 seriesIDSet.Unlock()
217 }
218 if !hasNewSeries {
219 return nil
220 }
221
222 // get or create the measurement index
223 mms := make([]*measurement, len(names))
224 for j, name := range names {
225 mms[j] = i.CreateMeasurementIndexIfNotExists(name)
226 }
227
228 i.mu.Lock()
229 defer i.mu.Unlock()
230
231 // Check for the series again under a write lock
232 var newSeriesN int
233 for j, key := range keys {
234 if seriesList[j] != nil {
235 continue
236 }
237
238 ss := i.series[string(key)]
239 if ss == nil {
240 newSeriesN++
241 continue
242 }
243 seriesList[j] = ss
244
245 // This series might need to be added to the local bitset, if the series
246 // was created on another shard.
247 seriesIDSet.Lock()
248 if !seriesIDSet.ContainsNoLock(ss.ID) {
249 seriesIDSet.AddNoLock(ss.ID)
250 }
251 seriesIDSet.Unlock()
252 }
253 if newSeriesN == 0 {
254 return nil
255 }
256
257 // Verify that the series will not exceed limit.
258 if !ignoreLimits {
259 if max := opt.Config.MaxSeriesPerDatabase; max > 0 && len(i.series)+len(keys) > max {
260 return errMaxSeriesPerDatabaseExceeded{limit: opt.Config.MaxSeriesPerDatabase}
261 }
262 }
263
264 for j, key := range keys {
265 if seriesList[j] != nil {
266 continue
267 }
268
269 // set the in memory ID for query processing on this shard
270 // The series key and tags are clone to prevent a memory leak
271 skey := string(key)
272 ss := newSeries(seriesIDs[j], mms[j], skey, tagsSlice[j].Clone())
273 i.series[skey] = ss
274
275 mms[j].AddSeries(ss)
276
277 // Add the series to the series sketch.
278 i.seriesSketch.Add(key)
279
280 // This series needs to be added to the bitset tracking undeleted series IDs.
281 seriesIDSet.Add(seriesIDs[j])
282 }
283
284 return nil
285 }
286
287 // CreateMeasurementIndexIfNotExists creates or retrieves an in memory index
288 // object for the measurement
289 func (i *Index) CreateMeasurementIndexIfNotExists(name []byte) *measurement {
290 name = escape.Unescape(name)
291
292 // See if the measurement exists using a read-lock
293 i.mu.RLock()
294 m := i.measurements[string(name)]
295 if m != nil {
296 i.mu.RUnlock()
297 return m
298 }
299 i.mu.RUnlock()
300
301 // Doesn't exist, so lock the index to create it
302 i.mu.Lock()
303 defer i.mu.Unlock()
304
305 // Make sure it was created in between the time we released our read-lock
306 // and acquire the write lock
307 m = i.measurements[string(name)]
308 if m == nil {
309 m = newMeasurement(i.database, string(name))
310 i.measurements[string(name)] = m
311
312 // Add the measurement to the measurements sketch.
313 i.measurementsSketch.Add([]byte(name))
314 }
315 return m
316 }
317
318 // HasTagKey returns true if tag key exists.
319 func (i *Index) HasTagKey(name, key []byte) (bool, error) {
320 i.mu.RLock()
321 mm := i.measurements[string(name)]
322 i.mu.RUnlock()
323
324 if mm == nil {
325 return false, nil
326 }
327 return mm.HasTagKey(string(key)), nil
328 }
329
330 // HasTagValue returns true if tag value exists.
331 func (i *Index) HasTagValue(name, key, value []byte) (bool, error) {
332 i.mu.RLock()
333 mm := i.measurements[string(name)]
334 i.mu.RUnlock()
335
336 if mm == nil {
337 return false, nil
338 }
339 return mm.HasTagKeyValue(key, value), nil
340 }
341
342 // TagValueN returns the cardinality of a tag value.
343 func (i *Index) TagValueN(name, key []byte) int {
344 i.mu.RLock()
345 mm := i.measurements[string(name)]
346 i.mu.RUnlock()
347
348 if mm == nil {
349 return 0
350 }
351 return mm.CardinalityBytes(key)
352 }
353
354 // MeasurementTagKeysByExpr returns an ordered set of tag keys filtered by an expression.
355 func (i *Index) MeasurementTagKeysByExpr(name []byte, expr influxql.Expr) (map[string]struct{}, error) {
356 i.mu.RLock()
357 mm := i.measurements[string(name)]
358 i.mu.RUnlock()
359
360 if mm == nil {
361 return nil, nil
362 }
363 return mm.TagKeysByExpr(expr)
364 }
365
366 // TagKeyHasAuthorizedSeries determines if there exists an authorized series for
367 // the provided measurement name and tag key.
368 func (i *Index) TagKeyHasAuthorizedSeries(auth query.Authorizer, name []byte, key string) bool {
369 i.mu.RLock()
370 mm := i.measurements[string(name)]
371 i.mu.RUnlock()
372
373 if mm == nil {
374 return false
375 }
376
377 // TODO(edd): This looks like it's inefficient. Since a series can have multiple
378 // tag key/value pairs on it, it's possible that the same unauthorised series
379 // will be checked multiple times. It would be more efficient if it were
380 // possible to get the set of unique series IDs for a given measurement name
381 // and tag key.
382 var authorized bool
383 mm.SeriesByTagKeyValue(key).Range(func(_ string, sIDs seriesIDs) bool {
384 if query.AuthorizerIsOpen(auth) {
385 authorized = true
386 return false
387 }
388
389 for _, id := range sIDs {
390 s := mm.SeriesByID(id)
391 if s == nil {
392 continue
393 }
394
395 if auth.AuthorizeSeriesRead(i.database, mm.NameBytes, s.Tags) {
396 authorized = true
397 return false
398 }
399 }
400
401 // This tag key/value combination doesn't have any authorised series, so
402 // keep checking other tag values.
403 return true
404 })
405 return authorized
406 }
407
408 // MeasurementTagKeyValuesByExpr returns a set of tag values filtered by an expression.
409 //
410 // See tsm1.Engine.MeasurementTagKeyValuesByExpr for a fuller description of this
411 // method.
412 func (i *Index) MeasurementTagKeyValuesByExpr(auth query.Authorizer, name []byte, keys []string, expr influxql.Expr, keysSorted bool) ([][]string, error) {
413 i.mu.RLock()
414 mm := i.measurements[string(name)]
415 i.mu.RUnlock()
416
417 if mm == nil || len(keys) == 0 {
418 return nil, nil
419 }
420
421 results := make([][]string, len(keys))
422
423 // If we haven't been provided sorted keys, then we need to sort them.
424 if !keysSorted {
425 sort.Strings(keys)
426 }
427
428 ids, _, _ := mm.WalkWhereForSeriesIds(expr)
429 if ids.Len() == 0 && expr == nil {
430 for ki, key := range keys {
431 values := mm.TagValues(auth, key)
432 sort.Strings(values)
433 results[ki] = values
434 }
435 return results, nil
436 }
437
438 // This is the case where we have filtered series by some WHERE condition.
439 // We only care about the tag values for the keys given the
440 // filtered set of series ids.
441
442 keyIdxs := make(map[string]int, len(keys))
443 for ki, key := range keys {
444 keyIdxs[key] = ki
445 }
446
447 resultSet := make([]stringSet, len(keys))
448 for i := 0; i < len(resultSet); i++ {
449 resultSet[i] = newStringSet()
450 }
451
452 // Iterate all series to collect tag values.
453 for _, id := range ids {
454 s := mm.SeriesByID(id)
455 if s == nil {
456 continue
457 }
458 if auth != nil && !auth.AuthorizeSeriesRead(i.database, s.Measurement.NameBytes, s.Tags) {
459 continue
460 }
461
462 // Iterate the tag keys we're interested in and collect values
463 // from this series, if they exist.
464 for _, t := range s.Tags {
465 if idx, ok := keyIdxs[string(t.Key)]; ok {
466 resultSet[idx].add(string(t.Value))
467 } else if string(t.Key) > keys[len(keys)-1] {
468 // The tag key is > the largest key we're interested in.
469 break
470 }
471 }
472 }
473 for i, s := range resultSet {
474 results[i] = s.list()
475 }
476 return results, nil
477 }
478
479 // ForEachMeasurementTagKey iterates over all tag keys for a measurement.
480 func (i *Index) ForEachMeasurementTagKey(name []byte, fn func(key []byte) error) error {
481 // Ensure we do not hold a lock on the index while fn executes in case fn tries
482 // to acquire a lock on the index again. If another goroutine has Lock, this will
483 // deadlock.
484 i.mu.RLock()
485 mm := i.measurements[string(name)]
486 i.mu.RUnlock()
487
488 if mm == nil {
489 return nil
490 }
491
492 for _, key := range mm.TagKeys() {
493 if err := fn([]byte(key)); err != nil {
494 return err
495 }
496 }
497
498 return nil
499 }
500
501 // TagKeyCardinality returns the number of values for a measurement/tag key.
502 func (i *Index) TagKeyCardinality(name, key []byte) int {
503 i.mu.RLock()
504 mm := i.measurements[string(name)]
505 i.mu.RUnlock()
506
507 if mm == nil {
508 return 0
509 }
510 return mm.CardinalityBytes(key)
511 }
512
513 // TagsForSeries returns the tag map for the passed in series
514 func (i *Index) TagsForSeries(key string) (models.Tags, error) {
515 i.mu.RLock()
516 ss := i.series[key]
517 i.mu.RUnlock()
518
519 if ss == nil {
520 return nil, nil
521 }
522 return ss.Tags, nil
523 }
524
525 // MeasurementNamesByExpr takes an expression containing only tags and returns a
526 // list of matching measurement names.
527 //
528 // TODO(edd): Remove authorisation from these methods. There shouldn't need to
529 // be any auth passed down into the index.
530 func (i *Index) MeasurementNamesByExpr(auth query.Authorizer, expr influxql.Expr) ([][]byte, error) {
531 i.mu.RLock()
532 defer i.mu.RUnlock()
533
534 // Return all measurement names if no expression is provided.
535 if expr == nil {
536 a := make([][]byte, 0, len(i.measurements))
537 for _, m := range i.measurements {
538 if m.Authorized(auth) {
539 a = append(a, m.NameBytes)
540 }
541 }
542 bytesutil.Sort(a)
543 return a, nil
544 }
545
546 return i.measurementNamesByExpr(auth, expr)
547 }
548
549 func (i *Index) measurementNamesByExpr(auth query.Authorizer, expr influxql.Expr) ([][]byte, error) {
550 if expr == nil {
551 return nil, nil
552 }
553
554 switch e := expr.(type) {
555 case *influxql.BinaryExpr:
556 switch e.Op {
557 case influxql.EQ, influxql.NEQ, influxql.EQREGEX, influxql.NEQREGEX:
558 tag, ok := e.LHS.(*influxql.VarRef)
559 if !ok {
560 return nil, fmt.Errorf("left side of '%s' must be a tag key", e.Op.String())
561 }
562
563 tf := &TagFilter{
564 Op: e.Op,
565 Key: tag.Val,
566 }
567
568 if influxql.IsRegexOp(e.Op) {
569 re, ok := e.RHS.(*influxql.RegexLiteral)
570 if !ok {
571 return nil, fmt.Errorf("right side of '%s' must be a regular expression", e.Op.String())
572 }
573 tf.Regex = re.Val
574 } else {
575 s, ok := e.RHS.(*influxql.StringLiteral)
576 if !ok {
577 return nil, fmt.Errorf("right side of '%s' must be a tag value string", e.Op.String())
578 }
579 tf.Value = s.Val
580 }
581
582 // Match on name, if specified.
583 if tag.Val == "_name" {
584 return i.measurementNamesByNameFilter(auth, tf.Op, tf.Value, tf.Regex), nil
585 } else if influxql.IsSystemName(tag.Val) {
586 return nil, nil
587 }
588
589 return i.measurementNamesByTagFilters(auth, tf), nil
590 case influxql.OR, influxql.AND:
591 lhs, err := i.measurementNamesByExpr(auth, e.LHS)
592 if err != nil {
593 return nil, err
594 }
595
596 rhs, err := i.measurementNamesByExpr(auth, e.RHS)
597 if err != nil {
598 return nil, err
599 }
600
601 if e.Op == influxql.OR {
602 return bytesutil.Union(lhs, rhs), nil
603 }
604 return bytesutil.Intersect(lhs, rhs), nil
605 default:
606 return nil, fmt.Errorf("invalid tag comparison operator")
607 }
608 case *influxql.ParenExpr:
609 return i.measurementNamesByExpr(auth, e.Expr)
610 }
611 return nil, fmt.Errorf("%#v", expr)
612 }
613
614 // measurementNamesByNameFilter returns the sorted measurements matching a name.
615 func (i *Index) measurementNamesByNameFilter(auth query.Authorizer, op influxql.Token, val string, regex *regexp.Regexp) [][]byte {
616 var names [][]byte
617 for _, m := range i.measurements {
618 var matched bool
619 switch op {
620 case influxql.EQ:
621 matched = m.Name == val
622 case influxql.NEQ:
623 matched = m.Name != val
624 case influxql.EQREGEX:
625 matched = regex.MatchString(m.Name)
626 case influxql.NEQREGEX:
627 matched = !regex.MatchString(m.Name)
628 }
629
630 if matched && m.Authorized(auth) {
631 names = append(names, m.NameBytes)
632 }
633 }
634 bytesutil.Sort(names)
635 return names
636 }
637
638 // measurementNamesByTagFilters returns the sorted measurements matching the filters on tag values.
639 func (i *Index) measurementNamesByTagFilters(auth query.Authorizer, filter *TagFilter) [][]byte {
640 // Build a list of measurements matching the filters.
641 var names [][]byte
642 var tagMatch bool
643 var authorized bool
644
645 valEqual := filter.Regex.MatchString
646 if filter.Op == influxql.EQ || filter.Op == influxql.NEQ {
647 valEqual = func(s string) bool { return filter.Value == s }
648 }
649
650 // Iterate through all measurements in the database.
651 for _, m := range i.measurements {
652 tagVals := m.SeriesByTagKeyValue(filter.Key)
653 if tagVals == nil {
654 continue
655 }
656
657 tagMatch = false
658 // Authorization must be explicitly granted when an authorizer is present.
659 authorized = query.AuthorizerIsOpen(auth)
660
661 // Check the tag values belonging to the tag key for equivalence to the
662 // tag value being filtered on.
663 tagVals.Range(func(tv string, seriesIDs seriesIDs) bool {
664 if !valEqual(tv) {
665 return true // No match. Keep checking.
666 }
667
668 tagMatch = true
669 if query.AuthorizerIsOpen(auth) {
670 return false // No need to continue checking series, there is a match.
671 }
672
673 // Is there a series with this matching tag value that is
674 // authorized to be read?
675 for _, sid := range seriesIDs {
676 s := m.SeriesByID(sid)
677
678 // If the series is deleted then it can't be used to authorise against.
679 if s != nil && s.Deleted() {
680 continue
681 }
682
683 if s != nil && auth.AuthorizeSeriesRead(i.database, m.NameBytes, s.Tags) {
684 // The Range call can return early as a matching
685 // tag value with an authorized series has been found.
686 authorized = true
687 return false
688 }
689 }
690
691 // The matching tag value doesn't have any authorized series.
692 // Check for other matching tag values if this is a regex check.
693 return filter.Op == influxql.EQREGEX
694 })
695
696 // For negation operators, to determine if the measurement is authorized,
697 // an authorized series belonging to the measurement must be located.
698 // Then, the measurement can be added iff !tagMatch && authorized.
699 if auth != nil && !tagMatch && (filter.Op == influxql.NEQREGEX || filter.Op == influxql.NEQ) {
700 authorized = m.Authorized(auth)
701 }
702
703 // tags match | operation is EQ | measurement matches
704 // --------------------------------------------------
705 // True | True | True
706 // True | False | False
707 // False | True | False
708 // False | False | True
709 if tagMatch == (filter.Op == influxql.EQ || filter.Op == influxql.EQREGEX) && authorized {
710 names = append(names, m.NameBytes)
711 }
712 }
713
714 bytesutil.Sort(names)
715 return names
716 }
717
718 // MeasurementNamesByRegex returns the measurements that match the regex.
719 func (i *Index) MeasurementNamesByRegex(re *regexp.Regexp) ([][]byte, error) {
720 i.mu.RLock()
721 defer i.mu.RUnlock()
722
723 var matches [][]byte
724 for _, m := range i.measurements {
725 if re.MatchString(m.Name) {
726 matches = append(matches, m.NameBytes)
727 }
728 }
729 return matches, nil
730 }
731
732 // DropMeasurement removes the measurement and all of its underlying
733 // series from the database index
734 func (i *Index) DropMeasurement(name []byte) error {
735 i.mu.Lock()
736 defer i.mu.Unlock()
737 return i.dropMeasurement(string(name))
738 }
739
740 func (i *Index) dropMeasurement(name string) error {
741 // Update the tombstone sketch.
742 i.measurementsTSSketch.Add([]byte(name))
743
744 m := i.measurements[name]
745 if m == nil {
746 return nil
747 }
748
749 delete(i.measurements, name)
750 for _, s := range m.SeriesByIDMap() {
751 delete(i.series, s.Key)
752 i.seriesTSSketch.Add([]byte(s.Key))
753 }
754 return nil
755 }
756
757 // DropMeasurementIfSeriesNotExist drops a measurement only if there are no more
758 // series for the measurment.
759 func (i *Index) DropMeasurementIfSeriesNotExist(name []byte) error {
760 i.mu.Lock()
761 defer i.mu.Unlock()
762
763 m := i.measurements[string(name)]
764 if m == nil {
765 return nil
766 }
767
768 if m.HasSeries() {
769 return nil
770 }
771
772 return i.dropMeasurement(string(name))
773 }
774
775 // DropSeriesGlobal removes the series key and its tags from the index.
776 func (i *Index) DropSeriesGlobal(key []byte) error {
777 if key == nil {
778 return nil
779 }
780
781 i.mu.Lock()
782 defer i.mu.Unlock()
783
784 k := string(key)
785 series := i.series[k]
786 if series == nil {
787 return nil
788 }
789
790 // Update the tombstone sketch.
791 i.seriesTSSketch.Add([]byte(k))
792
793 // Remove from the index.
794 delete(i.series, k)
795
796 // Remove the measurement's reference.
797 series.Measurement.DropSeries(series)
798 // Mark the series as deleted.
799 series.Delete()
800
801 // If the measurement no longer has any series, remove it as well.
802 if !series.Measurement.HasSeries() {
803 i.dropMeasurement(series.Measurement.Name)
804 }
805
806 return nil
807 }
808
809 // TagSets returns a list of tag sets.
810 func (i *Index) TagSets(shardSeriesIDs *tsdb.SeriesIDSet, name []byte, opt query.IteratorOptions) ([]*query.TagSet, error) {
811 i.mu.RLock()
812 defer i.mu.RUnlock()
813
814 mm := i.measurements[string(name)]
815 if mm == nil {
816 return nil, nil
817 }
818
819 tagSets, err := mm.TagSets(shardSeriesIDs, opt)
820 if err != nil {
821 return nil, err
822 }
823
824 return tagSets, nil
825 }
826
827 func (i *Index) SeriesKeys() []string {
828 i.mu.RLock()
829 s := make([]string, 0, len(i.series))
830 for k := range i.series {
831 s = append(s, k)
832 }
833 i.mu.RUnlock()
834 return s
835
836 }
837
838 // SetFieldSet sets a shared field set from the engine.
839 func (i *Index) SetFieldSet(fieldset *tsdb.MeasurementFieldSet) {
840 i.mu.Lock()
841 defer i.mu.Unlock()
842 i.fieldset = fieldset
843 }
844
845 // FieldSet returns the assigned fieldset.
846 func (i *Index) FieldSet() *tsdb.MeasurementFieldSet {
847 i.mu.RLock()
848 defer i.mu.RUnlock()
849 return i.fieldset
850 }
851
852 // SetFieldName adds a field name to a measurement.
853 func (i *Index) SetFieldName(measurement []byte, name string) {
854 m := i.CreateMeasurementIndexIfNotExists(measurement)
855 m.SetFieldName(name)
856 }
857
858 // ForEachMeasurementName iterates over each measurement name.
859 func (i *Index) ForEachMeasurementName(fn func(name []byte) error) error {
860 i.mu.RLock()
861 mms := make(measurements, 0, len(i.measurements))
862 for _, m := range i.measurements {
863 mms = append(mms, m)
864 }
865 sort.Sort(mms)
866 i.mu.RUnlock()
867
868 for _, m := range mms {
869 if err := fn(m.NameBytes); err != nil {
870 return err
871 }
872 }
873 return nil
874 }
875
876 func (i *Index) MeasurementSeriesIDIterator(name []byte) (tsdb.SeriesIDIterator, error) {
877 return i.MeasurementSeriesKeysByExprIterator(name, nil)
878 }
879
880 func (i *Index) TagKeySeriesIDIterator(name, key []byte) (tsdb.SeriesIDIterator, error) {
881 i.mu.RLock()
882 defer i.mu.RUnlock()
883
884 m := i.measurements[string(name)]
885 if m == nil {
886 return nil, nil
887 }
888 return tsdb.NewSeriesIDSliceIterator([]uint64(m.SeriesIDsByTagKey(key))), nil
889 }
890
891 func (i *Index) TagValueSeriesIDIterator(name, key, value []byte) (tsdb.SeriesIDIterator, error) {
892 i.mu.RLock()
893 defer i.mu.RUnlock()
894
895 m := i.measurements[string(name)]
896 if m == nil {
897 return nil, nil
898 }
899 return tsdb.NewSeriesIDSliceIterator([]uint64(m.SeriesIDsByTagValue(key, value))), nil
900 }
901
902 func (i *Index) TagKeyIterator(name []byte) (tsdb.TagKeyIterator, error) {
903 i.mu.RLock()
904 defer i.mu.RUnlock()
905
906 m := i.measurements[string(name)]
907 if m == nil {
908 return nil, nil
909 }
910 keys := m.TagKeys()
911 sort.Strings(keys)
912
913 a := make([][]byte, len(keys))
914 for i := range a {
915 a[i] = []byte(keys[i])
916 }
917 return tsdb.NewTagKeySliceIterator(a), nil
918 }
919
920 // TagValueIterator provides an iterator over all the tag values belonging to
921 // series with the provided measurement name and tag key.
922 //
923 // TagValueIterator does not currently support authorization.
924 func (i *Index) TagValueIterator(name, key []byte) (tsdb.TagValueIterator, error) {
925 i.mu.RLock()
926 defer i.mu.RUnlock()
927
928 m := i.measurements[string(name)]
929 if m == nil {
930 return nil, nil
931 }
932 values := m.TagValues(nil, string(key))
933 sort.Strings(values)
934
935 a := make([][]byte, len(values))
936 for i := range a {
937 a[i] = []byte(values[i])
938 }
939 return tsdb.NewTagValueSliceIterator(a), nil
940 }
941
942 func (i *Index) MeasurementSeriesKeysByExprIterator(name []byte, condition influxql.Expr) (tsdb.SeriesIDIterator, error) {
943 i.mu.RLock()
944 defer i.mu.RUnlock()
945
946 m := i.measurements[string(name)]
947 if m == nil {
948 return nil, nil
949 }
950
951 // Return all series if no condition specified.
952 if condition == nil {
953 return tsdb.NewSeriesIDSliceIterator([]uint64(m.SeriesIDs())), nil
954 }
955
956 // Get series IDs that match the WHERE clause.
957 ids, filters, err := m.WalkWhereForSeriesIds(condition)
958 if err != nil {
959 return nil, err
960 }
961
962 // Delete boolean literal true filter expressions.
963 // These are returned for `WHERE tagKey = 'tagVal'` type expressions and are okay.
964 filters.DeleteBoolLiteralTrues()
965
966 // Check for unsupported field filters.
967 // Any remaining filters means there were fields (e.g., `WHERE value = 1.2`).
968 if filters.Len() > 0 {
969 return nil, errors.New("fields not supported in WHERE clause during deletion")
970 }
971
972 return tsdb.NewSeriesIDSliceIterator([]uint64(ids)), nil
973 }
974
975 func (i *Index) MeasurementSeriesKeysByExpr(name []byte, condition influxql.Expr) ([][]byte, error) {
976 i.mu.RLock()
977 defer i.mu.RUnlock()
978
979 m := i.measurements[string(name)]
980 if m == nil {
981 return nil, nil
982 }
983
984 // Return all series if no condition specified.
985 if condition == nil {
986 return m.SeriesKeys(), nil
987 }
988
989 // Get series IDs that match the WHERE clause.
990 ids, filters, err := m.WalkWhereForSeriesIds(condition)
991 if err != nil {
992 return nil, err
993 }
994
995 // Delete boolean literal true filter expressions.
996 // These are returned for `WHERE tagKey = 'tagVal'` type expressions and are okay.
997 filters.DeleteBoolLiteralTrues()
998
999 // Check for unsupported field filters.
1000 // Any remaining filters means there were fields (e.g., `WHERE value = 1.2`).
1001 if filters.Len() > 0 {
1002 return nil, errors.New("fields not supported in WHERE clause during deletion")
1003 }
1004
1005 return m.SeriesKeysByID(ids), nil
1006 }
1007
1008 // SeriesIDIterator returns an influxql iterator over matching series ids.
1009 func (i *Index) SeriesIDIterator(opt query.IteratorOptions) (tsdb.SeriesIDIterator, error) {
1010 i.mu.RLock()
1011 defer i.mu.RUnlock()
1012
1013 // Read and sort all measurements.
1014 mms := make(measurements, 0, len(i.measurements))
1015 for _, mm := range i.measurements {
1016 mms = append(mms, mm)
1017 }
1018 sort.Sort(mms)
1019
1020 return &seriesIDIterator{
1021 database: i.database,
1022 mms: mms,
1023 opt: opt,
1024 }, nil
1025 }
1026
1027 // DiskSizeBytes always returns zero bytes, since this is an in-memory index.
1028 func (i *Index) DiskSizeBytes() int64 { return 0 }
1029
1030 // Rebuild recreates the measurement indexes to allow deleted series to be removed
1031 // and garbage collected.
1032 func (i *Index) Rebuild() {
1033 // Only allow one rebuild at a time. This will cause all subsequent rebuilds
1034 // to queue. The measurement rebuild is idempotent and will not be rebuilt if
1035 // it does not need to be.
1036 i.rebuildQueue.Lock()
1037 defer i.rebuildQueue.Unlock()
1038
1039 i.ForEachMeasurementName(func(name []byte) error {
1040 // Measurement never returns an error
1041 m, _ := i.Measurement(name)
1042 if m == nil {
1043 return nil
1044 }
1045
1046 i.mu.Lock()
1047 nm := m.Rebuild()
1048
1049 i.measurements[string(name)] = nm
1050 i.mu.Unlock()
1051 return nil
1052 })
1053 }
1054
1055 // assignExistingSeries assigns the existing series to shardID and returns the series, names and tags that
1056 // do not exists yet.
1057 func (i *Index) assignExistingSeries(shardID uint64, seriesIDSet *tsdb.SeriesIDSet, keys, names [][]byte, tagsSlice []models.Tags) ([][]byte, [][]byte, []models.Tags) {
1058 i.mu.RLock()
1059 var n int
1060 for j, key := range keys {
1061 if ss := i.series[string(key)]; ss == nil {
1062 keys[n] = keys[j]
1063 names[n] = names[j]
1064 tagsSlice[n] = tagsSlice[j]
1065 n++
1066 } else {
1067 // Add the existing series to this shard's bitset, since this may
1068 // be the first time the series is added to this shard.
1069 if !seriesIDSet.Contains(ss.ID) {
1070 seriesIDSet.Lock()
1071 if !seriesIDSet.ContainsNoLock(ss.ID) {
1072 seriesIDSet.AddNoLock(ss.ID)
1073 }
1074 seriesIDSet.Unlock()
1075 }
1076 }
1077 }
1078 i.mu.RUnlock()
1079 return keys[:n], names[:n], tagsSlice[:n]
1080 }
1081
1082 // Ensure index implements interface.
1083 var _ tsdb.Index = &ShardIndex{}
1084
1085 // ShardIndex represents a shim between the TSDB index interface and the shared
1086 // in-memory index. This is required because per-shard in-memory indexes will
1087 // grow the heap size too large.
1088 type ShardIndex struct {
1089 id uint64 // shard id
1090
1091 *Index // Shared reference to global database-wide index.
1092
1093 // Bitset storing all undeleted series IDs associated with this shard.
1094 seriesIDSet *tsdb.SeriesIDSet
1095
1096 opt tsdb.EngineOptions
1097 }
1098
1099 // DropSeries removes the provided series id from the local bitset that tracks
1100 // series in this shard only.
1101 func (idx *ShardIndex) DropSeries(seriesID uint64, _ []byte, _ bool) error {
1102 // Remove from shard-local bitset if it exists.
1103 idx.seriesIDSet.Lock()
1104 if idx.seriesIDSet.ContainsNoLock(seriesID) {
1105 idx.seriesIDSet.RemoveNoLock(seriesID)
1106 }
1107 idx.seriesIDSet.Unlock()
1108 return nil
1109 }
1110
1111 // DropMeasurementIfSeriesNotExist drops a measurement only if there are no more
1112 // series for the measurment.
1113 func (idx *ShardIndex) DropMeasurementIfSeriesNotExist(name []byte) error {
1114 return idx.Index.DropMeasurementIfSeriesNotExist(name)
1115 }
1116
1117 // CreateSeriesListIfNotExists creates a list of series if they doesn't exist in bulk.
1118 func (idx *ShardIndex) CreateSeriesListIfNotExists(keys, names [][]byte, tagsSlice []models.Tags) error {
1119 keys, names, tagsSlice = idx.assignExistingSeries(idx.id, idx.seriesIDSet, keys, names, tagsSlice)
1120 if len(keys) == 0 {
1121 return nil
1122 }
1123
1124 var (
1125 reason string
1126 droppedKeys [][]byte
1127 )
1128
1129 // Ensure that no tags go over the maximum cardinality.
1130 if maxValuesPerTag := idx.opt.Config.MaxValuesPerTag; maxValuesPerTag > 0 {
1131 var n int
1132
1133 outer:
1134 for i, name := range names {
1135 tags := tagsSlice[i]
1136 for _, tag := range tags {
1137 // Skip if the tag value already exists.
1138 if ok, _ := idx.HasTagValue(name, tag.Key, tag.Value); ok {
1139 continue
1140 }
1141
1142 // Read cardinality. Skip if we're below the threshold.
1143 n := idx.TagValueN(name, tag.Key)
1144 if n < maxValuesPerTag {
1145 continue
1146 }
1147
1148 if reason == "" {
1149 reason = fmt.Sprintf("max-values-per-tag limit exceeded (%d/%d): measurement=%q tag=%q value=%q",
1150 n, maxValuesPerTag, name, string(tag.Key), string(tag.Value))
1151 }
1152
1153 droppedKeys = append(droppedKeys, keys[i])
1154 continue outer
1155 }
1156
1157 // Increment success count if all checks complete.
1158 if n != i {
1159 keys[n], names[n], tagsSlice[n] = keys[i], names[i], tagsSlice[i]
1160 }
1161 n++
1162 }
1163
1164 // Slice to only include successful points.
1165 keys, names, tagsSlice = keys[:n], names[:n], tagsSlice[:n]
1166 }
1167
1168 if err := idx.Index.CreateSeriesListIfNotExists(idx.seriesIDSet, keys, names, tagsSlice, &idx.opt, idx.opt.Config.MaxSeriesPerDatabase == 0); err != nil {
1169 reason = err.Error()
1170 droppedKeys = append(droppedKeys, keys...)
1171 }
1172
1173 // Report partial writes back to shard.
1174 if len(droppedKeys) > 0 {
1175 dropped := len(droppedKeys) // number dropped before deduping
1176 bytesutil.SortDedup(droppedKeys)
1177 return &tsdb.PartialWriteError{
1178 Reason: reason,
1179 Dropped: dropped,
1180 DroppedKeys: droppedKeys,
1181 }
1182 }
1183
1184 return nil
1185 }
1186
1187 // SeriesN returns the number of unique non-tombstoned series local to this shard.
1188 func (idx *ShardIndex) SeriesN() int64 {
1189 idx.mu.RLock()
1190 defer idx.mu.RUnlock()
1191 return int64(idx.seriesIDSet.Cardinality())
1192 }
1193
1194 // InitializeSeries is called during start-up.
1195 // This works the same as CreateSeriesListIfNotExists except it ignore limit errors.
1196 func (idx *ShardIndex) InitializeSeries(keys, names [][]byte, tags []models.Tags) error {
1197 return idx.Index.CreateSeriesListIfNotExists(idx.seriesIDSet, keys, names, tags, &idx.opt, true)
1198 }
1199
1200 // CreateSeriesIfNotExists creates the provided series on the index if it is not
1201 // already present.
1202 func (idx *ShardIndex) CreateSeriesIfNotExists(key, name []byte, tags models.Tags) error {
1203 return idx.Index.CreateSeriesListIfNotExists(idx.seriesIDSet, [][]byte{key}, [][]byte{name}, []models.Tags{tags}, &idx.opt, false)
1204 }
1205
1206 // TagSets returns a list of tag sets based on series filtering.
1207 func (idx *ShardIndex) TagSets(name []byte, opt query.IteratorOptions) ([]*query.TagSet, error) {
1208 return idx.Index.TagSets(idx.seriesIDSet, name, opt)
1209 }
1210
1211 // SeriesIDSet returns the bitset associated with the series ids.
1212 func (idx *ShardIndex) SeriesIDSet() *tsdb.SeriesIDSet {
1213 return idx.seriesIDSet
1214 }
1215
1216 // NewShardIndex returns a new index for a shard.
1217 func NewShardIndex(id uint64, seriesIDSet *tsdb.SeriesIDSet, opt tsdb.EngineOptions) tsdb.Index {
1218 return &ShardIndex{
1219 Index: opt.InmemIndex.(*Index),
1220 id: id,
1221 seriesIDSet: seriesIDSet,
1222 opt: opt,
1223 }
1224 }
1225
1226 // seriesIDIterator emits series ids.
1227 type seriesIDIterator struct {
1228 database string
1229 mms measurements
1230 keys struct {
1231 buf []*series
1232 i int
1233 }
1234 opt query.IteratorOptions
1235 }
1236
1237 // Stats returns stats about the points processed.
1238 func (itr *seriesIDIterator) Stats() query.IteratorStats { return query.IteratorStats{} }
1239
1240 // Close closes the iterator.
1241 func (itr *seriesIDIterator) Close() error { return nil }
1242
1243 // Next emits the next point in the iterator.
1244 func (itr *seriesIDIterator) Next() (tsdb.SeriesIDElem, error) {
1245 for {
1246 // Load next measurement's keys if there are no more remaining.
1247 if itr.keys.i >= len(itr.keys.buf) {
1248 if err := itr.nextKeys(); err != nil {
1249 return tsdb.SeriesIDElem{}, err
1250 }
1251 if len(itr.keys.buf) == 0 {
1252 return tsdb.SeriesIDElem{}, nil
1253 }
1254 }
1255
1256 // Read the next key.
1257 series := itr.keys.buf[itr.keys.i]
1258 itr.keys.i++
1259
1260 if !itr.opt.Authorizer.AuthorizeSeriesRead(itr.database, series.Measurement.NameBytes, series.Tags) {
1261 continue
1262 }
1263
1264 return tsdb.SeriesIDElem{SeriesID: series.ID}, nil
1265 }
1266 }
1267
1268 // nextKeys reads all keys for the next measurement.
1269 func (itr *seriesIDIterator) nextKeys() error {
1270 for {
1271 // Ensure previous keys are cleared out.
1272 itr.keys.i, itr.keys.buf = 0, itr.keys.buf[:0]
1273
1274 // Read next measurement.
1275 if len(itr.mms) == 0 {
1276 return nil
1277 }
1278 mm := itr.mms[0]
1279 itr.mms = itr.mms[1:]
1280
1281 // Read all series keys.
1282 ids, err := mm.SeriesIDsAllOrByExpr(itr.opt.Condition)
1283 if err != nil {
1284 return err
1285 } else if len(ids) == 0 {
1286 continue
1287 }
1288 itr.keys.buf = mm.SeriesByIDSlice(ids)
1289
1290 // Sort series by key
1291 sort.Slice(itr.keys.buf, func(i, j int) bool {
1292 return itr.keys.buf[i].Key < itr.keys.buf[j].Key
1293 })
1294
1295 return nil
1296 }
1297 }
1298
1299 // errMaxSeriesPerDatabaseExceeded is a marker error returned during series creation
1300 // to indicate that a new series would exceed the limits of the database.
1301 type errMaxSeriesPerDatabaseExceeded struct {
1302 limit int
1303 }
1304
1305 func (e errMaxSeriesPerDatabaseExceeded) Error() string {
1306 return fmt.Sprintf("max-series-per-database limit exceeded: (%d)", e.limit)
1307 }