Version 10.0.2
Glossary of Terms

WiredTiger has a lot of domain specific nomenclature - this page attempts to decode it. This is intended for those navigating the WiredTiger source tree - it describes terms internal to the storage engine.

The definitions list how the terms are used in WiredTiger, which may not match how they are used in other settings.


(click headings to sort)

address cookieblock manageran opaque set of bytes returned by the block manager to reference a block in a Btree file, it includes an offset, size, checksum, and object id.
atomicitytransactionsa guarantee provided within the context of a transaction that all operations made within that transaction either succeed or fail.
barriergenerala call that forces the CPU and compiler to enforce ordering constraints on memory operations, used in multithreaded code.
blockblock managerthe smallest granularity of data that is read from or written to a Btree file. A btree page, when it appears on disk, may consist of one or more blocks.
block compressionbtreeafter pages of btrees are encoded to be written, they may be compressed according to a configured algorithm. Compressors may be added to WiredTiger via the extension mechanism.
block managerblock manageran internal API that abstracts writing, reading and allocating blocks to and from files. A block manager is associated with a Btree.
Bloom filterlsma data structure that identifies that a key cannot be present. Used by LSM.
btreebtreea data structure on disk or in memory that stores keys, it with its associated value. In WiredTiger, all btrees are in fact B+trees, meaning that adjacent keys and values are grouped into pages.
bulk insertbtreethe capability to rapidly insert a set of ordered key value pairs into a Btree. In WiredTiger, a Btree's dhandle must be obtained exclusively, guaranteeing that the inserts can be done single threaded.
cellfile formata key or value packed as it appears on disk for a Btree.
checkpointcheckpointa stable point that bounds how much work recovery must do. Data committed before a checkpoint is guaranteed to reside in data files. Thus, recovery must replay log files starting at the last completed checkpoint.
chunklsma single file within an LSM tree.
collatorgenerala comparison function that determines how keys will be ordered in a Btree. The default collator is byte oriented. A custom collator may be packaged as an extension and attached to a Btree.
columnschemaa single field in a record, which must be unpacked from a raw key or value.
column groupschemaa set of column store Btrees, whose record ids logically correspond. Together, a column group represents a table of data, with its columns being the union of columns in the individual Btrees.
column storebtreea Btrees that has as its key a record id
commit timestamptransactionsvalues in this transaction become visible at this timestamp.
compare and swap (CAS)generala CPU instruction that can be used to coordinate the activity of multiple threads. Specifically, the instruction atomically changes a memory location to a new value only if the existing value matches a second value.
compressiongeneralone of several techniques to reduce the size of data on disk and memory. See block compression, run length encoding, Huffman encoding, key prefix compression.
connectiongeneralan encapsulation of information stored for an application's use of a WiredTiger instance attached to a specific home directory. This encapsulation is kept in a handle that is used in the API.
cursorgenerala handle in the WiredTiger API that encapsulates a position in a Btree, and may hold the key and value associated with that position.
data handlegeneralan abstraction of a named file, table or other data source in WiredTiger
data sourcegeneralan abstraction that extends the uri name space. A custom data source defines APIs that are invoked when objects are created in, or cursors are opened on, the new name space.
dhandlegeneralsee data handle
diagnostic buildgenerala build of WiredTiger that includes extra code to check invariants, and abort if they fail.
durabilitytransactionsthe property that guarantees that transactions that have been committed will survive permanently.
encryptionbtreein WiredTiger, encryption is applied to data files, log files and metadata. Encryption algorithms may be added to WiredTiger via the extension mechanism.
encryptorbtreean encryption algorithm packaged as an extension.
evictiongeneralthe process of freeing memory in the cache, which often includes reconciling and writing dirty pages. This term generally includes the process of deciding which pages should be evicted.
extensiongenerala module that uses the WiredTiger extension interface, allowing it to be added in an encapsulated way, without altering the core of the WiredTiger library. Extensions are typically compiled into shared libraries.
extent listblock managera list of contiguous sets of blocks in a file. Extent lists are used to track available blocks and/or used blocks.
fast truncatebtreea truncate that spans a key range over more than one leaf page may be performed quickly by deleting entire data pages at a time.
fragverifyin verify, a part of a file that is the minimum allocation size and aligned the same. The smallest blocks may be the same as a frag, other blocks may be composed of multiple contiguous frags.
hazard pointergenerala data structure that assists in lock free algorithms, used by WiredTiger Btrees
history storegeneralstorage in WiredTiger (currently implemented as a Btree) that keeps previous values associated with a key.
home directorygeneralthe directory containing all the data for a WiredTiger connection. The connection is attached to this directory via a call to wiredtiger_open.
Huffman encodingbtreedata in a btree may optionally be encoded using a Huffman encoding, based on either English letter frequencies or a custom encoding. See Huffman Encoding for details.
indexschemaa Btree with records having values that are keys to another Btree. An index (or set of indices) become associated with a primary Btree via the table construct.
insertbtreean in-memory structure holding a key and a set of updates for a Btree.
internal pagebtreeeither in-memory or on disk, a page in a Btree that has a set of keys that reference pages beneath it.
isolationtransactionsdetermines which versions of data are visible to a running transaction, and whether it can see changes made by concurrently running transactions.
key prefix compressionbtreea technique to store identical key prefixes only once per page. See File formats and compression
kv or k/vbtreea key/value pair in a Btree.
leaf pagebtreeeither in-memory or on disk, a page in a Btree that has a pairs of keys and values, and no pages beneath it.
log structured merge tree (or LSM tree)lsma data structure that stores keys and values (as a Btree), but composed of potentially many trees (Btrees in WiredTiger).
LSMlsmsee log structured merge tree
mergebtreethe process of making a single page out of two adjacent smaller pages in a Btree. This can occur with leaf pages or internal pages.
metadatagenerala set of data that is used to help manage files, tables, indices and column groups in WiredTiger.
metadata trackinggenerala technique to track a set of changes to the metadata, so they can be "rolled back" when an error occurs.
mutexgenerala locking algorithm that waits, allowing other threads to execute, when the lock cannot be immediately acquired, and is woken to retry when the lock is available. Although more heavyweight than a spin lock, it consumes fewer resources while waiting. Appropriate for resources that may be in contention and may be held for longer periods.
object idtiered storagean integer that indicates an individual file that is a part of a Btree.
oldest timestamptransactionsa connection-wide value, specifies the oldest timestamp that must be tracked by the system. Values with stop timestamps older than this value do not have to be retained.
on diskgenerala shorthand meaning "in the file system", and may or may not be stored on a physical disk.
overflow pagebtreeeither in-memory or on disk, a page in a Btree that has a key or value that is too large to appear on a leaf or internal page.
packgeneralconvert in-memory representations of keys or values to a compact format for file storage
pagebtreeone logical node of a Btree, in memory, or on disk, that may store keys and/or values. See internal page, leaf page, overflow page.
page referencebtreean indirect reference to a key on a page in a Btree. The reference struct (WT_REF) acts as the indirection and may include a pointer to an in memory object or an address cookie to find the object on disk. "ref" for short.
page splitbtreethe process of breaking up a large page in a Btree into multiple smaller pages. This may occur with either leaf pages or internal pages.
pthreadgenerala thread implementation used on POSIX systems
rawschemadata as it appears on-disk, typically in a packed format.
read timestamptransactionsa timestamp that specifies what data should be visible.
recnogenerala 64 bit integer. When used as a key, the Btree is said to be a column store, and the keys are assigned incrementally by WiredTiger when new records are inserted.
reconcilegeneralconvert the in-memory version of a page to a more compact form for file storage.
recoverygenerala procedure used on opening WiredTiger whereby, starting at the last checkpoint written, log records are played back to bring the database up to date.
refbtreesee page reference
RLEgeneralsee run length encoding
run length encodinggeneralalso known as "RLE". A technique to save space whereby repeated items can be represented by a count followed by the item. For example the string of letters "AAAAAAABBBCDDDD" might be encoded as "7A3BC4D" using "out of band" digits.
salvagegeneralfunctionality to repair Btree disk files.
schemaschemathe algorithms that use metadata to map the raw keys and values in Btrees to higher level abstractions like tables with typed columns.
sessiongeneralan encapsulation of information stored for single thread of control in the application. This encapsulation is kept in a handle that is used in the API. Sessions manage transactions and performs the transactional operations.
skip listgenerala variation of a sorted linked list that allows for faster (O(log(N))) searching. It is used in WiredTiger as a lock-free data structure for keys inserted on a page.
spin lockgenerala simple locking algorithm that continually attempts to acquire a lock, appropriate for resources that are likely to be available and may be held for a short time. This lock is CPU intensive while it is waiting. Contrast with mutex
splitbtreesee page split
stable timestamptransactionsa connection-wide value, checkpoints will not include commits newer than this value.
tableschemaan abstraction that allows one or more btrees to be used in a coordinated way, which is specified by the schema. The table coordinates indices and column groups.
threadgenerala thread of control. WiredTiger uses pthreads for POSIX systems.
thread groupgenerala group of threads that perform a common task. Eviction is performed by a thread group.
timestamptransactionsrefers to one of several types of 64 bit values used to control transactional visibility of data in WiredTiger. See oldest timestamp, stable timestamp, commit timestamp, read timestamp.
transactiontransactionsa unit of work performed in WiredTiger that is atomic and consistent with the specified isolation level and durability level.
truncatebtreean operation to remove a range of key/values from a Btree. See also fast truncate
updatebtreea value associated with a key in a Btree. A key may have many updates, these correspond to values written to the key previously.
update chainbtreea list of updates.
verifygeneralfunctionality to check integrity of Btree disk files.