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

Loading...
Searching...
No Matches
maph.hpp
Go to the documentation of this file.
1
12#pragma once
13
14#include <sys/mman.h>
15#include <sys/stat.h>
16#include <fcntl.h>
17#include <unistd.h>
18#include <cstring>
19#include <string>
20#include <memory>
21#include <atomic>
22#include <functional>
23
24 namespace maph {
25
26// Fixed-size slot: 512 bytes aligned for cache
27 struct alignas(512) Slot {
28 std::atomic<uint32_t> version{0}; // Lock-free updates
29 uint32_t size{0}; // Actual JSON size
30 uint32_t hash{0}; // Key hash
31 uint32_t reserved{0}; // Padding
32 char data[496]{}; // JSON data
33
34 static constexpr size_t MAX_JSON_SIZE = 496;
35};
36
37 static_assert(sizeof(Slot) == 512, "Slot must be exactly 512 bytes");
38
39// File header
40 struct Header {
41 uint32_t magic{0x4D415048}; // "MAPH"
42 uint32_t version{1};
43 uint64_t num_slots{0};
44 uint64_t slot_size{sizeof(Slot)};
45 std::atomic<uint64_t> generation{0};
46 char padding[488]{};
47};
48
49 static_assert(sizeof(Header) == 512, "Header must be exactly 512 bytes");
50
54 class Maph {
55 private:
56 int fd_{-1};
57 void* mapped_{nullptr};
58 size_t file_size_{0};
59 Header* header_{nullptr};
60 Slot* slots_{nullptr};
61 bool readonly_{false};
62
63 // Perfect hash function (pluggable)
64 std::function<uint32_t(const std::string&)> hash_fn_;
65
66 public:
67 Maph() = default;
68 ~Maph() { close(); }
69
70 // No copy, move only
71 Maph(const Maph&) = delete;
72 Maph& operator=(const Maph&) = delete;
73 Maph(Maph&& other) noexcept { *this = std::move(other); }
74 Maph& operator=(Maph&& other) noexcept {
75 if (this != &other) {
76 close();
77 fd_ = other.fd_;
78 mapped_ = other.mapped_;
79 file_size_ = other.file_size_;
80 header_ = other.header_;
81 slots_ = other.slots_;
82 readonly_ = other.readonly_;
83 hash_fn_ = std::move(other.hash_fn_);
84 other.fd_ = -1;
85 other.mapped_ = nullptr;
86 }
87 return *this;
88 }
89
90 // ===== CREATION & OPENING =====
91
92 static std::unique_ptr<Maph> create(const std::string& path,
93 size_t num_slots) {
94 auto m = std::make_unique<Maph>();
95
96 size_t file_size = sizeof(Header) + (num_slots * sizeof(Slot));
97
98 int fd = ::open(path.c_str(), O_RDWR | O_CREAT | O_TRUNC, 0666);
99 if (fd < 0) return nullptr;
100
101 if (ftruncate(fd, file_size) < 0) {
102 ::close(fd);
103 return nullptr;
104 }
105
106 void* mapped = mmap(nullptr, file_size, PROT_READ | PROT_WRITE,
107 MAP_SHARED, fd, 0);
108 if (mapped == MAP_FAILED) {
109 ::close(fd);
110 return nullptr;
111 }
112
113 // Initialize header
114 Header* header = new (mapped) Header();
115 header->num_slots = num_slots;
116
117 // Zero slots
118 Slot* slots = reinterpret_cast<Slot*>(
119 static_cast<char*>(mapped) + sizeof(Header));
120 memset(slots, 0, num_slots * sizeof(Slot));
121
122 m->fd_ = fd;
123 m->mapped_ = mapped;
124 m->file_size_ = file_size;
125 m->header_ = header;
126 m->slots_ = slots;
127 m->readonly_ = false;
128
129 // Default hash function (can be overridden)
130 m->hash_fn_ = [num_slots](const std::string& key) {
131 std::hash<std::string> h;
132 return h(key) % num_slots;
133 };
134
135 return m;
136 }
137
138 static std::unique_ptr<Maph> open(const std::string& path,
139 bool readonly = false) {
140 auto m = std::make_unique<Maph>();
141
142 int flags = readonly ? O_RDONLY : O_RDWR;
143 int fd = ::open(path.c_str(), flags);
144 if (fd < 0) return nullptr;
145
146 struct stat st;
147 if (fstat(fd, &st) < 0) {
148 ::close(fd);
149 return nullptr;
150 }
151
152 int prot = readonly ? PROT_READ : (PROT_READ | PROT_WRITE);
153 void* mapped = mmap(nullptr, st.st_size, prot, MAP_SHARED, fd, 0);
154 if (mapped == MAP_FAILED) {
155 ::close(fd);
156 return nullptr;
157 }
158
159 Header* header = static_cast<Header*>(mapped);
160 if (header->magic != 0x4D415048) {
161 munmap(mapped, st.st_size);
162 ::close(fd);
163 return nullptr;
164 }
165
166 m->fd_ = fd;
167 m->mapped_ = mapped;
168 m->file_size_ = st.st_size;
169 m->header_ = header;
170 m->slots_ = reinterpret_cast<Slot*>(
171 static_cast<char*>(mapped) + sizeof(Header));
172 m->readonly_ = readonly;
173
174 // Default hash
175 size_t num_slots = header->num_slots;
176 m->hash_fn_ = [num_slots](const std::string& key) {
177 std::hash<std::string> h;
178 return h(key) % num_slots;
179 };
180
181 return m;
182 }
183
184 // ===== CORE OPERATIONS (FAST!) =====
185
186 // Get value for JSON key - direct memory access
187 std::string get(const std::string& json_key) const {
188 uint32_t index = hash_fn_(json_key);
189 if (index >= header_->num_slots) return "";
190
191 const Slot& slot = slots_[index];
192 if (slot.size == 0) return "";
193
194 // Optional: verify hash matches
195 // if (slot.hash != simple_hash(json_key)) return "";
196
197 return std::string(slot.data, slot.size);
198 }
199
200 // Set value - just memcpy
201 bool set(const std::string& json_key, const std::string& json_value) {
202 if (readonly_) return false;
203 if (json_value.size() > Slot::MAX_JSON_SIZE) return false;
204
205 uint32_t index = hash_fn_(json_key);
206 if (index >= header_->num_slots) return false;
207
208 Slot& slot = slots_[index];
209
210 // Lock-free update
211 uint32_t v = slot.version.fetch_add(1);
212
213 slot.size = json_value.size();
214 slot.hash = simple_hash(json_key);
215 memcpy(slot.data, json_value.data(), json_value.size());
216
217 slot.version.fetch_add(1);
218 header_->generation.fetch_add(1);
219
220 return true;
221 }
222
223 // Check existence - even faster
224 bool exists(const std::string& json_key) const {
225 uint32_t index = hash_fn_(json_key);
226 if (index >= header_->num_slots) return false;
227 return slots_[index].size > 0;
228 }
229
230 // Delete entry
231 bool remove(const std::string& json_key) {
232 if (readonly_) return false;
233
234 uint32_t index = hash_fn_(json_key);
235 if (index >= header_->num_slots) return false;
236
237 Slot& slot = slots_[index];
238 slot.version.fetch_add(1);
239 slot.size = 0;
240 slot.version.fetch_add(1);
241 header_->generation.fetch_add(1);
242
243 return true;
244 }
245
246 // ===== BATCH OPERATIONS =====
247
248 // Prefetch and batch get
249 std::vector<std::string> mget(const std::vector<std::string>& keys) const {
250 std::vector<std::string> results;
251 results.reserve(keys.size());
252
253 // Prefetch all slots into cache
254 for (const auto& key : keys) {
255 uint32_t index = hash_fn_(key);
256 if (index < header_->num_slots) {
257 __builtin_prefetch(&slots_[index], 0, 3);
258 }
259 }
260
261 // Now read (from cache)
262 for (const auto& key : keys) {
263 results.push_back(get(key));
264 }
265
266 return results;
267 }
268
269 // ===== UTILITIES =====
270
271 void set_hash_function(std::function<uint32_t(const std::string&)> fn) {
272 hash_fn_ = std::move(fn);
273 }
274
275 size_t size() const { return header_->num_slots; }
276
277 size_t used() const {
278 size_t count = 0;
279 for (size_t i = 0; i < header_->num_slots; ++i) {
280 if (slots_[i].size > 0) count++;
281 }
282 return count;
283 }
284
285 uint64_t generation() const { return header_->generation.load(); }
286
287 void sync() {
288 if (!readonly_ && mapped_) {
289 msync(mapped_, file_size_, MS_ASYNC);
290 }
291 }
292
293 void close() {
294 if (mapped_) {
295 munmap(mapped_, file_size_);
296 mapped_ = nullptr;
297 }
298 if (fd_ >= 0) {
299 ::close(fd_);
300 fd_ = -1;
301 }
302 }
303
304 private:
305 static uint32_t simple_hash(const std::string& s) {
306 uint32_t h = 0;
307 for (char c : s) {
308 h = h * 31 + c;
309 }
310 return h;
311 }
312};
313
314// ===== FLUENT API =====
315
316 class MaphBuilder {
317 private:
318 std::string path_;
319 size_t num_slots_{1000000};
320 std::function<uint32_t(const std::string&)> hash_fn_;
321
322 public:
323 MaphBuilder& path(const std::string& p) {
324 path_ = p;
325 return *this;
326 }
327
328 MaphBuilder& slots(size_t n) {
329 num_slots_ = n;
330 return *this;
331 }
332
333 MaphBuilder& hash(std::function<uint32_t(const std::string&)> fn) {
334 hash_fn_ = std::move(fn);
335 return *this;
336 }
337
338 std::unique_ptr<Maph> build() {
339 auto m = Maph::create(path_, num_slots_);
340 if (m && hash_fn_) {
341 m->set_hash_function(std::move(hash_fn_));
342 }
343 return m;
344 }
345};
346
347// Convenience functions
348 inline std::unique_ptr<Maph> open(const std::string& path) {
349 return Maph::open(path);
350}
351
352 inline std::unique_ptr<Maph> create(const std::string& path, size_t slots) {
353 return Maph::create(path, slots);
354}
355
356} // namespace maph
maph::MaphBuilder
Definition maph.hpp:316
maph::MaphBuilder::build
std::unique_ptr< Maph > build()
Definition maph.hpp:338
maph::MaphBuilder::path
MaphBuilder & path(const std::string &p)
Definition maph.hpp:323
maph::MaphBuilder::slots
MaphBuilder & slots(size_t n)
Definition maph.hpp:328
maph::MaphBuilder::hash
MaphBuilder & hash(std::function< uint32_t(const std::string &)> fn)
Definition maph.hpp:333
maph::Maph
Main maph class - lean and fast.
Definition maph.hpp:351
maph::Maph::create
static std::unique_ptr< Maph > create(const std::string &path, size_t num_slots)
Definition maph.hpp:92
maph::Maph::size
size_t size() const
Definition maph.hpp:275
maph::Maph::Maph
Maph(Maph &&other) noexcept
Definition maph.hpp:73
maph::Maph::Maph
Maph()=default
maph::Maph::remove
bool remove(const std::string &json_key)
Definition maph.hpp:231
maph::Maph::close
void close()
Close the database and unmap memory.
Definition maph.hpp:715
maph::Maph::generation
uint64_t generation() const
Definition maph.hpp:285
maph::Maph::mget
std::vector< std::string > mget(const std::vector< std::string > &keys) const
Definition maph.hpp:249
maph::Maph::open
static std::unique_ptr< Maph > open(const std::string &path, bool readonly=false)
Open an existing database file.
Definition maph.hpp:442
maph::Maph::set
bool set(const std::string &json_key, const std::string &json_value)
Definition maph.hpp:201
maph::Maph::Maph
Maph(const Maph &)=delete
maph::Maph::operator=
Maph & operator=(const Maph &)=delete
maph::Maph::get
std::string get(const std::string &json_key) const
Definition maph.hpp:187
maph::Maph::used
size_t used() const
Definition maph.hpp:277
maph::Maph::set_hash_function
void set_hash_function(std::function< uint32_t(const std::string &)> fn)
Definition maph.hpp:271
maph::Maph::~Maph
~Maph()
Definition maph.hpp:68
maph::Maph::exists
bool exists(const std::string &json_key) const
Definition maph.hpp:224
maph::Maph::sync
void sync()
Definition maph.hpp:287
maph::Maph::create
static std::unique_ptr< Maph > create(const std::string &path, uint64_t total_slots, uint64_t static_slots=0)
Create a new database file.
Definition maph.hpp:387
maph::Maph::operator=
Maph & operator=(Maph &&other) noexcept
Definition maph.hpp:74
maph::Maph::get
std::optional< JsonView > get(JsonView key) const
Get value for a key.
Definition maph.hpp:498
maph
Definition maph.hpp:46
maph::Header::padding
char padding[488]
Definition maph.hpp:46
maph::Header::slot_size
uint64_t slot_size
Definition maph.hpp:44
maph::open
auto open(const std::string &path)
Definition maph.hpp:958
maph::create
auto create(const std::string &path, uint64_t slots)
Definition maph.hpp:954
maph::Header::generation
std::atomic< uint64_t > generation
Global generation counter (incremented on modifications)
Definition maph.hpp:201
maph::Header::magic
uint32_t magic
Magic number for file validation ("MAPH")
Definition maph.hpp:197
maph::Header::num_slots
uint64_t num_slots
Definition maph.hpp:43
maph::Header::version
uint32_t version
Database format version.
Definition maph.hpp:198
maph::Header
Database file header containing metadata.
Definition maph.hpp:196
maph::Slot
Storage slot for key-value pairs.
Definition maph.hpp:115
maph::Slot::size
uint32_t size
Size of stored value in bytes.
Definition maph.hpp:117
maph::Slot::reserved
uint32_t reserved
Reserved for future use.
Definition maph.hpp:118
maph::Slot::MAX_JSON_SIZE
static constexpr size_t MAX_JSON_SIZE
Definition maph.hpp:34
maph::Slot::data
char data[SLOT_DATA_SIZE]
Value data storage.
Definition maph.hpp:119
maph::Slot::version
std::atomic< uint32_t > version
Definition maph.hpp:28
maph::Slot::hash
uint32_t hash
Definition maph.hpp:30