1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
// Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.
#pragma once
#ifndef ROCKSDB_LITE
#include <stdint.h>
#include <memory>
#include <string>
#include "rocksdb/table.h"
namespace ROCKSDB_NAMESPACE {
struct EnvOptions;
class Status;
class RandomAccessFile;
class WritableFile;
class Table;
class TableBuilder;
// PlainTableFactory is the entrance function to the PlainTable format of
// SST files. It returns instances PlainTableBuilder as the builder
// class and PlainTableReader as the reader class, where the format is
// actually implemented.
//
// The PlainTable is designed for memory-mapped file systems, e.g. tmpfs.
// Data is not organized in blocks, which allows fast access. Because of
// following downsides
// 1. Data compression is not supported.
// 2. Data is not checksumed.
// it is not recommended to use this format on other type of file systems.
//
// PlainTable requires fixed length key, configured as a constructor
// parameter of the factory class. Output file format:
// +-------------+-----------------+
// | version | user_key_length |
// +------------++------------+-----------------+ <= key1 offset
// | encoded key1 | value_size | |
// +------------+-------------+-------------+ |
// | value1 |
// | |
// +--------------------------+-------------+---+ <= key2 offset
// | encoded key2 | value_size | |
// +------------+-------------+-------------+ |
// | value2 |
// | |
// | ...... |
// +-----------------+--------------------------+
//
// When the key encoding type is kPlain. Key part is encoded as:
// +------------+--------------------+
// | [key_size] | internal key |
// +------------+--------------------+
// for the case of user_key_len = kPlainTableVariableLength case,
// and simply:
// +----------------------+
// | internal key |
// +----------------------+
// for user_key_len != kPlainTableVariableLength case.
//
// If key encoding type is kPrefix. Keys are encoding in this format.
// There are three ways to encode a key:
// (1) Full Key
// +---------------+---------------+-------------------+
// | Full Key Flag | Full Key Size | Full Internal Key |
// +---------------+---------------+-------------------+
// which simply encodes a full key
//
// (2) A key shared the same prefix as the previous key, which is encoded as
// format of (1).
// +-------------+-------------+-------------+-------------+------------+
// | Prefix Flag | Prefix Size | Suffix Flag | Suffix Size | Key Suffix |
// +-------------+-------------+-------------+-------------+------------+
// where key is the suffix part of the key, including the internal bytes.
// the actual key will be constructed by concatenating prefix part of the
// previous key, with the suffix part of the key here, with sizes given here.
//
// (3) A key shared the same prefix as the previous key, which is encoded as
// the format of (2).
// +-----------------+-----------------+------------------------+
// | Key Suffix Flag | Key Suffix Size | Suffix of Internal Key |
// +-----------------+-----------------+------------------------+
// The key will be constructed by concatenating previous key's prefix (which is
// also a prefix which the last key encoded in the format of (1)) and the
// key given here.
//
// For example, we for following keys (prefix and suffix are separated by
// spaces):
// 0000 0001
// 0000 00021
// 0000 0002
// 00011 00
// 0002 0001
// Will be encoded like this:
// FK 8 00000001
// PF 4 SF 5 00021
// SF 4 0002
// FK 7 0001100
// FK 8 00020001
// (where FK means full key flag, PF means prefix flag and SF means suffix flag)
//
// All those "key flag + key size" shown above are in this format:
// The 8 bits of the first byte:
// +----+----+----+----+----+----+----+----+
// | Type | Size |
// +----+----+----+----+----+----+----+----+
// Type indicates: full key, prefix, or suffix.
// The last 6 bits are for size. If the size bits are not all 1, it means the
// size of the key. Otherwise, varint32 is read after this byte. This varint
// value + 0x3F (the value of all 1) will be the key size.
//
// For example, full key with length 16 will be encoded as (binary):
// 00 010000
// (00 means full key)
// and a prefix with 100 bytes will be encoded as:
// 01 111111 00100101
// (63) (37)
// (01 means key suffix)
//
// All the internal keys above (including kPlain and kPrefix) are encoded in
// this format:
// There are two types:
// (1) normal internal key format
// +----------- ...... -------------+----+---+---+---+---+---+---+---+
// | user key |type| sequence ID |
// +----------- ..... --------------+----+---+---+---+---+---+---+---+
// (2) Special case for keys whose sequence ID is 0 and is value type
// +----------- ...... -------------+----+
// | user key |0x80|
// +----------- ..... --------------+----+
// To save 7 bytes for the special case where sequence ID = 0.
//
//
class PlainTableFactory : public TableFactory {
public:
~PlainTableFactory() {}
// user_key_len is the length of the user key. If it is set to be
// kPlainTableVariableLength, then it means variable length. Otherwise, all
// the keys need to have the fix length of this value. bloom_bits_per_key is
// number of bits used for bloom filer per key. hash_table_ratio is
// the desired utilization of the hash table used for prefix hashing.
// hash_table_ratio = number of prefixes / #buckets in the hash table
// hash_table_ratio = 0 means skip hash table but only replying on binary
// search.
// index_sparseness determines index interval for keys
// inside the same prefix. It will be the maximum number of linear search
// required after hash and binary search.
// index_sparseness = 0 means index for every key.
// huge_page_tlb_size determines whether to allocate hash indexes from huge
// page TLB and the page size if allocating from there. See comments of
// Arena::AllocateAligned() for details.
explicit PlainTableFactory(
const PlainTableOptions& _table_options = PlainTableOptions());
// Method to allow CheckedCast to work for this class
static const char* kClassName() { return kPlainTableName(); }
const char* Name() const override { return kPlainTableName(); }
using TableFactory::NewTableReader;
Status NewTableReader(const ReadOptions& ro,
const TableReaderOptions& table_reader_options,
std::unique_ptr<RandomAccessFileReader>&& file,
uint64_t file_size, std::unique_ptr<TableReader>* table,
bool prefetch_index_and_filter_in_cache) const override;
TableBuilder* NewTableBuilder(
const TableBuilderOptions& table_builder_options,
WritableFileWriter* file) const override;
std::string GetPrintableOptions() const override;
static const char kValueTypeSeqId0 = char(~0);
private:
PlainTableOptions table_options_;
};
} // namespace ROCKSDB_NAMESPACE
#endif // ROCKSDB_LITE
|
