aboutsummaryrefslogtreecommitdiff
path: root/src/leveldb/doc/impl.html
diff options
context:
space:
mode:
Diffstat (limited to 'src/leveldb/doc/impl.html')
-rw-r--r--src/leveldb/doc/impl.html213
1 files changed, 0 insertions, 213 deletions
diff --git a/src/leveldb/doc/impl.html b/src/leveldb/doc/impl.html
deleted file mode 100644
index 6a468be095..0000000000
--- a/src/leveldb/doc/impl.html
+++ /dev/null
@@ -1,213 +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://research.google.com/archive/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 files 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 4MB 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>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>Create a brand new memtable and log file and direct future updates here
-<li>In the background:
-<ul>
-<li>Write the contents of the previous memtable to an sstable
-<li>Discard the memtable
-<li>Delete the old log file and the old memtable
-<li>Add the new sstable to the young (level-0) level.
-</ul>
-</ul>
-
-<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 than
-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 significantly 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 more memory we will
-need to hold the corresponding memtable.
-
-<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.
-
-</body>
-</html>