You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2013/10/15 03:49:33 UTC
git commit: DOC: Large update of cache architure.
Updated Branches:
refs/heads/master 30fcc2b2e -> 5c39d024c
DOC: Large update of cache architure.
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo
Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/5c39d024
Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/5c39d024
Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/5c39d024
Branch: refs/heads/master
Commit: 5c39d024cd6bdd3aaa1b224904d23368b7d3d614
Parents: 30fcc2b
Author: Alan M. Carroll <am...@network-geographics.com>
Authored: Mon Oct 14 09:44:51 2013 -0500
Committer: Alan M. Carroll <am...@network-geographics.com>
Committed: Mon Oct 14 20:49:07 2013 -0500
----------------------------------------------------------------------
doc/arch/cache/cache-arch.en.rst | 378 +++++++++++++++----
doc/arch/cache/cache-data-structures.en.rst | 10 +-
.../images/ats-cache-doc-layout-pre-3-2-0.png | Bin 7731 -> 0 bytes
doc/arch/cache/images/ats-cache-doc-layout.png | Bin 9470 -> 0 bytes
doc/arch/cache/images/ats-cache-layout.jpg | Bin 55045 -> 0 bytes
.../cache/images/ats-cache-storage-units.png | Bin 6190 -> 0 bytes
.../cache/images/cache-directory-structure.png | Bin 0 -> 28553 bytes
.../cache/images/cache-doc-layout-3-2-0.png | Bin 0 -> 7357 bytes
.../cache/images/cache-doc-layout-4-0-1.png | Bin 0 -> 8524 bytes
doc/arch/cache/images/cache-multi-fragment.png | Bin 0 -> 47782 bytes
doc/arch/cache/images/cache-span-layout.png | Bin 0 -> 8533 bytes
doc/arch/cache/images/cache-spans.png | Bin 0 -> 5085 bytes
doc/arch/cache/images/cache-stripe-layout.png | Bin 0 -> 11594 bytes
doc/glossary.en.rst | 13 +-
14 files changed, 314 insertions(+), 87 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/cache-arch.en.rst
----------------------------------------------------------------------
diff --git a/doc/arch/cache/cache-arch.en.rst b/doc/arch/cache/cache-arch.en.rst
index e249604..cc7395a 100755
--- a/doc/arch/cache/cache-arch.en.rst
+++ b/doc/arch/cache/cache-arch.en.rst
@@ -1,19 +1,19 @@
.. 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
-
+ 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.
+
+ 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.
Cache Architecture
******************
@@ -23,9 +23,20 @@ Cache Architecture
Introduction
~~~~~~~~~~~~
-In addition to an HTTP proxy, |ATS| is also an HTTP cache. |TS| can cache any octet stream although it currently supports only those octet streams delivered by the HTTP protocol. When such a stream is cached it is termed an *object* in the cache. The server from which the content was retrieved is called the *origin server*. A stored object contains the octet stream content and the HTTP request and response headers. Each object is identified by a globally unique value called a *cache key*. By default this is generated by taking the `MD5 hash <http://www.openssl.org/docs/crypto/md5.html>`_ of the URI used to retrieve the content from the origin server.
+In addition to an HTTP proxy, |ATS| is also an HTTP cache. |TS| can cache any octet stream although it currently
+supports only those octet streams delivered by the HTTP protocol. When such a stream is cached (along with the HTTP
+protocol headers) it is termed an *object* in the cache. Each object is identified by a globally unique value called a
+*cache key*. By default this is generated by taking the `MD5 hash <http://www.openssl.org/docs/crypto/md5.html>`_ of the
+URI used to retrieve the content from the origin server.
+
+The purpose of this document is to describe the basic structure and implementation details of the |TS| cache.
+Configuration of the cache will be discussed only to the extent needed to understand the internal mechanisms. This
+document will be useful primarily to |TS| developers working on the |TS| codebase or plugins for |TS|. It is assumed the
+reader is already familiar with the :ref:`admin-guide` and specifically with :ref:`http-proxy-caching` and
+:ref:`configuring-the-cache` along with the associated configuration files and values.
-The purpose of this document is to provide implementation details of the |TS| cache. Configuration of the cache will be discussed only to the extent needed to understand the internal mechanisms. This documeint will be useful primarily to |TS| developers working on the |TS| codebase or plugins for |TS|. It is assumed the reader is already familiar with the :ref:`admin-guide` and specifically with :ref:`http-proxy-caching` and :ref:`configuring-the-cache`, along with the associated configuration files and values.
+Unfortunately the internal terminology is not particularly consistent so this document will frequently use terms in
+different ways than they are used in the code in an attempt to create some consistency.
Cache Layout
~~~~~~~~~~~~
@@ -35,107 +46,221 @@ The first step in understanding cache operations is to understand the data struc
Cache storage
=============
-The raw storage for the |TS| cache is configured in :file:`storage.config`. This defines the "storage units" used by the cache. The storage units are treated as undifferentiated byte ranges.
+The raw storage for the |TS| cache is configured in :file:`storage.config`. Each line in the file defines a :term:`cache span` which is treated as an undifferentiated unit of storage.
-.. figure:: images/ats-cache-storage-units.png
+.. figure:: images/cache-spans.png
:align: center
- Example cache storage units
+ Two cache spans
-This storage is used by defining *volumes* in :file:`volume.config`. Volumes can be defined by a percentage of the total storage or an absolute amount of storage. Each volume is striped across the storage units so that every volume will be on every storage unit for robustness and performance.
+This storage organized in to a set of :term:`cache volume`\ s which are defined in :file:`volume.config`. Cache volumes
+can be defined by a percentage of the total storage or an absolute amount of storage. By default each cache volume is spread across all of the cache spans for robustness. The intersection of a cache volume and a cache span is a :term:`cache stripe`. Each cache span is divided in to cache stripes and each cache volume is a collection of those stripes.
-If the volumes for the example storage units were defined as
+If the cache volumes for the example cache spans were defined as
.. image:: images/ats-cache-volume-definition.png
:align: center
then the actual layout would look like
-.. image:: images/ats-cache-volume-layout.png
+.. image:: images/cache-span-layout.png
:align: center
-A cached object is stored entirely in a single volume and a single storage unit, objects are never split across volumes. The storage that holds a single object is called a *document*. Objects are assigned to volumes automatically based on a hash of the URI used to retrieve the object from the origin server. It is possible to configure this to a limited extent in :file:`hosting.config` which supports content from specific host or domain to be stored on specific volumes.
+A cached object is stored entirely in a single stripe, and therefore in a single cache span - objects are never split
+across cache volumes. Objects are assigned to a stripe (and hence to a cache volume) automatically based on a hash of
+the URI used to retrieve the object from the origin server. It is possible to configure this to a limited extent in
+:file:`hosting.config` which supports content from specific host or domain to be stored on specific volumes. In
+addition, as of version 4.0.1 it is possible to control which cache spans (and hence, which cache stripes) are contained
+in a specific cache volume.
-Volume Structure
+The layout and structure of the cache spans, the cache volumes, and the cache stripes that compose them are derived
+entirely from the :file:`storage.config` and :file:`cache.config` and is recomputed from scratch when the
+:process:`traffic_server` is started. Therefore any change to those files can (and almost always will) invalidate the
+existing cache in its entirety.
+
+Stripe Structure
================
-Volumes are treated as an undifferentiated span of bytes. Internally each stripe on each storage unit is treated almost entirely independently. The data structures described in this section are duplicated for each volume stripe, the part of a volume that resides in a single storage unit. This is how the term "volume" and :cpp:class:`Vol` are used inside the code. What a user thinks of as a volume of the cache is stored in the little used :cpp:class:`CacheVol`.
+|TS| treats the storage associated with a cache stripe as an undifferentiated span of bytes. Internally each stripe is
+treated almost entirely independently. The data structures described in this section are duplicated for each stripe.
+Interally the term "volume" is used for these stripes and implemented primarily in :cpp:class:`Vol`. What a user thinks
+of as a volume (what this document calls a "cache volume") is represented by :cpp:class:`CacheVol`.
-.. index: write cursor
-.. _write-cursor:
+.. note::
-Each storage unit in a volume is divided in to two areas -- content and directory. The directory area is used to maintain disk backups of the :ref:`in memory directory <volume-directory>`. The content area stores the actual objects and is used as a circular buffer where new documents overwrite the least recently cached documents. In particular no operating system file structure is present inside a cache volume. The location in a volume where new cache data is written is called the *write cursor*. This means that objects can be de facto evicted from cache even if they have not expired if the data is overwritten by the write cursor.
+ Stripe assignment must be done before working with an object because the directory is local to the stripe. Any cached
+ objects for which the stripe assignment is changed are effectively lost as their directory data will not be found in
+ the new stripe.
-.. figure:: images/ats-cache-write-cursor.png
+.. index:: cache directory
+.. _cache-directory:
+
+Cache Directory
+---------------
+
+.. index:: directory entry
+.. index:: fragment
+.. index:: cache ID
+
+.. _fragment:
+
+Content in a stripe is tracked via a directory. We call each element of the directory a "directory entry" and each is
+represented by :cpp:class:`Dir`. Each entry refers to a chunk of contiguous storage in the cache. These are referred to
+variously as "fragments", "segments", "docs" / "documents", and a few other things. This document will use the term
+"fragment" as that is the most common reference in the code. Overall the directory is treated as a hash with a "cache
+ID" as the key. A cache ID is a 128 value generated in various ways depending on context. This key is reduced and used
+as an index in to the directory to locate an entry in the standard way.
+
+The directory is used as a memory resident structure which means a directory entry is as small as possible (currently 10
+bytes). This forces some compromises on the data that can be stored there. On the hand this means that most cache misses
+do not require disk I/O which has a large performance benefit.
+
+An additional point is the directory is always fully sized. Once a stripe is initialized the directory size is
+fixed and is never changed. This size is related (roughly linearly) to the size of the stripe. It is for this reason the
+memory footprint of |TS| depends strongly on the size of the disk cache. Because the directory size does not change,
+neither does this memory requirement so |TS| does not consume more memory as more content is stored in the cache. If
+there is enough memory to run |TS| with an empty cache there is enough to run it with a full cache.
+
+.. figure:: images/cache-directory-structure.png
:align: center
- The write cursor and documents in the cache.
+Each entry stores the cache ID as the key, along with an offset in to the stripe and a size. The size stored in the
+directory entry is an :ref:`approximate size <dir-size>` which is at least as big as the actual data. Exact size data is
+stored in the fragment on disk.
-.. index:: volume directory
-.. _volume-directory:
+.. note::
-To find objects each volume has a directory of all documents in that volume. This directory is kept memory resident which means cache misses do not cause disk I/O. A side effect of this is that increasing the size of the cache (not storing more objects) increases the memory footprint of Traffic Server. Every document consumes at least one directory entry, although larger documents can require more entries.
+ Data in HTTP headers cannot be examined without disk I/O. This includes the original URL for the object. The original
+ source of the cache ID is not stored anywhere.
-.. index:: cache key
-.. _cache-key:
+The entries in a directory are grouped. The first level grouping is a *bucket*. This is a fixed number (currently 4 -
+defined a ``DIR_DEPTH``) of entries. The index generated from a cache ID is used as a bucket index (not an entry index).
+Buckets are grouped in to *segments*. All segments in a stripe have the same number of buckets. The number of segments
+in a stripe is chosen so that each segment has as many buckets as possible without exceeeding 65535 entries in a
+segment. Note that all segments in the same stripe will have the same number of buckets.
-The directory is a hash table with a 128 bit key. This kind of key is referred to as a *cache key*. The cache key for an object is used to locate the corresponding directory entry after volume assignment [#]_. This entry in turn references a span in the volume content area which contains the object header and possibly the object as well. The size stored in the directory entry is an :ref:`approximate size <dir-size>` which is at least as big as the actual data on disk. The document header on disk contains metadata for the document including the exact size of the entire document, and the HTTP headers associated with the object.
+Each entry has a previous and next index value which is used to link the entries in the same segment. The index size is
+16 bits which suffices to index any entry in the same segment. The stripe header contains an array of entry indices
+which are used as the roots of a free list. When a stripe is initialized all entries in a segment are put in the
+corresponding free list rooted in the stripe header. Entries are removed from this list when used and returned when no
+longer in use. Entries are allocated from the bucket indexed by a cache key if possible. The entries in the bucket are
+searched first and if any are on the free list, that entry is used. If none are available than the first entry on the
+segment free list is used. This entry is attached to the bucket via the same next and previous indices used for the free
+list so that it can be found when doing a lookup of a cache ID.
-.. note:: Data in HTTP headers cannot be examined without disk I/O. This includes the original URL for the object, as only the cache key (possibly) derived from it is stored in memory.
+Storage Layout
+--------------
-For persistence the directory is stored on disk in copies (A and B), one of which is "clean" and the other of which is being written from memory. These are stored in the directory section of the volume.
+The storage layout is the stripe metadata followed by cached content. The metadata consists of three parts - the stripe
+header, the directory, and the stripe footer. The metadata is stored twice. The header and the footer are instances of
+:cpp:class:`VolHeaderFooter`. This is a stub structure which can have a trailing variable sized array. This array is
+used as the segment free lists in the directory. Each contains the segment index of the first element of the free list
+for the segment. The footer is a copy of the header without the segment free lists. This makes the size of the header
+dependent on the directory but not the footer.
-.. figure:: images/ats-cache-volume-directory.png
+.. figure:: images/cache-stripe-layout.png
:align: center
- Volume directory structure
+Each stripe has several values that describe its basic layout.
+
+skip
+ The start of stripe data. This represents either space reserved at the start of a physical device to avoid problems
+ with the host operating system, or an offset representing use of space in the cache span by other stripes.
-The total size of the directory (the number of entries) is computed by taking the size of the volume and dividing by the average object size. The directory always consumes this amount of memory which has the effect that if cache size is increased so is the memory requirement for |TS|. The average object size defaults to 8000 bytes but can be configured using the value::
+start
+ The offset for the start of the content, after the stripe metadata.
+
+length
+ Total number of bytes in the stripe. :cpp:member:`Vol::len`.
+
+data length
+ Total number of blocks in the stripe available for content storage. :cpp:member:`Vol::data_blocks`.
+
+.. note:: Great care must be taken with sizes and lengths in the cache code because there are at least three different metrics (bytes, cache blocks, store blocks) used in various places.
+
+The total size of the directory (the number of entries) is computed by taking the size of the stripe and dividing by the
+average object size. The directory always consumes this amount of memory which has the effect that if cache size is
+increased so is the memory requirement for |TS|. The average object size defaults to 8000 bytes but can be configured
+using the value::
proxy.config.cache.min_average_object_size
-in :file:`records.config`. Increasing the average object size will reduce the memory footprint of the directory at the expense of reducing the number of distinct objects that can be stored in the cache [#]_.
+in :file:`records.config`. Increasing the average object size will reduce the memory footprint of the directory at the
+expense of reducing the number of distinct objects that can be stored in the cache [#]_.
-.. note:: Cache data on disk is never updated.
+.. index: write cursor
+.. _write-cursor:
+
+The content area stores the actual objects and is used as a circular buffer where new objects overwrite the least
+recently cached objects. The location in a volume where new cache data is written is called the *write cursor*. This
+means that objects can be de facto evicted from cache even if they have not expired if the data is overwritten by the
+write cursor. If an object is overwritten this is not detected at that time and the directory is not updated. Instead it
+will be noted if the object is accessed in the future and the disk read of the fragment fails.
+
+.. figure:: images/ats-cache-write-cursor.png
+ :align: center
-This is a key thing to keep in mind. What appear to be updates (such as doing a refresh on stale content and getting back a 304) are actually new copies of data being written at the write cursor. The originals are left as "dead" space which will be consumed when the write cursor arrives at that disk location. Once the volume directory is updated (in memory!) the original object in the cache is effectively destroyed. This is the general space management techinque used in other cases as well. If an object needs to removed from cache, only its volume directory entry is changed. No other work (and *particulary* no disk I/O) needs to be done.
+ The write cursor and documents in the cache.
-.. [#] Because each storage unit in each volume has a separate directory, the assignment must be done before the directory lookup.
+.. note:: Cache data on disk is never updated.
-.. [#] An interesting potential optimization would be configuring average object size per cache volume.
+This is a key thing to keep in mind. What appear to be updates (such as doing a refresh on stale content and getting
+back a 304) are actually new copies of data being written at the write cursor. The originals are left as "dead" space
+which will be consumed when the write cursor arrives at that disk location. Once the stripe directory is updated (in
+memory!) the original fragment in the cache is effectively destroyed. This is the general space management techinque
+used in other cases as well. If an object needs to removed from cache, only the directory needs to be changed. No other
+work (and *particularly* no disk I/O) needs to be done.
Object Structure
================
-Objects are stored as two types of data, metadata and content data. Metadata is all the data about the object and the content and includes the HTTP headers. The content data is the content of the object, the actual data delivered to the client as the object.
+Objects are stored as two types of data, metadata and content data. Metadata is all the data about the object and the
+content and includes the HTTP headers. The content data is the content of the object, the octet stream delivered to the
+client as the object.
-Objects are rooted in a :cpp:class:Doc structure stored in the cache. This is termed the "first ``Doc``" and always contains the metadata. It is always accessed first for any object. This ``Doc`` is located by doing a lookup of the corresponding cache key in the volume directory which specifies the location and approximate size of the ``Doc``. The ``Doc`` itself has fully accurate size data of both that specific ``Doc`` and the object.
+Objects are rooted in a :cpp:class:`Doc` structure stored in the cache. :cpp:class:`Doc` serves as the header data for a
+fragment and is contained at the start of every fragment. The first fragment for an object is termed the "first ``Doc``"
+and always contains the object metadata. Any operation on the object will read this fragment first. The fragment is
+located by converting the cache key for the object to a cache ID and then doing a lookup for a directory entry with that
+key. The directory entry has the offset and approximate size of the first fragment which is then read from the disk. This fragment will contain the request header and response along with overall object properties (such as content length).
.. index:: alternate
-|TS| supports `varying content <http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.44>`_ for objects. These are called *alternates*. All metadata for all alternates is stored in the first ``Doc`` including the set of alternates and the HTTP headers for them. This enables `alternate selection <http://trafficserver.apache.org/docs/trunk/sdk/http-hooks-and-transactions/http-alternate-selection.en.html>`_ to be done after the initial read from disk. An object that has more than one alternate will have the alternate content stored separately from the first ``Doc``. For objects with only one alternate the content may or may not be in the same (first) fragment as the metadata. Each separate alternate content is allocated a volume directory entry and the key for that entry is stored in the first ``Doc`` metadata.
+|TS| supports `varying content <http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.44>`_ for objects. These
+are called *alternates*. All metadata for all alternates is stored in the first fragment including the set of alternates
+and the HTTP headers for them. This enables `alternate selection
+<http://trafficserver.apache.org/docs/trunk/sdk/http-hooks-and-transactions/http-alternate-selection.en.html>`_ to be
+done after the initial read from disk. An object that has more than one alternate will have the alternate content stored
+separately from the first fragment. For objects with only one alternate the content may or may not be in the same (first)
+fragment as the metadata. Each separate alternate content is allocated a directory entry and the key for that
+entry is stored in the first fragment metadata.
-Prior to version 3.2.0 only the header data (not the fragment data) was stored in the :cpp:class:`CacheHTTPInfoVector` class which was marshaled to a variable length area of the on disk image.
+Prior to version 4.0.1 the header data was stored in the :cpp:class:`CacheHTTPInfoVector` class which was marshaled to a variable length area of the on disk image, followed by information about additional fragments if needed to store the object.
-.. figure:: images/ats-cache-doc-layout-pre-3-2-0.png
+.. figure:: images/cache-doc-layout-3-2-0.png
:align: center
- ``Doc`` layout, pre 3.2.0
+ ``Doc`` layout 3.2.0
-This had the problem that with only one fragment table it could not be reliable accurate for objects with more than one alternate [#]_. Therefore the fragment data was moved from being a separate variable length section of the metadata to being directly incorporated in to the :cpp:class:`CacheHTTPInfoVector` along with the header data, yielding a layout of the following form.
+This had the problem that with only one fragment table it could not be reliable for objects with more than one alternate
+[#]_. Therefore the fragment data was moved from being a separate variable length section of the metadata to being
+directly incorporated in to the :cpp:class:`CacheHTTPInfoVector`, yielding a layout of the following form.
-.. figure:: images/ats-cache-doc-layout.png
+.. figure:: images/cache-doc-layout-4-0-1.png
:align: center
- ``Doc`` layout, 3.2.0
+ ``Doc`` layout 4.0.1
+
+Each element in the vector contains for each alternate, in addition to the HTTP headers and the fragment table (if any), a cache key. This cache key identifies a directory entry that is referred to as the "earliest ``Doc``". This is the location where the content for the alternate begins.
-Each element in the vector contains for each alternate, in addition to the HTTP headers and the fragment table (if any), a cache key. This cache key identifies a volume directory entry that is referred to as the "earliest ``Doc``". This is the location where the content for the alternate begins.
+When the object is first cached, it will have a single alternate and that will be stored (if not too large) in first ``Doc``. This is termed a *resident alternate* in the code. This can only happen on the initial store of the object. If the metadata is updated (such as a ``304`` response to an ``If-Modified-Since`` request) then unless the object is small, the object data will be left in the original fragment and a new fragment written as the first fragment, making the alternate non-resident. "Small" is defined as less than the value :ts:cv:`proxy.config.cache.alt_rewrite_max_size`.
-When the object is first cached, it will have a single alternate and that will be stored (if not too large) in first ``Doc``. This is termed a *resident alternate* in the code. Resident alternates are not linked and the next time the header information is updated the object content will be separated.
+.. note::
-.. note:: The :cpp:class:`CacheHTTPInfoVector` is stored only in the first ``Doc``. Subsequent ``Doc`` instances will have an ``hlen`` of zero.
+ The :cpp:class:`CacheHTTPInfoVector` is stored only in the first ``Doc``. Subsequent ``Doc`` instances for the
+ object, including the earliest ``Doc``, should have an ``hlen`` of zero and if not, it is ignored.
-Large objects are split in to *fragments* when written to the cache. Each fragment has its own entry in the volume directory. This is indicated by a total document length that is longer than the content in first ``Doc`` or an earliest ``Doc``. In such a case a fragment offset table is stored. This contains the byte offset in the object content of the first byte of content data for each fragment past the first (as the offset for the first is always zero). This allows range requests to be serviced much more efficiently for large objects, as intermediate fragments can be skipped the first fragment with relevant data loaded next after the first/earliest ``Doc``. The last fragment in the sequence is detected by the fragment size and offset reaching the end of the total size of the object, there is no explicit end mark. Each fragment is computationally chained from the previous in that the cache key for fragment N is computed by::
+Large objects are split in to multiple fragments when written to the cache. This is indicated by a total document length that is longer than the content in first ``Doc`` or an earliest ``Doc``. In such a case a fragment offset table is stored. This contains the byte offset in the object content of the first byte of content data for each fragment past the first (as the offset for the first is always zero). This allows range requests to be serviced much more efficiently for large objects, as intermediate fragments can be skipped the first fragment with relevant data loaded next after the first/earliest ``Doc``. The last fragment in the sequence is detected by the fragment size and offset reaching the end of the total size of the object, there is no explicit end mark. Each fragment is computationally chained from the previous in that the cache key for fragment N is computed by::
key_for_N_plus_one = next_key(key_for_N);
@@ -143,15 +268,23 @@ where ``next_key`` is a global function that deterministically computes a new ca
Objects with multiple fragments are laid out such that the data fragments (including the earliest ``Doc``) are written first and the first ``Doc`` is written last. When read from disk, both the first and earliest ``Doc`` are validated (tested to ensure that they haven't been overwritten by the write cursor) to verify that the entire document is present on disk (as they bookend the other fragments - the write cursor cannot overwrite them without overwriting at leastone of the verified ``Doc`` instances). Note that while the fragments of a single object are ordered they are not necessarily contiguous as data from different objects are interleaved as the data arrives in |TS|.
-.. index:: pinned
+.. figure:: images/cache-multi-fragment.png
+ :align: center
-Documents which are "pinned" into the cache must not be overwritten so they are "evacuated" from in front of the write cursor. Each fragment is read and rewritten. There is a special lookup mechanism for objects that are being evacuated so that they can be found in memory rather than the potentially unreliable disk regions. The cache scans ahead of the write cursor to discover pinned objects as there is a dead zone immediately before the write cursor from which data cannot be evacuated. Evacuated data is read from disk and placed in the write queue and written as its turn comes up.
+ Multi-alternate and multi-fragment object storage
-It appears that objects can only be pinned via the :file:`cache.config` file and if the value::
+.. index:: pinned
- proxy.config.cache.permit.pinning
+Documents which are "pinned" into the cache must not be overwritten so they are "evacuated" from in front of the write
+cursor. Each fragment is read and rewritten. There is a special lookup mechanism for objects that are being evacuated so
+that they can be found in memory rather than the potentially unreliable disk regions. The cache scans ahead of the write
+cursor to discover pinned objects as there is a dead zone immediately before the write cursor from which data cannot be
+evacuated. Evacuated data is read from disk and placed in the write queue and written as its turn comes up.
-is set to non-zero (it is zero by default). Objects which are in use when the write cursor is near use the same underlying evacuation mechanism but are handled automatically and not via the explicit ``pinned`` bit in :cpp:class:`Dir`.
+It appears that objects can only be pinned via the :file:`cache.config` file and if the
+:ts:cv:`proxy.config.cache.permit.pinning` is set to non-zero (it is zero by default). Objects which are in use when the
+write cursor is near use the same underlying evacuation mechanism but are handled automatically and not via the explicit
+``pinned`` bit in :cpp:class:`Dir`.
.. [#] It could, under certain circumstances, be accurate for none of the alternates.
@@ -381,22 +514,44 @@ If this is zero then the built caclulations are used which compare the freshness
If the object is not stale then it is served to the client. If stale the client request may be changed to an ``If Modified Since`` request to revalidate.
-The request is served using a standard virtual connection tunnel (``HttpTunnel``) with the :cpp:class:`CacheVC` acting as the producer and the client ``NetVC`` acting as the sink. If the request is a range request this can be modified with a transform to select the appropriate parts of the object or, if the request contains a single range, it can use the range acceleration.
+The request is served using a standard virtual connection tunnel (``HttpTunnel``) with the :cpp:class:`CacheVC` acting
+as the producer and the client ``NetVC`` acting as the sink. If the request is a range request this can be modified with
+a transform to select the appropriate parts of the object or, if the request contains a single range, it can use the
+range acceleration.
-Range acceleration is done by consulting a fragment offset table attached to the earliest ``Doc`` which contains offsets for all fragments past the first. This allows loading the fragment containing the first requested byte immediately rather than performing reads on the intermediate fragments.
+Range acceleration is done by consulting a fragment offset table attached to the earliest ``Doc`` which contains offsets
+for all fragments past the first. This allows loading the fragment containing the first requested byte immediately
+rather than performing reads on the intermediate fragments.
Cache Write
===========
-Writing to cache is handled by an instance of the class :cpp:class:`CacheVC`. This is a virtual connection which receives data and writes it to cache, acting as a sink. For a standard transaction data transfers between virtual connections (*VConns*) are handled by :ccp:class:HttpTunnel. Writing to cache is done by attaching a ``CacheVC`` instance as a tunnel consumer. It therefore operates in parallel with the virtual connection that transfers data to the client. The data does not flow to the cache and then to the client, it is split and goes both directions in parallel. This avoids any data synchronization issues between the two.
+Writing to cache is handled by an instance of the class :cpp:class:`CacheVC`. This is a virtual connection which
+receives data and writes it to cache, acting as a sink. For a standard transaction data transfers between virtual
+connections (*VConns*) are handled by :cpp:class:HttpTunnel. Writing to cache is done by attaching a ``CacheVC``
+instance as a tunnel consumer. It therefore operates in parallel with the virtual connection that transfers data to the
+client. The data does not flow to the cache and then to the client, it is split and goes both directions in parallel.
+This avoids any data synchronization issues between the two.
.. sidebar:: Writing to disk
- The actual write to disk is handled in a separate thread dedicated to I/O operations, the AIO threads. The cache logic marshals the data and then hands the operation off to the AIO thread which signals back once the operation completes.
+ The actual write to disk is handled in a separate thread dedicated to I/O operations, the AIO threads. The cache
+ logic marshals the data and then hands the operation off to the AIO thread which signals back once the operation
+ completes.
-While each ``CacheVC`` handles its transactions independently, they do interact at the volume level as each ``CacheVC`` makes calls to the volume object to write its data to the volume content. The ``CacheVC`` accumulates data internally until either the transaction is complete or the amount of data to write exceeds the target fragment size. In the former case the entire object is submitted to the volume to be written. In the latter case a target fragment size amount of data is submitted and the ``CacheVC`` continues to operate on subsequent data. The volume in turn places these write requests in an holding area called the `aggregation buffer`_.
+While each ``CacheVC`` handles its transactions independently, they do interact at the volume level as each ``CacheVC``
+makes calls to the volume object to write its data to the volume content. The ``CacheVC`` accumulates data internally
+until either the transaction is complete or the amount of data to write exceeds the target fragment size. In the former
+case the entire object is submitted to the volume to be written. In the latter case a target fragment size amount of
+data is submitted and the ``CacheVC`` continues to operate on subsequent data. The volume in turn places these write
+requests in an holding area called the `aggregation buffer`_.
-For objects under the target fragment size there is no consideration of order, the object is simply written to the volume content. For larger objects the earliest ``Doc`` is written first and the first ``Doc`` written last. This provides some detection ability should the object be overwritten. Because of the nature of the write cursor no fragment after the first fragment (in the earliest ``Doc``) can be overwritten without also overwriting that first fragment (since we know at the time the object was finalized in the cache the write cursor was at the position of the first ``Doc``).
+For objects under the target fragment size there is no consideration of order, the object is simply written to the
+volume content. For larger objects the earliest ``Doc`` is written first and the first ``Doc`` written last. This
+provides some detection ability should the object be overwritten. Because of the nature of the write cursor no fragment
+after the first fragment (in the earliest ``Doc``) can be overwritten without also overwriting that first fragment
+(since we know at the time the object was finalized in the cache the write cursor was at the position of the first
+``Doc``).
.. note:: It is the responsibility of the ``CacheVC`` to not submit writes that exceed the target fragment size.
@@ -411,31 +566,94 @@ Cache write also covers the case where an existing object in the cache is modifi
* An alternate of the object is retrieved from an origin server and added to the object.
* An alternate of the object is removed (e.g., due to a ``DELETE`` request).
-In every case the metadata for the object must be modified. Because |TS| never updates data already in the cache this means the first ``Doc`` will be written to the cache again and the volume directory entry updated. Because a client request has already been processed the first ``Doc`` has been read from cache and is in memory. The alternate vector is updated as appropriate (an entry added or removed, or changed to contain the new HTTP headers), and then written to disk. It is possible for multiple alternates to be updated by different ``CacheVC`` instances at the same time. The only contention is the first ``Doc``, the rest of the data for each alternate is completely independent.
+In every case the metadata for the object must be modified. Because |TS| never updates data already in the cache this
+means the first ``Doc`` will be written to the cache again and the volume directory entry updated. Because a client
+request has already been processed the first ``Doc`` has been read from cache and is in memory. The alternate vector is
+updated as appropriate (an entry added or removed, or changed to contain the new HTTP headers), and then written to
+disk. It is possible for multiple alternates to be updated by different ``CacheVC`` instances at the same time. The only
+contention is the first ``Doc``, the rest of the data for each alternate is completely independent.
.. _aggregation-buffer:
Aggregation Buffer
------------------
-Disk writes to cache are handled through an *aggregation buffer*. There is one for each :cpp:class:`Vol` instance.
-To minimize the number of system calls data is written to disk in units of roughly :ref:`target fragment size <target-fragment-size>` bytes. The algorithm used is simple - data is piled up in the aggregation buffer until no more will fit without going over the target fragment size, at which point the buffer is written to disk and the volume directory entries for objects with data in the buffer are updated with the actual disk locations for those objects (which are determined by the write to disk action). After the buffer is written it is cleared and process repeats. There is a special lookup table for the aggregation buffer so that object lookup can find cache data in that memory.
+Disk writes to cache are handled through an *aggregation buffer*. There is one for each :cpp:class:`Vol` instance. To
+minimize the number of system calls data is written to disk in units of roughly :ref:`target fragment size
+<target-fragment-size>` bytes. The algorithm used is simple - data is piled up in the aggregation buffer until no more
+will fit without going over the targer fragment size, at which point the buffer is written to disk and the volume
+directory entries for objects with data in the buffer are updated with the actual disk locations for those objects
+(which are determined by the write to disk action). After the buffer is written it is cleared and process repeats. There
+is a special lookup table for the aggregation buffer so that object lookup can find cache data in that memory.
-Because data in the aggregation buffer is visible to other parts of the cache, particularly `cache lookup`_, there is no need to push a partial filled aggregation buffer to disk. In effect any such data is effectively memory cached until enough additional cache content arrives to fill the buffer.
+Because data in the aggregation buffer is visible to other parts of the cache, particularly `cache lookup`_, there is no
+need to push a partial filled aggregation buffer to disk. In effect any such data is effectively memory cached until
+enough additional cache content arrives to fill the buffer.
-The target fragment size has little effect on small objects because the fragmen size is used only to parcel out disk write operations. For larger objects the effect very significant as it causes those objects to be broken up in to fragments at different locations on in the volume. Each fragment write has its own entry in the volume directory which are computationally chained (each cache key is computed from the previous one). If possible a fragment table is accumulated in the first ``Doc`` which has the offsets of the first byte for each fragment.
+The target fragment size has little effect on small objects because the fragment sized is used only to parcel out disk
+write operations. For larger objects the effect very significant as it causes those objects to be broken up in to
+fragments at different locations on in the volume. Each fragment write has its own entry in the volume directory which
+are computational chained (each cache key is computed from the previous one). If possible a fragment table is
+accumulated in the earliest ``Doc`` which has the offsets of the first byte for each fragment.
Evacuation
----------
-By default the write cursor will overwrite (de facto evict from cache) objects as it proceeds once it has gone around the volume content at least once. In some cases this is not acceptable and the object is *evacuated* by reading it from the cache and then writing it back to cache which moves the physical storage of the object from in front of the write cursor to behind the write cursor. Objects that are evacuated are those that are active in either a read or write operation, or objects that are pinned [#]_.
-
-Evacuation starts by dividing up the volume content in to a set of regions of ``EVACUATION_BUCKET_SIZE`` bytes. The :cpp:member:`Vol::evacuate` member is an array with an element for each region. Each element is a doubly linked list of :cpp:class:`EvacuationBlock` instances. Each instance contains a :cpp:class:`Dir` that specifies the document to evacuate. Objects to be evacuated are described in an ``EvacuationBlock`` which is put into an evacuation bucket based on the offset of the storage location.
-
-There are two types of evacuations, reader based and forced. The ``EvacuationBlock`` has a reader count to track this. If the reader count is zero, then it is a forced evacuation and the target, if it exists, will be evacuated when the write cursor gets close. If the reader value is non-zero then it is a count of entities that are currently expecting to be able to read the object. Readers increment the count when they require read access to the object, or create the ``EvacuationBlock`` with a count of 1. When a reader is finished with the object it decrements the count and removes the ``EvacuationBlock`` if the count goes to zero. If the ``EvacuationBlock`` already exists with a count of zero, the count is not modified and the number of readers is not tracked, so the evacuation be valid as long as the object exists.
+By default the write cursor will overwrite (de facto evict from cache) objects as it proceeds once it has gone around
+the volume content at least once. In some cases this is not acceptable and the object is *evacuated* by reading it from
+the cache and then writing it back to cache which moves the physical storage of the object from in front of the write
+cursor to behind the write cursor. Objects that are evacuated are those that are active in either a read or write
+operation, or objects that are pinned [#]_.
+
+Evacuation starts by dividing up the volume content in to a set of regions of ``EVACUATION_BUCKET_SIZE`` bytes. The
+:cpp:member:`Vol::evacuate` member is an array with an element for each region. Each element is a doubly linked list of
+:cpp:class:`EvacuationBlock` instances. Each instance contains a :cpp:class:`Dir` that specifies the document to
+evacuate. Objects to be evacuated are descrinbed in an ``EvacuationBlock`` which is put in to an evacuation bucket based
+on the offset of the storage location.
+
+There are two types of evacuations, reader based and forced. The ``EvacuationBlock`` has a reader count to track this.
+If the reader count is zero, then it is a forced evacuation and the the target, if it exists, will be evacuated when the
+write cursor gets close. If the reader value is non-zero then it is a count of entities that are currently expecting to
+be able to read the object. Readers increment the count when they require read access to the object, or create the
+``EvacuationBlock`` with a count of 1. When a reader is finished with the object it decrements the count and removes the
+``EvacuationBlock`` if the count goes to zero. If the ``EvacuationBlock`` already exists with a count of zero, the count
+is not modified and the number of readers is not tracked, so the evacuation be valid as long as the object exists.
Objects are evacuated as the write cursor approaches. The volume calculates the current amount of
Before doing a write, the method :cpp:func:`Vol::evac_range()` is called to start an evacuation. If an eva
-.. [#] `Work is under way <https://issues.apache.org/jira/browse/TS-2020>`_ on extending this to include objects that are in the ram cache.
+Initialization
+==============
+
+Initialization starts with an instance of :cpp:class:`Store` reading the storage configuration file, by default
+:file:`storage.config`. For each valid element in the file an instance of :cpp:class:`Span` is created. These are of
+basically four types,
+
+* File
+* Directory
+* Disk
+* Raw device
+
+After setting all the `Span` instances they are grouped by device id to internal linked lists attached to the
+:cpp:member:`Store::disk` array [#]_. Spans that refer to the same directory, disk, or raw device are coalesced in to a
+single span. Spans that refer to the same file with overlapping offsets are also coalesced [#]_. This is all done in :c:func:`ink_cache_init()` called during startup.
+
+After configuration initialization the cache processor is started by calling :ccp:func:`CacheProcessor::start()`. This
+does a number of things.
+
+For each valid span, an instance of :cpp:class:`CacheDisk` is created. This class is a continuation and so can be used
+to perform potentially blocking operations on the span. This what is passed to the AIO threads to be called when an I/O
+operation completes. These are then dispatched to AIO threads to perform storage unit initialization. After all of those
+have completed, the resulting storage is distributed across the volumes in :c:func:`cplist_reconfigure`. The :cpp:class:`CacheVol` instances are created at this time.
+
+.. rubric:: Footnotes
+
+.. [#] `Work is under way <https://issues.apache.org/jira/browse/TS-2020>`_ on extending this to include objects that
+ are in the ram cache.
+
+.. [#] This linked list is mostly ignored in later processing, causing all but one file or directory storage units on
+ the same device to be ignored. See `TS-1869 <https://issues.apache.org/jira/browse/TS-1869>`_.
+
+.. [#] It is unclear to me how that can happen, as the offsets are computed later and should all be zero at the time the
+ spans are coalesced, and as far as I can tell the sort / coalesce is only done during initialization.
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/cache-data-structures.en.rst
----------------------------------------------------------------------
diff --git a/doc/arch/cache/cache-data-structures.en.rst b/doc/arch/cache/cache-data-structures.en.rst
index 6c93ebf..6ce9bc8 100755
--- a/doc/arch/cache/cache-data-structures.en.rst
+++ b/doc/arch/cache/cache-data-structures.en.rst
@@ -5,9 +5,9 @@
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
@@ -89,6 +89,10 @@ Cache Data Structures
Array of of :cpp:class:`EvacuationBlock` buckets. This is sized so there is one bucket for every evacuation span.
+ .. cpp:member:: off_t len
+
+ Length of stripe in bytes.
+
.. cpp:function:: int Vol::evac_range(off_t low, off_t high, int evac_phase)
Start an evacuation if there is any :cpp:class:`EvacuationBlock` in the range from *low* to *high*. Return 0 if no evacuation was started, non-zero otherwise.
@@ -153,6 +157,8 @@ Cache Data Structures
Unknown. (A checksum of some sort)
+.. cpp:class:: VolHeaderFooter
+
.. rubric:: Footnotes
.. [#] Changed in version 3.2.0. This previously resided in the first ``Doc`` but that caused different alternates to share the same fragment table.
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/ats-cache-doc-layout-pre-3-2-0.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/ats-cache-doc-layout-pre-3-2-0.png b/doc/arch/cache/images/ats-cache-doc-layout-pre-3-2-0.png
deleted file mode 100755
index d7b2c4f..0000000
Binary files a/doc/arch/cache/images/ats-cache-doc-layout-pre-3-2-0.png and /dev/null differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/ats-cache-doc-layout.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/ats-cache-doc-layout.png b/doc/arch/cache/images/ats-cache-doc-layout.png
deleted file mode 100755
index 438ed77..0000000
Binary files a/doc/arch/cache/images/ats-cache-doc-layout.png and /dev/null differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/ats-cache-layout.jpg
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/ats-cache-layout.jpg b/doc/arch/cache/images/ats-cache-layout.jpg
deleted file mode 100644
index 3c13487..0000000
Binary files a/doc/arch/cache/images/ats-cache-layout.jpg and /dev/null differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/ats-cache-storage-units.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/ats-cache-storage-units.png b/doc/arch/cache/images/ats-cache-storage-units.png
deleted file mode 100644
index 47e1bda..0000000
Binary files a/doc/arch/cache/images/ats-cache-storage-units.png and /dev/null differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-directory-structure.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-directory-structure.png b/doc/arch/cache/images/cache-directory-structure.png
new file mode 100755
index 0000000..8719d1e
Binary files /dev/null and b/doc/arch/cache/images/cache-directory-structure.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-doc-layout-3-2-0.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-doc-layout-3-2-0.png b/doc/arch/cache/images/cache-doc-layout-3-2-0.png
new file mode 100755
index 0000000..d758342
Binary files /dev/null and b/doc/arch/cache/images/cache-doc-layout-3-2-0.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-doc-layout-4-0-1.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-doc-layout-4-0-1.png b/doc/arch/cache/images/cache-doc-layout-4-0-1.png
new file mode 100755
index 0000000..d97b154
Binary files /dev/null and b/doc/arch/cache/images/cache-doc-layout-4-0-1.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-multi-fragment.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-multi-fragment.png b/doc/arch/cache/images/cache-multi-fragment.png
new file mode 100755
index 0000000..164d7d6
Binary files /dev/null and b/doc/arch/cache/images/cache-multi-fragment.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-span-layout.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-span-layout.png b/doc/arch/cache/images/cache-span-layout.png
new file mode 100644
index 0000000..317d69a
Binary files /dev/null and b/doc/arch/cache/images/cache-span-layout.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-spans.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-spans.png b/doc/arch/cache/images/cache-spans.png
new file mode 100644
index 0000000..6a5e5f8
Binary files /dev/null and b/doc/arch/cache/images/cache-spans.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/arch/cache/images/cache-stripe-layout.png
----------------------------------------------------------------------
diff --git a/doc/arch/cache/images/cache-stripe-layout.png b/doc/arch/cache/images/cache-stripe-layout.png
new file mode 100755
index 0000000..73b4140
Binary files /dev/null and b/doc/arch/cache/images/cache-stripe-layout.png differ
http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5c39d024/doc/glossary.en.rst
----------------------------------------------------------------------
diff --git a/doc/glossary.en.rst b/doc/glossary.en.rst
index 0970090..a3180f6 100644
--- a/doc/glossary.en.rst
+++ b/doc/glossary.en.rst
@@ -40,20 +40,23 @@ Glossary
cache volume
Persistent storage for the cache, defined and manipulable by the user.
Cache volumes are defined in :file:`volume.config`. A cache volume is
- spread across :term:`storage unit`\ s to increase performance through
+ spread across :term:`cache span`\ s to increase performance through
parallel I/O. Storage units can be split across cache volumes. Each
- such part of a storage unit in a cache volume is a :term:`volume`.
+ such part of a storage unit in a cache volume is a :term:`cache stripe`.
- volume
+ cache stripe
A homogenous persistent store for the cache. A volume always resides
entirely on a single physical device and is treated as an
undifferentiated span of bytes.
- See also :term:`storage unit`, :term:`cache volume`
+ See also :term:`cache span`, :term:`cache volume`
- storage unit
+ cache span
The physical storage described by a single line in :file:`storage.config`.
+ storage unit
+ Obsolete term for :term:`cache span`.
+
revalidation
Verifying that a currently cached object is still valid. This is usually done using an `If-Modified-Since
<http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.25>`_ request which allows the origin server to