1 //  Copyright (c) 2013, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 //
6 #pragma once
7 
8 #ifndef ROCKSDB_LITE
9 
10 #include <atomic>
11 #include <limits>
12 #include <sstream>
13 #include <string>
14 #include <vector>
15 
16 #include "rocksdb/cache.h"
17 #include "utilities/persistent_cache/hash_table.h"
18 #include "utilities/persistent_cache/hash_table_evictable.h"
19 #include "utilities/persistent_cache/persistent_cache_tier.h"
20 
21 // VolatileCacheTier
22 //
23 // This file provides persistent cache tier implementation for caching
24 // key/values in RAM.
25 //
26 //        key/values
27 //           |
28 //           V
29 // +-------------------+
30 // | VolatileCacheTier | Store in an evictable hash table
31 // +-------------------+
32 //           |
33 //           V
34 //       on eviction
35 //   pushed to next tier
36 //
37 // The implementation is designed to be concurrent. The evictable hash table
38 // implementation is not concurrent at this point though.
39 //
40 // The eviction algorithm is LRU
41 namespace ROCKSDB_NAMESPACE {
42 
43 class VolatileCacheTier : public PersistentCacheTier {
44  public:
45   explicit VolatileCacheTier(
46       const bool is_compressed = true,
47       const size_t max_size = std::numeric_limits<size_t>::max())
is_compressed_(is_compressed)48       : is_compressed_(is_compressed), max_size_(max_size) {}
49 
50   virtual ~VolatileCacheTier();
51 
52   // insert to cache
53   Status Insert(const Slice& page_key, const char* data,
54                 const size_t size) override;
55   // lookup key in cache
56   Status Lookup(const Slice& page_key, std::unique_ptr<char[]>* data,
57                 size_t* size) override;
58 
59   // is compressed cache ?
IsCompressed()60   bool IsCompressed() override { return is_compressed_; }
61 
62   // erase key from cache
63   bool Erase(const Slice& key) override;
64 
GetPrintableOptions()65   std::string GetPrintableOptions() const override {
66     return "VolatileCacheTier";
67   }
68 
69   // Expose stats as map
70   PersistentCache::StatsType Stats() override;
71 
72  private:
73   //
74   // Cache data abstraction
75   //
76   struct CacheData : LRUElement<CacheData> {
CacheDataCacheData77     explicit CacheData(CacheData&& rhs) ROCKSDB_NOEXCEPT
78         : key(std::move(rhs.key)),
79           value(std::move(rhs.value)) {}
80 
81     explicit CacheData(const std::string& _key, const std::string& _value = "")
keyCacheData82         : key(_key), value(_value) {}
83 
~CacheDataCacheData84     virtual ~CacheData() {}
85 
86     const std::string key;
87     const std::string value;
88   };
89 
90   static void DeleteCacheData(CacheData* data);
91 
92   //
93   // Index and LRU definition
94   //
95   struct CacheDataHash {
operatorCacheDataHash96     uint64_t operator()(const CacheData* obj) const {
97       assert(obj);
98       return std::hash<std::string>()(obj->key);
99     }
100   };
101 
102   struct CacheDataEqual {
operatorCacheDataEqual103     bool operator()(const CacheData* lhs, const CacheData* rhs) const {
104       assert(lhs);
105       assert(rhs);
106       return lhs->key == rhs->key;
107     }
108   };
109 
110   struct Statistics {
111     std::atomic<uint64_t> cache_misses_{0};
112     std::atomic<uint64_t> cache_hits_{0};
113     std::atomic<uint64_t> cache_inserts_{0};
114     std::atomic<uint64_t> cache_evicts_{0};
115 
CacheHitPctStatistics116     double CacheHitPct() const {
117       auto lookups = cache_hits_ + cache_misses_;
118       return lookups ? 100 * cache_hits_ / static_cast<double>(lookups) : 0.0;
119     }
120 
CacheMissPctStatistics121     double CacheMissPct() const {
122       auto lookups = cache_hits_ + cache_misses_;
123       return lookups ? 100 * cache_misses_ / static_cast<double>(lookups) : 0.0;
124     }
125   };
126 
127   typedef EvictableHashTable<CacheData, CacheDataHash, CacheDataEqual>
128       IndexType;
129 
130   // Evict LRU tail
131   bool Evict();
132 
133   const bool is_compressed_ = true;    // does it store compressed data
134   IndexType index_;                    // in-memory cache
135   std::atomic<uint64_t> max_size_{0};  // Maximum size of the cache
136   std::atomic<uint64_t> size_{0};      // Size of the cache
137   Statistics stats_;
138 };
139 
140 }  // namespace ROCKSDB_NAMESPACE
141 
142 #endif
143