Debian Codegraph @

tsdb/index/tsi1/doc.go

raw
1 /*
2
3 Package tsi1 provides a memory-mapped index implementation that supports
4 high cardinality series.
5
6 Overview
7
8 The top-level object in tsi1 is the Index. It is the primary access point from
9 the rest of the system. The Index is composed of LogFile and IndexFile objects.
10
11 Log files are small write-ahead log files that record new series immediately
12 in the order that they are received. The data within the file is indexed
13 in-memory so it can be quickly accessed. When the system is restarted, this log
14 file is replayed and the in-memory representation is rebuilt.
15
16 Index files also contain series information, however, they are highly indexed
17 so that reads can be performed quickly. Index files are built through a process
18 called compaction where a log file or multiple index files are merged together.
19
20
21 Operations
22
23 The index can perform many tasks related to series, measurement, & tag data.
24 All data is inserted by adding a series to the index. When adding a series,
25 the measurement, tag keys, and tag values are all extracted and indexed
26 separately.
27
28 Once a series has been added, it can be removed in several ways. First, the
29 individual series can be removed. Second, it can be removed as part of a bulk
30 operation by deleting the entire measurement.
31
32 The query engine needs to be able to look up series in a variety of ways such
33 as by measurement name, by tag value, or by using regular expressions. The
34 index provides an API to iterate over subsets of series and perform set
35 operations such as unions and intersections.
36
37
38 Log File Layout
39
40 The write-ahead file that series initially are inserted into simply appends
41 all new operations sequentially. It is simply composed of a series of log
42 entries. An entry contains a flag to specify the operation type, the measurement
43 name, the tag set, and a checksum.
44
45 ┏━━━━━━━━━LogEntry━━━━━━━━━┓
46 ┃ ┌──────────────────────┐ ┃
47 ┃ │ Flag │ ┃
48 ┃ ├──────────────────────┤ ┃
49 ┃ │ Measurement │ ┃
50 ┃ ├──────────────────────┤ ┃
51 ┃ │ Key/Value │ ┃
52 ┃ ├──────────────────────┤ ┃
53 ┃ │ Key/Value │ ┃
54 ┃ ├──────────────────────┤ ┃
55 ┃ │ Key/Value │ ┃
56 ┃ ├──────────────────────┤ ┃
57 ┃ │ Checksum │ ┃
58 ┃ └──────────────────────┘ ┃
59 ┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
60
61 When the log file is replayed, if the checksum is incorrect or the entry is
62 incomplete (because of a partially failed write) then the log is truncated.
63
64
65 Index File Layout
66
67 The index file is composed of 3 main block types: one series block, one or more
68 tag blocks, and one measurement block. At the end of the index file is a
69 trailer that records metadata such as the offsets to these blocks.
70
71
72 Series Block Layout
73
74 The series block stores raw series keys in sorted order. It also provides hash
75 indexes so that series can be looked up quickly. Hash indexes are inserted
76 periodically so that memory size is limited at write time. Once all the series
77 and hash indexes have been written then a list of index entries are written
78 so that hash indexes can be looked up via binary search.
79
80 The end of the block contains two HyperLogLog++ sketches which track the
81 estimated number of created series and deleted series. After the sketches is
82 a trailer which contains metadata about the block.
83
84 ┏━━━━━━━SeriesBlock━━━━━━━━┓
85 ┃ ┌──────────────────────┐ ┃
86 ┃ │ Series Key │ ┃
87 ┃ ├──────────────────────┤ ┃
88 ┃ │ Series Key │ ┃
89 ┃ ├──────────────────────┤ ┃
90 ┃ │ Series Key │ ┃
91 ┃ ├──────────────────────┤ ┃
92 ┃ │ │ ┃
93 ┃ │ Hash Index │ ┃
94 ┃ │ │ ┃
95 ┃ ├──────────────────────┤ ┃
96 ┃ │ Series Key │ ┃
97 ┃ ├──────────────────────┤ ┃
98 ┃ │ Series Key │ ┃
99 ┃ ├──────────────────────┤ ┃
100 ┃ │ Series Key │ ┃
101 ┃ ├──────────────────────┤ ┃
102 ┃ │ │ ┃
103 ┃ │ Hash Index │ ┃
104 ┃ │ │ ┃
105 ┃ ├──────────────────────┤ ┃
106 ┃ │ Index Entries │ ┃
107 ┃ ├──────────────────────┤ ┃
108 ┃ │ HLL Sketches │ ┃
109 ┃ ├──────────────────────┤ ┃
110 ┃ │ Trailer │ ┃
111 ┃ └──────────────────────┘ ┃
112 ┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
113
114
115 Tag Block Layout
116
117 After the series block is one or more tag blocks. One of these blocks exists
118 for every measurement in the index file. The block is structured as a sorted
119 list of values for each key and then a sorted list of keys. Each of these lists
120 has their own hash index for fast direct lookups.
121
122 ┏━━━━━━━━Tag Block━━━━━━━━━┓
123 ┃ ┌──────────────────────┐ ┃
124 ┃ │ Value │ ┃
125 ┃ ├──────────────────────┤ ┃
126 ┃ │ Value │ ┃
127 ┃ ├──────────────────────┤ ┃
128 ┃ │ Value │ ┃
129 ┃ ├──────────────────────┤ ┃
130 ┃ │ │ ┃
131 ┃ │ Hash Index │ ┃
132 ┃ │ │ ┃
133 ┃ └──────────────────────┘ ┃
134 ┃ ┌──────────────────────┐ ┃
135 ┃ │ Value │ ┃
136 ┃ ├──────────────────────┤ ┃
137 ┃ │ Value │ ┃
138 ┃ ├──────────────────────┤ ┃
139 ┃ │ │ ┃
140 ┃ │ Hash Index │ ┃
141 ┃ │ │ ┃
142 ┃ └──────────────────────┘ ┃
143 ┃ ┌──────────────────────┐ ┃
144 ┃ │ Key │ ┃
145 ┃ ├──────────────────────┤ ┃
146 ┃ │ Key │ ┃
147 ┃ ├──────────────────────┤ ┃
148 ┃ │ │ ┃
149 ┃ │ Hash Index │ ┃
150 ┃ │ │ ┃
151 ┃ └──────────────────────┘ ┃
152 ┃ ┌──────────────────────┐ ┃
153 ┃ │ Trailer │ ┃
154 ┃ └──────────────────────┘ ┃
155 ┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
156
157 Each entry for values contains a sorted list of offsets for series keys that use
158 that value. Series iterators can be built around a single tag key value or
159 multiple iterators can be merged with set operators such as union or
160 intersection.
161
162
163 Measurement block
164
165 The measurement block stores a sorted list of measurements, their associated
166 series offsets, and the offset to their tag block. This allows all series for
167 a measurement to be traversed quickly and it allows fast direct lookups of
168 measurements and their tags.
169
170 This block also contains HyperLogLog++ sketches for new and deleted
171 measurements.
172
173 ┏━━━━Measurement Block━━━━━┓
174 ┃ ┌──────────────────────┐ ┃
175 ┃ │ Measurement │ ┃
176 ┃ ├──────────────────────┤ ┃
177 ┃ │ Measurement │ ┃
178 ┃ ├──────────────────────┤ ┃
179 ┃ │ Measurement │ ┃
180 ┃ ├──────────────────────┤ ┃
181 ┃ │ │ ┃
182 ┃ │ Hash Index │ ┃
183 ┃ │ │ ┃
184 ┃ ├──────────────────────┤ ┃
185 ┃ │ HLL Sketches │ ┃
186 ┃ ├──────────────────────┤ ┃
187 ┃ │ Trailer │ ┃
188 ┃ └──────────────────────┘ ┃
189 ┗━━━━━━━━━━━━━━━━━━━━━━━━━━┛
190
191
192 Manifest file
193
194 The index is simply an ordered set of log and index files. These files can be
195 merged together or rewritten but their order must always be the same. This is
196 because series, measurements, & tags can be marked as deleted (aka tombstoned)
197 and this action needs to be tracked in time order.
198
199 Whenever the set of active files is changed, a manifest file is written to
200 track the set. The manifest specifies the ordering of files and, on startup,
201 all files not in the manifest are removed from the index directory.
202
203
204 Compacting index files
205
206 Compaction is the process of taking files and merging them together into a
207 single file. There are two stages of compaction within TSI.
208
209 First, once log files exceed a size threshold then they are compacted into an
210 index file. This threshold is relatively small because log files must maintain
211 their index in the heap which TSI tries to avoid. Small log files are also very
212 quick to convert into an index file so this is done aggressively.
213
214 Second, once a contiguous set of index files exceed a factor (e.g. 10x) then
215 they are all merged together into a single index file and the old files are
216 discarded. Because all blocks are written in sorted order, the new index file
217 can be streamed and minimize memory use.
218
219
220 Concurrency
221
222 Index files are immutable so they do not require fine grained locks, however,
223 compactions require that we track which files are in use so they are not
224 discarded too soon. This is done by using reference counting with file sets.
225
226 A file set is simply an ordered list of index files. When the current file set
227 is obtained from the index, a counter is incremented to track its usage. Once
228 the user is done with the file set, it is released and the counter is
229 decremented. A file cannot be removed from the file system until this counter
230 returns to zero.
231
232 Besides the reference counting, there are no other locking mechanisms when
233 reading or writing index files. Log files, however, do require a lock whenever
234 they are accessed. This is another reason to minimize log file size.
235
236
237 */
238 package tsi1