diff options
| author | dgrogan@chromium.org <dgrogan@chromium.org@62dab493-f737-651d-591e-8d6aee1b9529> | 2011-04-19 23:01:25 +0000 |
|---|---|---|
| committer | dgrogan@chromium.org <dgrogan@chromium.org@62dab493-f737-651d-591e-8d6aee1b9529> | 2011-04-19 23:01:25 +0000 |
| commit | b743906eeabc925f3e824d91a9747012bf249e2f (patch) | |
| tree | e7cb4f854196c43045756469627920e4e7b146c1 /doc | |
| parent | b409afe968b6917574ec08e02c4bf6e6f722e3ca (diff) | |
| download | leveldb-b743906eeabc925f3e824d91a9747012bf249e2f.tar.gz | |
Revision created by MOE tool push_codebase.
MOE_MIGRATION=
git-svn-id: https://leveldb.googlecode.com/svn/trunk@22 62dab493-f737-651d-591e-8d6aee1b9529
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/doc.css | 89 | ||||
| -rw-r--r-- | doc/impl.html | 228 | ||||
| -rw-r--r-- | doc/index.html | 509 | ||||
| -rw-r--r-- | doc/log_format.txt | 75 | ||||
| -rw-r--r-- | doc/table_format.txt | 61 |
5 files changed, 0 insertions, 962 deletions
diff --git a/doc/doc.css b/doc/doc.css deleted file mode 100644 index 700c564..0000000 --- a/doc/doc.css +++ /dev/null @@ -1,89 +0,0 @@ -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 deleted file mode 100644 index b190d2c..0000000 --- a/doc/impl.html +++ /dev/null @@ -1,228 +0,0 @@ -<!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). We also switch to a new output file when the key -range of the current output file has grown enough to overlap more then -ten level-(L+2) files. This last rule ensures that a later compaction -of a level-(L+1) file will not pick up too much data from level-(L+2). - -<p> -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 deleted file mode 100644 index 2a83fc3..0000000 --- a/doc/index.html +++ /dev/null @@ -1,509 +0,0 @@ -<!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. -<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> - -<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. - -<h1>Synchronous Writes</h1> -By default, each write to <code>leveldb</code> is asynchronous: it -returns after pushing the write from the process into the operating -system. The transfer from operating system memory to the underlying -persistent storage happens asynchronously. The <code>sync</code> flag -can be turned on for a particular write to make the write operation -not return until the data being written has been pushed all the way to -persistent storage. (On Posix systems, this is implemented by calling -either <code>fsync(...)</code> or <code>fdatasync(...)</code> or -<code>msync(..., MS_SYNC)</code> before the write operation returns.) -<pre> - leveldb::WriteOptions write_options; - write_options.sync = true; - db->Put(write_options, ...); -</pre> -Asynchronous writes are often more than a thousand 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 often be used safely. For example, when -loading a large amount of data into the database you can handle lost -updates by restarting the bulk load after a crash. 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. (The synchronous write can update -a marker that describes where to restart on a crash.) - -<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 (i.e., -<code>write_options.sync</code> is set to true). The extra cost of -the synchronous write will be amortized across all of the writes in -the 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 may be somewhat 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>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 4096 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 deleted file mode 100644 index 3a0414b..0000000 --- a/doc/log_format.txt +++ /dev/null @@ -1,75 +0,0 @@ -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 six bytes of a block (since it -won't fit). Any leftover bytes here form the trailer, which must -consist entirely of zero bytes and must be skipped by readers. - -Aside: if exactly seven bytes are left in the current block, and a new -non-zero length record is added, the writer must emit a FIRST record -(which contains zero bytes of user data) to fill up the trailing seven -bytes of the block and then emit all of the user data in subsequent -blocks. - -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 deleted file mode 100644 index ad5aa4b..0000000 --- a/doc/table_format.txt +++ /dev/null @@ -1,61 +0,0 @@ -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 |