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 2015/08/05 12:52:02 UTC
svn commit: r1694171 - in /jackrabbit/oak/trunk/oak-doc/src/site: ./
markdown/nodestore/ markdown/nodestore/segment/
Author: mduerig
Date: Wed Aug 5 10:52:01 2015
New Revision: 1694171
URL: http://svn.apache.org/r1694171
Log:
OAK-3120: Contribute blog posts about FileStore to official documentation
Patch by Francesco Mari
Added:
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/
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/segment.png
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.svg
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md
Modified:
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/overview.md
jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segmentmk.md
jackrabbit/oak/trunk/oak-doc/src/site/site.xml
Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/overview.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/overview.md?rev=1694171&r1=1694170&r2=1694171&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/overview.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/overview.md Wed Aug 5 10:52:01 2015
@@ -17,9 +17,10 @@
# Node Storage
-Oak comes with two node storage flavours: [Segment](segmentmk.html) and [Document](documentmk.html).
-Segment storage is optimised for maximal performance in standalone deployments,
-and document storage is optimised for maximal scalability in clustered deployments.
+Oak comes with two node storage flavours: [Segment](segment/overview.html) and
+[Document](documentmk.html). Segment storage is optimised for maximal
+performance in standalone deployments, and document storage is optimised for
+maximal scalability in clustered deployments.
## NodeStore API
@@ -32,4 +33,4 @@ which is suited to work with in Java, an
## MicroKernel API
The `MicroKernel` API was deprecated in OAK 1.2 and dropped from the project as of
-Oak 1.3.0. It used to exposes its functionality through a String only (JSON) API.
\ No newline at end of file
+Oak 1.3.0. It used to exposes its functionality through a String only (JSON) API.
Added: 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=1694171&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md (added)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/overview.md Wed Aug 5 10:52:01 2015
@@ -0,0 +1,39 @@
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+-->
+
+# Segment Node Store
+
+The Segment Node Store is the implementation of the [Node
+Store](../overview.html) that persists repository data on the file
+system in an efficient, organized and performant way.
+
+One of the most important tasks of the Segment Node Store is the management of 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 a TAR file
+and how Oak leverages 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 nodes and properties are 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).
+
+This website also contain a broader overview of the Segment Store and of the
+design desictions that brought to his implementation. The page is quite old and
+potentially outdated, but contains valuable information and is accessible
+[here](../segmentmk.html).
Added: 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=1694171&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md (added)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/records.md Wed Aug 5 10:52:01 2015
@@ -0,0 +1,291 @@
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+-->
+
+# Records and segments
+
+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).
+
+## Data and bulk 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.
+
+The most interesting kind of segment is the data segment, because it stores
+information about the repository in a structured and easily accessible way.
+
+## Overview of 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.
+
+## Record identifiers
+
+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
+is (unsurprisingly) a record identifier.
+
+A record identifier is composed of a *segment field* and a *position field*. The
+segment field is a single byte that identifies the segment where the referenced
+record is stored. The position field is the position of the record inside the
+segment identified by the segment field. There are some peculiarities in both
+the segment and the position field that may not be immediately obvious. The
+picture below shows how a segment looks like.
+
+
+
+The segment field is just one byte long, but a segment identifier is 16 bytes
+long. To bridge the gap, the segment header contains an array of segment
+identifiers that is used as a look-up table. The array can store only 255
+segment identifiers, so a single byte is enough to access every element in the
+array. In fact, the segment field in a record identifier is just an index in the
+array of segment identifiers that is used as a look-up table. The look-up table
+always contains the segment identifier of the current segment in the first
+position: if a segment field is set to zero, the referenced record is stored in
+the current segment.
+
+The definition of the position field relies on some important properties of data
+segments:
+
+- data segments have a maximum size of 256 KiB, or `0x40000` bytes. The size of
+ a data segment can never exceed this limit, but it is perfectly legal to have
+ data segments smaller than 256 KiB.
+
+- records are always aligned on a two-bit boundaries. Stated differently, when a
+ record is written in a segment, it must be stored at a position that is a
+ multiple of four.
+
+- records are stored from the end of the segment. Even if this may seem
+ counterintuitive, it makes perfectly sense if you consider that new records
+ are written as a consequence of an in-depth traversal of a content tree.
+ Writing records from the end of the segment guarantees that the records that
+ are relevant to the root of the content tree are at the beginning of the
+ segment, while records that are relevant to the leaves of the content tree are
+ stored at the end. This makes reading from the segment faster, because
+ operating systems are optimized to read files from the beginning to the end,
+ and not backwards.
+
+So, according to the the previous properties, allowed positions range from
+`0x40000` (not included) to zero (included). Moreover, assigned positions must
+be multiples of four.
+
+```
+0x3FFFC, 0x3FFF8, 0x3FFF4, 0x3FFF0, 0x3FFEC, ..., 0x0
+```
+
+As you can see, three bytes would be necessary to store these positions, but we
+know that a record identifier uses only two bytes to store position values. This
+is possible because of a very simple optimization made to the positions before
+being used in a record identifier. Since the positions are multiples of four,
+the last two least significant bits are always zero. Being constant, these bits
+can be removed by shifting the positions to the right twice. After the shift,
+the list of possible positions become
+
+```
+0xFFFF, 0xFFFE, 0xFFFD, 0xFFFC, 0xFFFB, ..., 0x0
+```
+
+With this optimization, only two bytes are necessary to store a position inside
+a record identifier. Of course, when you read a position from a record
+identifier you have to remember to shift the position to left twice to obtain a
+valid position.
+
+The last important piece of information about positions is that they are always
+assigned on a logic segment size of `0x40000` bytes, even if the segment ends up
+to be smaller than 256 KiB. This doesn't mean that these absolute positions are
+useless: in fact, they are converted to offsets relative to the effective end of
+the segment.
+
+Hopefully an example will clarify this.
+
+Let's suppose that you are reading from a segment whose size is just 128 bytes.
+Let's also suppose that you want to read a record from the position `0xFFF8`.
+The problem is that the position `0xFFF8` was computed on a logical segment size
+of 256 KiB (or `0x40000` bytes), so you have to convert the position `0xFFF8`
+into an offset that can be used with the segment you are reading from. First of
+all, the two least significant bits were stripped away from the position, so you
+have to rotate `0xFFF8` two places to the left to obtain a proper position of
+`0xFFF8 << 2 = 0x3FFE0`. How far was this position from the logical size of
+`0x40000` bytes? It is easy to compute that the referenced record is `0x40000 -
+0x3FFE0 = 0x20 = 32` bytes before the end of the segment.
+
+Given that the size of the current segment is only 128 bytes, you can use an
+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.
+
+Let's give a brief description of the aforementioned records.
+
+### 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.
+
+### 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.
+
+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.
+
+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.
+
+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
+be used straight away without further reads in the segment. If the data is too
+long, instead, it is stored separated from the repository content not to impact
+the performance of the readers of the segment.
+
+### 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.
+
+The list record is a logical record using two different types of physical
+records to represent itself:
+
+- bucket record: this is a recursive record representing a list of at most 255
+ references. A bucket record can reference other bucket records,
+ hierarchically, or the record identifiers of the elements to be stored in the
+ list. A bucket record doesn't maintain any other information exception record
+ identifiers.
+
+- 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.
+
+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
+small lists, without loosing the capability to store lists with a big number of
+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:
+
+- 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.
+
+- branch record: if the number of elements in the map is too big, the original
+ map is split into smaller maps based on a hash function applied to the keys of
+ 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.
+
+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,
+only a "diff" of the map is stored. This prevents the full storage of the
+modified map, which can save a considerable amount of space if the original map
+was big.
+
+### Template records
+
+A template record stores metadata about nodes that, on average, don't change so
+often. A template record stores information like the primary type, the mixin
+types, the property names and the property types of a node. Having this
+information stored away from the node itself prevents to write them over and
+over again if they don't change when the node changes.
+
+In example, on average, a node is created with a certain primary type and,
+optionally, with some mixin types. Usually, because of its primary type, a node
+is already created with a set of initial properties. After that, only the value
+of the properties change, but not the structure of the node itself.
+
+The template record allows Oak to handle simple modifications to nodes in the
+most efficient way possible.
+
+### 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
+before, a template record defines the overall structure of the node, while the
+variable part of it is maintained in the node record itself.
+
+The variable part of the node is represented by a list of property values and a
+map of child nodes.
+
+The list of property values is implemented as a list of record identifiers. For
+each property in the node, its value is written in the segment. The record
+identifiers referencing the values of the properties are then packed together in
+a list record. The identifier of the list record is stored as part of the node
+record. If the value of some properties didn't change, the previous record
+identifier is just reused.
+
+The map of child nodes is implemented as a map of record identifiers. For every
+child node, its node record identifier is stored in a map indexed by name. The
+map is persisted in a map record, and its identifier is stored in the node
+record. Thanks to the optimizations implemented by the map record, small changes
+to the map of children node don't create a lot of overhead in the segment.
Added: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.png
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.png?rev=1694171&view=auto
==============================================================================
Binary files jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.png (added) and jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.png Wed Aug 5 10:52:01 2015 differ
Added: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.svg
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.svg?rev=1694171&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.svg (added)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/segment.svg Wed Aug 5 10:52:01 2015
@@ -0,0 +1,4 @@
+<?xml version="1.0" standalone="yes"?>
+
+<svg version="1.1" viewBox="0.0 0.0 837.0 412.0" fill="none" stroke="none" stroke-linecap="square" stroke-miterlimit="10" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><clipPath id="p.0"><path d="m0 0l837.0 0l0 412.0l-837.0 0l0 -412.0z" clip-rule="nonzero"></path></clipPath><g clip-path="url(#p.0)"><path fill="#000000" fill-opacity="0.0" d="m0 0l837.0 0l0 412.0l-837.0 0z" fill-rule="nonzero"></path><path fill="#cfe2f3" d="m195.39037 22.098858l259.48157 0l0 66.09279l-259.48157 0z" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m195.39037 22.098858l259.48157 0l0 66.09279l-259.48157 0z" fill-rule="nonzero"></path><path fill="#000000" d="m271.49054 61.005257l-1.390625 0l0 -4.6875l-4.28125 0l0 4.6875l-1.390625 0l0 -10.21875l1.390625 0l0 4.328125l4.28125 0l0 -4.328125l1.390625 0l0 10.21875zm8.234375 0l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.1718
75l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm10.140625 0l-1.515625 0l-0.703125 -2.234375l-4.25 0l-0.71875 2.234375l-1.453125 0l3.390625 -10.21875l1.90625 0l3.34375 10.21875zm-2.625 -3.46875l-1.71875 -5.46875l-1.734375 5.46875l3.453125 0zm10.9375 -1.75q0 0.734375 -0.125 1.40625q-0.109375 0.671875 -0.359375 1.25q-0.25 0.578125 -0.65625 1.046875q-0.390625 0.46875 -0.96875 0.8125q-0.578125 0.328125 -1.34375 0.515625q-0.765625 0.1875 -1.734375 0.1875l-2.1875 0l0 -10.21875l2.625 0q2.390625 0 3.5625 1.234375q1.1875 1.234375 1.1875 3.765625zm-1.46875 0.09375q0 -1.078125 -0.203125 -1.828125q-0.203125 -0.75 -0.625 -1.203125q-0.40625 -0.46875 -1.03125 -0.671875q-0.625 -0.21875 -1.46875 -0.21875l-1.1875 0l0 7.84375l1.03125 0q3.484375 0 3.484375 -3.921875zm9.40625 5.125l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.171875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.640625 0l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0
.390625 -0.390625q-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.734375 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.328125 0.15625 -0.75zm19.40625 4.640625q0 0.71875 -0.296875 1.265625q-0.296875 0.546875 -0.828125 0.921875q-0.53125 0.359375 -1.28125 0.546875q-0.75 0.171875 -1.640625 0.171875q-0.40625 0 -0.8125 -0.03125q-0.40625 -0.03125 -0.78125 -0.078125q-0.359375 -0.046875 -0.6875 -0.109375q-0.328125 -0.
0625 -0.59375 -0.140625l0 -1.34375q0.578125 0.21875 1.3125 0.34375q0.734375 0.125 1.65625 0.125q0.671875 0 1.140625 -0.09375q0.484375 -0.109375 0.78125 -0.3125q0.296875 -0.21875 0.4375 -0.515625q0.140625 -0.296875 0.140625 -0.671875q0 -0.421875 -0.234375 -0.703125q-0.234375 -0.296875 -0.609375 -0.53125q-0.375 -0.234375 -0.859375 -0.421875q-0.46875 -0.1875 -0.96875 -0.390625q-0.5 -0.203125 -0.984375 -0.4375q-0.484375 -0.25 -0.859375 -0.5625q-0.375 -0.328125 -0.609375 -0.765625q-0.21875 -0.4375 -0.21875 -1.046875q0 -0.515625 0.21875 -1.015625q0.21875 -0.515625 0.671875 -0.90625q0.46875 -0.40625 1.1875 -0.640625q0.71875 -0.25 1.71875 -0.25q0.265625 0 0.5625 0.03125q0.296875 0.015625 0.609375 0.0625q0.3125 0.046875 0.609375 0.109375q0.296875 0.046875 0.5625 0.109375l0 1.25q-0.609375 -0.171875 -1.21875 -0.265625q-0.59375 -0.09375 -1.15625 -0.09375q-1.1875 0 -1.75 0.40625q-0.5625 0.390625 -0.5625 1.0625q0 0.421875 0.21875 0.71875q0.234375 0.296875 0.609375 0.53125q0.375 0.234375 0.859375
0.421875q0.484375 0.1875 0.984375 0.390625q0.5 0.203125 0.96875 0.453125q0.484375 0.234375 0.859375 0.578125q0.375 0.328125 0.609375 0.78125q0.234375 0.4375 0.234375 1.046875zm8.375 2.765625l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.171875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.203125 -0.390625q-1.234375 0.515625 -2.578125 0.515625q-2.15625 0 -3.328125 -1.296875q-1.15625 -1.296875 -1.15625 -3.828125q0 -1.21875 0.3125 -2.203125q0.328125 -1.0 0.921875 -1.6875q0.59375 -0.703125 1.4375 -1.078125q0.84375 -0.375 1.890625 -0.375q0.71875 0 1.328125 0.125q0.609375 0.125 1.171875 0.375l0 1.359375q-0.5625 -0.296875 -1.15625 -0.453125q-0.59375 -0.171875 -1.296875 -0.171875q-0.71875 0 -1.296875 0.28125q-0.578125 0.265625 -0.984375 0.78125q-0.40625 0.5 -0.625 1.25q-0.21875 0.734375 -0.21875 1.671875q0 1.984375 0.796875 3.0q0.8125 1.0 2.359375 1.0q0.65625 0 1.25 -0.140625q0.609375 -0.15625 1.171875 -0.4375l0 1.3125zm9.140625 -8.640625l-3.015625 0l0 9.
03125l-1.40625 0l0 -9.03125l-3.03125 0l0 -1.1875l7.453125 0l0 1.1875zm4.375 -0.015625l-2.359375 0l0 -1.171875l6.109375 0l0 1.171875l-2.34375 0l0 7.859375l2.34375 0l0 1.1875l-6.109375 0l0 -1.1875l2.359375 0l0 -7.859375zm13.46875 3.875q0 1.375 -0.328125 2.375q-0.328125 1.0 -0.875 1.65625q-0.546875 0.640625 -1.296875 0.96875q-0.734375 0.3125 -1.546875 0.3125q-0.984375 0 -1.71875 -0.359375q-0.734375 -0.359375 -1.21875 -1.03125q-0.46875 -0.671875 -0.703125 -1.625q-0.234375 -0.96875 -0.234375 -2.1875q0 -1.359375 0.3125 -2.359375q0.328125 -1.0 0.875 -1.640625q0.546875 -0.65625 1.28125 -0.96875q0.734375 -0.328125 1.5625 -0.328125q0.984375 0 1.703125 0.359375q0.734375 0.359375 1.21875 1.03125q0.484375 0.671875 0.71875 1.640625q0.25 0.953125 0.25 2.15625zm-1.453125 0.09375q0 -0.890625 -0.140625 -1.640625q-0.125 -0.75 -0.4375 -1.28125q-0.296875 -0.546875 -0.78125 -0.84375q-0.484375 -0.296875 -1.15625 -0.296875q-0.65625 0 -1.140625 0.328125q-0.46875 0.3125 -0.78125 0.859375q-0.296875 0.53125 -0
.453125 1.265625q-0.140625 0.734375 -0.140625 1.546875q0 0.90625 0.140625 1.65625q0.140625 0.75 0.4375 1.28125q0.3125 0.53125 0.78125 0.828125q0.484375 0.296875 1.15625 0.296875q0.65625 0 1.125 -0.3125q0.484375 -0.3125 0.78125 -0.859375q0.3125 -0.546875 0.453125 -1.265625q0.15625 -0.734375 0.15625 -1.5625zm9.75 5.078125l-1.8125 0l-2.96875 -6.375l-0.859375 -2.046875l0 5.15625l0 3.265625l-1.296875 0l0 -10.21875l1.78125 0l2.84375 6.03125l1.015625 2.34375l0 -5.46875l0 -2.90625l1.296875 0l0 10.21875z" fill-rule="nonzero"></path><path fill="#f4cccc" d="m195.39037 88.19166l259.48157 0l0 301.71103l-259.48157 0z" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m195.39037 88.19166l259.48157 0l0 301.71103l-259.48157 0z" fill-rule="nonzero"></path><path fill="#000000" d="m280.5843 239.68842q0 0.734375 -0.125 1.40625q-0.109375 0.671875 -0.359375 1.25q-0.25 0.578125 -0.65625 1.046875q-0.390625 0.46875 -0.96875 0.8125q-0.578125
0.328125 -1.34375 0.515625q-0.765625 0.1875 -1.734375 0.1875l-2.1875 0l0 -10.21875l2.625 0q2.390625 0 3.5625 1.234375q1.1875 1.234375 1.1875 3.765625zm-1.46875 0.09375q0 -1.078125 -0.203125 -1.828125q-0.203125 -0.75 -0.625 -1.203125q-0.40625 -0.46875 -1.03125 -0.671875q-0.625 -0.21875 -1.46875 -0.21875l-1.1875 0l0 7.84375l1.03125 0q3.484375 0 3.484375 -3.921875zm10.75 5.125l-1.515625 0l-0.703125 -2.234375l-4.25 0l-0.71875 2.234375l-1.453125 0l3.390625 -10.21875l1.90625 0l3.34375 10.21875zm-2.625 -3.46875l-1.71875 -5.46875l-1.734375 5.46875l3.453125 0zm10.828125 -5.5625l-3.015625 0l0 9.03125l-1.40625 0l0 -9.03125l-3.03125 0l0 -1.1875l7.453125 0l0 1.1875zm9.390625 9.03125l-1.515625 0l-0.703125 -2.234375l-4.25 0l-0.71875 2.234375l-1.453125 0l3.390625 -10.21875l1.90625 0l3.34375 10.21875zm-2.625 -3.46875l-1.71875 -5.46875l-1.734375 5.46875l3.453125 0zm19.296875 0.703125q0 0.71875 -0.296875 1.265625q-0.296875 0.546875 -0.828125 0.921875q-0.53125 0.359375 -1.28125 0.546875q-0.75 0.171875
-1.640625 0.171875q-0.40625 0 -0.8125 -0.03125q-0.40625 -0.03125 -0.78125 -0.078125q-0.359375 -0.046875 -0.6875 -0.109375q-0.328125 -0.0625 -0.59375 -0.140625l0 -1.34375q0.578125 0.21875 1.3125 0.34375q0.734375 0.125 1.65625 0.125q0.671875 0 1.140625 -0.09375q0.484375 -0.109375 0.78125 -0.3125q0.296875 -0.21875 0.4375 -0.515625q0.140625 -0.296875 0.140625 -0.671875q0 -0.421875 -0.234375 -0.703125q-0.234375 -0.296875 -0.609375 -0.53125q-0.375 -0.234375 -0.859375 -0.421875q-0.46875 -0.1875 -0.96875 -0.390625q-0.5 -0.203125 -0.984375 -0.4375q-0.484375 -0.25 -0.859375 -0.5625q-0.375 -0.328125 -0.609375 -0.765625q-0.21875 -0.4375 -0.21875 -1.046875q0 -0.515625 0.21875 -1.015625q0.21875 -0.515625 0.671875 -0.90625q0.46875 -0.40625 1.1875 -0.640625q0.71875 -0.25 1.71875 -0.25q0.265625 0 0.5625 0.03125q0.296875 0.015625 0.609375 0.0625q0.3125 0.046875 0.609375 0.109375q0.296875 0.046875 0.5625 0.109375l0 1.25q-0.609375 -0.171875 -1.21875 -0.265625q-0.59375 -0.09375 -1.15625 -0.09375q-1.1875
0 -1.75 0.40625q-0.5625 0.390625 -0.5625 1.0625q0 0.421875 0.21875 0.71875q0.234375 0.296875 0.609375 0.53125q0.375 0.234375 0.859375 0.421875q0.484375 0.1875 0.984375 0.390625q0.5 0.203125 0.96875 0.453125q0.484375 0.234375 0.859375 0.578125q0.375 0.328125 0.609375 0.78125q0.234375 0.4375 0.234375 1.046875zm8.375 2.765625l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.171875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.203125 -0.390625q-1.234375 0.515625 -2.578125 0.515625q-2.15625 0 -3.328125 -1.296875q-1.15625 -1.296875 -1.15625 -3.828125q0 -1.21875 0.3125 -2.203125q0.328125 -1.0 0.921875 -1.6875q0.59375 -0.703125 1.4375 -1.078125q0.84375 -0.375 1.890625 -0.375q0.71875 0 1.328125 0.125q0.609375 0.125 1.171875 0.375l0 1.359375q-0.5625 -0.296875 -1.15625 -0.453125q-0.59375 -0.171875 -1.296875 -0.171875q-0.71875 0 -1.296875 0.28125q-0.578125 0.265625 -0.984375 0.78125q-0.40625 0.5 -0.625 1.25q-0.21875 0.734375 -0.21875 1.671875q0 1.984375 0.79687
5 3.0q0.8125 1.0 2.359375 1.0q0.65625 0 1.25 -0.140625q0.609375 -0.15625 1.171875 -0.4375l0 1.3125zm9.140625 -8.640625l-3.015625 0l0 9.03125l-1.40625 0l0 -9.03125l-3.03125 0l0 -1.1875l7.453125 0l0 1.1875zm4.375 -0.015625l-2.359375 0l0 -1.171875l6.109375 0l0 1.171875l-2.34375 0l0 7.859375l2.34375 0l0 1.1875l-6.109375 0l0 -1.1875l2.359375 0l0 -7.859375zm13.46875 3.875q0 1.375 -0.328125 2.375q-0.328125 1.0 -0.875 1.65625q-0.546875 0.640625 -1.296875 0.96875q-0.734375 0.3125 -1.546875 0.3125q-0.984375 0 -1.71875 -0.359375q-0.734375 -0.359375 -1.21875 -1.03125q-0.46875 -0.671875 -0.703125 -1.625q-0.234375 -0.96875 -0.234375 -2.1875q0 -1.359375 0.3125 -2.359375q0.328125 -1.0 0.875 -1.640625q0.546875 -0.65625 1.28125 -0.96875q0.734375 -0.328125 1.5625 -0.328125q0.984375 0 1.703125 0.359375q0.734375 0.359375 1.21875 1.03125q0.484375 0.671875 0.71875 1.640625q0.25 0.953125 0.25 2.15625zm-1.453125 0.09375q0 -0.890625 -0.140625 -1.640625q-0.125 -0.75 -0.4375 -1.28125q-0.296875 -0.546875 -0.781
25 -0.84375q-0.484375 -0.296875 -1.15625 -0.296875q-0.65625 0 -1.140625 0.328125q-0.46875 0.3125 -0.78125 0.859375q-0.296875 0.53125 -0.453125 1.265625q-0.140625 0.734375 -0.140625 1.546875q0 0.90625 0.140625 1.65625q0.140625 0.75 0.4375 1.28125q0.3125 0.53125 0.78125 0.828125q0.484375 0.296875 1.15625 0.296875q0.65625 0 1.125 -0.3125q0.484375 -0.3125 0.78125 -0.859375q0.3125 -0.546875 0.453125 -1.265625q0.15625 -0.734375 0.15625 -1.5625zm9.75 5.078125l-1.8125 0l-2.96875 -6.375l-0.859375 -2.046875l0 5.15625l0 3.265625l-1.296875 0l0 -10.21875l1.78125 0l2.84375 6.03125l1.015625 2.34375l0 -5.46875l0 -2.90625l1.296875 0l0 10.21875z" fill-rule="nonzero"></path><path fill="#000000" fill-opacity="0.0" d="m172.25581 389.90268c-13.082474 0 -23.687912 -1.7675171 -23.687912 -3.9478455l0 -176.00624c0 -2.1803284 -10.605438 -3.9478302 -23.687912 -3.9478302l0 0c13.082474 0 23.687912 -1.7675018 23.687912 -3.9478302l0 -176.00624l0 0c0 -2.1803246 10.605438 -3.9478283 23.687912 -3.9478283z" fill-rule=
"nonzero"></path><path fill="#000000" fill-opacity="0.0" d="m172.25581 389.90268c-13.082474 0 -23.687912 -1.7675171 -23.687912 -3.9478455l0 -176.00624c0 -2.1803284 -10.605438 -3.9478302 -23.687912 -3.9478302l0 0c13.082474 0 23.687912 -1.7675018 23.687912 -3.9478302l0 -176.00624l0 0c0 -2.1803246 10.605438 -3.9478283 23.687912 -3.9478283" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m172.25581 389.90268c-13.082474 0 -23.687912 -1.7675171 -23.687912 -3.9478455l0 -176.00624c0 -2.1803284 -10.605438 -3.9478302 -23.687912 -3.9478302l0 0c13.082474 0 23.687912 -1.7675018 23.687912 -3.9478302l0 -176.00624l0 0c0 -2.1803246 10.605438 -3.9478283 23.687912 -3.9478283" fill-rule="nonzero"></path><path fill="#000000" fill-opacity="0.0" d="m29.003004 181.29729l95.869 0l0 49.40695l-95.869 0z" fill-rule="nonzero"></path><path fill="#000000" d="m54.02344 211.86076l-6.71875 0l0 -1.21875l2.640625 -2.625q0.640625 -0.640625 1.046875 -
1.109375q0.40625 -0.46875 0.625 -0.859375q0.234375 -0.390625 0.3125 -0.734375q0.078125 -0.34375 0.078125 -0.734375q0 -0.375 -0.109375 -0.71875q-0.09375 -0.34375 -0.3125 -0.59375q-0.203125 -0.265625 -0.546875 -0.40625q-0.328125 -0.15625 -0.796875 -0.15625q-0.640625 0 -1.171875 0.296875q-0.53125 0.28125 -0.984375 0.75l-0.75 -0.90625q0.578125 -0.609375 1.328125 -0.96875q0.765625 -0.375 1.765625 -0.375q0.671875 0 1.234375 0.203125q0.5625 0.203125 0.96875 0.59375q0.40625 0.375 0.625 0.9375q0.21875 0.546875 0.21875 1.25q0 0.578125 -0.15625 1.078125q-0.15625 0.5 -0.46875 1.0q-0.3125 0.5 -0.796875 1.03125q-0.484375 0.53125 -1.140625 1.15625l-1.84375 1.8125l4.953125 0l0 1.296875zm8.546875 -3.265625q0 0.75 -0.328125 1.375q-0.328125 0.625 -0.90625 1.078125q-0.578125 0.453125 -1.359375 0.703125q-0.78125 0.25 -1.6875 0.25q-0.21875 0 -0.484375 -0.015625q-0.265625 0 -0.53125 -0.03125q-0.25 -0.015625 -0.5 -0.046875q-0.234375 -0.015625 -0.4375 -0.046875l0 -1.234375q0.421875 0.09375 0.96875 0.140625q
0.546875 0.046875 1.09375 0.046875q0.625 0 1.125 -0.140625q0.5 -0.15625 0.84375 -0.421875q0.359375 -0.28125 0.546875 -0.671875q0.1875 -0.40625 0.1875 -0.890625q0 -0.953125 -0.6875 -1.390625q-0.671875 -0.4375 -1.953125 -0.4375l-1.9375 0l0 -5.21875l5.5 0l0 1.1875l-4.21875 0l0 2.875l0.890625 0q0.734375 0 1.421875 0.140625q0.703125 0.125 1.234375 0.453125q0.546875 0.328125 0.875 0.890625q0.34375 0.5625 0.34375 1.40625zm9.171879 0.03125q0 0.703125 -0.25 1.328125q-0.25 0.609375 -0.71875 1.0625q-0.46875 0.453125 -1.140625 0.71875q-0.65625 0.265625 -1.453125 0.265625q-0.84375 0 -1.5 -0.265625q-0.640625 -0.28125 -1.078125 -0.828125q-0.4375 -0.5625 -0.671875 -1.40625q-0.21875 -0.859375 -0.21875 -2.03125q0 -0.78125 0.09375 -1.515625q0.109375 -0.734375 0.34375 -1.375q0.234375 -0.65625 0.625 -1.1875q0.390625 -0.546875 0.96875 -0.921875q0.578125 -0.390625 1.359375 -0.609375q0.796875 -0.21875 1.84375 -0.21875l1.0 0l0 1.1875l-1.09375 0q-0.90625 0 -1.578125 0.21875q-0.671875 0.21875 -1.125 0.625q-0.
453125 0.390625 -0.703125 0.953125q-0.234375 0.5625 -0.296875 1.265625l-0.03125 0.3125q0.484375 -0.28125 1.125 -0.453125q0.65625 -0.1875 1.40625 -0.1875q0.765625 0 1.34375 0.234375q0.59375 0.21875 0.96875 0.625q0.390625 0.40625 0.578125 0.96875q0.203125 0.5625 0.203125 1.234375zm-1.421875 0.078125q0 -0.46875 -0.109375 -0.84375q-0.109375 -0.375 -0.359375 -0.640625q-0.234375 -0.265625 -0.609375 -0.40625q-0.375 -0.140625 -0.890625 -0.140625q-0.296875 0 -0.609375 0.0625q-0.296875 0.046875 -0.59375 0.140625q-0.28125 0.09375 -0.546875 0.21875q-0.265625 0.125 -0.484375 0.265625q0 1.015625 0.140625 1.6875q0.140625 0.671875 0.40625 1.078125q0.28125 0.40625 0.6875 0.578125q0.40625 0.171875 0.9375 0.171875q0.453125 0 0.8125 -0.140625q0.375 -0.140625 0.640625 -0.421875q0.28125 -0.28125 0.421875 -0.6875q0.15625 -0.40625 0.15625 -0.921875zm19.203125 3.15625l-1.75 0l-3.828125 -5.015625l0 5.015625l-1.390625 0l0 -10.21875l1.390625 0l0 4.75l3.75 -4.75l1.640625 0l-4.03125 4.859375l4.21875 5.359375zm4.
53125 -6.71875l-2.3125 0l0 -1.125l3.6875 0l0 6.703125l2.34375 0l0 1.140625l-6.296875 0l0 -1.140625l2.578125 0l0 -5.578125zm0.484375 -4.421875q0.21875 0 0.40625 0.09375q0.203125 0.078125 0.34375 0.234375q0.15625 0.140625 0.234375 0.328125q0.078125 0.1875 0.078125 0.421875q0 0.21875 -0.078125 0.421875q-0.078125 0.1875 -0.234375 0.34375q-0.140625 0.140625 -0.34375 0.21875q-0.1875 0.078125 -0.40625 0.078125q-0.234375 0 -0.4375 -0.078125q-0.1875 -0.078125 -0.328125 -0.21875q-0.140625 -0.15625 -0.234375 -0.34375q-0.078125 -0.203125 -0.078125 -0.421875q0 -0.234375 0.078125 -0.421875q0.09375 -0.1875 0.234375 -0.328125q0.140625 -0.15625 0.328125 -0.234375q0.203125 -0.09375 0.4375 -0.09375zm12.328125 8.078125q0 0.734375 -0.28125 1.3125q-0.28125 0.5625 -0.8125 0.953125q-0.53125 0.390625 -1.28125 0.59375q-0.734375 0.203125 -1.65625 0.203125l-2.671875 0l0 -10.21875l2.921875 0q3.421875 0 3.421875 2.484375q0 0.828125 -0.40625 1.421875q-0.390625 0.59375 -1.28125 0.890625q0.421875 0.078125 0.78125 0
.265625q0.375 0.1875 0.65625 0.484375q0.28125 0.296875 0.4375 0.703125q0.171875 0.40625 0.171875 0.90625zm-1.8125 -4.484375q0 -0.3125 -0.09375 -0.578125q-0.09375 -0.28125 -0.328125 -0.484375q-0.234375 -0.203125 -0.640625 -0.3125q-0.390625 -0.125 -1.0 -0.125l-1.4375 0l0 3.203125l1.390625 0q0.484375 0 0.859375 -0.09375q0.390625 -0.109375 0.671875 -0.3125q0.28125 -0.21875 0.421875 -0.53125q0.15625 -0.328125 0.15625 -0.765625zm0.34375 4.53125q0 -0.390625 -0.171875 -0.703125q-0.15625 -0.3125 -0.46875 -0.515625q-0.3125 -0.21875 -0.765625 -0.328125q-0.453125 -0.125 -1.015625 -0.125l-1.421875 0l0 3.515625l1.46875 0q1.203125 0 1.78125 -0.4375q0.59375 -0.453125 0.59375 -1.40625z" fill-rule="nonzero"></path><path fill="#000000" fill-opacity="0.0" d="m478.00653 90.192l0 0c13.0824585 0 23.687897 1.7675018 23.687897 3.9478302l0 140.9595c0 2.1803284 10.605438 3.9478302 23.687897 3.9478302l0 0c-13.0824585 0 -23.687897 1.7675018 -23.687897 3.9478302l0 140.9595c0 2.1803284 -10.605438 3.947815 -23.687
897 3.947815z" fill-rule="nonzero"></path><path fill="#000000" fill-opacity="0.0" d="m478.00653 90.192l0 0c13.0824585 0 23.687897 1.7675018 23.687897 3.9478302l0 140.9595c0 2.1803284 10.605438 3.9478302 23.687897 3.9478302l0 0c-13.0824585 0 -23.687897 1.7675018 -23.687897 3.9478302l0 140.9595c0 2.1803284 -10.605438 3.947815 -23.687897 3.947815" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m478.00653 90.192l0 0c13.0824585 0 23.687897 1.7675018 23.687897 3.9478302l0 140.9595c0 2.1803284 10.605438 3.9478302 23.687897 3.9478302l0 0c-13.0824585 0 -23.687897 1.7675018 -23.687897 3.9478302l0 140.9595c0 2.1803284 -10.605438 3.947815 -23.687897 3.947815" fill-rule="nonzero"></path><path fill="#ea9999" d="m548.5169 347.32886l259.48157 0l0 40.559906l-259.48157 0z" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m548.5169 347.32886l259.48157 0l0 40.55990
6l-259.48157 0z" fill-rule="nonzero"></path><path fill="#000000" d="m660.0858 373.4688l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0.390625 -0.390625q-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.734375 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.328125 0.15625 -0.75zm10.1875 7.40625l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.1
71875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.203125 -0.390625q-1.234375 0.515625 -2.578125 0.515625q-2.15625 0 -3.328125 -1.296875q-1.15625 -1.296875 -1.15625 -3.828125q0 -1.21875 0.3125 -2.203125q0.328125 -1.0 0.921875 -1.6875q0.59375 -0.703125 1.4375 -1.078125q0.84375 -0.375 1.890625 -0.375q0.71875 0 1.328125 0.125q0.609375 0.125 1.171875 0.375l0 1.359375q-0.5625 -0.296875 -1.15625 -0.453125q-0.59375 -0.171875 -1.296875 -0.171875q-0.71875 0 -1.296875 0.28125q-0.578125 0.265625 -0.984375 0.78125q-0.40625 0.5 -0.625 1.25q-0.21875 0.734375 -0.21875 1.671875q0 1.984375 0.796875 3.0q0.8125 1.0 2.359375 1.0q0.65625 0 1.25 -0.140625q0.609375 -0.15625 1.171875 -0.4375l0 1.3125zm9.390625 -4.78125q0 1.375 -0.328125 2.375q-0.328125 1.0 -0.875 1.65625q-0.546875 0.640625 -1.296875 0.96875q-0.734375 0.3125 -1.546875 0.3125q-0.984375 0 -1.71875 -0.359375q-0.734375 -0.359375 -1.21875 -1.03125q-0.46875 -0.671875 -0.703125 -1.625q-0.234375 -0.96875 -0.234375 -2.1875q0 -1.359375 0.3125 -2.3593
75q0.328125 -1.0 0.875 -1.640625q0.546875 -0.65625 1.28125 -0.96875q0.734375 -0.328125 1.5625 -0.328125q0.984375 0 1.703125 0.359375q0.734375 0.359375 1.21875 1.03125q0.484375 0.671875 0.71875 1.640625q0.25 0.953125 0.25 2.15625zm-1.453125 0.09375q0 -0.890625 -0.140625 -1.640625q-0.125 -0.75 -0.4375 -1.28125q-0.296875 -0.546875 -0.78125 -0.84375q-0.484375 -0.296875 -1.15625 -0.296875q-0.65625 0 -1.140625 0.328125q-0.46875 0.3125 -0.78125 0.859375q-0.296875 0.53125 -0.453125 1.265625q-0.140625 0.734375 -0.140625 1.546875q0 0.90625 0.140625 1.65625q0.140625 0.75 0.4375 1.28125q0.3125 0.53125 0.78125 0.828125q0.484375 0.296875 1.15625 0.296875q0.65625 0 1.125 -0.3125q0.484375 -0.3125 0.78125 -0.859375q0.3125 -0.546875 0.453125 -1.265625q0.15625 -0.734375 0.15625 -1.5625zm10.09375 5.078125l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0.390625 -0.390625q-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l
-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.734375 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.328125 0.15625 -0.75zm11.046875 2.1875q0 0.734375 -0.125 1.40625q-0.109375 0.671875 -0.359375 1.25q-0.25 0.578125 -0.65625 1.046875q-0.390625 0.46875 -0.96875 0.8125q-0.578125 0.328125 -1.34375 0.515625q-0.765625 0.1875 -1.734375 0.1875l-2.1875 0l0 -10.21875l2.625 0q2.390625 0 3.5625 1.234375q1.1875 1.234375 1.1875 3.765625zm-1.46875 0.09375q0 -1.078125 -0.203125 -1.828125q-0.203125 -0.75 -0.625 -1.203125q
-0.40625 -0.46875 -1.03125 -0.671875q-0.625 -0.21875 -1.46875 -0.21875l-1.1875 0l0 7.84375l1.03125 0q3.484375 0 3.484375 -3.921875z" fill-rule="nonzero"></path><path fill="#ea9999" d="m548.5169 254.24222l259.48157 0l0 93.089355l-259.48157 0z" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m548.5169 254.24222l259.48157 0l0 93.089355l-259.48157 0z" fill-rule="nonzero"></path><path fill="#000000" d="m660.0858 306.64688l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0.390625 -0.390625q-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.7343
75 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.328125 0.15625 -0.75zm10.1875 7.40625l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.171875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.203125 -0.390625q-1.234375 0.515625 -2.578125 0.515625q-2.15625 0 -3.328125 -1.296875q-1.15625 -1.296875 -1.15625 -3.828125q0 -1.21875 0.3125 -2.203125q0.328125 -1.0 0.921875 -1.6875q0.59375 -0.703125 1.4375 -1.078125q0.84375 -0.375 1.890625 -0.375q0.71875 0 1.328125 0.125q0.609375 0.125 1.171875 0.375l0 1.359375q-0.5625 -0.296875 -1.15625 -0.453125q-0.59375 -0.171875 -1.296875 -0.171875q-0.71875 0 -1.296875 0.28125q-0.578125 0.265625 -0.984375 0.78125q-0.40625 0.5 -0.625 1.25q-0.21875 0.734375 -0.21875 1.671875q0 1.984375 0.796875 3.0q
0.8125 1.0 2.359375 1.0q0.65625 0 1.25 -0.140625q0.609375 -0.15625 1.171875 -0.4375l0 1.3125zm9.390625 -4.78125q0 1.375 -0.328125 2.375q-0.328125 1.0 -0.875 1.65625q-0.546875 0.640625 -1.296875 0.96875q-0.734375 0.3125 -1.546875 0.3125q-0.984375 0 -1.71875 -0.359375q-0.734375 -0.359375 -1.21875 -1.03125q-0.46875 -0.671875 -0.703125 -1.625q-0.234375 -0.96875 -0.234375 -2.1875q0 -1.359375 0.3125 -2.359375q0.328125 -1.0 0.875 -1.640625q0.546875 -0.65625 1.28125 -0.96875q0.734375 -0.328125 1.5625 -0.328125q0.984375 0 1.703125 0.359375q0.734375 0.359375 1.21875 1.03125q0.484375 0.671875 0.71875 1.640625q0.25 0.953125 0.25 2.15625zm-1.453125 0.09375q0 -0.890625 -0.140625 -1.640625q-0.125 -0.75 -0.4375 -1.28125q-0.296875 -0.546875 -0.78125 -0.84375q-0.484375 -0.296875 -1.15625 -0.296875q-0.65625 0 -1.140625 0.328125q-0.46875 0.3125 -0.78125 0.859375q-0.296875 0.53125 -0.453125 1.265625q-0.140625 0.734375 -0.140625 1.546875q0 0.90625 0.140625 1.65625q0.140625 0.75 0.4375 1.28125q0.3125 0.53
125 0.78125 0.828125q0.484375 0.296875 1.15625 0.296875q0.65625 0 1.125 -0.3125q0.484375 -0.3125 0.78125 -0.859375q0.3125 -0.546875 0.453125 -1.265625q0.15625 -0.734375 0.15625 -1.5625zm10.09375 5.078125l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0.390625 -0.390625q-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.734375 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.32812
5 0.15625 -0.75zm11.046875 2.1875q0 0.734375 -0.125 1.40625q-0.109375 0.671875 -0.359375 1.25q-0.25 0.578125 -0.65625 1.046875q-0.390625 0.46875 -0.96875 0.8125q-0.578125 0.328125 -1.34375 0.515625q-0.765625 0.1875 -1.734375 0.1875l-2.1875 0l0 -10.21875l2.625 0q2.390625 0 3.5625 1.234375q1.1875 1.234375 1.1875 3.765625zm-1.46875 0.09375q0 -1.078125 -0.203125 -1.828125q-0.203125 -0.75 -0.625 -1.203125q-0.40625 -0.46875 -1.03125 -0.671875q-0.625 -0.21875 -1.46875 -0.21875l-1.1875 0l0 7.84375l1.03125 0q3.484375 0 3.484375 -3.921875z" fill-rule="nonzero"></path><path fill="#ea9999" d="m548.5169 213.68231l259.48157 0l0 40.559906l-259.48157 0z" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m548.5169 213.68231l259.48157 0l0 40.559906l-259.48157 0z" fill-rule="nonzero"></path><path fill="#000000" d="m660.0858 239.82227l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0.390625 -0.390625q
-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.734375 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.328125 0.15625 -0.75zm10.1875 7.40625l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.171875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.203125 -0.390625q-1.234375 0.515625 -2.578125 0.515625q-2.15625 0 -3.328125 -1.296875q-1.15625 -1.296875 -1.15625 -3.828125q0 -1.21875 0.3
125 -2.203125q0.328125 -1.0 0.921875 -1.6875q0.59375 -0.703125 1.4375 -1.078125q0.84375 -0.375 1.890625 -0.375q0.71875 0 1.328125 0.125q0.609375 0.125 1.171875 0.375l0 1.359375q-0.5625 -0.296875 -1.15625 -0.453125q-0.59375 -0.171875 -1.296875 -0.171875q-0.71875 0 -1.296875 0.28125q-0.578125 0.265625 -0.984375 0.78125q-0.40625 0.5 -0.625 1.25q-0.21875 0.734375 -0.21875 1.671875q0 1.984375 0.796875 3.0q0.8125 1.0 2.359375 1.0q0.65625 0 1.25 -0.140625q0.609375 -0.15625 1.171875 -0.4375l0 1.3125zm9.390625 -4.78125q0 1.375 -0.328125 2.375q-0.328125 1.0 -0.875 1.65625q-0.546875 0.640625 -1.296875 0.96875q-0.734375 0.3125 -1.546875 0.3125q-0.984375 0 -1.71875 -0.359375q-0.734375 -0.359375 -1.21875 -1.03125q-0.46875 -0.671875 -0.703125 -1.625q-0.234375 -0.96875 -0.234375 -2.1875q0 -1.359375 0.3125 -2.359375q0.328125 -1.0 0.875 -1.640625q0.546875 -0.65625 1.28125 -0.96875q0.734375 -0.328125 1.5625 -0.328125q0.984375 0 1.703125 0.359375q0.734375 0.359375 1.21875 1.03125q0.484375 0.671875 0.71
875 1.640625q0.25 0.953125 0.25 2.15625zm-1.453125 0.09375q0 -0.890625 -0.140625 -1.640625q-0.125 -0.75 -0.4375 -1.28125q-0.296875 -0.546875 -0.78125 -0.84375q-0.484375 -0.296875 -1.15625 -0.296875q-0.65625 0 -1.140625 0.328125q-0.46875 0.3125 -0.78125 0.859375q-0.296875 0.53125 -0.453125 1.265625q-0.140625 0.734375 -0.140625 1.546875q0 0.90625 0.140625 1.65625q0.140625 0.75 0.4375 1.28125q0.3125 0.53125 0.78125 0.828125q0.484375 0.296875 1.15625 0.296875q0.65625 0 1.125 -0.3125q0.484375 -0.3125 0.78125 -0.859375q0.3125 -0.546875 0.453125 -1.265625q0.15625 -0.734375 0.15625 -1.5625zm10.09375 5.078125l-1.578125 0l-1.515625 -3.265625q-0.171875 -0.375 -0.359375 -0.625q-0.171875 -0.25 -0.390625 -0.390625q-0.203125 -0.140625 -0.453125 -0.203125q-0.234375 -0.0625 -0.546875 -0.0625l-0.65625 0l0 4.546875l-1.390625 0l0 -10.21875l2.734375 0q0.890625 0 1.53125 0.203125q0.640625 0.1875 1.046875 0.546875q0.421875 0.34375 0.609375 0.84375q0.1875 0.5 0.1875 1.09375q0 0.484375 -0.140625 0.90625q-0.
140625 0.421875 -0.421875 0.78125q-0.265625 0.34375 -0.6875 0.59375q-0.40625 0.25 -0.9375 0.375q0.4375 0.15625 0.734375 0.53125q0.296875 0.359375 0.609375 0.984375l1.625 3.359375zm-2.234375 -7.40625q0 -0.828125 -0.515625 -1.234375q-0.5 -0.40625 -1.4375 -0.40625l-1.3125 0l0 3.375l1.125 0q0.5 0 0.890625 -0.109375q0.390625 -0.109375 0.671875 -0.328125q0.28125 -0.234375 0.421875 -0.546875q0.15625 -0.328125 0.15625 -0.75zm11.046875 2.1875q0 0.734375 -0.125 1.40625q-0.109375 0.671875 -0.359375 1.25q-0.25 0.578125 -0.65625 1.046875q-0.390625 0.46875 -0.96875 0.8125q-0.578125 0.328125 -1.34375 0.515625q-0.765625 0.1875 -1.734375 0.1875l-2.1875 0l0 -10.21875l2.625 0q2.390625 0 3.5625 1.234375q1.1875 1.234375 1.1875 3.765625zm-1.46875 0.09375q0 -1.078125 -0.203125 -1.828125q-0.203125 -0.75 -0.625 -1.203125q-0.40625 -0.46875 -1.03125 -0.671875q-0.625 -0.21875 -1.46875 -0.21875l-1.1875 0l0 7.84375l1.03125 0q3.484375 0 3.484375 -3.921875z" fill-rule="nonzero"></path><path fill="#f4cccc" d="m548.
5169 90.192l259.48157 0l0 123.50116l-259.48157 0z" fill-rule="nonzero"></path><path stroke="#000000" stroke-width="2.0" stroke-linejoin="round" stroke-linecap="butt" d="m548.5169 90.192l259.48157 0l0 123.50116l-259.48157 0z" fill-rule="nonzero"></path><path fill="#000000" d="m663.6405 157.80258l-5.796875 0l0 -10.21875l5.796875 0l0 1.171875l-4.40625 0l0 3.171875l4.234375 0l0 1.171875l-4.234375 0l0 3.515625l4.40625 0l0 1.1875zm9.84375 0l-1.359375 0l-0.203125 -6.375l-0.09375 -2.4375l-0.46875 1.421875l-1.515625 4.0625l-0.953125 0l-1.4375 -3.90625l-0.484375 -1.578125l-0.03125 2.546875l-0.171875 6.265625l-1.3125 0l0.5 -10.21875l1.640625 0l1.375 3.84375l0.453125 1.296875l0.421875 -1.296875l1.453125 -3.84375l1.6875 0l0.5 10.21875zm8.3125 -7.09375q0 0.625 -0.234375 1.25q-0.234375 0.609375 -0.734375 1.09375q-0.484375 0.484375 -1.25 0.78125q-0.765625 0.296875 -1.828125 0.296875l-1.265625 0l0 3.671875l-1.390625 0l0 -10.21875l2.875 0q0.765625 0 1.453125 0.171875q0.703125 0.171875 1.21875 0.54687
5q0.53125 0.375 0.84375 0.96875q0.3125 0.59375 0.3125 1.4375zm-1.4375 0.0625q0 -0.984375 -0.65625 -1.5q-0.640625 -0.53125 -1.796875 -0.53125l-1.421875 0l0 4.203125l1.296875 0q1.234375 0 1.90625 -0.53125q0.671875 -0.546875 0.671875 -1.640625zm10.421875 -2.0l-3.015625 0l0 9.03125l-1.40625 0l0 -9.03125l-3.03125 0l0 -1.1875l7.453125 0l0 1.1875zm9.46875 -1.1875l-3.6875 6.5625l0 3.65625l-1.40625 0l0 -3.6875l-3.703125 -6.53125l1.6875 0l2.03125 3.734375l0.75 1.5l0.6875 -1.359375l2.046875 -3.875l1.59375 0z" fill-rule="nonzero"></path></g></svg>
+
Added: 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=1694171&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md (added)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/tar.md Wed Aug 5 10:52:01 2015
@@ -0,0 +1,210 @@
+<!--
+ Licensed to the Apache Software Foundation (ASF) under one or more
+ contributor license agreements. See the NOTICE file distributed with
+ this work for additional information regarding copyright ownership.
+ The ASF licenses this file to You under the Apache License, Version 2.0
+ (the "License"); you may not use this file except in compliance with
+ the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+-->
+
+# Structure of TAR files
+
+Here is described the phisical layout of a TAR file as used by Apache Oak.
+First, a brief introduction of the TAR format is given. Next, more details are
+provided about the low level information that are written in TAR entries.
+Finally, it's described how Oak saves a graph data structure inside the TAR file
+and how this representation is optimized for fast retrieval.
+
+## Organization of a TAR file
+
+Phisically speaking, a TAR file is a linear sequence of blocks. A TAR file is
+terminated by two blocks containing zero bytes. Every block has a size of 512
+bytes.
+
+Logically speaking, a TAR file is a linear sequence of entries. Every entry is
+represented by two or more blocks. The first block always contains the entry
+header. Subsequent blocks store the content of the file.
+
+The entry header is composed of the following fields:
+
+- file name (100 bytes) - name of the file stored in this entry.
+
+- file mode (8 bytes) - string representation of the octal file mode.
+
+- owner's numeric ID (8 bytes) - string representation of the user ID of the
+ owner of the file.
+
+- group's numeric ID (8 bytes) - string representation of the group ID of the
+ owner of the file.
+
+- file size (12 bytes) - string representation of the octal size of the file.
+
+- last modification time (12 bytes) - string representation of the octal time
+ stamp when the file was last modified.
+
+- checksum (8 bytes) - checksum for the header data.
+
+- file type (1 byte) - type of the file stored in the entry. This field
+ specifies if the file is a regular file, a hard link or a symbolic link.
+
+- name of linked file (1 byte) - in case the file stored in the entry is a link,
+ this field stores the name of the file pointed to by the link.
+
+## The TAR file as used by Oak
+
+Some fields are not used by Oak. In particular, Oak sets the file mode, the
+owner's numeric ID, the group's numeric ID, the checksum, and the name of linked
+file to uninteresting values. The only meaningful values assigned to the fields
+of the entry values are:
+
+- file name: the name of the data file. There are different data files used by
+ Oak. They are described below.
+
+- file size: the size of the data file. The value assigned to this field is
+ trivially computed from the amount of information stored in the data file.
+
+- last modification time: the time stamp when the entry was written.
+
+There are three kind of files stored in a TAR file:
+
+- segments: this type of file contains data about a segment in the segment
+ store. This kind of file has a file name in the form `UUID.CRC2`, where `UUID`
+ is a 128 bit UUID represented as an hexadecimal string and `CRC2` is a zer-
+ padded numeric string representing the CRC2 checksum of the raw segment data.
+
+- graph: this file has a name ending in `.gph` and contains a representaion of a
+ graph. The graph is represented as an adjacency list of UUIDs.
+
+- index: this file has a name ending in `.idx` and contains a sorted list of
+ every segment contained in the TAR file.
+
+The layout of the TAR file used by Oak is engineered for perfomance of read
+operations. In particular, the most important information is stored in the
+bottom entries. Reading the entries from the bottom of the file, you encounter
+first the index, then the graph, then segment files. The idea is that the index
+must be read first, because it provides a fast tool to locate segments in the
+rest of the file. Next comes the graph, that describes how segments relate to
+each other. Last come the segments, whose relative order can be ignored.
+
+At the same time, the layout of the TAR file allows fast append-only operations
+when writing. Since the relative order of segment files is not important,
+segment entries can be written in a first come, first served basis. The index at
+the end of the file will provide a fast way to access them even if they are
+scattered around the file.
+
+## Segment files
+
+Segment files contain raw data about a segment. Even if there are multiple kinds
+of segments, TAR file only distinguishes between data and non-data segments. A
+non-data segment is always saved as-is in the TAR file, without further
+processing. A data segment, instead, is inspected to extract references to other
+segments.
+
+A data segment can contain at most 255 references to other segments. These
+references are simply stored as a list of UUIDs. The referenced segments can be
+stored inside the current TAR file or outside of it. In the first case, the
+referenced segment can be found by inspecting the index. In the second case, an
+external agent is responsible to find the segment in another TAR file.
+
+The list of segments referenced by a data segment will end up in the graph file.
+To speed up the process of locating a segment in the list of referenced segment,
+this list is maintained ordered.
+
+## Graph files
+
+The graph file represents the relationships between segments stored inside or
+outside the TAR file. The graph is stored as an adjacency list of UUID, where
+each UUID represents a segment.
+
+The format of the graph file is optimized for reading. The graph file is stored
+in reverse order to maintain the most important information at the end of the
+file. This strategy is inline with the overall layout of the entries in the TAR
+file.
+
+The content of the graph file is divided in three main parts: a graph header, a
+graph adjacency list and a vertex mapping table.
+
+The graph header contains the following fields:
+
+- a magic number (4 bytes): identifies the beginning of a graph file.
+
+- size of the graph adjacency list (4 bytes): number of bytes occupied by the
+ graph adjacency list.
+
+- size of the vertex mapping table (4 bytes): number of bytes occupied by the
+ vertex mapping table.
+
+- checksum (4 bytes): a CRC2 checksum of the content of the graph file.
+
+Immediately after the graph header, the graph adjacency list is stored. In the
+list, each vertex is represented by an integer. Each integer represents an index
+in the vertex mapping table. For each vertex stored in the adjacency list, the
+following information are written:
+
+- the integer representing the current vertex.
+
+- zero or more integers for each vertex referenced by the current one.
+
+- a sentinel value representing the list of adjacent vertices (-1).
+
+At the end, the vertex mapping table is stored. This table is just an ordered
+list of UUIDs. The integers used in the graph adjacency list can be used as
+index in the vertext mapping table to read the UUID of the corresponding
+segment. This is a space optimization. Since UUIDs can be repeated more than
+once in the adjacency list, it make sense to replace them with cheaper
+placeholders. A UUID is 128 bit long, while an integer just 4.
+
+## Index files
+
+The index file is an ordered list of references to the entries contained in the
+TAR file. The references are ordered by UUID and they point to the position in
+the file where the entry is stored. Like the graph file, even the index file is
+stored backwards.
+
+The index file is divided in two parts. The first is an index header, the second
+contains the real data about the index.
+
+The index data contains the following fields:
+
+- a magic number (4 bytes): identifies the beginning of an index file.
+
+- size fo the index (4 bytes): number of bytes occupied by the index data. This
+ size also contains padding bytes that are added to the index to make it align
+ with the TAR block boundary.
+
+- number of entries (4 bytes): how many entries the index contains.
+
+- checksum (4 bytes): a CRC32 checksum of the content of the index file.
+
+After the header, the content of the index starts. For every entry contained in
+the index, the following information are stored:
+
+- the most significat bits of the UUID (8 bytes)
+
+- the least significat bits of the UUID (8 bytes)
+
+- the offset in the TAR file where the TAR entry containing the segment is
+ located.
+
+- the size of the entry in the TAR file.
+
+Since the entries in the index are sorted by UUID, and since the UUIDs assigned
+to the entries are uniformly distributed, when searching an entry by its UUID an
+efficient algorithm called interpolation search can be used. This algorithm is a
+variation of binary search. While in binary search the search space (in this
+case, the array of entry) is halved at every iteration, interpolation search
+exploits the distribution of the keys to remove a portion of the search space
+that is potentially bigger than the half of it. Interpolation search is a more
+natural approximation of the way a person searches in a phone book. If the name
+to search begins with the letter T, in example, it makes no sense to open the
+phone book at the half. It is way more efficient, instead, to open the phone
+book close to the bottom quarter, since names starting with the letter T are
+more likely to be distributed in that part of the phone book.
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=1694171&r1=1694170&r2=1694171&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 Wed Aug 5 10:52:01 2015
@@ -18,6 +18,8 @@
Segment Storage Design Overview
=========================
+TODO: merge with [Records and segments](segment/records.html).
+
The SegmentNodeStore is an Oak storage backend that stores content as various
types of *records* within larger *segments*. One or more *journals* are
used to track the latest state of the repository. In the Tar implementation
Modified: jackrabbit/oak/trunk/oak-doc/src/site/site.xml
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/site.xml?rev=1694171&r1=1694170&r2=1694171&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/site.xml (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/site.xml Wed Aug 5 10:52:01 2015
@@ -41,7 +41,7 @@ under the License.
<item href="nodestore/overview.html" name="Node Storage" />
<item href="plugins/blobstore.html" name="Blob Storage" />
<item href="nodestore/documentmk.html" name="DocumentNodeStore" />
- <item href="nodestore/segmentmk.html" name="SegmentNodeStore" />
+ <item href="nodestore/segment/overview.html" name="Segment Node Store" />
<item href="query/query.html" name="Query" />
<item href="query/lucene.html" name="Index - Lucene" />
<item href="query/solr.html" name="Index - Solr" />