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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
use std::convert::TryInto;
use std::num::NonZeroUsize;
use std::{cmp, io};
use byteorder::{BigEndian, WriteBytesExt};
use crate::block_writer::BlockWriter;
use crate::compression::{compress, CompressionType};
use crate::count_write::CountWrite;
use crate::metadata::{FileVersion, Metadata};
pub const DEFAULT_BLOCK_SIZE: usize = 8192;
pub const MIN_BLOCK_SIZE: usize = 1024;
/// A struct that is used to configure a [`Writer`].
pub struct WriterBuilder {
compression_type: CompressionType,
compression_level: u32,
index_key_interval: Option<NonZeroUsize>,
block_size: usize,
}
impl Default for WriterBuilder {
fn default() -> WriterBuilder {
WriterBuilder {
compression_type: CompressionType::None,
compression_level: 0,
index_key_interval: None,
block_size: DEFAULT_BLOCK_SIZE,
}
}
}
impl WriterBuilder {
/// Creates a [`WriterBuilder`], it can be used to
/// configure your [`Writer`] to better fit your needs.
pub fn new() -> WriterBuilder {
WriterBuilder::default()
}
/// Defines the [`CompressionType`] that will be used to compress the writer blocks.
pub fn compression_type(&mut self, ctype: CompressionType) -> &mut Self {
self.compression_type = ctype;
self
}
/// Defines the copression level of the defined [`CompressionType`]
/// that will be used to compress the writer blocks.
pub fn compression_level(&mut self, level: u32) -> &mut Self {
self.compression_level = level;
self
}
/// Defines the size of the blocks that the writer will writer.
///
/// The bigger the blocks are the better they are compressed
/// but the more time it takes to compress and decompress them.
pub fn block_size(&mut self, size: usize) -> &mut Self {
self.block_size = cmp::max(MIN_BLOCK_SIZE, size);
self
}
/// The interval at which we store the index of a key in the
/// footer index, used to seek into a block.
pub fn index_key_interval(&mut self, interval: NonZeroUsize) -> &mut Self {
self.index_key_interval = Some(interval);
self
}
/// Creates the [`Writer`] that will write into the provided [`io::Write`] type.
pub fn build<W: io::Write>(&self, writer: W) -> Writer<W> {
let mut block_writer_builder = BlockWriter::builder();
if let Some(interval) = self.index_key_interval {
block_writer_builder.index_key_interval(interval);
}
let mut index_block_writer_builder = BlockWriter::builder();
if let Some(interval) = self.index_key_interval {
index_block_writer_builder.index_key_interval(interval);
}
Writer {
block_writer: block_writer_builder.build(),
index_block_writer: index_block_writer_builder.build(),
compression_type: self.compression_type,
compression_level: self.compression_level,
block_size: self.block_size,
entries_count: 0,
writer: CountWrite::new(writer),
}
}
/// Creates the [`Writer`] that will write into a [`Vec`] of bytes.
pub fn memory(&mut self) -> Writer<Vec<u8>> {
self.build(Vec::new())
}
}
/// A struct you can use to write entries into any [`io::Write`] type,
/// entries must be inserted in key-order.
pub struct Writer<W> {
/// The block writer that is currently storing the key/values entries.
block_writer: BlockWriter,
/// The block writer that associates the offset (big endian u64) of the
/// blocks in the file with the last key of these given blocks.
index_block_writer: BlockWriter,
/// The compression method used to compress individual blocks.
compression_type: CompressionType,
/// The compression level used to compress individual blocks.
compression_level: u32,
/// The amount of bytes to reach before dumping this block on disk.
block_size: usize,
/// The amount of key already inserted.
entries_count: u64,
/// The writer in which we write the block, index block and footer metadata.
writer: CountWrite<W>,
}
impl Writer<Vec<u8>> {
/// Creates a [`Writer`] that will write into a [`Vec`] of bytes.
pub fn memory() -> Writer<Vec<u8>> {
WriterBuilder::new().memory()
}
}
impl Writer<()> {
/// Creates a [`WriterBuilder`], it can be used to configure your [`Writer`].
pub fn builder() -> WriterBuilder {
WriterBuilder::default()
}
}
impl<W: io::Write> Writer<W> {
/// Gets a reference to the underlying writer.
pub fn as_ref(&self) -> &W {
self.writer.as_ref()
}
}
impl<W: io::Write> Writer<W> {
/// Creates a [`Writer`] that will write into the provided [`io::Write`] type.
pub fn new(writer: W) -> Writer<W> {
WriterBuilder::new().build(writer)
}
/// Writes the provided entry into the underlying [`io::Write`] type,
/// key-values must be given in key-order.
pub fn insert<A, B>(&mut self, key: A, val: B) -> io::Result<()>
where
A: AsRef<[u8]>,
B: AsRef<[u8]>,
{
self.block_writer.insert(key.as_ref(), val.as_ref());
self.entries_count += 1;
if self.block_writer.current_size_estimate() >= self.block_size {
// Only write a block if there is at least a key in it.
if let Some(last_key) = self.block_writer.last_key() {
// Get the current offset and last key of the current block,
// write it in the index block writer.
let offset = self.writer.count();
self.index_block_writer.insert(last_key, &offset.to_be_bytes());
compress_and_write_block(
&mut self.writer,
&mut self.block_writer,
self.compression_type,
self.compression_level,
)?;
}
}
Ok(())
}
/// Consumes this [`Writer`] and write the latest block currently being built.
///
/// You must call this method before using the underlying [`io::Write`] type.
pub fn finish(self) -> io::Result<()> {
self.into_inner().map(drop)
}
/// Consumes this [`Writer`] and write the latest block currenty being built.
///
/// Returns the underlying [`io::Write`] provided type.
pub fn into_inner(mut self) -> io::Result<W> {
// Write the last block only if it is not empty.
if let Some(last_key) = self.block_writer.last_key() {
// Get the current offset and last key of the current block,
// write it in the index block writer.
let offset = self.writer.count();
self.index_block_writer.insert(last_key, &offset.to_be_bytes());
compress_and_write_block(
&mut self.writer,
&mut self.block_writer,
self.compression_type,
self.compression_level,
)?;
}
// We must write the index block to the file.
let index_block_offset = self.writer.count();
compress_and_write_block(
&mut self.writer,
&mut self.index_block_writer,
self.compression_type,
self.compression_level,
)?;
// Then we can write the metadata that specify where the index block is stored.
let metadata = Metadata {
file_version: FileVersion::FormatV1,
index_block_offset,
compression_type: self.compression_type,
entries_count: self.entries_count,
};
metadata.write_into(&mut self.writer)?;
self.writer.into_inner()
}
}
/// Compress and write the block into the writer prefixed by the length of it as an `u64`.
fn compress_and_write_block<W: io::Write>(
mut writer: W,
block_writer: &mut BlockWriter,
compression_type: CompressionType,
compression_level: u32,
) -> io::Result<()> {
let buffer = block_writer.finish();
// Compress, write the length of the compressed block then the block itself.
let buffer = compress(compression_type, compression_level, buffer.as_ref())?;
let block_len = buffer.len().try_into().unwrap();
writer.write_u64::<BigEndian>(block_len)?;
writer.write_all(&buffer)?;
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[cfg_attr(miri, ignore)]
fn no_compression() {
let wb = Writer::builder();
let mut writer = wb.build(Vec::new());
for x in 0..2000u32 {
let x = x.to_be_bytes();
writer.insert(&x, &x).unwrap();
}
let bytes = writer.into_inner().unwrap();
assert_ne!(bytes.len(), 0);
}
#[test]
#[cfg_attr(miri, ignore)]
#[cfg(feature = "snappy")]
fn snappy_compression() {
let mut wb = Writer::builder();
wb.compression_type(CompressionType::Snappy);
let mut writer = wb.build(Vec::new());
for x in 0..2000u32 {
let x = x.to_be_bytes();
writer.insert(&x, &x).unwrap();
}
let bytes = writer.into_inner().unwrap();
assert_ne!(bytes.len(), 0);
}
}