Debian Codegraph @

tsdb/index/tsi1/log_file.go

raw
1 package tsi1
2
3 import (
4 "bufio"
5 "bytes"
6 "encoding/binary"
7 "errors"
8 "fmt"
9 "hash/crc32"
10 "io"
11 "os"
12 "sort"
13 "sync"
14 "time"
15 "unsafe"
16
17 "github.com/influxdata/influxdb/models"
18 "github.com/influxdata/influxdb/pkg/bloom"
19 "github.com/influxdata/influxdb/pkg/estimator"
20 "github.com/influxdata/influxdb/pkg/estimator/hll"
21 "github.com/influxdata/influxdb/pkg/mmap"
22 "github.com/influxdata/influxdb/tsdb"
23 )
24
25 // Log errors.
26 var (
27 ErrLogEntryChecksumMismatch = errors.New("log entry checksum mismatch")
28 )
29
30 // Log entry flag constants.
31 const (
32 LogEntrySeriesTombstoneFlag = 0x01
33 LogEntryMeasurementTombstoneFlag = 0x02
34 LogEntryTagKeyTombstoneFlag = 0x04
35 LogEntryTagValueTombstoneFlag = 0x08
36 )
37
38 // defaultLogFileBufferSize describes the size of the buffer that the LogFile's buffered
39 // writer uses. If the LogFile does not have an explicit buffer size set then
40 // this is the size of the buffer; it is equal to the default buffer size used
41 // by a bufio.Writer.
42 const defaultLogFileBufferSize = 4096
43
44 // indexFileBufferSize is the buffer size used when compacting the LogFile down
45 // into a .tsi file.
46 const indexFileBufferSize = 1 << 17 // 128K
47
48 // LogFile represents an on-disk write-ahead log file.
49 type LogFile struct {
50 mu sync.RWMutex
51 wg sync.WaitGroup // ref count
52 id int // file sequence identifier
53 data []byte // mmap
54 file *os.File // writer
55 w *bufio.Writer // buffered writer
56 bufferSize int // The size of the buffer used by the buffered writer
57 nosync bool // Disables buffer flushing and file syncing. Useful for offline tooling.
58 buf []byte // marshaling buffer
59 keyBuf []byte
60
61 sfile *tsdb.SeriesFile // series lookup
62 size int64 // tracks current file size
63 modTime time.Time // tracks last time write occurred
64
65 // In-memory series existence/tombstone sets.
66 seriesIDSet, tombstoneSeriesIDSet *tsdb.SeriesIDSet
67
68 // In-memory index.
69 mms logMeasurements
70
71 // Filepath to the log file.
72 path string
73 }
74
75 // NewLogFile returns a new instance of LogFile.
76 func NewLogFile(sfile *tsdb.SeriesFile, path string) *LogFile {
77 return &LogFile{
78 sfile: sfile,
79 path: path,
80 mms: make(logMeasurements),
81
82 seriesIDSet: tsdb.NewSeriesIDSet(),
83 tombstoneSeriesIDSet: tsdb.NewSeriesIDSet(),
84 }
85 }
86
87 // bytes estimates the memory footprint of this LogFile, in bytes.
88 func (f *LogFile) bytes() int {
89 var b int
90 b += 24 // mu RWMutex is 24 bytes
91 b += 16 // wg WaitGroup is 16 bytes
92 b += int(unsafe.Sizeof(f.id))
93 // Do not include f.data because it is mmap'd
94 // TODO(jacobmarble): Uncomment when we are using go >= 1.10.0
95 //b += int(unsafe.Sizeof(f.w)) + f.w.Size()
96 b += int(unsafe.Sizeof(f.buf)) + len(f.buf)
97 b += int(unsafe.Sizeof(f.keyBuf)) + len(f.keyBuf)
98 // Do not count SeriesFile because it belongs to the code that constructed this Index.
99 b += int(unsafe.Sizeof(f.size))
100 b += int(unsafe.Sizeof(f.modTime))
101 b += int(unsafe.Sizeof(f.seriesIDSet)) + f.seriesIDSet.Bytes()
102 b += int(unsafe.Sizeof(f.tombstoneSeriesIDSet)) + f.tombstoneSeriesIDSet.Bytes()
103 b += int(unsafe.Sizeof(f.mms)) + f.mms.bytes()
104 b += int(unsafe.Sizeof(f.path)) + len(f.path)
105 return b
106 }
107
108 // Open reads the log from a file and validates all the checksums.
109 func (f *LogFile) Open() error {
110 if err := f.open(); err != nil {
111 f.Close()
112 return err
113 }
114 return nil
115 }
116
117 func (f *LogFile) open() error {
118 f.id, _ = ParseFilename(f.path)
119
120 // Open file for appending.
121 file, err := os.OpenFile(f.Path(), os.O_WRONLY|os.O_CREATE, 0666)
122 if err != nil {
123 return err
124 }
125 f.file = file
126
127 if f.bufferSize == 0 {
128 f.bufferSize = defaultLogFileBufferSize
129 }
130 f.w = bufio.NewWriterSize(f.file, f.bufferSize)
131
132 // Finish opening if file is empty.
133 fi, err := file.Stat()
134 if err != nil {
135 return err
136 } else if fi.Size() == 0 {
137 return nil
138 }
139 f.size = fi.Size()
140 f.modTime = fi.ModTime()
141
142 // Open a read-only memory map of the existing data.
143 data, err := mmap.Map(f.Path(), 0)
144 if err != nil {
145 return err
146 }
147 f.data = data
148
149 // Read log entries from mmap.
150 var n int64
151 for buf := f.data; len(buf) > 0; {
152 // Read next entry. Truncate partial writes.
153 var e LogEntry
154 if err := e.UnmarshalBinary(buf); err == io.ErrShortBuffer || err == ErrLogEntryChecksumMismatch {
155 break
156 } else if err != nil {
157 return err
158 }
159
160 // Execute entry against in-memory index.
161 f.execEntry(&e)
162
163 // Move buffer forward.
164 n += int64(e.Size)
165 buf = buf[e.Size:]
166 }
167
168 // Move to the end of the file.
169 f.size = n
170 _, err = file.Seek(n, io.SeekStart)
171 return err
172 }
173
174 // Close shuts down the file handle and mmap.
175 func (f *LogFile) Close() error {
176 // Wait until the file has no more references.
177 f.wg.Wait()
178
179 if f.w != nil {
180 f.w.Flush()
181 f.w = nil
182 }
183
184 if f.file != nil {
185 f.file.Close()
186 f.file = nil
187 }
188
189 if f.data != nil {
190 mmap.Unmap(f.data)
191 }
192
193 f.mms = make(logMeasurements)
194 return nil
195 }
196
197 // FlushAndSync flushes buffered data to disk and then fsyncs the underlying file.
198 // If the LogFile has disabled flushing and syncing then FlushAndSync is a no-op.
199 func (f *LogFile) FlushAndSync() error {
200 if f.nosync {
201 return nil
202 }
203
204 if f.w != nil {
205 if err := f.w.Flush(); err != nil {
206 return err
207 }
208 }
209
210 if f.file == nil {
211 return nil
212 }
213 return f.file.Sync()
214 }
215
216 // ID returns the file sequence identifier.
217 func (f *LogFile) ID() int { return f.id }
218
219 // Path returns the file path.
220 func (f *LogFile) Path() string { return f.path }
221
222 // SetPath sets the log file's path.
223 func (f *LogFile) SetPath(path string) { f.path = path }
224
225 // Level returns the log level of the file.
226 func (f *LogFile) Level() int { return 0 }
227
228 // Filter returns the bloom filter for the file.
229 func (f *LogFile) Filter() *bloom.Filter { return nil }
230
231 // Retain adds a reference count to the file.
232 func (f *LogFile) Retain() { f.wg.Add(1) }
233
234 // Release removes a reference count from the file.
235 func (f *LogFile) Release() { f.wg.Done() }
236
237 // Stat returns size and last modification time of the file.
238 func (f *LogFile) Stat() (int64, time.Time) {
239 f.mu.RLock()
240 size, modTime := f.size, f.modTime
241 f.mu.RUnlock()
242 return size, modTime
243 }
244
245 // SeriesIDSet returns the series existence set.
246 func (f *LogFile) SeriesIDSet() (*tsdb.SeriesIDSet, error) {
247 return f.seriesIDSet, nil
248 }
249
250 // TombstoneSeriesIDSet returns the series tombstone set.
251 func (f *LogFile) TombstoneSeriesIDSet() (*tsdb.SeriesIDSet, error) {
252 return f.tombstoneSeriesIDSet, nil
253 }
254
255 // Size returns the size of the file, in bytes.
256 func (f *LogFile) Size() int64 {
257 f.mu.RLock()
258 v := f.size
259 f.mu.RUnlock()
260 return v
261 }
262
263 // Measurement returns a measurement element.
264 func (f *LogFile) Measurement(name []byte) MeasurementElem {
265 f.mu.RLock()
266 defer f.mu.RUnlock()
267
268 mm, ok := f.mms[string(name)]
269 if !ok {
270 return nil
271 }
272
273 return mm
274 }
275
276 func (f *LogFile) MeasurementHasSeries(ss *tsdb.SeriesIDSet, name []byte) bool {
277 f.mu.RLock()
278 defer f.mu.RUnlock()
279
280 mm, ok := f.mms[string(name)]
281 if !ok {
282 return false
283 }
284
285 // TODO(edd): if mm is using a seriesSet then this could be changed to do a fast intersection.
286 for _, id := range mm.seriesIDs() {
287 if ss.Contains(id) {
288 return true
289 }
290 }
291 return false
292 }
293
294 // MeasurementNames returns an ordered list of measurement names.
295 func (f *LogFile) MeasurementNames() []string {
296 f.mu.RLock()
297 defer f.mu.RUnlock()
298 return f.measurementNames()
299 }
300
301 func (f *LogFile) measurementNames() []string {
302 a := make([]string, 0, len(f.mms))
303 for name := range f.mms {
304 a = append(a, name)
305 }
306 sort.Strings(a)
307 return a
308 }
309
310 // DeleteMeasurement adds a tombstone for a measurement to the log file.
311 func (f *LogFile) DeleteMeasurement(name []byte) error {
312 f.mu.Lock()
313 defer f.mu.Unlock()
314
315 e := LogEntry{Flag: LogEntryMeasurementTombstoneFlag, Name: name}
316 if err := f.appendEntry(&e); err != nil {
317 return err
318 }
319 f.execEntry(&e)
320
321 // Flush buffer and sync to disk.
322 return f.FlushAndSync()
323 }
324
325 // TagKeySeriesIDIterator returns a series iterator for a tag key.
326 func (f *LogFile) TagKeySeriesIDIterator(name, key []byte) tsdb.SeriesIDIterator {
327 f.mu.RLock()
328 defer f.mu.RUnlock()
329
330 mm, ok := f.mms[string(name)]
331 if !ok {
332 return nil
333 }
334
335 tk, ok := mm.tagSet[string(key)]
336 if !ok {
337 return nil
338 }
339
340 // Combine iterators across all tag keys.
341 itrs := make([]tsdb.SeriesIDIterator, 0, len(tk.tagValues))
342 for _, tv := range tk.tagValues {
343 if tv.cardinality() == 0 {
344 continue
345 }
346 if itr := tsdb.NewSeriesIDSetIterator(tv.seriesIDSet()); itr != nil {
347 itrs = append(itrs, itr)
348 }
349 }
350
351 return tsdb.MergeSeriesIDIterators(itrs...)
352 }
353
354 // TagKeyIterator returns a value iterator for a measurement.
355 func (f *LogFile) TagKeyIterator(name []byte) TagKeyIterator {
356 f.mu.RLock()
357 defer f.mu.RUnlock()
358
359 mm, ok := f.mms[string(name)]
360 if !ok {
361 return nil
362 }
363
364 a := make([]logTagKey, 0, len(mm.tagSet))
365 for _, k := range mm.tagSet {
366 a = append(a, k)
367 }
368 return newLogTagKeyIterator(a)
369 }
370
371 // TagKey returns a tag key element.
372 func (f *LogFile) TagKey(name, key []byte) TagKeyElem {
373 f.mu.RLock()
374 defer f.mu.RUnlock()
375
376 mm, ok := f.mms[string(name)]
377 if !ok {
378 return nil
379 }
380
381 tk, ok := mm.tagSet[string(key)]
382 if !ok {
383 return nil
384 }
385
386 return &tk
387 }
388
389 // TagValue returns a tag value element.
390 func (f *LogFile) TagValue(name, key, value []byte) TagValueElem {
391 f.mu.RLock()
392 defer f.mu.RUnlock()
393
394 mm, ok := f.mms[string(name)]
395 if !ok {
396 return nil
397 }
398
399 tk, ok := mm.tagSet[string(key)]
400 if !ok {
401 return nil
402 }
403
404 tv, ok := tk.tagValues[string(value)]
405 if !ok {
406 return nil
407 }
408
409 return &tv
410 }
411
412 // TagValueIterator returns a value iterator for a tag key.
413 func (f *LogFile) TagValueIterator(name, key []byte) TagValueIterator {
414 f.mu.RLock()
415 defer f.mu.RUnlock()
416
417 mm, ok := f.mms[string(name)]
418 if !ok {
419 return nil
420 }
421
422 tk, ok := mm.tagSet[string(key)]
423 if !ok {
424 return nil
425 }
426 return tk.TagValueIterator()
427 }
428
429 // DeleteTagKey adds a tombstone for a tag key to the log file.
430 func (f *LogFile) DeleteTagKey(name, key []byte) error {
431 f.mu.Lock()
432 defer f.mu.Unlock()
433
434 e := LogEntry{Flag: LogEntryTagKeyTombstoneFlag, Name: name, Key: key}
435 if err := f.appendEntry(&e); err != nil {
436 return err
437 }
438 f.execEntry(&e)
439
440 // Flush buffer and sync to disk.
441 return f.FlushAndSync()
442 }
443
444 // TagValueSeriesIDIterator returns a series iterator for a tag value.
445 func (f *LogFile) TagValueSeriesIDIterator(name, key, value []byte) tsdb.SeriesIDIterator {
446 f.mu.RLock()
447 defer f.mu.RUnlock()
448
449 mm, ok := f.mms[string(name)]
450 if !ok {
451 return nil
452 }
453
454 tk, ok := mm.tagSet[string(key)]
455 if !ok {
456 return nil
457 }
458
459 tv, ok := tk.tagValues[string(value)]
460 if !ok {
461 return nil
462 } else if tv.cardinality() == 0 {
463 return nil
464 }
465
466 return tsdb.NewSeriesIDSetIterator(tv.seriesIDSet())
467 }
468
469 // MeasurementN returns the total number of measurements.
470 func (f *LogFile) MeasurementN() (n uint64) {
471 f.mu.RLock()
472 defer f.mu.RUnlock()
473 return uint64(len(f.mms))
474 }
475
476 // TagKeyN returns the total number of keys.
477 func (f *LogFile) TagKeyN() (n uint64) {
478 f.mu.RLock()
479 defer f.mu.RUnlock()
480 for _, mm := range f.mms {
481 n += uint64(len(mm.tagSet))
482 }
483 return n
484 }
485
486 // TagValueN returns the total number of values.
487 func (f *LogFile) TagValueN() (n uint64) {
488 f.mu.RLock()
489 defer f.mu.RUnlock()
490 for _, mm := range f.mms {
491 for _, k := range mm.tagSet {
492 n += uint64(len(k.tagValues))
493 }
494 }
495 return n
496 }
497
498 // DeleteTagValue adds a tombstone for a tag value to the log file.
499 func (f *LogFile) DeleteTagValue(name, key, value []byte) error {
500 f.mu.Lock()
501 defer f.mu.Unlock()
502
503 e := LogEntry{Flag: LogEntryTagValueTombstoneFlag, Name: name, Key: key, Value: value}
504 if err := f.appendEntry(&e); err != nil {
505 return err
506 }
507 f.execEntry(&e)
508
509 // Flush buffer and sync to disk.
510 return f.FlushAndSync()
511 }
512
513 // AddSeriesList adds a list of series to the log file in bulk.
514 func (f *LogFile) AddSeriesList(seriesSet *tsdb.SeriesIDSet, names [][]byte, tagsSlice []models.Tags) error {
515 seriesIDs, err := f.sfile.CreateSeriesListIfNotExists(names, tagsSlice)
516 if err != nil {
517 return err
518 }
519
520 var writeRequired bool
521 entries := make([]LogEntry, 0, len(names))
522 seriesSet.RLock()
523 for i := range names {
524 if seriesSet.ContainsNoLock(seriesIDs[i]) {
525 // We don't need to allocate anything for this series.
526 continue
527 }
528 writeRequired = true
529 entries = append(entries, LogEntry{SeriesID: seriesIDs[i], name: names[i], tags: tagsSlice[i], cached: true})
530 }
531 seriesSet.RUnlock()
532
533 // Exit if all series already exist.
534 if !writeRequired {
535 return nil
536 }
537
538 f.mu.Lock()
539 defer f.mu.Unlock()
540
541 seriesSet.Lock()
542 defer seriesSet.Unlock()
543
544 for i := range entries {
545 entry := &entries[i]
546 if seriesSet.ContainsNoLock(entry.SeriesID) {
547 // We don't need to allocate anything for this series.
548 continue
549 }
550 if err := f.appendEntry(entry); err != nil {
551 return err
552 }
553 f.execEntry(entry)
554 seriesSet.AddNoLock(entry.SeriesID)
555 }
556
557 // Flush buffer and sync to disk.
558 return f.FlushAndSync()
559 }
560
561 // DeleteSeriesID adds a tombstone for a series id.
562 func (f *LogFile) DeleteSeriesID(id uint64) error {
563 f.mu.Lock()
564 defer f.mu.Unlock()
565
566 e := LogEntry{Flag: LogEntrySeriesTombstoneFlag, SeriesID: id}
567 if err := f.appendEntry(&e); err != nil {
568 return err
569 }
570 f.execEntry(&e)
571
572 // Flush buffer and sync to disk.
573 return f.FlushAndSync()
574 }
575
576 // SeriesN returns the total number of series in the file.
577 func (f *LogFile) SeriesN() (n uint64) {
578 f.mu.RLock()
579 defer f.mu.RUnlock()
580
581 for _, mm := range f.mms {
582 n += uint64(mm.cardinality())
583 }
584 return n
585 }
586
587 // appendEntry adds a log entry to the end of the file.
588 func (f *LogFile) appendEntry(e *LogEntry) error {
589 // Marshal entry to the local buffer.
590 f.buf = appendLogEntry(f.buf[:0], e)
591
592 // Save the size of the record.
593 e.Size = len(f.buf)
594
595 // Write record to file.
596 n, err := f.w.Write(f.buf)
597 if err != nil {
598 // Move position backwards over partial entry.
599 // Log should be reopened if seeking cannot be completed.
600 if n > 0 {
601 f.w.Reset(f.file)
602 if _, err := f.file.Seek(int64(-n), io.SeekCurrent); err != nil {
603 f.Close()
604 }
605 }
606 return err
607 }
608
609 // Update in-memory file size & modification time.
610 f.size += int64(n)
611 f.modTime = time.Now()
612
613 return nil
614 }
615
616 // execEntry executes a log entry against the in-memory index.
617 // This is done after appending and on replay of the log.
618 func (f *LogFile) execEntry(e *LogEntry) {
619 switch e.Flag {
620 case LogEntryMeasurementTombstoneFlag:
621 f.execDeleteMeasurementEntry(e)
622 case LogEntryTagKeyTombstoneFlag:
623 f.execDeleteTagKeyEntry(e)
624 case LogEntryTagValueTombstoneFlag:
625 f.execDeleteTagValueEntry(e)
626 default:
627 f.execSeriesEntry(e)
628 }
629 }
630
631 func (f *LogFile) execDeleteMeasurementEntry(e *LogEntry) {
632 mm := f.createMeasurementIfNotExists(e.Name)
633 mm.deleted = true
634 mm.tagSet = make(map[string]logTagKey)
635 mm.series = make(map[uint64]struct{})
636 mm.seriesSet = nil
637 }
638
639 func (f *LogFile) execDeleteTagKeyEntry(e *LogEntry) {
640 mm := f.createMeasurementIfNotExists(e.Name)
641 ts := mm.createTagSetIfNotExists(e.Key)
642
643 ts.deleted = true
644
645 mm.tagSet[string(e.Key)] = ts
646 }
647
648 func (f *LogFile) execDeleteTagValueEntry(e *LogEntry) {
649 mm := f.createMeasurementIfNotExists(e.Name)
650 ts := mm.createTagSetIfNotExists(e.Key)
651 tv := ts.createTagValueIfNotExists(e.Value)
652
653 tv.deleted = true
654
655 ts.tagValues[string(e.Value)] = tv
656 mm.tagSet[string(e.Key)] = ts
657 }
658
659 func (f *LogFile) execSeriesEntry(e *LogEntry) {
660 var seriesKey []byte
661 if e.cached {
662 sz := tsdb.SeriesKeySize(e.name, e.tags)
663 if len(f.keyBuf) < sz {
664 f.keyBuf = make([]byte, 0, sz)
665 }
666 seriesKey = tsdb.AppendSeriesKey(f.keyBuf[:0], e.name, e.tags)
667 } else {
668 seriesKey = f.sfile.SeriesKey(e.SeriesID)
669 }
670
671 // Series keys can be removed if the series has been deleted from
672 // the entire database and the server is restarted. This would cause
673 // the log to replay its insert but the key cannot be found.
674 //
675 // https://github.com/influxdata/influxdb/issues/9444
676 if seriesKey == nil {
677 return
678 }
679
680 // Check if deleted.
681 deleted := e.Flag == LogEntrySeriesTombstoneFlag
682
683 // Read key size.
684 _, remainder := tsdb.ReadSeriesKeyLen(seriesKey)
685
686 // Read measurement name.
687 name, remainder := tsdb.ReadSeriesKeyMeasurement(remainder)
688 mm := f.createMeasurementIfNotExists(name)
689 mm.deleted = false
690 if !deleted {
691 mm.addSeriesID(e.SeriesID)
692 } else {
693 mm.removeSeriesID(e.SeriesID)
694 }
695
696 // Read tag count.
697 tagN, remainder := tsdb.ReadSeriesKeyTagN(remainder)
698
699 // Save tags.
700 var k, v []byte
701 for i := 0; i < tagN; i++ {
702 k, v, remainder = tsdb.ReadSeriesKeyTag(remainder)
703 ts := mm.createTagSetIfNotExists(k)
704 tv := ts.createTagValueIfNotExists(v)
705
706 // Add/remove a reference to the series on the tag value.
707 if !deleted {
708 tv.addSeriesID(e.SeriesID)
709 } else {
710 tv.removeSeriesID(e.SeriesID)
711 }
712
713 ts.tagValues[string(v)] = tv
714 mm.tagSet[string(k)] = ts
715 }
716
717 // Add/remove from appropriate series id sets.
718 if !deleted {
719 f.seriesIDSet.Add(e.SeriesID)
720 f.tombstoneSeriesIDSet.Remove(e.SeriesID)
721 } else {
722 f.seriesIDSet.Remove(e.SeriesID)
723 f.tombstoneSeriesIDSet.Add(e.SeriesID)
724 }
725 }
726
727 // SeriesIDIterator returns an iterator over all series in the log file.
728 func (f *LogFile) SeriesIDIterator() tsdb.SeriesIDIterator {
729 f.mu.RLock()
730 defer f.mu.RUnlock()
731
732 ss := tsdb.NewSeriesIDSet()
733 allSeriesSets := make([]*tsdb.SeriesIDSet, 0, len(f.mms))
734
735 for _, mm := range f.mms {
736 if mm.seriesSet != nil {
737 allSeriesSets = append(allSeriesSets, mm.seriesSet)
738 continue
739 }
740
741 // measurement is not using seriesSet to store series IDs.
742 mm.forEach(func(seriesID uint64) {
743 ss.AddNoLock(seriesID)
744 })
745 }
746
747 // Fast merge all seriesSets.
748 if len(allSeriesSets) > 0 {
749 ss.Merge(allSeriesSets...)
750 }
751
752 return tsdb.NewSeriesIDSetIterator(ss)
753 }
754
755 // createMeasurementIfNotExists returns a measurement by name.
756 func (f *LogFile) createMeasurementIfNotExists(name []byte) *logMeasurement {
757 mm := f.mms[string(name)]
758 if mm == nil {
759 mm = &logMeasurement{
760 name: name,
761 tagSet: make(map[string]logTagKey),
762 series: make(map[uint64]struct{}),
763 }
764 f.mms[string(name)] = mm
765 }
766 return mm
767 }
768
769 // MeasurementIterator returns an iterator over all the measurements in the file.
770 func (f *LogFile) MeasurementIterator() MeasurementIterator {
771 f.mu.RLock()
772 defer f.mu.RUnlock()
773
774 var itr logMeasurementIterator
775 for _, mm := range f.mms {
776 itr.mms = append(itr.mms, *mm)
777 }
778 sort.Sort(logMeasurementSlice(itr.mms))
779 return &itr
780 }
781
782 // MeasurementSeriesIDIterator returns an iterator over all series for a measurement.
783 func (f *LogFile) MeasurementSeriesIDIterator(name []byte) tsdb.SeriesIDIterator {
784 f.mu.RLock()
785 defer f.mu.RUnlock()
786
787 mm := f.mms[string(name)]
788 if mm == nil || mm.cardinality() == 0 {
789 return nil
790 }
791 return tsdb.NewSeriesIDSetIterator(mm.seriesIDSet())
792 }
793
794 // CompactTo compacts the log file and writes it to w.
795 func (f *LogFile) CompactTo(w io.Writer, m, k uint64, cancel <-chan struct{}) (n int64, err error) {
796 f.mu.RLock()
797 defer f.mu.RUnlock()
798
799 // Check for cancellation.
800 select {
801 case <-cancel:
802 return n, ErrCompactionInterrupted
803 default:
804 }
805
806 // Wrap in bufferred writer with a buffer equivalent to the LogFile size.
807 bw := bufio.NewWriterSize(w, indexFileBufferSize) // 128K
808
809 // Setup compaction offset tracking data.
810 var t IndexFileTrailer
811 info := newLogFileCompactInfo()
812 info.cancel = cancel
813
814 // Write magic number.
815 if err := writeTo(bw, []byte(FileSignature), &n); err != nil {
816 return n, err
817 }
818
819 // Retreve measurement names in order.
820 names := f.measurementNames()
821
822 // Flush buffer & mmap series block.
823 if err := bw.Flush(); err != nil {
824 return n, err
825 }
826
827 // Write tagset blocks in measurement order.
828 if err := f.writeTagsetsTo(bw, names, info, &n); err != nil {
829 return n, err
830 }
831
832 // Write measurement block.
833 t.MeasurementBlock.Offset = n
834 if err := f.writeMeasurementBlockTo(bw, names, info, &n); err != nil {
835 return n, err
836 }
837 t.MeasurementBlock.Size = n - t.MeasurementBlock.Offset
838
839 // Write series set.
840 t.SeriesIDSet.Offset = n
841 nn, err := f.seriesIDSet.WriteTo(bw)
842 if n += nn; err != nil {
843 return n, err
844 }
845 t.SeriesIDSet.Size = n - t.SeriesIDSet.Offset
846
847 // Write tombstone series set.
848 t.TombstoneSeriesIDSet.Offset = n
849 nn, err = f.tombstoneSeriesIDSet.WriteTo(bw)
850 if n += nn; err != nil {
851 return n, err
852 }
853 t.TombstoneSeriesIDSet.Size = n - t.TombstoneSeriesIDSet.Offset
854
855 // Build series sketches.
856 sSketch, sTSketch, err := f.seriesSketches()
857 if err != nil {
858 return n, err
859 }
860
861 // Write series sketches.
862 t.SeriesSketch.Offset = n
863 data, err := sSketch.MarshalBinary()
864 if err != nil {
865 return n, err
866 } else if _, err := bw.Write(data); err != nil {
867 return n, err
868 }
869 t.SeriesSketch.Size = int64(len(data))
870 n += t.SeriesSketch.Size
871
872 t.TombstoneSeriesSketch.Offset = n
873 if data, err = sTSketch.MarshalBinary(); err != nil {
874 return n, err
875 } else if _, err := bw.Write(data); err != nil {
876 return n, err
877 }
878 t.TombstoneSeriesSketch.Size = int64(len(data))
879 n += t.TombstoneSeriesSketch.Size
880
881 // Write trailer.
882 nn, err = t.WriteTo(bw)
883 n += nn
884 if err != nil {
885 return n, err
886 }
887
888 // Flush buffer.
889 if err := bw.Flush(); err != nil {
890 return n, err
891 }
892
893 return n, nil
894 }
895
896 func (f *LogFile) writeTagsetsTo(w io.Writer, names []string, info *logFileCompactInfo, n *int64) error {
897 for _, name := range names {
898 if err := f.writeTagsetTo(w, name, info, n); err != nil {
899 return err
900 }
901 }
902 return nil
903 }
904
905 // writeTagsetTo writes a single tagset to w and saves the tagset offset.
906 func (f *LogFile) writeTagsetTo(w io.Writer, name string, info *logFileCompactInfo, n *int64) error {
907 mm := f.mms[name]
908
909 // Check for cancellation.
910 select {
911 case <-info.cancel:
912 return ErrCompactionInterrupted
913 default:
914 }
915
916 enc := NewTagBlockEncoder(w)
917 var valueN int
918 for _, k := range mm.keys() {
919 tag := mm.tagSet[k]
920
921 // Encode tag. Skip values if tag is deleted.
922 if err := enc.EncodeKey(tag.name, tag.deleted); err != nil {
923 return err
924 } else if tag.deleted {
925 continue
926 }
927
928 // Sort tag values.
929 values := make([]string, 0, len(tag.tagValues))
930 for v := range tag.tagValues {
931 values = append(values, v)
932 }
933 sort.Strings(values)
934
935 // Add each value.
936 for _, v := range values {
937 value := tag.tagValues[v]
938 if err := enc.EncodeValue(value.name, value.deleted, value.seriesIDs()); err != nil {
939 return err
940 }
941
942 // Check for cancellation periodically.
943 if valueN++; valueN%1000 == 0 {
944 select {
945 case <-info.cancel:
946 return ErrCompactionInterrupted
947 default:
948 }
949 }
950 }
951 }
952
953 // Save tagset offset to measurement.
954 offset := *n
955
956 // Flush tag block.
957 err := enc.Close()
958 *n += enc.N()
959 if err != nil {
960 return err
961 }
962
963 // Save tagset offset to measurement.
964 size := *n - offset
965
966 info.mms[name] = &logFileMeasurementCompactInfo{offset: offset, size: size}
967
968 return nil
969 }
970
971 func (f *LogFile) writeMeasurementBlockTo(w io.Writer, names []string, info *logFileCompactInfo, n *int64) error {
972 mw := NewMeasurementBlockWriter()
973
974 // Check for cancellation.
975 select {
976 case <-info.cancel:
977 return ErrCompactionInterrupted
978 default:
979 }
980
981 // Add measurement data.
982 for _, name := range names {
983 mm := f.mms[name]
984 mmInfo := info.mms[name]
985 assert(mmInfo != nil, "measurement info not found")
986 mw.Add(mm.name, mm.deleted, mmInfo.offset, mmInfo.size, mm.seriesIDs())
987 }
988
989 // Flush data to writer.
990 nn, err := mw.WriteTo(w)
991 *n += nn
992 return err
993 }
994
995 // logFileCompactInfo is a context object to track compaction position info.
996 type logFileCompactInfo struct {
997 cancel <-chan struct{}
998 mms map[string]*logFileMeasurementCompactInfo
999 }
1000
1001 // newLogFileCompactInfo returns a new instance of logFileCompactInfo.
1002 func newLogFileCompactInfo() *logFileCompactInfo {
1003 return &logFileCompactInfo{
1004 mms: make(map[string]*logFileMeasurementCompactInfo),
1005 }
1006 }
1007
1008 type logFileMeasurementCompactInfo struct {
1009 offset int64
1010 size int64
1011 }
1012
1013 // MeasurementsSketches returns sketches for existing and tombstoned measurement names.
1014 func (f *LogFile) MeasurementsSketches() (sketch, tSketch estimator.Sketch, err error) {
1015 f.mu.RLock()
1016 defer f.mu.RUnlock()
1017 return f.measurementsSketches()
1018 }
1019
1020 func (f *LogFile) measurementsSketches() (sketch, tSketch estimator.Sketch, err error) {
1021 sketch, tSketch = hll.NewDefaultPlus(), hll.NewDefaultPlus()
1022 for _, mm := range f.mms {
1023 if mm.deleted {
1024 tSketch.Add(mm.name)
1025 } else {
1026 sketch.Add(mm.name)
1027 }
1028 }
1029 return sketch, tSketch, nil
1030 }
1031
1032 // SeriesSketches returns sketches for existing and tombstoned series.
1033 func (f *LogFile) SeriesSketches() (sketch, tSketch estimator.Sketch, err error) {
1034 f.mu.RLock()
1035 defer f.mu.RUnlock()
1036 return f.seriesSketches()
1037 }
1038
1039 func (f *LogFile) seriesSketches() (sketch, tSketch estimator.Sketch, err error) {
1040 sketch = hll.NewDefaultPlus()
1041 f.seriesIDSet.ForEach(func(id uint64) {
1042 name, keys := f.sfile.Series(id)
1043 sketch.Add(models.MakeKey(name, keys))
1044 })
1045
1046 tSketch = hll.NewDefaultPlus()
1047 f.tombstoneSeriesIDSet.ForEach(func(id uint64) {
1048 name, keys := f.sfile.Series(id)
1049 tSketch.Add(models.MakeKey(name, keys))
1050 })
1051 return sketch, tSketch, nil
1052 }
1053
1054 // LogEntry represents a single log entry in the write-ahead log.
1055 type LogEntry struct {
1056 Flag byte // flag
1057 SeriesID uint64 // series id
1058 Name []byte // measurement name
1059 Key []byte // tag key
1060 Value []byte // tag value
1061 Checksum uint32 // checksum of flag/name/tags.
1062 Size int // total size of record, in bytes.
1063
1064 cached bool // Hint to LogFile that series data is already parsed
1065 name []byte // series naem, this is a cached copy of the parsed measurement name
1066 tags models.Tags // series tags, this is a cached copied of the parsed tags
1067 }
1068
1069 // UnmarshalBinary unmarshals data into e.
1070 func (e *LogEntry) UnmarshalBinary(data []byte) error {
1071 var sz uint64
1072 var n int
1073 var seriesID uint64
1074 var err error
1075
1076 orig := data
1077 start := len(data)
1078
1079 // Parse flag data.
1080 if len(data) < 1 {
1081 return io.ErrShortBuffer
1082 }
1083 e.Flag, data = data[0], data[1:]
1084
1085 // Parse series id.
1086 if seriesID, n, err = uvarint(data); err != nil {
1087 return err
1088 }
1089 e.SeriesID, data = seriesID, data[n:]
1090
1091 // Parse name length.
1092 if sz, n, err = uvarint(data); err != nil {
1093 return err
1094 }
1095
1096 // Read name data.
1097 if len(data) < n+int(sz) {
1098 return io.ErrShortBuffer
1099 }
1100 e.Name, data = data[n:n+int(sz)], data[n+int(sz):]
1101
1102 // Parse key length.
1103 if sz, n, err = uvarint(data); err != nil {
1104 return err
1105 }
1106
1107 // Read key data.
1108 if len(data) < n+int(sz) {
1109 return io.ErrShortBuffer
1110 }
1111 e.Key, data = data[n:n+int(sz)], data[n+int(sz):]
1112
1113 // Parse value length.
1114 if sz, n, err = uvarint(data); err != nil {
1115 return err
1116 }
1117
1118 // Read value data.
1119 if len(data) < n+int(sz) {
1120 return io.ErrShortBuffer
1121 }
1122 e.Value, data = data[n:n+int(sz)], data[n+int(sz):]
1123
1124 // Compute checksum.
1125 chk := crc32.ChecksumIEEE(orig[:start-len(data)])
1126
1127 // Parse checksum.
1128 if len(data) < 4 {
1129 return io.ErrShortBuffer
1130 }
1131 e.Checksum, data = binary.BigEndian.Uint32(data[:4]), data[4:]
1132
1133 // Verify checksum.
1134 if chk != e.Checksum {
1135 return ErrLogEntryChecksumMismatch
1136 }
1137
1138 // Save length of elem.
1139 e.Size = start - len(data)
1140
1141 return nil
1142 }
1143
1144 // appendLogEntry appends to dst and returns the new buffer.
1145 // This updates the checksum on the entry.
1146 func appendLogEntry(dst []byte, e *LogEntry) []byte {
1147 var buf [binary.MaxVarintLen64]byte
1148 start := len(dst)
1149
1150 // Append flag.
1151 dst = append(dst, e.Flag)
1152
1153 // Append series id.
1154 n := binary.PutUvarint(buf[:], uint64(e.SeriesID))
1155 dst = append(dst, buf[:n]...)
1156
1157 // Append name.
1158 n = binary.PutUvarint(buf[:], uint64(len(e.Name)))
1159 dst = append(dst, buf[:n]...)
1160 dst = append(dst, e.Name...)
1161
1162 // Append key.
1163 n = binary.PutUvarint(buf[:], uint64(len(e.Key)))
1164 dst = append(dst, buf[:n]...)
1165 dst = append(dst, e.Key...)
1166
1167 // Append value.
1168 n = binary.PutUvarint(buf[:], uint64(len(e.Value)))
1169 dst = append(dst, buf[:n]...)
1170 dst = append(dst, e.Value...)
1171
1172 // Calculate checksum.
1173 e.Checksum = crc32.ChecksumIEEE(dst[start:])
1174
1175 // Append checksum.
1176 binary.BigEndian.PutUint32(buf[:4], e.Checksum)
1177 dst = append(dst, buf[:4]...)
1178
1179 return dst
1180 }
1181
1182 // logMeasurements represents a map of measurement names to measurements.
1183 type logMeasurements map[string]*logMeasurement
1184
1185 // bytes estimates the memory footprint of this logMeasurements, in bytes.
1186 func (mms *logMeasurements) bytes() int {
1187 var b int
1188 for k, v := range *mms {
1189 b += len(k)
1190 b += v.bytes()
1191 }
1192 b += int(unsafe.Sizeof(*mms))
1193 return b
1194 }
1195
1196 type logMeasurement struct {
1197 name []byte
1198 tagSet map[string]logTagKey
1199 deleted bool
1200 series map[uint64]struct{}
1201 seriesSet *tsdb.SeriesIDSet
1202 }
1203
1204 // bytes estimates the memory footprint of this logMeasurement, in bytes.
1205 func (m *logMeasurement) bytes() int {
1206 var b int
1207 b += len(m.name)
1208 for k, v := range m.tagSet {
1209 b += len(k)
1210 b += v.bytes()
1211 }
1212 b += (int(m.cardinality()) * 8)
1213 b += int(unsafe.Sizeof(*m))
1214 return b
1215 }
1216
1217 func (m *logMeasurement) addSeriesID(x uint64) {
1218 if m.seriesSet != nil {
1219 m.seriesSet.AddNoLock(x)
1220 return
1221 }
1222
1223 m.series[x] = struct{}{}
1224
1225 // If the map is getting too big it can be converted into a roaring seriesSet.
1226 if len(m.series) > 25 {
1227 m.seriesSet = tsdb.NewSeriesIDSet()
1228 for id := range m.series {
1229 m.seriesSet.AddNoLock(id)
1230 }
1231 m.series = nil
1232 }
1233 }
1234
1235 func (m *logMeasurement) removeSeriesID(x uint64) {
1236 if m.seriesSet != nil {
1237 m.seriesSet.RemoveNoLock(x)
1238 return
1239 }
1240 delete(m.series, x)
1241 }
1242
1243 func (m *logMeasurement) cardinality() int64 {
1244 if m.seriesSet != nil {
1245 return int64(m.seriesSet.Cardinality())
1246 }
1247 return int64(len(m.series))
1248 }
1249
1250 // forEach applies fn to every series ID in the logMeasurement.
1251 func (m *logMeasurement) forEach(fn func(uint64)) {
1252 if m.seriesSet != nil {
1253 m.seriesSet.ForEachNoLock(fn)
1254 return
1255 }
1256
1257 for seriesID := range m.series {
1258 fn(seriesID)
1259 }
1260 }
1261
1262 // seriesIDs returns a sorted set of seriesIDs.
1263 func (m *logMeasurement) seriesIDs() []uint64 {
1264 a := make([]uint64, 0, m.cardinality())
1265 if m.seriesSet != nil {
1266 m.seriesSet.ForEachNoLock(func(id uint64) { a = append(a, id) })
1267 return a // IDs are already sorted.
1268 }
1269
1270 for seriesID := range m.series {
1271 a = append(a, seriesID)
1272 }
1273 sort.Sort(uint64Slice(a))
1274 return a
1275 }
1276
1277 // seriesIDSet returns a copy of the logMeasurement's seriesSet, or creates a new
1278 // one
1279 func (m *logMeasurement) seriesIDSet() *tsdb.SeriesIDSet {
1280 if m.seriesSet != nil {
1281 return m.seriesSet.CloneNoLock()
1282 }
1283
1284 ss := tsdb.NewSeriesIDSet()
1285 for seriesID := range m.series {
1286 ss.AddNoLock(seriesID)
1287 }
1288 return ss
1289 }
1290
1291 func (m *logMeasurement) Name() []byte { return m.name }
1292 func (m *logMeasurement) Deleted() bool { return m.deleted }
1293
1294 func (m *logMeasurement) createTagSetIfNotExists(key []byte) logTagKey {
1295 ts, ok := m.tagSet[string(key)]
1296 if !ok {
1297 ts = logTagKey{name: key, tagValues: make(map[string]logTagValue)}
1298 }
1299 return ts
1300 }
1301
1302 // keys returns a sorted list of tag keys.
1303 func (m *logMeasurement) keys() []string {
1304 a := make([]string, 0, len(m.tagSet))
1305 for k := range m.tagSet {
1306 a = append(a, k)
1307 }
1308 sort.Strings(a)
1309 return a
1310 }
1311
1312 // logMeasurementSlice is a sortable list of log measurements.
1313 type logMeasurementSlice []logMeasurement
1314
1315 func (a logMeasurementSlice) Len() int { return len(a) }
1316 func (a logMeasurementSlice) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1317 func (a logMeasurementSlice) Less(i, j int) bool { return bytes.Compare(a[i].name, a[j].name) == -1 }
1318
1319 // logMeasurementIterator represents an iterator over a slice of measurements.
1320 type logMeasurementIterator struct {
1321 mms []logMeasurement
1322 }
1323
1324 // Next returns the next element in the iterator.
1325 func (itr *logMeasurementIterator) Next() (e MeasurementElem) {
1326 if len(itr.mms) == 0 {
1327 return nil
1328 }
1329 e, itr.mms = &itr.mms[0], itr.mms[1:]
1330 return e
1331 }
1332
1333 type logTagKey struct {
1334 name []byte
1335 deleted bool
1336 tagValues map[string]logTagValue
1337 }
1338
1339 // bytes estimates the memory footprint of this logTagKey, in bytes.
1340 func (tk *logTagKey) bytes() int {
1341 var b int
1342 b += len(tk.name)
1343 for k, v := range tk.tagValues {
1344 b += len(k)
1345 b += v.bytes()
1346 }
1347 b += int(unsafe.Sizeof(*tk))
1348 return b
1349 }
1350
1351 func (tk *logTagKey) Key() []byte { return tk.name }
1352 func (tk *logTagKey) Deleted() bool { return tk.deleted }
1353
1354 func (tk *logTagKey) TagValueIterator() TagValueIterator {
1355 a := make([]logTagValue, 0, len(tk.tagValues))
1356 for _, v := range tk.tagValues {
1357 a = append(a, v)
1358 }
1359 return newLogTagValueIterator(a)
1360 }
1361
1362 func (tk *logTagKey) createTagValueIfNotExists(value []byte) logTagValue {
1363 tv, ok := tk.tagValues[string(value)]
1364 if !ok {
1365 tv = logTagValue{name: value, series: make(map[uint64]struct{})}
1366 }
1367 return tv
1368 }
1369
1370 // logTagKey is a sortable list of log tag keys.
1371 type logTagKeySlice []logTagKey
1372
1373 func (a logTagKeySlice) Len() int { return len(a) }
1374 func (a logTagKeySlice) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1375 func (a logTagKeySlice) Less(i, j int) bool { return bytes.Compare(a[i].name, a[j].name) == -1 }
1376
1377 type logTagValue struct {
1378 name []byte
1379 deleted bool
1380 series map[uint64]struct{}
1381 seriesSet *tsdb.SeriesIDSet
1382 }
1383
1384 // bytes estimates the memory footprint of this logTagValue, in bytes.
1385 func (tv *logTagValue) bytes() int {
1386 var b int
1387 b += len(tv.name)
1388 b += int(unsafe.Sizeof(*tv))
1389 b += (int(tv.cardinality()) * 8)
1390 return b
1391 }
1392
1393 func (tv *logTagValue) addSeriesID(x uint64) {
1394 if tv.seriesSet != nil {
1395 tv.seriesSet.AddNoLock(x)
1396 return
1397 }
1398
1399 tv.series[x] = struct{}{}
1400
1401 // If the map is getting too big it can be converted into a roaring seriesSet.
1402 if len(tv.series) > 25 {
1403 tv.seriesSet = tsdb.NewSeriesIDSet()
1404 for id := range tv.series {
1405 tv.seriesSet.AddNoLock(id)
1406 }
1407 tv.series = nil
1408 }
1409 }
1410
1411 func (tv *logTagValue) removeSeriesID(x uint64) {
1412 if tv.seriesSet != nil {
1413 tv.seriesSet.RemoveNoLock(x)
1414 return
1415 }
1416 delete(tv.series, x)
1417 }
1418
1419 func (tv *logTagValue) cardinality() int64 {
1420 if tv.seriesSet != nil {
1421 return int64(tv.seriesSet.Cardinality())
1422 }
1423 return int64(len(tv.series))
1424 }
1425
1426 // seriesIDs returns a sorted set of seriesIDs.
1427 func (tv *logTagValue) seriesIDs() []uint64 {
1428 a := make([]uint64, 0, tv.cardinality())
1429 if tv.seriesSet != nil {
1430 tv.seriesSet.ForEachNoLock(func(id uint64) { a = append(a, id) })
1431 return a // IDs are already sorted.
1432 }
1433
1434 for seriesID := range tv.series {
1435 a = append(a, seriesID)
1436 }
1437 sort.Sort(uint64Slice(a))
1438 return a
1439 }
1440
1441 // seriesIDSet returns a copy of the logMeasurement's seriesSet, or creates a new
1442 // one
1443 func (tv *logTagValue) seriesIDSet() *tsdb.SeriesIDSet {
1444 if tv.seriesSet != nil {
1445 return tv.seriesSet.CloneNoLock()
1446 }
1447
1448 ss := tsdb.NewSeriesIDSet()
1449 for seriesID := range tv.series {
1450 ss.AddNoLock(seriesID)
1451 }
1452 return ss
1453 }
1454
1455 func (tv *logTagValue) Value() []byte { return tv.name }
1456 func (tv *logTagValue) Deleted() bool { return tv.deleted }
1457
1458 // logTagValue is a sortable list of log tag values.
1459 type logTagValueSlice []logTagValue
1460
1461 func (a logTagValueSlice) Len() int { return len(a) }
1462 func (a logTagValueSlice) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
1463 func (a logTagValueSlice) Less(i, j int) bool { return bytes.Compare(a[i].name, a[j].name) == -1 }
1464
1465 // logTagKeyIterator represents an iterator over a slice of tag keys.
1466 type logTagKeyIterator struct {
1467 a []logTagKey
1468 }
1469
1470 // newLogTagKeyIterator returns a new instance of logTagKeyIterator.
1471 func newLogTagKeyIterator(a []logTagKey) *logTagKeyIterator {
1472 sort.Sort(logTagKeySlice(a))
1473 return &logTagKeyIterator{a: a}
1474 }
1475
1476 // Next returns the next element in the iterator.
1477 func (itr *logTagKeyIterator) Next() (e TagKeyElem) {
1478 if len(itr.a) == 0 {
1479 return nil
1480 }
1481 e, itr.a = &itr.a[0], itr.a[1:]
1482 return e
1483 }
1484
1485 // logTagValueIterator represents an iterator over a slice of tag values.
1486 type logTagValueIterator struct {
1487 a []logTagValue
1488 }
1489
1490 // newLogTagValueIterator returns a new instance of logTagValueIterator.
1491 func newLogTagValueIterator(a []logTagValue) *logTagValueIterator {
1492 sort.Sort(logTagValueSlice(a))
1493 return &logTagValueIterator{a: a}
1494 }
1495
1496 // Next returns the next element in the iterator.
1497 func (itr *logTagValueIterator) Next() (e TagValueElem) {
1498 if len(itr.a) == 0 {
1499 return nil
1500 }
1501 e, itr.a = &itr.a[0], itr.a[1:]
1502 return e
1503 }
1504
1505 // FormatLogFileName generates a log filename for the given index.
1506 func FormatLogFileName(id int) string {
1507 return fmt.Sprintf("L0-%08d%s", id, LogFileExt)
1508 }