From 31cb7a90788e67334721b5b352a29d2b9a99ccae Mon Sep 17 00:00:00 2001 From: Jan Tuomi Date: Fri, 18 Oct 2024 13:31:36 +0300 Subject: Modify ARCHITECTURE.md --- ARCHITECTURE.md | 11 +++++++++++ logdb_offset_indexes.drawio.svg | 4 ++++ 2 files changed, 15 insertions(+) create mode 100644 logdb_offset_indexes.drawio.svg diff --git a/ARCHITECTURE.md b/ARCHITECTURE.md index 9f68a60..624debb 100644 --- a/ARCHITECTURE.md +++ b/ARCHITECTURE.md @@ -224,3 +224,14 @@ The design space here allows for a couple of approaches: or other garbage collection to ensure that the data is removed from the heap when no longer referenced. An index of key -> key mappings is very lightweight: a million records fits in around 20 MB. It's so little that we can probably afford to keep the entire indexes in memory. A database could easily grow to hundreds of millions of records though, so we would still need to have some kind of eviction policy. The second approach is chosen for now, although the third one might be the most efficient in the long run. + +## 2024-10-18 In memory heap vs. log offsets + +Upon further consideration, the option of not storing data in memory at all but +instead storing log offsets and segment numbers in the indexes is intriguing. This would allow for a very lightweight index structure, since the log offsets are just 64-bit integers and segment numbers are 16-bit. We can easily store millions of these in memory. We would still have to do eviction, but we could do it based on the segment number + log offset, which is a simple integer comparison. The evicted entry is the least recently written: compare log segment first and then log offset. This would remove the need for a priority queue that is currently in use. + +The downside is that we have to do a disk seek to read the record, but this is not that big of a deal, since it is a constant time operation. + +See diagram below: + +![LogDB indexes with offsets](./logdb_offset_indexes.drawio.svg) diff --git a/logdb_offset_indexes.drawio.svg b/logdb_offset_indexes.drawio.svg new file mode 100644 index 0000000..694ca1e --- /dev/null +++ b/logdb_offset_indexes.drawio.svg @@ -0,0 +1,4 @@ + + + +
Primary index
Primary index
LK
LK
PK
PK
LK
LK
PK
PK
LK
LK
PK
PK
Secondary index
Secondary index
SK
SK
Set<LK>
Set<LK>
SK
SK
Set<LK>
Set<LK>
SK
SK
Set<LK>
Set<LK>
log.1
log.1
offset 0: <data>
offset 0: <data>
offset 30: <data>
offset 30: <data>
offset 64: <data>
offset 64: <data>
log.2
log.2
offset 0: <data>
offset 0: <data>
offset 26: <data>
offset 26: <data>
offset 34: <data>
offset 34: <data>
...
...
log (active)
log (active)
offset 0: <data>
offset 0: <data>
PK = primary key
SK = secondary key
LK = log key (segment # + file offset)
PK = primary key...Text is not SVG - cannot display \ No newline at end of file -- cgit v1.3