Inside Bitcoin

251define a proper subclass of `leveldb::Comparator` that expresses these rules:
252
253```c++
254class TwoPartComparator : public leveldb::Comparator {
255 public:
256  // Three-way comparison function:
257  //   if a < b: negative result
258  //   if a > b: positive result
259  //   else: zero result
260  int Compare(const leveldb::Slice& a, const leveldb::Slice& b) const {
261    int a1, a2, b1, b2;
262    ParseKey(a, &a1, &a2);
263    ParseKey(b, &b1, &b2);
264    if (a1 < b1) return -1;
265    if (a1 > b1) return +1;
266    if (a2 < b2) return -1;
267    if (a2 > b2) return +1;
268    return 0;
269  }
270
271  // Ignore the following methods for now:
272  const char* Name() const { return "TwoPartComparator"; }
273  void FindShortestSeparator(std::string*, const leveldb::Slice&) const {}
274  void FindShortSuccessor(std::string*) const {}
275};
276```
277
278Now create a database using this custom comparator:
279
280```c++
281TwoPartComparator cmp;
282leveldb::DB* db;
283leveldb::Options options;
284options.create_if_missing = true;
285options.comparator = &cmp;
286leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
287...
288```
289
290### Backwards compatibility
291
292The result of the comparator's Name method is attached to the database when it
293is created, and is checked on every subsequent database open. If the name
294changes, the `leveldb::DB::Open` call will fail. Therefore, change the name if
295and only if the new key format and comparison function are incompatible with
296existing databases, and it is ok to discard the contents of all existing
297databases.
298
299You can however still gradually evolve your key format over time with a little
300bit of pre-planning. For example, you could store a version number at the end of
301each key (one byte should suffice for most uses). When you wish to switch to a
302new key format (e.g., adding an optional third part to the keys processed by
303`TwoPartComparator`), (a) keep the same comparator name (b) increment the
304version number for new keys (c) change the comparator function so it uses the
305version numbers found in the keys to decide how to interpret them.
306
307## Performance
308
309Performance can be tuned by changing the default values of the types defined in
310`include/options.h`.
311
312### Block size
313
314leveldb groups adjacent keys together into the same block and such a block is
315the unit of transfer to and from persistent storage. The default block size is
316approximately 4096 uncompressed bytes.  Applications that mostly do bulk scans
317over the contents of the database may wish to increase this size. Applications
318that do a lot of point reads of small values may wish to switch to a smaller
319block size if performance measurements indicate an improvement. There isn't much
320benefit in using blocks smaller than one kilobyte, or larger than a few
321megabytes. Also note that compression will be more effective with larger block
322sizes.
323
324### Compression
325
326Each block is individually compressed before being written to persistent
327storage. Compression is on by default since the default compression method is
328very fast, and is automatically disabled for incompressible data. In rare cases,
329applications may want to disable compression entirely, but should only do so if
330benchmarks show a performance improvement:
331
332```c++
333leveldb::Options options;
334options.compression = leveldb::kNoCompression;
335... leveldb::DB::Open(options, name, ...) ....
336```
337
338### Cache
339
340The contents of the database are stored in a set of files in the filesystem and
341each file stores a sequence of compressed blocks. If options.block_cache is
342non-NULL, it is used to cache frequently used uncompressed block contents.
343
344```c++
345#include "leveldb/cache.h"
346
347leveldb::Options options;
348options.block_cache = leveldb::NewLRUCache(100 * 1048576);  // 100MB cache
349leveldb::DB* db;
350leveldb::DB::Open(options, name, &db);
351... use the db ...
352delete db
353delete options.block_cache;
354```
355
356Note that the cache holds uncompressed data, and therefore it should be sized
357according to application level data sizes, without any reduction from
358compression. (Caching of compressed blocks is left to the operating system
359buffer cache, or any custom Env implementation provided by the client.)
360
361When performing a bulk read, the application may wish to disable caching so that
362the data processed by the bulk read does not end up displacing most of the
363cached contents. A per-iterator option can be used to achieve this:
364
365```c++
366leveldb::ReadOptions options;
367options.fill_cache = false;
368leveldb::Iterator* it = db->NewIterator(options);
369for (it->SeekToFirst(); it->Valid(); it->Next()) {
370  ...
371}
372```
373
374### Key Layout
375
376Note that the unit of disk transfer and caching is a block. Adjacent keys
377(according to the database sort order) will usually be placed in the same block.
378Therefore the application can improve its performance by placing keys that are
379accessed together near each other and placing infrequently used keys in a
380separate region of the key space.
381
382For example, suppose we are implementing a simple file system on top of leveldb.
383The types of entries we might wish to store are:
384
385    filename -> permission-bits, length, list of file_block_ids
386    file_block_id -> data
387
388We might want to prefix filename keys with one letter (say '/') and the
389`file_block_id` keys with a different letter (say '0') so that scans over just
390the metadata do not force us to fetch and cache bulky file contents.
391
392### Filters
393
394Because of the way leveldb data is organized on disk, a single `Get()` call may
395involve multiple reads from disk. The optional FilterPolicy mechanism can be
396used to reduce the number of disk reads substantially.
397
398```c++
399leveldb::Options options;
400options.filter_policy = NewBloomFilterPolicy(10);
401leveldb::DB* db;
402leveldb::DB::Open(options, "/tmp/testdb", &db);
403... use the database ...
404delete db;
405delete options.filter_policy;
406```
407
408The preceding code associates a Bloom filter based filtering policy with the
409database.  Bloom filter based filtering relies on keeping some number of bits of
410data in memory per key (in this case 10 bits per key since that is the argument
411we passed to `NewBloomFilterPolicy`). This filter will reduce the number of
412unnecessary disk reads needed for Get() calls by a factor of approximately
413a 100. Increasing the bits per key will lead to a larger reduction at the cost
414of more memory usage. We recommend that applications whose working set does not
415fit in memory and that do a lot of random reads set a filter policy.
416
417If you are using a custom comparator, you should ensure that the filter policy
418you are using is compatible with your comparator. For example, consider a
419comparator that ignores trailing spaces when comparing keys.
420`NewBloomFilterPolicy` must not be used with such a comparator. Instead, the
421application should provide a custom filter policy that also ignores trailing
422spaces. For example:
423
424```c++
425class CustomFilterPolicy : public leveldb::FilterPolicy {
426 private:
427  FilterPolicy* builtin_policy_;
428
429 public:
430  CustomFilterPolicy() : builtin_policy_(NewBloomFilterPolicy(10)) {}
431  ~CustomFilterPolicy() { delete builtin_policy_; }
432
433  const char* Name() const { return "IgnoreTrailingSpacesFilter"; }
434
435  void CreateFilter(const Slice* keys, int n, std::string* dst) const {
436    // Use builtin bloom filter code after removing trailing spaces
437    std::vector<Slice> trimmed(n);
438    for (int i = 0; i < n; i++) {
439      trimmed[i] = RemoveTrailingSpaces(keys[i]);
440    }
441    return builtin_policy_->CreateFilter(&trimmed[i], n, dst);
442  }
443};
444```
445
446Advanced applications may provide a filter policy that does not use a bloom
447filter but uses some other mechanism for summarizing a set of keys. See
448`leveldb/filter_policy.h` for detail.
449
450## Checksums
451
452leveldb associates checksums with all data it stores in the file system. There
453are two separate controls provided over how aggressively these checksums are
454verified:
455
456`ReadOptions::verify_checksums` may be set to true to force checksum
457verification of all data that is read from the file system on behalf of a
458particular read.  By default, no such verification is done.
459
460`Options::paranoid_checks` may be set to true before opening a database to make
461the database implementation raise an error as soon as it detects an internal
462corruption. Depending on which portion of the database has been corrupted, the
463error may be raised when the database is opened, or later by another database
464operation. By default, paranoid checking is off so that the database can be used
465even if parts of its persistent storage have been corrupted.
466
467If a database is corrupted (perhaps it cannot be opened when paranoid checking
468is turned on), the `leveldb::RepairDB` function may be used to recover as much
469of the data as possible
470
471## Approximate Sizes
472
473The `GetApproximateSizes` method can used to get the approximate number of bytes
474of file system space used by one or more key ranges.
475
476```c++
477leveldb::Range ranges[2];
478ranges[0] = leveldb::Range("a", "c");
479ranges[1] = leveldb::Range("x", "z");
480uint64_t sizes[2];
481leveldb::Status s = db->GetApproximateSizes(ranges, 2, sizes);
482```
483
484The preceding call will set `sizes[0]` to the approximate number of bytes of
485file system space used by the key range `[a..c)` and `sizes[1]` to the
486approximate number of bytes used by the key range `[x..z)`.
487
488## Environment
489
490All file operations (and other operating system calls) issued by the leveldb
491implementation are routed through a `leveldb::Env` object. Sophisticated clients
492may wish to provide their own Env implementation to get better control.
493For example, an application may introduce artificial delays in the file IO
494paths to limit the impact of leveldb on other activities in the system.
495
496```c++
497class SlowEnv : public leveldb::Env {
498  ... implementation of the Env interface ...
499};
500