maph 1.0.0 High-Performance Memory-Mapped Key-Value Database with O(1) Lookups

Loading...
Searching...
No Matches
maph_hybrid.hpp
Go to the documentation of this file.
1
12#pragma once
13
14#include <sys/mman.h>
15#include <fcntl.h>
16#include <unistd.h>
17#include <cstring>
18#include <atomic>
19#include <chrono>
20
21 namespace maph {
22
23// Enhanced slot with hash and optional expiration
24 struct alignas(64) HybridSlot {
25 std::atomic<uint32_t> version{0}; // Lock-free updates
26 uint32_t key_hash{0}; // 0 = empty, else hash of key
27 uint32_t size{0}; // Value size
28 uint32_t expires_at{0}; // 0 = never, else unix timestamp
29 char value[496]{}; // JSON value (or key+value if needed)
30
31 static constexpr size_t MAX_VALUE_SIZE = 496;
32 static constexpr uint32_t EMPTY = 0;
33 static constexpr uint32_t TOMBSTONE = 0xFFFFFFFF; // Deleted slot
34
35 bool is_empty() const { return key_hash == EMPTY; }
36 bool is_deleted() const { return key_hash == TOMBSTONE; }
37 bool is_expired() const {
38 if (expires_at == 0) return false;
39 return expires_at < std::chrono::system_clock::to_time_t(
40 std::chrono::system_clock::now());
41 }
42 bool is_valid() const {
43 return !is_empty() && !is_deleted() && !is_expired();
44 }
45};
46
47 static_assert(sizeof(HybridSlot) == 512);
48
49 struct HybridHeader {
50 uint32_t magic{0x4D415048};
51 uint32_t version{2};
52 uint64_t num_slots{0};
53 uint64_t num_static{0}; // Number of perfect-hashed keys
54 std::atomic<uint64_t> num_dynamic{0}; // Number of dynamically added keys
55 std::atomic<uint64_t> generation{0};
56 double max_load_factor{0.75}; // For dynamic keys
57 char padding[464]{};
58};
59
60 class HybridMaph {
61 private:
62 int fd_{-1};
63 void* mapped_{nullptr};
64 size_t file_size_{0};
65 HybridHeader* header_{nullptr};
66 HybridSlot* slots_{nullptr};
67 bool readonly_{false};
68
69 // Perfect hash for static keys (first N slots)
70 std::function<uint32_t(uint32_t)> perfect_hash_;
71
72 // Regular hash for all keys
73 static uint32_t hash_key(const std::string& key) {
74 // FNV-1a hash
75 uint32_t h = 2166136261u;
76 for (char c : key) {
77 h ^= c;
78 h *= 16777619u;
79 }
80 return h;
81 }
82
83 public:
84 static std::unique_ptr<HybridMaph> create(
85 const std::string& path,
86 size_t total_slots,
87 size_t static_slots = 0) {
88
89 auto m = std::make_unique<HybridMaph>();
90
91 size_t file_size = sizeof(HybridHeader) + (total_slots * sizeof(HybridSlot));
92
93 int fd = ::open(path.c_str(), O_RDWR | O_CREAT | O_TRUNC, 0666);
94 if (fd < 0) return nullptr;
95
96 if (ftruncate(fd, file_size) < 0) {
97 ::close(fd);
98 return nullptr;
99 }
100
101 void* mapped = mmap(nullptr, file_size, PROT_READ | PROT_WRITE,
102 MAP_SHARED, fd, 0);
103 if (mapped == MAP_FAILED) {
104 ::close(fd);
105 return nullptr;
106 }
107
108 HybridHeader* header = new (mapped) HybridHeader();
109 header->num_slots = total_slots;
110 header->num_static = static_slots;
111 header->num_dynamic = 0;
112
113 HybridSlot* slots = reinterpret_cast<HybridSlot*>(
114 static_cast<char*>(mapped) + sizeof(HybridHeader));
115 memset(slots, 0, total_slots * sizeof(HybridSlot));
116
117 m->fd_ = fd;
118 m->mapped_ = mapped;
119 m->file_size_ = file_size;
120 m->header_ = header;
121 m->slots_ = slots;
122
123 // Default perfect hash for static range
124 m->perfect_hash_ = [static_slots](uint32_t hash) {
125 return hash % static_slots;
126 };
127
128 return m;
129 }
130
131 // ===== FAST PATH: Perfect-hashed static keys =====
132
133 std::string get_static(const std::string& key) const {
134 if (header_->num_static == 0) return "";
135
136 uint32_t hash = hash_key(key);
137 uint32_t index = perfect_hash_(hash);
138
139 const HybridSlot& slot = slots_[index];
140
141 // Direct hit - no probing needed!
142 if (slot.key_hash == hash && slot.is_valid()) {
143 return std::string(slot.value, slot.size);
144 }
145
146 return "";
147 }
148
149 bool set_static(const std::string& key, const std::string& value,
150 uint32_t ttl_seconds = 0) {
151 if (readonly_ || header_->num_static == 0) return false;
152 if (value.size() > HybridSlot::MAX_VALUE_SIZE) return false;
153
154 uint32_t hash = hash_key(key);
155 uint32_t index = perfect_hash_(hash);
156
157 HybridSlot& slot = slots_[index];
158
159 uint32_t v = slot.version.fetch_add(1);
160
161 slot.key_hash = hash;
162 slot.size = value.size();
163 memcpy(slot.value, value.data(), value.size());
164
165 if (ttl_seconds > 0) {
166 slot.expires_at = std::chrono::system_clock::to_time_t(
167 std::chrono::system_clock::now()) + ttl_seconds;
168 } else {
169 slot.expires_at = 0;
170 }
171
172 slot.version.fetch_add(1);
173 header_->generation.fetch_add(1);
174
175 return true;
176 }
177
178 // ===== DYNAMIC PATH: Add any key with probing =====
179
180 std::string get(const std::string& key) const {
181 uint32_t hash = hash_key(key);
182
183 // Try static first (if in range)
184 if (header_->num_static > 0) {
185 uint32_t static_idx = perfect_hash_(hash);
186 if (static_idx < header_->num_static) {
187 const HybridSlot& slot = slots_[static_idx];
188 if (slot.key_hash == hash && slot.is_valid()) {
189 return std::string(slot.value, slot.size);
190 }
191 }
192 }
193
194 // Linear probe in dynamic range
195 uint32_t start = header_->num_static;
196 uint32_t end = header_->num_slots;
197
198 // Start probe position
199 uint32_t idx = start + (hash % (end - start));
200
201 for (uint32_t i = 0; i < 100; ++i) { // Max probe distance
202 const HybridSlot& slot = slots_[idx];
203
204 if (slot.is_empty()) {
205 return ""; // Not found
206 }
207
208 if (slot.key_hash == hash && slot.is_valid()) {
209 return std::string(slot.value, slot.size);
210 }
211
212 // Linear probe (could use quadratic or double hashing)
213 idx = start + ((idx - start + 1) % (end - start));
214 }
215
216 return ""; // Not found after max probes
217 }
218
219 bool set(const std::string& key, const std::string& value,
220 uint32_t ttl_seconds = 0) {
221 if (readonly_) return false;
222 if (value.size() > HybridSlot::MAX_VALUE_SIZE) return false;
223
224 uint32_t hash = hash_key(key);
225
226 // Check load factor for dynamic section
227 double load = (double)header_->num_dynamic /
228 (header_->num_slots - header_->num_static);
229 if (load > header_->max_load_factor) {
230 return false; // Would need resize
231 }
232
233 // Find slot using linear probing
234 uint32_t start = header_->num_static;
235 uint32_t end = header_->num_slots;
236 uint32_t idx = start + (hash % (end - start));
237
238 for (uint32_t i = 0; i < 100; ++i) {
239 HybridSlot& slot = slots_[idx];
240
241 // Found empty or matching slot
242 if (slot.is_empty() || slot.key_hash == hash || slot.is_deleted()) {
243 uint32_t v = slot.version.fetch_add(1);
244
245 bool was_empty = slot.is_empty() || slot.is_deleted();
246
247 slot.key_hash = hash;
248 slot.size = value.size();
249 memcpy(slot.value, value.data(), value.size());
250
251 if (ttl_seconds > 0) {
252 slot.expires_at = std::chrono::system_clock::to_time_t(
253 std::chrono::system_clock::now()) + ttl_seconds;
254 } else {
255 slot.expires_at = 0;
256 }
257
258 slot.version.fetch_add(1);
259
260 if (was_empty) {
261 header_->num_dynamic.fetch_add(1);
262 }
263 header_->generation.fetch_add(1);
264
265 return true;
266 }
267
268 idx = start + ((idx - start + 1) % (end - start));
269 }
270
271 return false; // Couldn't find slot
272 }
273
274 // ===== DELETE & EXPIRATION =====
275
276 bool remove(const std::string& key) {
277 if (readonly_) return false;
278
279 uint32_t hash = hash_key(key);
280
281 // Search both static and dynamic ranges
282 // ... (similar to get but marks slot as TOMBSTONE)
283
284 return false;
285 }
286
287 void expire_cleanup() {
288 if (readonly_) return;
289
290 uint32_t now = std::chrono::system_clock::to_time_t(
291 std::chrono::system_clock::now());
292
293 for (size_t i = 0; i < header_->num_slots; ++i) {
294 HybridSlot& slot = slots_[i];
295
296 if (slot.expires_at != 0 && slot.expires_at < now) {
297 slot.version.fetch_add(1);
298 slot.key_hash = HybridSlot::TOMBSTONE;
299 slot.version.fetch_add(1);
300 header_->num_dynamic.fetch_sub(1);
301 }
302 }
303 }
304
305 // ===== STATS & DEBUG =====
306
307 struct Stats {
308 size_t total_slots;
309 size_t static_slots;
310 size_t dynamic_slots;
311 size_t used_static;
312 size_t used_dynamic;
313 size_t expired;
314 double load_factor;
315 size_t avg_probe_distance;
316 };
317
318 Stats get_stats() const {
319 Stats s{};
320 s.total_slots = header_->num_slots;
321 s.static_slots = header_->num_static;
322 s.dynamic_slots = s.total_slots - s.static_slots;
323
324 for (size_t i = 0; i < header_->num_static; ++i) {
325 if (slots_[i].is_valid()) s.used_static++;
326 if (slots_[i].is_expired()) s.expired++;
327 }
328
329 for (size_t i = header_->num_static; i < header_->num_slots; ++i) {
330 if (slots_[i].is_valid()) s.used_dynamic++;
331 if (slots_[i].is_expired()) s.expired++;
332 }
333
334 s.load_factor = (double)(s.used_static + s.used_dynamic) / s.total_slots;
335
336 return s;
337 }
338
339 // ===== BUILDING STATIC SET =====
340
341 void build_static_set(const std::vector<std::string>& static_keys,
342 const std::vector<std::string>& static_values) {
343 // In production: Build perfect hash function here
344 // For now: Simple modulo
345
346 for (size_t i = 0; i < static_keys.size() && i < header_->num_static; ++i) {
347 set_static(static_keys[i], static_values[i]);
348 }
349 }
350};
351
352} // namespace maph
maph::HybridMaph
Definition maph_hybrid.hpp:60
maph::HybridMaph::expire_cleanup
void expire_cleanup()
Definition maph_hybrid.hpp:287
maph::HybridMaph::set
bool set(const std::string &key, const std::string &value, uint32_t ttl_seconds=0)
Definition maph_hybrid.hpp:219
maph::HybridMaph::Stats::total_slots
size_t total_slots
Definition maph_hybrid.hpp:308
maph::HybridMaph::Stats::static_slots
size_t static_slots
Definition maph_hybrid.hpp:309
maph::HybridMaph::Stats::dynamic_slots
size_t dynamic_slots
Definition maph_hybrid.hpp:310
maph::HybridMaph::get_stats
Stats get_stats() const
Definition maph_hybrid.hpp:318
maph::HybridMaph::Stats::load_factor
double load_factor
Definition maph_hybrid.hpp:314
maph::HybridMaph::remove
bool remove(const std::string &key)
Definition maph_hybrid.hpp:276
maph::HybridMaph::get
std::string get(const std::string &key) const
Definition maph_hybrid.hpp:180
maph::HybridMaph::create
static std::unique_ptr< HybridMaph > create(const std::string &path, size_t total_slots, size_t static_slots=0)
Definition maph_hybrid.hpp:84
maph::HybridMaph::Stats::avg_probe_distance
size_t avg_probe_distance
Definition maph_hybrid.hpp:315
maph::HybridMaph::set_static
bool set_static(const std::string &key, const std::string &value, uint32_t ttl_seconds=0)
Definition maph_hybrid.hpp:149
maph::HybridMaph::get_static
std::string get_static(const std::string &key) const
Definition maph_hybrid.hpp:133
maph::HybridMaph::Stats::used_dynamic
size_t used_dynamic
Definition maph_hybrid.hpp:312
maph::HybridMaph::Stats::expired
size_t expired
Definition maph_hybrid.hpp:313
maph::HybridMaph::Stats::used_static
size_t used_static
Definition maph_hybrid.hpp:311
maph::HybridMaph::build_static_set
void build_static_set(const std::vector< std::string > &static_keys, const std::vector< std::string > &static_values)
Definition maph_hybrid.hpp:341
maph::HybridMaph::Stats
Definition maph_hybrid.hpp:307
maph
Definition maph.hpp:46
maph::HybridHeader::num_static
uint64_t num_static
Definition maph_hybrid.hpp:53
maph::open
auto open(const std::string &path)
Definition maph.hpp:958
maph::HybridHeader::magic
uint32_t magic
Definition maph_hybrid.hpp:50
maph::HybridHeader::num_slots
uint64_t num_slots
Definition maph_hybrid.hpp:52
maph::HybridHeader::padding
char padding[464]
Definition maph_hybrid.hpp:57
maph::HybridHeader::version
uint32_t version
Definition maph_hybrid.hpp:51
maph::HybridHeader::num_dynamic
std::atomic< uint64_t > num_dynamic
Definition maph_hybrid.hpp:54
maph::HybridHeader::max_load_factor
double max_load_factor
Definition maph_hybrid.hpp:56
maph::HybridHeader::generation
std::atomic< uint64_t > generation
Definition maph_hybrid.hpp:55
maph::HybridHeader
Definition maph_hybrid.hpp:49
maph::HybridSlot
Definition maph_hybrid.hpp:24
maph::HybridSlot::is_expired
bool is_expired() const
Definition maph_hybrid.hpp:37
maph::HybridSlot::EMPTY
static constexpr uint32_t EMPTY
Definition maph_hybrid.hpp:32
maph::HybridSlot::is_valid
bool is_valid() const
Definition maph_hybrid.hpp:42
maph::HybridSlot::TOMBSTONE
static constexpr uint32_t TOMBSTONE
Definition maph_hybrid.hpp:33
maph::HybridSlot::expires_at
uint32_t expires_at
Definition maph_hybrid.hpp:28
maph::HybridSlot::is_deleted
bool is_deleted() const
Definition maph_hybrid.hpp:36
maph::HybridSlot::size
uint32_t size
Definition maph_hybrid.hpp:27
maph::HybridSlot::MAX_VALUE_SIZE
static constexpr size_t MAX_VALUE_SIZE
Definition maph_hybrid.hpp:31
maph::HybridSlot::version
std::atomic< uint32_t > version
Definition maph_hybrid.hpp:25
maph::HybridSlot::value
char value[496]
Definition maph_hybrid.hpp:29
maph::HybridSlot::key_hash
uint32_t key_hash
Definition maph_hybrid.hpp:26
maph::HybridSlot::is_empty
bool is_empty() const
Definition maph_hybrid.hpp:35