Re: [05/12] git commit: [TS-2183] Make a restructured text version of the ram-cache wiki page

[Igor Galić <i....@brainsware.org>]

----- Original Message -----
> [TS-2183] Make a restructured text version of the ram-cache wiki page
> 
> 
> Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo
> Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/219ba692
> Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/219ba692
> Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/219ba692
> 
> Branch: refs/heads/master
> Commit: 219ba692eaf6e85fe99c41efdd176a9f2ed18c4b
> Parents: 0f45c06
> Author: Miles Libbey <ml...@apache.org>
> Authored: Fri Dec 13 13:52:15 2013 -0800
> Committer: Miles Libbey <ml...@apache.org>
> Committed: Fri Dec 13 13:52:15 2013 -0800
> 
> ----------------------------------------------------------------------
>  doc/arch/cache/ram-cache.en.rst | 88 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 88 insertions(+)
> ----------------------------------------------------------------------
> 
> 
> http://git-wip-us.apache.org/repos/asf/trafficserver/blob/219ba692/doc/arch/cache/ram-cache.en.rst
> ----------------------------------------------------------------------
> diff --git a/doc/arch/cache/ram-cache.en.rst
> b/doc/arch/cache/ram-cache.en.rst
> new file mode 100644
> index 0000000..b0b15e1
> --- /dev/null
> +++ b/doc/arch/cache/ram-cache.en.rst
> @@ -0,0 +1,88 @@
> +.. 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.
> +
> +.. include:: common.defs
> +
> +*********
> +Ram Cache
> +*********
> +
> +New Ram Cache Algorithm (CLFUS)
> +===============================
> +
> +The new Ram Cache uses ideas from a number of cache replacement policies and
> algorithms, including LRU, LFU, CLOCK, GDFS and 2Q, called CLFUS (Clocked
> Least Frequently Used by Size). It avoids any patented algorithms and
> includes the following features:
> +

for easier reading, please break at max 120 char.

> +* Balances Recentness, Frequency and Size to maximize hit rate (not byte hit
> rate).
> +* Is Scan Resistant and extracts robust hit rates even when the working set
> does not fit in the Ram Cache.
> +* Supports compression at 3 levels fastlz, gzip(libz), and xz(liblzma).
> Compression can be moved to another thread.
> +* Has very low CPU overhead, only little more than a basic LRU.  Rather than
> using an O(lg n) heap, it uses a probabilistic replacement policy for O(1)
> cost with low C.

What's a very low C?

> +* Has relatively low memory overhead of approximately 200 bytes per object
> in memory.
> +
> +The rational for emphasizing hit rate over byte hit rate is that the
> overhead of pulling more bytes from secondary storage is low compared to the
> cost of a request.
> +
> +The Ram Cache consists of an object hash fronting 2 LRU/CLOCK lists and a
> "Seen" hash table.  The first "Cached" list contains objects in memory while
> the second contains a "History" of objects which have either recently been
> in memory or are being considered for keeping in memory.  The "Seen" hash
> table is used to make the algorithm scan resistant.
> +
> +The list entries record the following information:
> +
> +* key - 16 byte unique object identifier
> +* auxkeys - 8 bytes worth of version number (in our system the block in the
> partition).  When the version of an object changes old entries are purged
> from the cache.
> +* hits - number of hits within this clock period
> +* size - the size of the object in the cache
> +* len - the actual length of the object (differs from size because of
> compression and padding)
> +* compressed_len - the compressed length of the object
> +* compressed (none, fastlz, libz, liblzma)
> +* uncompressible (flag)
> +* copy - whether or not this object should be copied in and copied out (e.g.
> HTTP HDR)
> +* LRU link
> +* HASH link
> +* IOBufferData (smart point to the data buffer)
> +
> +
> +The interface to the cache is Get and Put operations.  Get operations check

are those different from GET and PUT?

