You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by md...@apache.org on 2017/01/31 15:06:43 UTC
svn commit: r1781099 - in
/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore:
segment/overview.md segment/records.md segment/tar.md
segment/tarmk-classes.md segmentmk.md
Author: mduerig
Date: Tue Jan 31 15:06:43 2017
New Revision: 1781099
URL: http://svn.apache.org/viewvc?rev=1781099&view=rev
Log:
OAK-5547: Document TarMK design
Mark segmentmk.md as historic and incorporate its content where applicable into the rest of the documentation.
Modified:
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tarmk-classes.md
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segmentmk.md
Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md?rev=1781099&r1=1781098&r2=1781099&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md Tue Jan 31 15:06:43 2017
@@ -17,8 +17,7 @@
# Oak Segment Tar
-Oak Segment Tar is an implementation of the Node Store that stores repository data on the file system.
-
+* [Overview](#overview)
* [Garbage Collection](#garbage-collection)
* [Generational Garbage Collection](#generational-garbage-collection)
* [Estimation, Compaction and Cleanup](#estimation-compaction-cleanup)
@@ -49,8 +48,26 @@ Oak Segment Tar is an implementation of
* [Debug](#debug)
* [Diff](#diff)
* [History](#history)
-* [Design](#design)
- * [Format changes](#format-changes)
+
+## <a name="overview"/> Overview
+
+Oak Segment Tar is an Oak storage backend that stores content as various types of *records* within larger *segments*. Segments themselves are collected within *tar files* along with further auxiliary information. A *journal* is used to track the latest state of the repository. It is based on the following key principles:
+
+ * *Immutability*. Segments are immutable, which makes is easy to cache frequently accessed segments. This also makes it less likely for programming or system errors to cause repository inconsistencies, and simplifies features like backups or master-slave clustering.
+
+ * *Compactness*. The formatting of records is optimized for size to reduce IO costs and to fit as much content in caches as possible.
+
+ * *Locality*. Segments are written so that related records, like a node and its immediate children, usually end up stored in the same segment. This makes tree traversals very fast and avoids most cache misses for typical clients that access more than one related node per session.
+
+The content tree and all its revisions are stored in a collection of immutable *records* within *segments*. Each segment is identified by a UUID and typically contains a continuous subset of the content tree, for example a node with its properties and closest child nodes. Some segments might also be used to store commonly occurring property values or other shared data. Segments can be to up to 256KiB in size. See [Segments and records](records.html) for a detailed description of the segments and records.
+
+Segments are collectively stored in *tar files* and check-summed to ensure their integrity. Tar files also contain an index of the tar segments, the graph of segment references of all segments it contains and an index of all external binaries referenced from the segments in the tar file. See [Structure of TAR files](tar.html) for details.
+
+The *journal* is a special, atomically updated file that records the state of the repository as a sequence of references to successive root node records. For crash resiliency the journal is always only updated with a new reference once the referenced record has been flushed to disk. The most recent root node reference stored in the journal is used as the starting point for garbage collection. All content currently visible to clients must be accessible through that reference.
+
+Oak Segment Tar is an evolution of a [previous implementation](../segmentmk.html). Upgrading requires [migrating](../../migration.html) to the [new storage format](changes.html).
+
+See [Design of Oak Segment Tar](tarmk-classes.html) for a high level design overview of Oak Segment Tar.
## <a name="garbage-collection"/> Garbage Collection
@@ -630,24 +647,3 @@ The `--depth` parameter determines if th
`DEPTH` must be a positive integer specifying how deep the printed content should be.
If this option is not specified, the depth is assumed to be `0`, i.e. only information about the node will be printed.
-## <a name="design"/> Design
-
-The Segment Node Store serializes repository data and stores it in a set of TAR files.
-These files are the most coarse-grained containers for the repository data.
-You can learn more about the general structure of TAR files by reading [this page](tar.html).
-
-Every TAR file contains segments, finer-grained containers of repository data.
-Unsurprisingly, segments inspired the name of this Node Store implementation.
-Repository data is serialized to one or more records, and these records are saved into the segments.
-You can learn about the internal organization of segments and the different ways to serialize records by reading [this page](records.html).
-
-See [this page](tarmk-classes.html) for a high level design overview of the TarMK.
-
-This page contains an overview of the legacy implementation of the Segment Store and of the design decisions that brought to this implementation.
-The page is old and describes a deprecated implementation, but can still be accessed [here](../segmentmk.html).
-
-### <a name="format-changes"/> Format changes
-
-The Oak Segment Tar module introduces a number of changes in the data format compared to the legacy Oak Segment.
-The changes are described in greater detail [here](changes.html).
-Pointers to actual Jira issues can also be found on that page.
Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md?rev=1781099&r1=1781098&r2=1781099&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md Tue Jan 31 15:06:43 2017
@@ -15,54 +15,117 @@
limitations under the License.
-->
-# Records and segments
+# Segments and records
-While TAR files and segments are a coarse-grained mechanism to divide the
-repository content in more manageable pieces, the real information is stored
-inside the segments as finer-grained records. Here I zoom in the segments and
-show the binary representation of data stored by Oak in the segments. It is not
-strictly necessary to know how segments work in order to understand this
-content, but if you feel lost you can refer to [this description of the
-structure of TAR files](tar.html).
+While [TAR files](tar.html) and segments are a coarse-grained mechanism to
+divide the repository content in more manageable pieces, the real information
+is stored inside the segments as finer-grained records. This page details the
+structure of segments and show the binary representation of data stored by Oak.
-## Data and bulk segments
+## Segments
Segments are not created equal. Oak, in fact, distinguishes data and bulk
segments, where the former is used to store structured data (e.g. information
about node and properties), while the latter contains unstructured data (e.g.
the value of binary properties or of very long strings).
-It is possible to take apart a bulk segment from a data segment by just looking
-at its identifier. As explained in a previous post, a segment identifier is a
-randomly generated UUID. Segment identifiers are 16 bytes long, but Oak uses 4
-bits to store a flag capable to set apart bulk segments from data segments.
+It is possible to tell apart a bulk segment from a data segment by just looking
+at its identifier. A segment identifier is a randomly generated UUID. Segment
+identifiers are 16 bytes long, but Oak uses 4 bits to set apart bulk segments
+from data segments. The following bit patterns are used (each `x` represents
+four random bits):
-The most interesting kind of segment is the data segment, because it stores
-information about the repository in a structured and easily accessible way.
+ * `xxxxxxxx-xxxx-4xxx-axxx-xxxxxxxxxxxx` data segment UUID
+ * `xxxxxxxx-xxxx-4xxx-bxxx-xxxxxxxxxxxx` bulk segment UUID
-## Overview of data segments
+(This encoding makes segment UUIDs appear as syntactically valid version 4
+random UUIDs specified in RFC 4122.)
+
+## Bulk segments
+
+Bulk segments contain raw binary data, interpreted simply as a sequence
+of block records with no headers or other extra metadata:
+
+ [block 1] [block 2] ... [block N]
+
+A bulk segment whose length is `n` bytes consists of `n div 4096` block
+records of 4KiB each followed possibly a block record of `n mod 4096` bytes,
+if there still are remaining bytes in the segment. The structure of a
+bulk segment can thus be determined based only on the segment length.
+
+## Data segments
A data segment can be roughly divided in two parts, a header and a data section.
The header contains management information about the segment itself, while the
data section stores the actual repository data.
-Repository data is split into records, that are tiny bits of information that
-represent different types of information. There are different types of records,
-where every type is specialized in storing a specific piece of information: node
-records, template records, map records, list records, and so on.
-
-In general, a record can be considered as a contiguous sequence of bytes stored
-at a specific position inside a segment. A record can also have references to
-other records, where the referenced records can be stored in the same segment or
-not. Since records can reference each other, a segment actually stores a graph
-of records, where the implementation guarantees that the graph is acyclic.
-
-The segment also maintains a set of references to *root records* those records
-in the graph that are not referenced by any other records. In graph jargon,
-these records would be called source vertices. The set of references to root
-records is stored in the header section of the segment.
+Repository data is split into records of different types. Every type is specialized
+for storing a specific piece of information: node records, template records, map
+records, list records, etc.
+
+A record is a contiguous sequence of bytes stored at a specific offset inside a
+segment. A record can have references to other records, where the referenced records
+can be stored in the same segment or not. Since records can reference each other, a
+segment actually stores a graph of records.
+
+The segment header also maintains a set of references to *root records*: those
+records that are not referenced from any other records in the segment.
+
+The overall structure of a data segment is:
+
+ [segment header] [record 1] [record 2] ... [record N]
+
+The segment header and each record is zero-padded to make their size a multiple of
+four bytes and to align the next record at a four-byte boundary.
+
+The segment header consists of the following fields. All integers are stored in big
+endian format.
+
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+ | magic bytes: "0aK" | version | reserved
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+ reserved | generation | idcount
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+ idcount | rootcount | reserved
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+ reserved |
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+ | Referenced segment identifiers (idcount x 16 bytes) |
+ | |
+ | ...... |
+ | |
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+ | Root record references (rootcount x 9 bytes) |
+ | |
+ | ...... +---------+---------+---------+
+ | | padding (set to 0) |
+ +---------+---------+---------+---------+---------+---------+---------+---------+
+
+The first three bytes of a segment always contain the ASCII string "0aK",
+which is intended to make the binary segment data format easily detectable.
+The next byte indicates the version of the segment format and is currently set
+to 12.
+
+The `generation` field indicates the segment's generation wrt. to garbage
+collection. This field is used by the garbage collector to determine whether
+a segment needs to be retained or can be collected.
+
+The `idcount` field indicates how many other segments are referenced by
+records within this segment. The identifiers of those segments are listed
+starting at offset 32 of the segment header. This lookup table is used to
+optimize garbage collection and to avoid having to repeat the 16-byte
+UUIDs whenever references to records in other segments are made.
+
+The `rootcount` field indicates the number of root record references that
+follow after the segment identifier lookup table. They identify the types
+and locations of those records within this segment that are not accessible
+by following references in other records within this segment. Each entry in
+that table consists of a record number (4 bytes), a record type (1 byte)
+and a record offset (4 bytes) from the end of the segment.
+
+## Record numbers and offsets
-## Record identifiers
+TODO: bring this section up to date wrt. OAK-4659
Records need a mechanism to reference each other, both from inside the same
segment and across different segments. The mechanism used to reference a record
@@ -156,44 +219,40 @@ Given that the size of the current segme
absolute position of `128 - 32 = 96` in the segment to read the record you are
interested in.
-## Record types
-
-As stated before, there are many types of records. It is necessary to make a
-distinction between logical and physical records, where the former are an
-idealized representation of a data structure, and the latter are used to encode
-the data structures in the segments as sequence of bits.
-
-Usually there is a one-to-one mapping between logical and physical records, like
-in block records, value records, template records and node records. Other types
-of logical record, like map records and list records, use more than one physical
-record to represent the content.
+## Records
-Let's give a brief description of the aforementioned records.
+The content inside a segment is divided in records of different types:
+blocks, lists, maps, values, templates and nodes. These record types
+and their internal structures are described in subsections below.
### Block records
A block record is the simplest form of record, because it is just a plain
-sequence of bytes. It doesn't even contain a length: it is up to the writer of
-this record to store the length elsewhere.
-
-The only adjustment performed to the data is the alignment. The implementation
-makes sure that the written sequence of bytes is stored at a position that is a
-multiple of four.
+sequence of bytes up to 4kB. It doesn't even contain a length: it is up to
+the writer of this record to store the length elsewhere. The only adjustment
+performed to the data is the alignment. The implementation makes sure that
+the written sequence of bytes is stored at a position that is a multiple of
+four.
+
+Block records are used as building blocks of large binary and string values.
+They are the only record type that can't contain references to other records.
+Block records are typically stored in *bulk segments* that consist only of
+block records and are thus easily identifiable as containing zero references
+to other segments.
### Value records
-Value records are an improvement over block records, because they give the
-possibility to store arbitrary binary data with an additional length and
-optional references to other records.
+Value records have more structure than block records and store data with an
+additional length and optional references to other records.
-The implementation represents value records in different ways, depending on the
+The implementation represents value records in different ways depending on the
length of the data to be written. If the data is short enough, the record can be
-written in the simplest way possible: a lento field and the data inlined
-directly in the record.
+written in the simplest way possible: a length field and the data inlined directly
+in the record.
When the data is too big, instead, it is split into block records written into
block segments. The reference to these block records are stored into a list
-record, whose identifier is stored inside the value record.
+record (see next section), whose identifier is stored inside the value record.
This means that value record represent a good compromise when writing binary or
string data. If the data is short enough, it is written in such a way that can
@@ -201,11 +260,35 @@ be used straight away without further re
long, instead, it is stored separated from the repository content not to impact
the performance of the readers of the segment.
+Value records are used for storing names and values of the content tree. Since
+item names can be thought of as name values and since all JCR and Oak values can
+be expressed in binary form (strings encoded in UTF-8), it is easiest to simply
+use that form for storing all values. The size overhead of such a form for small
+value types like booleans or dates is amortized by the facts that those types are
+used only for a minority of values in typical content trees and that repeating
+copies of a value can be stored just once.
+
+There are four types of value records: small, medium, long and external.
+The small- and medium-sized values are stored in inline form, prepended
+by one or two bytes that indicate the length of the value. Long values
+of up to two exabytes (2^61) are stored as a list of block records. Finally
+an external value record contains the length of the value and a string
+reference (up to 4kB in length) to some external storage location.
+
+The type of a value record is encoded in the high-order bits of the first
+byte of the record. These bit patterns are:
+
+ * `0xxxxxxx`: small value, length (0 - 127 bytes) encoded in 7 bits
+ * `10xxxxxx`: medium value length (128 - 16511 bytes) encoded in 6 + 8 bits
+ * `110xxxxx`: long value, length (up to 2^61 bytes) encoded in 5 + 7*8 bits
+ * `1110xxxx`: external value, reference string length encoded in 4 + 8 bits
+
+
### List records
-List records are a general-purpose list of record identifiers. They are used as
-building blocks for other types of records, as we saw for value records and as
-we will see for template records and node records.
+List records represent a general-purpose list of record identifiers. They are
+used as building blocks for other types of records, as we saw for value records
+and as we will see for template records and node records.
The list record is a logical record using two different types of physical
records to represent itself:
@@ -219,6 +302,21 @@ records to represent itself:
- list record: this is a top-level record that maintains the size of the list in
an integer field and a record identifier pointing to a bucket.
+
+ +--------+--------+--------+-----+
+ | sub-list ID 1 | ... |
+ +--------+--------+--------+-----+
+ |
+ v
+ +--------+--------+--------+-----+--------+--------+--------+
+ | record ID 1 | ... | record ID 255 |
+ +--------+--------+--------+-----+--------+--------+--------+
+
+The result is a hierarchically stored immutable list where each element
+can be accessed in O(log N) time and the size overhead of updating or
+appending list elements (and thus creating a new immutable list) is
+also O(log N).
+
List records are useful to store a list of references to other records. If the
list is too big, it is split into different bucket records that may be stored
in the same segment or across segments. This guarantees good performance for
@@ -227,9 +325,9 @@ elements.
### Map records
-Map records are a general-purpose maps of strings to record identifiers. As
-lists, they are used as building blocks for other types of records and are
-represented using two types of physical record:
+Map records implement a general-purpose unordered map of strings to record
+identifiers. They are used for nodes with a large number of properties or
+child nodes. As lists they are represented using two types of physical record:
- leaf record: if the number of elements in the map is small, they are all
stored in a leaf record. This covers the simplest case for small maps.
@@ -239,9 +337,18 @@ represented using two types of physical
the map. A branch record is recursive, because it can reference other branch
records if the sub-maps are too big and need to be split again.
-The implementation of the map record relies on the properties defined by an
-external data structure called HAMT (Hash Array Mapped Trie), capable of
-combining the properties of hash table and a trie.
+Maps are stored using the hash array mapped trie (HAMT) data structure.
+The hash code of each key is split into pieces of 5 bits each and the
+keys are sorted into 32 (2^5) buckets based on the first 5 bits. If a bucket
+contains less than 32 entries, then it is stored directly as a list of
+key-value pairs. Otherwise the keys are split into sub-buckets based on the
+next 5 bits of their hash codes. When all buckets are stored, the list of
+top-level bucket references gets stored along with the total number of
+entries in the map.
+
+The result is a hierarchically stored immutable map where each element
+can be accessed in O(log N) time and the size overhead of updating or
+inserting list elements is also O(log N).
Map records are also optimized for small changes. In example, if only one
element of a previously stored map is modified, and the map is stored again,
@@ -265,12 +372,44 @@ of the properties change, but not the st
The template record allows Oak to handle simple modifications to nodes in the
most efficient way possible.
+As such a template record describes the common structure of a family of related
+nodes. Since the structures of most nodes in a typical content tree fall
+into a small set of common templates, it makes sense to store such templates
+separately instead of repeating that information separately for each node.
+For example, the property names and types as well as child node names of all
+nt:file nodes are typically the same. The presence of mixins and different
+subtypes increases the number of different templates, but they're typically
+still far fewer than nodes in the repository.
+
+A template record consists of a set of up to N (exact size TBD, N ~ 256)
+property name and type pairs. Additionally, since nodes that are empty or
+contain just a single child node are most common, a template record also
+contains information whether the node has zero, one or many child nodes.
+In case of a single child node, the template also contains the name of
+that node. For example, the template for typical mix:versionable nt:file
+nodes would be (using CND-like notation):
+
+ - jcr:primaryType (NAME)
+ - jcr:mixinTypes (NAME) multiple
+ - jcr:created (DATE)
+ - jcr:uuid (STRING)
+ - jcr:versionHistory (REFERENCE)
+ - jcr:predecessors (REFERENCE) multiple
+ - jcr:baseVersion (REFERENCE)
+ + jcr:content
+
+The names used in a template are stored as separate value records and
+included by reference. This way multiple templates that for example all
+contain the "jcr:primaryType" property name don't need to repeatedly
+store it.
+
+
### Node records
The node record is the single most important type of record, capable of storing
both the data associated to the node and the structure of the content tree.
-A node record always maintain a reference to a template record. As stated
+A node record always maintains a reference to a template record. As stated
before, a template record defines the overall structure of the node, while the
variable part of it is maintained in the node record itself.
Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md?rev=1781099&r1=1781098&r2=1781099&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md Tue Jan 31 15:06:43 2017
@@ -190,6 +190,9 @@ After the segment header, the actual rec
advertised in the corresponding record header stored in the last part of the
segment header.
+See [Segments and records](records.html) for description of the various record types
+and their format.
+
## Binary references files
The binary references file represents an index of binary references (blobs) in a
Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tarmk-classes.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tarmk-classes.md?rev=1781099&r1=1781098&r2=1781099&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tarmk-classes.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tarmk-classes.md Tue Jan 31 15:06:43 2017
@@ -14,15 +14,16 @@
See the License for the specific language governing permissions and
limitations under the License.
-->
-# Design of the TarMK
+# Design of Oak Segment Tar
-This section gives a high level overview of the TarMK design, its most important classes, their purpose and relationship. More in depth information is available from the Javadoc of the individual classes.
+This section gives a high level overview of the design of Oak Segment Tar, its most important classes, their purpose and relationship. More in depth information is available from the Javadoc of the individual classes.
## Overview
-
+
-The `SegmentNodeStore` is the TarMK's implementation of the [NodeStore API](../overview.html). It uses a `Revisions` instance for accessing and setting the current head state, a `SegmentReader` for reading records from segments, a `SegmentWriter` for writing records to segments and a `BlobStore` for reading and writing binaries.
+The `SegmentNodeStore` is Oak Segment Tar's implementation of the [NodeStore API](../overview.html). It uses a `Revisions` instance for accessing and setting the current head state, a `SegmentReader` for reading records from segments, a `SegmentWriter` for writing records to segments and a `BlobStore` for reading and writing binaries.
+The `SegmentNodeStore` is Oak Segment Tar's implementation of the [NodeStore API](../overview.html). It uses a `Revisions` instance for accessing and setting the current head state, a `SegmentReader` for reading records from segments, a `SegmentWriter` for writing records to segments and a `BlobStore` for reading and writing binaries.
The `SegmentStore` serves as a persistence backend for the `SegmentNodeStore`. It is responsible for providing concrete implementations of `Revisions`, `SegmentReader` and `BlobStore` to the former.
Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segmentmk.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segmentmk.md?rev=1781099&r1=1781098&r2=1781099&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segmentmk.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segmentmk.md Tue Jan 31 15:06:43 2017
@@ -18,7 +18,9 @@
Segment Storage Design Overview
=========================
-TODO: merge with [Records and segments](segment/records.html).
+*NOTE:* The information on this page applies to an older version of the
+TarMK and is mainly of historical interest. For the documentation of the
+current versions see [Oak Segment Tar](segment/overview.html).
The SegmentNodeStore is an Oak storage backend that stores content as various
types of *records* within larger *segments*. One or more *journals* are