| 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 |