> if an object is in the cache and are called on a read attempt.  The Put
> operation decides whether or not to cache the provided object in memory.  It
> is called after a read from secondary storage.
> +
> +Seen Hash
> +=========
> +
> +The Seen List becomes active after the Cached and History lists become full
> after a cold start.  The purpose is to make the cache scan resistant which
> means that the cache state must not be effected at all by a long sequence
> Get and Put operations on objects which are seen only once.  This is
> essential, without it not only would the cache be polluted, but it could
> lose critical information about the objects that it cares about.  It is
> therefore essential that the Cache and History lists are not effected by Get
> or Put operations on objects seen the first time.  The Seen Hash maintains a
> set of 16 bit hash tags, and requests which do not hit in the object cache
> (are in the Cache List or History List) and do not match the hash tag result
> in the hash tag begin updated but are otherwise ignored. The Seen Hash is
> sized to approximately the number of objects in the cache in order to match
> the number that are passed through it with the CLOCK rate of the Cached and
> History Lists.
> +
> +Cached List
> +===========
> +
> +The Cached list contains objects actually in memory.  The basic operation is
> LRU with new entries inserted into a FIFO (queue) and hits causing objects
> to be reinserted.  The interesting bit comes when an object is being
> considered for insertion.  First we check if the Object Hash to see if the
> object is in the Cached List or History.  Hits result in updating the "hit"
> field and reinsertion.  History hits result in the "hit" field being updated
> and a comparison to see if this object should be kept in memory.  The
> comparison is against the least recently used members of the Cache List, and
> is based on a weighted frequency::
> +
> +   CACHE_VALUE = hits / (size + overhead)
> +
> +A new object must beat enough bytes worth of currently cached objects to
> cover itself.  Each time an object is considered for replacement the CLOCK
> moves forward.  If the History object has a greater value then it is
> inserted into the Cached List and the replaced objects are removed from
> memory and their list entries are inserted into the History List.  If the
> History object has a lesser value it is reinserted into the History List.
> Objects considered for replacement (at least one) but not replaced have
> their "hits" field set to zero and are reinserted into the Cached List.
> This is the CLOCK operation on the Cached List.
> +
> +History List
> +============
> +
> +Each CLOCK the least recently used entry in the History List is dequeued and
> if the "hits" field is not greater than 1 (it was hit at least once in the
> History or Cached List) it is deleted, otherwise the "hits" is set to zero
> and it is requeued on the History List.
> +
> +Compression/Decompression
> +=========================
> +
> +Compression is performed by a background operation (currently called as part
> of Put) which maintains a pointer into the Cached List and runs toward the
> head compressing entries.  Decompression occurs on demand during a Get.  In
> the case of objects tagged "copy" the compressed version is reinserted in
> the LRU since we need to make a copy anyway.  Those not tagged "copy" are
> inserted uncompressed in the hope that they can be reused in uncompressed
> form.  This is a compile time option and may be something we want to change.
> +
> +There are 3 algorithms and levels of compression (speed on 1 thread i7 920)
> :
> +
> +* fastlz: 173 MB/sec compression, 442 MB/sec decompression : basically free
> since disk or network will limit first, ~53% final size
> +* libz: 55 MB/sec compression, 234 MB/sec decompression : almost free,
> particularly decompression, ~37% final size
> +* liblzma: 3 MB/sec compression, 50 MB/sec decompression : expensive, ~27%
> final size
> +
> +These are ballpark numbers, and your millage will vary enormously.  JPEG for

mileage 

> example will not compress with any of these. The RamCache does detect
> compression level and will declare something "incompressible" if it doesn't
> get below 90% of the original size. This value is cached so that the
> RamCache will not attempt to compress it again (at least as long as it is in
> the history).
> +


General: all of the CAPSLOCK words should be put in the glossary

-- 
Igor Galić

Tel: +43 (0) 664 886 22 883
Mail: i.galic@brainsware.org
URL: http://brainsware.org/
GPG: 8716 7A9F 989B ABD5 100F  4008 F266 55D6 2998 1641