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 #pragma once
6 
7 #ifndef ROCKSDB_LITE
8 
9 #include <functional>
10 #include <string>
11 #include <unordered_map>
12 
13 #include "rocksdb/slice.h"
14 
15 #include "utilities/persistent_cache/block_cache_tier_file.h"
16 #include "utilities/persistent_cache/hash_table.h"
17 #include "utilities/persistent_cache/hash_table_evictable.h"
18 #include "utilities/persistent_cache/lrulist.h"
19 
20 namespace ROCKSDB_NAMESPACE {
21 
22 //
23 // Block Cache Tier Metadata
24 //
25 // The BlockCacheTierMetadata holds all the metadata associated with block
26 // cache. It
27 // fundamentally contains 2 indexes and an LRU.
28 //
29 // Block Cache Index
30 //
31 // This is a forward index that maps a given key to a LBA (Logical Block
32 // Address). LBA is a disk pointer that points to a record on the cache.
33 //
34 // LBA = { cache-id, offset, size }
35 //
36 // Cache File Index
37 //
38 // This is a forward index that maps a given cache-id to a cache file object.
39 // Typically you would lookup using LBA and use the object to read or write
40 struct BlockInfo {
41   explicit BlockInfo(const Slice& key, const LBA& lba = LBA())
42       : key_(key.ToString()), lba_(lba) {}
43 
44   std::string key_;
45   LBA lba_;
46 };
47 
48 class BlockCacheTierMetadata {
49  public:
50   explicit BlockCacheTierMetadata(const uint32_t blocks_capacity = 1024 * 1024,
51                                   const uint32_t cachefile_capacity = 10 * 1024)
cache_file_index_(cachefile_capacity)52       : cache_file_index_(cachefile_capacity), block_index_(blocks_capacity) {}
53 
~BlockCacheTierMetadata()54   virtual ~BlockCacheTierMetadata() {}
55 
56   // Insert a given cache file
57   bool Insert(BlockCacheFile* file);
58 
59   // Lookup cache file based on cache_id
60   BlockCacheFile* Lookup(const uint32_t cache_id);
61 
62   // Insert block information to block index
63   BlockInfo* Insert(const Slice& key, const LBA& lba);
64   // bool Insert(BlockInfo* binfo);
65 
66   // Lookup block information from block index
67   bool Lookup(const Slice& key, LBA* lba);
68 
69   // Remove a given from the block index
70   BlockInfo* Remove(const Slice& key);
71 
72   // Find and evict a cache file using LRU policy
73   BlockCacheFile* Evict();
74 
75   // Clear the metadata contents
76   virtual void Clear();
77 
78  protected:
79   // Remove all block information from a given file
80   virtual void RemoveAllKeys(BlockCacheFile* file);
81 
82  private:
83   // Cache file index definition
84   //
85   // cache-id => BlockCacheFile
86   struct BlockCacheFileHash {
operatorBlockCacheFileHash87     uint64_t operator()(const BlockCacheFile* rec) {
88       return std::hash<uint32_t>()(rec->cacheid());
89     }
90   };
91 
92   struct BlockCacheFileEqual {
operatorBlockCacheFileEqual93     uint64_t operator()(const BlockCacheFile* lhs, const BlockCacheFile* rhs) {
94       return lhs->cacheid() == rhs->cacheid();
95     }
96   };
97 
98   typedef EvictableHashTable<BlockCacheFile, BlockCacheFileHash,
99                              BlockCacheFileEqual>
100       CacheFileIndexType;
101 
102   // Block Lookup Index
103   //
104   // key => LBA
105   struct Hash {
operatorHash106     size_t operator()(BlockInfo* node) const {
107       return std::hash<std::string>()(node->key_);
108     }
109   };
110 
111   struct Equal {
operatorEqual112     size_t operator()(BlockInfo* lhs, BlockInfo* rhs) const {
113       return lhs->key_ == rhs->key_;
114     }
115   };
116 
117   typedef HashTable<BlockInfo*, Hash, Equal> BlockIndexType;
118 
119   CacheFileIndexType cache_file_index_;
120   BlockIndexType block_index_;
121 };
122 
123 }  // namespace ROCKSDB_NAMESPACE
124 
125 #endif
126