Inside Bitcoin

1leveldb
2=======
3
4_Jeff Dean, Sanjay Ghemawat_
5
6The leveldb library provides a persistent key value store. Keys and values are
7arbitrary byte arrays.  The keys are ordered within the key value store
8according to a user-specified comparator function.
9
10## Opening A Database
11
12A leveldb database has a name which corresponds to a file system directory. All
13of the contents of database are stored in this directory. The following example
14shows how to open a database, creating it if necessary:
15
16```c++
17#include <cassert>
18#include "leveldb/db.h"
19
20leveldb::DB* db;
21leveldb::Options options;
22options.create_if_missing = true;
23leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);
24assert(status.ok());
25...
26```
27
28If you want to raise an error if the database already exists, add the following
29line before the `leveldb::DB::Open` call:
30
31```c++
32options.error_if_exists = true;
33```
34
35## Status
36
37You may have noticed the `leveldb::Status` type above. Values of this type are
38returned by most functions in leveldb that may encounter an error. You can check
39if such a result is ok, and also print an associated error message:
40
41```c++
42leveldb::Status s = ...;
43if (!s.ok()) cerr << s.ToString() << endl;
44```
45
46## Closing A Database
47
48When you are done with a database, just delete the database object. Example:
49
50```c++
51... open the db as described above ...
52... do something with db ...
53delete db;
54```
55
56## Reads And Writes
57
58The database provides Put, Delete, and Get methods to modify/query the database.
59For example, the following code moves the value stored under key1 to key2.
60
61```c++
62std::string value;
63leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
64if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);
65if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);
66```
67
68## Atomic Updates
69
70Note that if the process dies after the Put of key2 but before the delete of
71key1, the same value may be left stored under multiple keys. Such problems can
72be avoided by using the `WriteBatch` class to atomically apply a set of updates:
73
74```c++
75#include "leveldb/write_batch.h"
76...
77std::string value;
78leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);
79if (s.ok()) {
80  leveldb::WriteBatch batch;
81  batch.Delete(key1);
82  batch.Put(key2, value);
83  s = db->Write(leveldb::WriteOptions(), &batch);
84}
85```
86
87The `WriteBatch` holds a sequence of edits to be made to the database, and these
88edits within the batch are applied in order. Note that we called Delete before
89Put so that if key1 is identical to key2, we do not end up erroneously dropping
90the value entirely.
91
92Apart from its atomicity benefits, `WriteBatch` may also be used to speed up
93bulk updates by placing lots of individual mutations into the same batch.
94
95## Synchronous Writes
96
97By default, each write to leveldb is asynchronous: it returns after pushing the
98write from the process into the operating system. The transfer from operating
99system memory to the underlying persistent storage happens asynchronously. The
100sync flag can be turned on for a particular write to make the write operation
101not return until the data being written has been pushed all the way to
102persistent storage. (On Posix systems, this is implemented by calling either
103`fsync(...)` or `fdatasync(...)` or `msync(..., MS_SYNC)` before the write
104operation returns.)
105
106```c++
107leveldb::WriteOptions write_options;
108write_options.sync = true;
109db->Put(write_options, ...);
110```
111
112Asynchronous writes are often more than a thousand times as fast as synchronous
113writes. The downside of asynchronous writes is that a crash of the machine may
114cause the last few updates to be lost. Note that a crash of just the writing
115process (i.e., not a reboot) will not cause any loss since even when sync is
116false, an update is pushed from the process memory into the operating system
117before it is considered done.
118
119Asynchronous writes can often be used safely. For example, when loading a large
120amount of data into the database you can handle lost updates by restarting the
121bulk load after a crash. A hybrid scheme is also possible where every Nth write
122is synchronous, and in the event of a crash, the bulk load is restarted just
123after the last synchronous write finished by the previous run. (The synchronous
124write can update a marker that describes where to restart on a crash.)
125
126`WriteBatch` provides an alternative to asynchronous writes. Multiple updates
127may be placed in the same WriteBatch and applied together using a synchronous
128write (i.e., `write_options.sync` is set to true). The extra cost of the
129synchronous write will be amortized across all of the writes in the batch.
130
131## Concurrency
132
133A database may only be opened by one process at a time. The leveldb
134implementation acquires a lock from the operating system to prevent misuse.
135Within a single process, the same `leveldb::DB` object may be safely shared by
136multiple concurrent threads. I.e., different threads may write into or fetch
137iterators or call Get on the same database without any external synchronization
138(the leveldb implementation will automatically do the required synchronization).
139However other objects (like Iterator and `WriteBatch`) may require external
140synchronization. If two threads share such an object, they must protect access
141to it using their own locking protocol. More details are available in the public
142header files.
143
144## Iteration
145
146The following example demonstrates how to print all key,value pairs in a
147database.
148
149```c++
150leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());
151for (it->SeekToFirst(); it->Valid(); it->Next()) {
152  cout << it->key().ToString() << ": "  << it->value().ToString() << endl;
153}
154assert(it->status().ok());  // Check for any errors found during the scan
155delete it;
156```
157
158The following variation shows how to process just the keys in the range
159[start,limit):
160
161```c++
162for (it->Seek(start);
163   it->Valid() && it->key().ToString() < limit;
164   it->Next()) {
165  ...
166}
167```
168
169You can also process entries in reverse order. (Caveat: reverse iteration may be
170somewhat slower than forward iteration.)
171
172```c++
173for (it->SeekToLast(); it->Valid(); it->Prev()) {
174  ...
175}
176```
177
178## Snapshots
179
180Snapshots provide consistent read-only views over the entire state of the
181key-value store.  `ReadOptions::snapshot` may be non-NULL to indicate that a
182read should operate on a particular version of the DB state. If
183`ReadOptions::snapshot` is NULL, the read will operate on an implicit snapshot
184of the current state.
185
186Snapshots are created by the `DB::GetSnapshot()` method:
187
188```c++
189leveldb::ReadOptions options;
190options.snapshot = db->GetSnapshot();
191... apply some updates to db ...
192leveldb::Iterator* iter = db->NewIterator(options);
193... read using iter to view the state when the snapshot was created ...
194delete iter;
195db->ReleaseSnapshot(options.snapshot);
196```
197
198Note that when a snapshot is no longer needed, it should be released using the
199`DB::ReleaseSnapshot` interface. This allows the implementation to get rid of
200state that was being maintained just to support reading as of that snapshot.
201
202## Slice
203
204The return value of the `it->key()` and `it->value()` calls above are instances
205of the `leveldb::Slice` type. Slice is a simple structure that contains a length
206and a pointer to an external byte array. Returning a Slice is a cheaper
207alternative to returning a `std::string` since we do not need to copy
208potentially large keys and values. In addition, leveldb methods do not return
209null-terminated C-style strings since leveldb keys and values are allowed to
210contain `'\0'` bytes.
211
212C++ strings and null-terminated C-style strings can be easily converted to a
213Slice:
214
215```c++
216leveldb::Slice s1 = "hello";
217
218std::string str("world");
219leveldb::Slice s2 = str;
220```
221
222A Slice can be easily converted back to a C++ string:
223
224```c++
225std::string str = s1.ToString();
226assert(str == std::string("hello"));
227```
228
229Be careful when using Slices since it is up to the caller to ensure that the
230external byte array into which the Slice points remains live while the Slice is
231in use. For example, the following is buggy:
232
233```c++
234leveldb::Slice slice;
235if (...) {
236  std::string str = ...;
237  slice = str;
238}
239Use(slice);
240```
241
242When the if statement goes out of scope, str will be destroyed and the backing
243storage for slice will disappear.
244
245## Comparators
246
247The preceding examples used the default ordering function for key, which orders
248bytes lexicographically. You can however supply a custom comparator when opening
249a database.  For example, suppose each database key consists of two numbers and
250we should sort by the first number, breaking ties by the second number. First,