diff options
| author | jorlow@chromium.org <jorlow@chromium.org@62dab493-f737-651d-591e-8d6aee1b9529> | 2011-03-18 22:37:00 +0000 |
|---|---|---|
| committer | jorlow@chromium.org <jorlow@chromium.org@62dab493-f737-651d-591e-8d6aee1b9529> | 2011-03-18 22:37:00 +0000 |
| commit | f67e15e50f392625b4097caf22e8be1b0fe96013 (patch) | |
| tree | 1cb1764c7627f9bac27ed0e0abf27010156e5007 /doc | |
| parent | 54f1fd7eef101db1dfb2bb66a59083c45a38aa4a (diff) | |
| download | leveldb-f67e15e50f392625b4097caf22e8be1b0fe96013.tar.gz | |
Initial checkin.
git-svn-id: https://leveldb.googlecode.com/svn/trunk@2 62dab493-f737-651d-591e-8d6aee1b9529
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/doc.css | 89 | ||||
| -rw-r--r-- | doc/impl.html | 222 | ||||
| -rw-r--r-- | doc/index.html | 508 | ||||
| -rw-r--r-- | doc/log_format.txt | 72 | ||||
| -rw-r--r-- | doc/table_format.txt | 61 |
5 files changed, 952 insertions, 0 deletions
diff --git a/doc/doc.css b/doc/doc.css new file mode 100644 index 0000000..700c564 --- /dev/null +++ b/doc/doc.css @@ -0,0 +1,89 @@ +body { + margin-left: 0.5in; + margin-right: 0.5in; + background: white; + color: black; +} + +h1 { + margin-left: -0.2in; + font-size: 14pt; +} +h2 { + margin-left: -0in; + font-size: 12pt; +} +h3 { + margin-left: -0in; +} +h4 { + margin-left: -0in; +} +hr { + margin-left: -0in; +} + +/* Definition lists: definition term bold */ +dt { + font-weight: bold; +} + +address { + text-align: center; +} +code,samp,var { + color: blue; +} +kbd { + color: #600000; +} +div.note p { + float: right; + width: 3in; + margin-right: 0%; + padding: 1px; + border: 2px solid #6060a0; + background-color: #fffff0; +} + +ul { + margin-top: -0em; + margin-bottom: -0em; +} + +ol { + margin-top: -0em; + margin-bottom: -0em; +} + +UL.nobullets { + list-style-type: none; + list-style-image: none; + margin-left: -1em; +} + +p { + margin: 1em 0 1em 0; + padding: 0 0 0 0; +} + +pre { + line-height: 1.3em; + padding: 0.4em 0 0.8em 0; + margin: 0 0 0 0; + border: 0 0 0 0; + color: blue; +} + +.datatable { + margin-left: auto; + margin-right: auto; + margin-top: 2em; + margin-bottom: 2em; + border: 1px solid; +} + +.datatable td,th { + padding: 0 0.5em 0 0.5em; + text-align: right; +} diff --git a/doc/impl.html b/doc/impl.html new file mode 100644 index 0000000..2f2c809 --- /dev/null +++ b/doc/impl.html @@ -0,0 +1,222 @@ +<!DOCTYPE html> +<html> +<head> +<link rel="stylesheet" type="text/css" href="doc.css" /> +<title>Leveldb file layout and compactions</title> +</head> + +<body> + +<h1>Files</h1> + +The implementation of leveldb is similar in spirit to the +representation of a single +<a href="http://labs.google.com/papers/bigtable.html"> +Bigtable tablet (section 5.3)</a>. +However the organization of the files that make up the representation +is somewhat different and is explained below. + +<p> +Each database is represented by a set of file stored in a directory. +There are several different types of files as documented below: +<p> +<h2>Log files</h2> +<p> +A log file (*.log) stores a sequence of recent updates. Each update +is appended to the current log file. When the log file reaches a +pre-determined size (approximately 1MB by default), it is converted +to a sorted table (see below) and a new log file is created for future +updates. +<p> +A copy of the current log file is kept in an in-memory structure (the +<code>memtable</code>). This copy is consulted on every read so that read +operations reflect all logged updates. +<p> +<h2>Sorted tables</h2> +<p> +A sorted table (*.sst) stores a sequence of entries sorted by key. +Each entry is either a value for the key, or a deletion marker for the +key. (Deletion markers are kept around to hide obsolete values +present in older sorted tables). +<p> +The set of sorted tables are organized into a sequence of levels. The +sorted table generated from a log file is placed in a special <code>young</code> +level (also called level-0). When the number of young files exceeds a +certain threshold (currently four), all of the young files are merged +together with all of the overlapping level-1 files to produce a +sequence of new level-1 files (we create a new level-1 file for every +2MB of data.) +<p> +Files in the young level may contain overlapping keys. However files +in other levels have distinct non-overlapping key ranges. Consider +level number L where L >= 1. When the combined size of files in +level-L exceeds (10^L) MB (i.e., 10MB for level-1, 100MB for level-2, +...), one file in level-L, and all of the overlapping files in +level-(L+1) are merged to form a set of new files for level-(L+1). +These merges have the effect of gradually migrating new updates from +the young level to the largest level using only bulk reads and writes +(i.e., minimizing expensive seeks). + +<h2>Large value files</h2> +<p> +Each large value (greater than 64KB by default) is placed in a large +value file (*.val) of its own. An entry is maintained in the log +and/or sorted tables that maps from the corresponding key to the +name of this large value file. The name of the large value file +is derived from a SHA1 hash of the value and its length so that +identical values share the same file. +<p> +<h2>Manifest</h2> +<p> +A MANIFEST file lists the set of sorted tables that make up each +level, the corresponding key ranges, and other important metadata. +A new MANIFEST file (with a new number embedded in the file name) +is created whenever the database is reopened. The MANIFEST file is +formatted as a log, and changes made to the serving state (as files +are added or removed) are appended to this log. +<p> +<h2>Current</h2> +<p> +CURRENT is a simple text file that contains the name of the latest +MANIFEST file. +<p> +<h2>Info logs</h2> +<p> +Informational messages are printed to files named LOG and LOG.old. +<p> +<h2>Others</h2> +<p> +Other files used for miscellaneous purposes may also be present +(LOCK, *.dbtmp). + +<h1>Level 0</h1> +When the log file grows above a certain size (1MB by default): +<ul> +<li>Write the contents of the current memtable to an sstable +<li>Replace the current memtable by a brand new empty memtable +<li>Switch to a new log file +<li>Delete the old log file and the old memtable +</ul> +Experimental measurements show that generating an sstable from a 1MB +log file takes ~12ms, which seems like an acceptable latency hiccup to +add infrequently to a log write. + +<p> +The new sstable is added to a special level-0 level. level-0 contains +a set of files (up to 4 by default). However unlike other levels, +these files do not cover disjoint ranges, but may overlap each other. + +<h1>Compactions</h1> + +<p> +When the size of level L exceeds its limit, we compact it in a +background thread. The compaction picks a file from level L and all +overlapping files from the next level L+1. Note that if a level-L +file overlaps only part of a level-(L+1) file, the entire file at +level-(L+1) is used as an input to the compaction and will be +discarded after the compaction. Aside: because level-0 is special +(files in it may overlap each other), we treat compactions from +level-0 to level-1 specially: a level-0 compaction may pick more than +one level-0 file in case some of these files overlap each other. + +<p> +A compaction merges the contents of the picked files to produce a +sequence of level-(L+1) files. We switch to producing a new +level-(L+1) file after the current output file has reached the target +file size (2MB). The old files are discarded and the new files are +added to the serving state. + +<p> +Compactions for a particular level rotate through the key space. In +more detail, for each level L, we remember the ending key of the last +compaction at level L. The next compaction for level L will pick the +first file that starts after this key (wrapping around to the +beginning of the key space if there is no such file). + +<p> +Compactions drop overwritten values. They also drop deletion markers +if there are no higher numbered levels that contain a file whose range +overlaps the current key. + +<h2>Timing</h2> + +Level-0 compactions will read up to four 1MB files from level-0, and +at worst all the level-1 files (10MB). I.e., we will read 14MB and +write 14MB. + +<p> +Other than the special level-0 compactions, we will pick one 2MB file +from level L. In the worst case, this will overlap ~ 12 files from +level L+1 (10 because level-(L+1) is ten times the size of level-L, +and another two at the boundaries since the file ranges at level-L +will usually not be aligned with the file ranges at level-L+1). The +compaction will therefore read 26MB and write 26MB. Assuming a disk +IO rate of 100MB/s (ballpark range for modern drives), the worst +compaction cost will be approximately 0.5 second. + +<p> +If we throttle the background writing to something small, say 10% of +the full 100MB/s speed, a compaction may take up to 5 seconds. If the +user is writing at 10MB/s, we might build up lots of level-0 files +(~50 to hold the 5*10MB). This may signficantly increase the cost of +reads due to the overhead of merging more files together on every +read. + +<p> +Solution 1: To reduce this problem, we might want to increase the log +switching threshold when the number of level-0 files is large. Though +the downside is that the larger this threshold, the larger the delay +that we will add to write latency when a write triggers a log switch. + +<p> +Solution 2: We might want to decrease write rate artificially when the +number of level-0 files goes up. + +<p> +Solution 3: We work on reducing the cost of very wide merges. +Perhaps most of the level-0 files will have their blocks sitting +uncompressed in the cache and we will only need to worry about the +O(N) complexity in the merging iterator. + +<h2>Number of files</h2> + +Instead of always making 2MB files, we could make larger files for +larger levels to reduce the total file count, though at the expense of +more bursty compactions. Alternatively, we could shard the set of +files into multiple directories. + +<p> +An experiment on an <code>ext3</code> filesystem on Feb 04, 2011 shows +the following timings to do 100K file opens in directories with +varying number of files: +<table class="datatable"> +<tr><th>Files in directory</th><th>Microseconds to open a file</th></tr> +<tr><td>1000</td><td>9</td> +<tr><td>10000</td><td>10</td> +<tr><td>100000</td><td>16</td> +</table> +So maybe even the sharding is not necessary on modern filesystems? + +<h1>Recovery</h1> + +<ul> +<li> Read CURRENT to find name of the latest committed MANIFEST +<li> Read the named MANIFEST file +<li> Clean up stale files +<li> We could open all sstables here, but it is probably better to be lazy... +<li> Convert log chunk to a new level-0 sstable +<li> Start directing new writes to a new log file with recovered sequence# +</ul> + +<h1>Garbage collection of files</h1> + +<code>DeleteObsoleteFiles()</code> is called at the end of every +compaction and at the end of recovery. It finds the names of all +files in the database. It deletes all log files that are not the +current log file. It deletes all table files that are not referenced +from some level and are not the output of an active compaction. It +deletes all large value files that are not referenced from any live +table or log file. + +</body> +</html> diff --git a/doc/index.html b/doc/index.html new file mode 100644 index 0000000..53471d2 --- /dev/null +++ b/doc/index.html @@ -0,0 +1,508 @@ +<!DOCTYPE html> +<html> +<head> +<link rel="stylesheet" type="text/css" href="doc.css" /> +<title>Leveldb</title> +</head> + +<body> +<h1>Leveldb</h1> +<address>Jeff Dean, Sanjay Ghemawat</address> +<p> +The <code>leveldb</code> library provides a persistent key value store. Keys and +values are arbitrary byte arrays. The keys are ordered within the key +value store according to a user-specified comparator function. + +<p> +<h1>Opening A Database</h1> +<p> +A <code>leveldb</code> database has a name which corresponds to a file system +directory. All of the contents of database are stored in this +directory. The following example shows how to open a database, +creating it if necessary: +<p> +<pre> + #include <assert> + #include "leveldb/include/db.h" + + leveldb::DB* db; + leveldb::Options options; + options.create_if_missing = true; + leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db); + assert(status.ok()); + ... +</pre> +If you want to raise an error if the database already exists, add +the following line before the <code>leveldb::DB::Open</code> call: +<pre> + options.error_if_exists = true; +</pre> +<h1>Status</h1> +<p> +You may have noticed the <code>leveldb::Status</code> type above. Values of this +type are returned by most functions in <code>leveldb</code> that may encounter an +error. You can check if such a result is ok, and also print an +associated error message: +<p> +<pre> + leveldb::Status s = ...; + if (!s.ok()) cerr << s.ToString() << endl; +</pre> +<h1>Closing A Database</h1> +<p> +When you are done with a database, just delete the database object. +Example: +<p> +<pre> + ... open the db as described above ... + ... do something with db ... + delete db; +</pre> +<h1>Reads And Writes</h1> +<p> +The database provides <code>Put</code>, <code>Delete</code>, and <code>Get</code> methods to +modify/query the database. For example, the following code +moves the value stored under key1 to key2. +<p> +<pre> + std::string value; + leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value); + if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value); + if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1); +</pre> +See <a href="#async">important performance note</a> below for how to +speed up writes significantly. + +<h1>Atomic Updates</h1> +<p> +Note that if the process dies after the Put of key2 but before the +delete of key1, the same value may be left stored under multiple keys. +Such problems can be avoided by using the <code>WriteBatch</code> class to +atomically apply a set of updates: +<p> +<pre> + #include "leveldb/include/write_batch.h" + ... + std::string value; + leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value); + if (s.ok()) { + leveldb::WriteBatch batch; + batch.Delete(key1); + batch.Put(key2, value); + s = db->Write(leveldb::WriteOptions(), &batch); + } +</pre> +The <code>WriteBatch</code> holds a sequence of edits to be made to the database, +and these edits within the batch are applied in order. Note that we +called <code>Delete</code> before <code>Put</code> so that if <code>key1</code> is identical to <code>key2</code>, +we do not end up erroneously dropping the value entirely. +<p> +Apart from its atomicity benefits, <code>WriteBatch</code> may also be used to +speed up bulk updates by placing lots of individual mutations into the +same batch. +<p> +<h1>Concurrency</h1> +<p> +A database may only be opened by one process at a time. The <code>leveldb</code> +implementation acquires a lock from the operating system to prevent +misuse. Within a single process, the same <code>leveldb::DB</code> object may +be safely used by multiple concurrent threads. +<p> +<h1>Iteration</h1> +<p> +The following example demonstrates how to print all key,value pairs +in a database. +<p> +<pre> + leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions()); + for (it->SeekToFirst(); it->Valid(); it->Next()) { + cout << it->key().ToString() << ": " << it->value().ToString() << endl; + } + assert(it->status().ok()); // Check for any errors found during the scan + delete it; +</pre> +The following variation shows how to process just the keys in the +range <code>[start,limit)</code>: +<p> +<pre> + for (it->Seek(start); + it->Valid() && it->key().ToString() < limit; + it->Next()) { + ... + } +</pre> +You can also process entries in reverse order. (Caveat: reverse +iteration is currently a factor of two or three slower than forward +iteration.) +<p> +<pre> + for (it->SeekToLast(); it->Valid(); it->Prev()) { + ... + } +</pre> +<h1>Snapshots</h1> +<p> +Snapshots provide consistent read-only views over the entire state of +the key-value store. <code>ReadOptions::snapshot</code> may be non-NULL to indicate +that a read should operate on a particular version of the DB state. +If <code>ReadOptions::snapshot</code> is NULL, the read will operate on an +implicit snapshot of the current state. +<p> +Snapshots typically are created by the DB::GetSnapshot() method: +<p> +<pre> + leveldb::ReadOptions options; + options.snapshot = db->GetSnapshot(); + ... apply some updates to db ... + leveldb::Iterator* iter = db->NewIterator(options); + ... read using iter to view the state when the snapshot was created ... + delete iter; + db->ReleaseSnapshot(options.snapshot); +</pre> +Note that when a snapshot is no longer needed, it should be released +using the DB::ReleaseSnapshot interface. This allows the +implementation to get rid of state that was being maintained just to +support reading as of that snapshot. +<p> +A Write operation can also return a snapshot that +represents the state of the database just after applying a particular +set of updates: +<p> +<pre> + leveldb::Snapshot* snapshot; + leveldb::WriteOptions write_options; + write_options.post_write_snapshot = &snapshot; + leveldb::Status status = db->Write(write_options, ...); + ... perform other mutations to db ... + + leveldb::ReadOptions read_options; + read_options.snapshot = snapshot; + leveldb::Iterator* iter = db->NewIterator(read_options); + ... read as of the state just after the Write call returned ... + delete iter; + + db->ReleaseSnapshot(snapshot); +</pre> +<h1>Slice</h1> +<p> +The return value of the <code>it->key()</code> and <code>it->value()</code> calls above +are instances of the <code>leveldb::Slice</code> type. <code>Slice</code> is a simple +structure that contains a length and a pointer to an external byte +array. Returning a <code>Slice</code> is a cheaper alternative to returning a +<code>std::string</code> since we do not need to copy potentially large keys and +values. In addition, <code>leveldb</code> methods do not return null-terminated +C-style strings since <code>leveldb</code> keys and values are allowed to +contain '\0' bytes. +<p> +C++ strings and null-terminated C-style strings can be easily converted +to a Slice: +<p> +<pre> + leveldb::Slice s1 = "hello"; + + std::string str("world"); + leveldb::Slice s2 = str; +</pre> +A Slice can be easily converted back to a C++ string: +<pre> + std::string str = s1.ToString(); + assert(str == std::string("hello")); +</pre> +Be careful when using Slices since it is up to the caller to ensure that +the external byte array into which the Slice points remains live while +the Slice is in use. For example, the following is buggy: +<p> +<pre> + leveldb::Slice slice; + if (...) { + std::string str = ...; + slice = str; + } + Use(slice); +</pre> +When the <code>if</code> statement goes out of scope, <code>str</code> will be destroyed and the +backing storage for <code>slice</code> will disappear. +<p> +<h1>Comparators</h1> +<p> +The preceding examples used the default ordering function for key, +which orders bytes lexicographically. You can however supply a custom +comparator when opening a database. For example, suppose each +database key consists of two numbers and we should sort by the first +number, breaking ties by the second number. First, define a proper +subclass of <code>leveldb::Comparator</code> that expresses these rules: +<p> +<pre> + class TwoPartComparator : public leveldb::Comparator { + public: + // Three-way comparison function: + // if a < b: negative result + // if a > b: positive result + // else: zero result + int Compare(const leveldb::Slice& a, const leveldb::Slice& b) const { + int a1, a2, b1, b2; + ParseKey(a, &a1, &a2); + ParseKey(b, &b1, &b2); + if (a1 < b1) return -1; + if (a1 > b1) return +1; + if (a2 < b2) return -1; + if (a2 > b2) return +1; + return 0; + } + + // Ignore the following methods for now: + const char* Name() { return "TwoPartComparator"; } + void FindShortestSeparator(std::string*, const leveldb::Slice&) const { } + void FindShortSuccessor(std::string*) const { } + }; +</pre> +Now create a database using this custom comparator: +<p> +<pre> + TwoPartComparator cmp; + leveldb::DB* db; + leveldb::Options options; + options.create_if_missing = true; + options.comparator = &cmp; + leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db); + ... +</pre> +<h2>Backwards compatibility</h2> +<p> +The result of the comparator's <code>Name</code> method is attached to the +database when it is created, and is checked on every subsequent +database open. If the name changes, the <code>leveldb::DB::Open</code> call will +fail. Therefore, change the name if and only if the new key format +and comparison function are incompatible with existing databases, and +it is ok to discard the contents of all existing databases. +<p> +You can however still gradually evolve your key format over time with +a little bit of pre-planning. For example, you could store a version +number at the end of each key (one byte should suffice for most uses). +When you wish to switch to a new key format (e.g., adding an optional +third part to the keys processed by <code>TwoPartComparator</code>), +(a) keep the same comparator name (b) increment the version number +for new keys (c) change the comparator function so it uses the +version numbers found in the keys to decide how to interpret them. +<p> +<h1>Performance</h1> +<p> +Performance can be tuned by changing the default values of the +types defined in <code>leveldb/include/options.h</code>. + +<p> +<h2><a name="async">Asynchronous Writes</a></h2> + +By default, each write to <code>leveldb</code> is synchronous: it does +not return until the write has been pushed from memory to persistent +storage. (On Posix systems, this is implemented by calling either +<code>fdatasync(...)</code> or <code>msync(..., MS_SYNC)</code>.) +<strong>Synchronous writes may be very slow and the synchrony can be +optionally disabled</strong>: +<pre> + leveldb::WriteOptions write_options; + write_options.sync = false; + db->Put(write_options, ...); +</pre> +Asynchronous writes are often more than a hundred times as fast as +synchronous writes. The downside of asynchronous writes is that a +crash of the machine may cause the last few updates to be lost. Note +that a crash of just the writing process (i.e., not a reboot) will not +cause any loss since even when <code>sync</code> is false, an update +is pushed from the process memory into the operating system before it +is considered done. + +<p> +Asynchronous writes can be particularly beneficial when loading a +large amount of data into the database since you can mitigate the +problem of lost updates by restarting the bulk load. A hybrid scheme +is also possible where every Nth write is synchronous, and in the +event of a crash, the bulk load is restarted just after the last +synchronous write finished by the previous run. + +<p> +<code>WriteBatch</code> provides an alternative to asynchronous writes. +Multiple updates may be placed in the same <code>WriteBatch</code> and +applied together using a synchronous write. The extra cost of the +synchronous write will be amortized across all of the writes in the batch. + +<p> +<h2>Block size</h2> +<p> +<code>leveldb</code> groups adjacent keys together into the same block and such a +block is the unit of transfer to and from persistent storage. The +default block size is approximately 8192 uncompressed bytes. +Applications that mostly do bulk scans over the contents of the +database may wish to increase this size. Applications that do a lot +of point reads of small values may wish to switch to a smaller block +size if performance measurements indicate an improvement. There isn't +much benefit in using blocks smaller than one kilobyte, or larger than +a few megabytes. Also note that compression will be more effective +with larger block sizes. +<p> +<h2>Compression</h2> +<p> +Each block is individually compressed before being written to +persistent storage. Compression is on by default since the default +compression method is very fast, and is automatically disabled for +uncompressible data. In rare cases, applications may want to disable +compression entirely, but should only do so if benchmarks show a +performance improvement: +<p> +<pre> + leveldb::Options options; + options.compression = leveldb::kNoCompression; + ... leveldb::DB::Open(options, name, ...) .... +</pre> +<h2>Cache</h2> +<p> +The contents of the database are stored in a set of files in the +filesystem and each file stores a sequence of compressed blocks. If +<code>options.cache</code> is non-NULL, it is used to cache frequently used +uncompressed block contents. +<p> +<pre> + #include "leveldb/include/cache.h" + + leveldb::Options options; + options.cache = leveldb::NewLRUCache(100 * 1048576); // 100MB cache + leveldb::DB* db; + leveldb::DB::Open(options, name, &db); + ... use the db ... + delete db + delete options.cache; +</pre> +Note that the cache holds uncompressed data, and therefore it should +be sized according to application level data sizes, without any +reduction from compression. (Caching of compressed blocks is left to +the operating system buffer cache, or any custom <code>Env</code> +implementation provided by the client.) +<p> +When performing a bulk read, the application may wish to disable +caching so that the data processed by the bulk read does not end up +displacing most of the cached contents. A per-iterator option can be +used to achieve this: +<p> +<pre> + leveldb::ReadOptions options; + options.fill_cache = false; + leveldb::Iterator* it = db->NewIterator(options); + for (it->SeekToFirst(); it->Valid(); it->Next()) { + ... + } +</pre> +<h2>Key Layout</h2> +<p> +Note that the unit of disk transfer and caching is a block. Adjacent +keys (according to the database sort order) will usually be placed in +the same block. Therefore the application can improve its performance +by placing keys that are accessed together near each other and placing +infrequently used keys in a separate region of the key space. +<p> +For example, suppose we are implementing a simple file system on top +of <code>leveldb</code>. The types of entries we might wish to store are: +<p> +<pre> + filename -> permission-bits, length, list of file_block_ids + file_block_id -> data +</pre> +We might want to prefix <code>filename</code> keys with one letter (say '/') and the +<code>file_block_id</code> keys with a different letter (say '0') so that scans +over just the metadata do not force us to fetch and cache bulky file +contents. +<p> +<h2>Large Values</h2> +<p> +<code>leveldb</code> has special treatment of large values (by default, a value +of length greater than or equal to 64K is considered large, though a +field in Options can be used to adjust this threshold). Each such +large value is placed in a separate operating system file, and the +normal database blocks just contain pointers to such files. +<p> +Furthermore, if the same large value occurs multiple times in a single +database, it will be stored just once. +<p> +<h1>Checksums</h1> +<p> +<code>leveldb</code> associates checksums with all data it stores in the file system. +There are two separate controls provided over how aggressively these +checksums are verified: +<p> +<ul> +<li> <code>ReadOptions::verify_checksums</code> may be set to true to force + checksum verification of all data that is read from the file system on + behalf of a particular read. By default, no such verification is + done. +<p> +<li> <code>Options::paranoid_checks</code> may be set to true before opening a + database to make the database implementation raise an error as soon as + it detects an internal corruption. Depending on which portion of the + database has been corrupted, the error may be raised when the database + is opened, or later by another database operation. By default, + paranoid checking is off so that the database can be used even if + parts of its persistent storage have been corrupted. +<p> + If a database is corrupted (perhaps it cannot be opened when + paranoid checking is turned on), the <code>leveldb::RepairDB</code> function + may be used to recover as much of the data as possible +<p> +</ul> +<h1>Approximate Sizes</h1> +<p> +The <code>GetApproximateSizes</code> method can used to get the approximate +number of bytes of file system space used by one or more key ranges. +<p> +<pre> + leveldb::Range ranges[2]; + ranges[0] = leveldb::Range("a", "c"); + ranges[1] = leveldb::Range("x", "z"); + uint64_t sizes[2]; + leveldb::Status s = db->GetApproximateSizes(ranges, 2, sizes); +</pre> +The preceding call will set <code>sizes[0]</code> to the approximate number of +bytes of file system space used by the key range <code>[a..c)</code> and +<code>sizes[1]</code> to the approximate number of bytes used by the key range +<code>[x..z)</code>. +<p> +<h1>Environment</h1> +<p> +All file operations (and other operating system calls) issued by the +<code>leveldb</code> implementation are routed through a <code>leveldb::Env</code> object. +Sophisticated clients may wish to provide their own <code>Env</code> +implementation to get better control. For example, an application may +introduce artificial delays in the file IO paths to limit the impact +of <code>leveldb</code> on other activities in the system. +<p> +<pre> + class SlowEnv : public leveldb::Env { + .. implementation of the Env interface ... + }; + + SlowEnv env; + leveldb::Options options; + options.env = &env; + Status s = leveldb::DB::Open(options, ...); +</pre> +<h1>Porting</h1> +<p> +<code>leveldb</code> may be ported to a new platform by providing platform +specific implementations of the types/methods/functions exported by +<code>leveldb/port/port.h</code>. See <code>leveldb/port/port_example.h</code> for more +details. +<p> +In addition, the new platform may need a new default <code>leveldb::Env</code> +implementation. See <code>leveldb/util/env_posix.h</code> for an example. + +<h1>Other Information</h1> + +<p> +Details about the <code>leveldb</code> implementation may be found in +the following documents: +<ul> +<li> <a href="impl.html">Implementation notes</a> +<li> <a href="table_format.txt">Format of an immutable Table file</a> +<li> <a href="log_format.txt">Format of a log file</a> +</ul> + +</body> +</html> diff --git a/doc/log_format.txt b/doc/log_format.txt new file mode 100644 index 0000000..9a801d4 --- /dev/null +++ b/doc/log_format.txt @@ -0,0 +1,72 @@ +The log file contents are a sequence of 32KB blocks. The only +exception is that the tail of the file may contain a partial block. + +Each block consists of a sequence of records: + block := record* trailer? + record := + checksum: uint32 // crc32c of type and data[] + length: uint16 + type: uint8 // One of FULL, FIRST, MIDDLE, LAST + data: uint8[length] + +A record never starts within the last seven bytes of a block. Any +leftover bytes here form the trailer, which must consist entirely of +zero bytes and must be skipped by readers. In particular, even if +there are exactly seven bytes left in the block, and a zero-length +user record is added (which will fit in these seven bytes), the writer +must skip these trailer bytes and add the record to the next block. + +More types may be added in the future. Some Readers may skip record +types they do not understand, others may report that some data was +skipped. + +FULL == 1 +FIRST == 2 +MIDDLE == 3 +LAST == 4 + +The FULL record contains the contents of an entire user record. + +FIRST, MIDDLE, LAST are types used for user records that have been +split into multiple fragments (typically because of block boundaries). +FIRST is the type of the first fragment of a user record, LAST is the +type of the last fragment of a user record, and MID is the type of all +interior fragments of a user record. + +Example: consider a sequence of user records: + A: length 1000 + B: length 97270 + C: length 8000 +A will be stored as a FULL record in the first block. + +B will be split into three fragments: first fragment occupies the rest +of the first block, second fragment occupies the entirety of the +second block, and the third fragment occupies a prefix of the third +block. This will leave six bytes free in the third block, which will +be left empty as the trailer. + +C will be stored as a FULL record in the fourth block. + +=================== + +Some benefits over the recordio format: + +(1) We do not need any heuristics for resyncing - just go to next +block boundary and scan. If there is a corruption, skip to the next +block. As a side-benefit, we do not get confused when part of the +contents of one log file are embedded as a record inside another log +file. + +(2) Splitting at approximate boundaries (e.g., for mapreduce) is +simple: find the next block boundary and skip records until we +hit a FULL or FIRST record. + +(3) We do not need extra buffering for large records. + +Some downsides compared to recordio format: + +(1) No packing of tiny records. This could be fixed by adding a new +record type, so it is a shortcoming of the current implementation, +not necessarily the format. + +(2) No compression. Again, this could be fixed by adding new record types. diff --git a/doc/table_format.txt b/doc/table_format.txt new file mode 100644 index 0000000..ad5aa4b --- /dev/null +++ b/doc/table_format.txt @@ -0,0 +1,61 @@ +File format +=========== + + <beginning_of_file> + [data block 1] + [data block 2] + ... + [data block N] + [meta block 1] + ... + [meta block K] + [metaindex block] + [index block] + [Footer] (fixed size; starts at file_size - sizeof(Footer)) + <end_of_file> + +The file contains internal pointers. Each such pointer is called +a BlockHandle and contains the following information: + offset: varint64 + size: varint64 + +(1) The sequence of key/value pairs in the file are stored in sorted +order and partitioned into a sequence of data blocks. These blocks +come one after another at the beginning of the file. Each data block +is formatted according to the code in block_builder.cc, and then +optionally compressed. + +(2) After the data blocks we store a bunch of meta blocks. The +supported meta block types are described below. More meta block types +may be added in the future. Each meta block is again formatted using +block_builder.cc and then optionally compressed. + +(3) A "metaindex" block. It contains one entry for every other meta +block where the key is the name of the meta block and the value is a +BlockHandle pointing to that meta block. + +(4) An "index" block. This block contains one entry per data block, +where the key is a string >= last key in that data block and before +the first key in the successive data block. The value is the +BlockHandle for the data block. + +(6) At the very end of the file is a fixed length footer that contains +the BlockHandle of the metaindex and index blocks as well as a magic number. + metaindex_handle: char[p]; // Block handle for metaindex + index_handle: char[q]; // Block handle for index + padding: char[40-p-q]; // 0 bytes to make fixed length + // (40==2*BlockHandle::kMaxEncodedLength) + magic: fixed64; // == 0xdb4775248b80fb57 + +"stats" Meta Block +------------------ + +This meta block contains a bunch of stats. The key is the name +of the statistic. The value contains the statistic. +TODO(postrelease): record following stats. + data size + index size + key size (uncompressed) + value size (uncompressed) + number of entries + number of data blocks |