Cache in RocksDB
==================

The cache is used to store the latest used data in memory for fast searching.

0. LRU Cache
--------------

The LRU Cache in RocksDB implement O(1) Put/Get.The basic mechanism is putting
by double-linked list and getting by hash map.

The basic data structure as below:

::

      |  LRUHandle* |                        prev
      |  LRUHandle* | ---> |  LRUHandle  | <-------------------------
      |  LRUHandle* |          |next ^     ----------------------    |
      |  LRUHandle* |          V     |prev    next              |    |
      |  LRUHandle* |   -> |  LRUHandle  |                      V    |
      |  LRUHandle* |   |                              ---->| LRUHandle |
      |  LRUHandle* | ---              prev            |       |
      |  LRUHandle* |             ---------------------|       |next
      |  LRUHandle* |             |  ---------------------------
      |  LRUHandle* | ---|        |  |  ^
                         |        |  V  |next  next_hash(for collision)
                         --> |  LRUHandle  | ----------> |  LRUHandle  | ----->


So the RocksDB put(and evict) item by double-linked list and hash table,
get item by hash table.