diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | ARCHITECTURE.md | 222 | ||||
| -rw-r--r-- | README.md | 4 | ||||
| -rw-r--r-- | logdb_indexes.drawio.svg | 4 |
4 files changed, 231 insertions, 0 deletions
@@ -1 +1,2 @@ /target +.DS_Store diff --git a/ARCHITECTURE.md b/ARCHITECTURE.md new file mode 100644 index 0000000..cda4934 --- /dev/null +++ b/ARCHITECTURE.md @@ -0,0 +1,222 @@ +# Architecture decision log + +This document is used to record architectural decisions made on the project, +their context, and the (believed) consequences of those decisions. Pros and +cons of the decisions are also recorded. + +## 2024-10-01 Build a log-structured database + +This is a snippet from the README that describes the main intended features of +the database: + +<blockquote> +An educational endeavor in implementing a log-structured database with a focus +on simplicity, understandability and performance. + +LogDB has the following features: + +- Log-structured single-table storage, based on a durable append-only log +- In-memory indexes for fast lookups (primary and secondary) +- Log rotation and compaction for efficient storage even with larger databases +- Multiple concurrent readers and a single writer, using filesystem locks for + synchronization +- Simple data types: `Int`, `Float`, `String`, `Bytes` (arbitrary bytestring), + and `Null` +- A Rust API for interacting with the database, as well as Python bindings for + the Rust API + +LogDB does not support: + +- Authentication or authorization in any capacity +- Multiple tables +- Schema evolution, other than adding new nullable fields + +Possible future features: + +- Transactions +</blockquote> + +**Pros** +`+` Log-structured databases are generally simpler to implement and understand +than traditional B-tree based databases. + +**Cons** +`-` Log-structured databases are generally good for certain access patterns. + +## 2024-10-01 Access patterns + +As a log-structured database, LogDB is optimized for write-heavy and read-light +workloads. + +**Pros** +`+` Good fit for application that write a lot and read little, such as event +logging, time series data, or IoT data. + +**Cons** +`-` Not a good fit for read-heavy workloads, such as analytics or web services. + +## 2024-10-01 Simple Rust + +LogDB is implemented in Rust, which is a systems programming language that is +known for its performance, safety, and expressiveness. Asynchronous Rust is +infamous for being difficult to learn and use, so the project aims to keep the +Rust code as simple as possible. This means that there are no async functions, +`Arc`, `Mutex`, `RwLock`, `Rc`, `RefCell` or `unsafe` blocks in the codebase. + +Concurrency is handled by using filesystem locks for synchronization, which lets +us keep the code simple and easy to understand. + +The user is permitted to use async functions in their own code, but the database +itself does not use them. + +## 2024-10-01 Data types + +LogDB supports the following data types: + +- `Int`: 64-bit signed integer +- `Float`: 64-bit floating point number +- `String`: UTF-8 encoded string +- `Bytes`: Arbitrary bytestring +- `Null`: A null value + +A column is declared with a data type, not including `Null`. The column will +contain values of that specified type, and that data type cannot be changed +after the fact (no schema evolution). A column can be additionally declared as +nullable, which means that it can contain `Null` values too. + +Schema evolution is supported only by adding new nullable fields to the schema. +Users can theorethically add stuff like Avro encoded data to a `Bytes` field, +but the database itself does not support any kind of schema evolution. + +Only `Int` and `String` can be used as index keys. A primary index is mandatory, +and secondary indexes are optional. + +**Pros** +`+` Simple and easy to understand data model +`+` No need for complex types or type conversions +`+` No need to support schema evolution + +**Cons** +`-` Limited flexibility in data types +`-` Database not that well applicable to use cases requiring complex data types +or schema evolution, +e.g. web applications with changing requirements + +## 2024-10-03 Forward and backward readers + +LogDB has in-memory indexes (memtables) for fast lookups. Queries that do not +hit an index are performed by scanning the log from the end to the beginning. +This requires a backward reader that can read the log in reverse order. There +exist crates that have this functionality but a quick spike showed that they +are either buggy or work in a way that is not suitable for LogDB, so a custom +solution is implemented. + +On startup, LogDB populates the indexes by reading the log from the beginning, +as if replaying writes in chronological order. This requires a forward reader +that can read the log in forward order. A regular `BufReader` is used for this. + +**Pros** +`+` Things work as expected + +**Cons** +`-` Custom implementation required for backward reader, requiring effort and +testing that does not go into actual database development + +## 2024-10-03 Filesystem locks + +LogDB uses filesystem locks for synchronization between multiple readers and a +single writer. This is a simple and effective way to ensure that only one writer +is active at a time, and that readers do not read from a file that is being +written to. The locks are implemented using the `fs2` crate. + +A writer acquires an exclusive lock which blocks all other readers and writers. +A reader acquires a shared lock which blocks writers but allows other readers +to acquire the shared lock as well. + +In a scenario where one writer and numerous readers with retry policies are +competing for a lock, writer starvation could occur (writer never gets the lock +). This is a known limitation of the filesystem lock approach. To remedy this, +a separate "lock request file" is used to signal that a writer is waiting for +the lock. Readers check if this file is locked and do not enter the lock queue +if it is. This way, the writer is guaranteed to get the lock eventually. + +**Pros** +`+` Simple and proven way to synchronize readers and writers + +**Cons** +`-` Using the filesystem incurs a performance penalty compared to in-memory +synchronization. However, this is a trade-off to allow for readers and writers +to be separate processes. + +## 2024-10-05 Log rotation and compaction + +LogDB uses log rotation and compaction to keep the active log from growing +indefinitely. Obsolete writes are expunged from the log. This reduces the +amortized worst-case time complexity of reads from `O(m)` where `m` is the +number of writes to `O(n)` where `n` is the number of records in the database. +Note that `n <= m` always. + +Log rotation is triggered when the active log segment reaches the configured +capacity, and the maintenance function is called by the user. The segment is +rotated by renaming the current log file to a new name, and creating a new +empty log file. The rotated file names are suffixed `1..n`, where `n` is the +number of rotations that have occurred. + +To find the newest record, LogDB scans backwards log segment files starting +from the active log file `log`, then `log.n`, `log.n-1`, and so on until +`log.1`. This is done until the record is found or all log segment files have +been scanned. + +After rotation, the rotated log file is also compacted. Compaction is done by +forward reading the log file, adding the records to a map, and writing them +back to a temporary file. The new file is then renamed to the original file +name. + +**Pros** +`+` Keeps the active log from growing indefinitely and frees up space that is +used for obsolete data +`+` Reduces the time complexity of reads + +**Cons** +`-` Log rotation and compaction are expensive operations that require disk I/O +`-` Synchronous rotation blocks writers and readers + +## 2024-10-07 Python bindings + +LogDB provides Python bindings using PyO3 to allow users to interact with the +database. The rationale behind this decision is to make the database accessible +to a language with a more approachable ecosystem for things like web services. + +These should be implemented as a separate crate to keep the core database code +clean and focused. The Python bindings should provide a high-level, pythonic +API that abstracts away the details of the Rust implementation. + +These bindings should be implemented when the database API design is stable. + +## 2024-10-15 Index invariants + + + +The structure of primary and secondary indexes is shown in the diagram above +(here PK = primary key, SK = secondary key). The primary index is a map from +primary key the record value in memory. This makes the primary index act as a +heap of sorts, since the data is inlined in the index. The secondary index is a +map from secondary key to a set of primary keys. + +The design space here allows for a couple of approaches: + +1. We can specify the invariant that all indexes must contain the same set of + primary keys. Then, we can use a SK to find a set of PKs than can be quickly + looked up in the primary index. However, this approach has a flaw: if we + evict a PK from the primary index, we must also evict it from all secondary + index value sets, to keep the invariant. This means that some SK -> Set<PK> + maps are incomplete. This in turn means that we cannot be sure that a + secondary index lookup will return all matches, forcing us to scan the log + for the rest of the matches. This makes the secondary index useless, since a + scan is required anyway. +2. We can specify that the all secondary indexes must contain the full set of + matching record PKs. This means that a secondary index might have a reference + to a record that is no longer in the primary index. In this case the log + is scanned to find the record (which must exist). + +LogDB uses the second approach. @@ -18,11 +18,15 @@ LogDB does not support: - Schema evolution, other than adding new nullable fields Possible future features: + - Transactions +See the [ARCHITECTURE.md](ARCHITECTURE.md) document for more details on the design and implementation of LogDB. + ## Inspiration The most significant sources of inspiration for LogDB are: + - [SQLite](https://www.sqlite.org/index.html) for its filesystem storage and locking mechanisms. - [Designing Data-Intensive Applications (book)](https://www.oreilly.com/library/view/designing-data-intensive-applications/9781491903063/) for its excellent overview of database internals and in-depth analysis of log-structured storage. diff --git a/logdb_indexes.drawio.svg b/logdb_indexes.drawio.svg new file mode 100644 index 0000000..ecef1f5 --- /dev/null +++ b/logdb_indexes.drawio.svg @@ -0,0 +1,4 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- Do not edit this file with editors other than draw.io --> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1" width="305px" height="160px" viewBox="-0.5 -0.5 305 160" content="<mxfile host="app.diagrams.net" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:131.0) Gecko/20100101 Firefox/131.0" version="24.7.17">
 <diagram name="Page-1" id="nMafp9zaeK5C4Zbn3acO">
 <mxGraphModel dx="857" dy="548" grid="1" gridSize="10" guides="1" tooltips="1" connect="1" arrows="1" fold="1" page="1" pageScale="1" pageWidth="850" pageHeight="1100" math="0" shadow="0">
 <root>
 <mxCell id="0" />
 <mxCell id="1" parent="0" />
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-1" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=#000000;fillStyle=solid;strokeColor=none;" vertex="1" parent="1">
 <mxGeometry x="355" y="380" width="140" height="160" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-2" value="Primary index" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="385" y="380" width="80" height="35" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-8" style="edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;strokeColor=#FFFFFF;" edge="1" parent="1" source="GVMDcLo0JTW8xXX-t8_r-3" target="GVMDcLo0JTW8xXX-t8_r-5">
 <mxGeometry relative="1" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-7" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="430" y="430" width="50" height="40" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-5" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-7">
 <mxGeometry y="10" width="50" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-6" value="Record" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-7">
 <mxGeometry x="1.25" y="3.75" width="47.5" height="32.5" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-9" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="370" y="440" width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-3" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-9">
 <mxGeometry width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-4" value="PK" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-9">
 <mxGeometry x="2.5" y="1.8799999999999955" width="25" height="16.25" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-10" style="edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;strokeColor=#FFFFFF;" edge="1" source="GVMDcLo0JTW8xXX-t8_r-15" target="GVMDcLo0JTW8xXX-t8_r-12" parent="1">
 <mxGeometry relative="1" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-11" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="430" y="460" width="50" height="40" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-12" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-11">
 <mxGeometry y="10" width="50" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-13" value="Record" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-11">
 <mxGeometry x="1.25" y="3.75" width="47.5" height="32.5" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-14" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="370" y="470" width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-15" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-14">
 <mxGeometry width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-16" value="PK" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-14">
 <mxGeometry x="2.5" y="1.8799999999999955" width="25" height="16.25" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-17" style="edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;strokeColor=#FFFFFF;" edge="1" source="GVMDcLo0JTW8xXX-t8_r-22" target="GVMDcLo0JTW8xXX-t8_r-19" parent="1">
 <mxGeometry relative="1" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-18" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="430" y="490" width="50" height="40" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-19" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-18">
 <mxGeometry y="10" width="50" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-20" value="Record" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-18">
 <mxGeometry x="1.25" y="3.75" width="47.5" height="32.5" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-21" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="370" y="500" width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-22" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-21">
 <mxGeometry width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-23" value="PK" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-21">
 <mxGeometry x="2.5" y="1.8799999999999955" width="25" height="16.25" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-24" value="" style="rounded=0;whiteSpace=wrap;html=1;fillColor=#000000;fillStyle=solid;strokeColor=none;" vertex="1" parent="1">
 <mxGeometry x="520" y="380" width="140" height="160" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-25" value="Secondary index" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="540" y="380" width="100" height="35" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-26" style="edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;strokeColor=#FFFFFF;" edge="1" source="GVMDcLo0JTW8xXX-t8_r-31" target="GVMDcLo0JTW8xXX-t8_r-28" parent="1">
 <mxGeometry relative="1" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-30" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="535" y="440" width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-31" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-30">
 <mxGeometry width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-32" value="SK" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-30">
 <mxGeometry x="2.5" y="1.8799999999999955" width="25" height="16.25" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-29" value="Set&amp;lt;PK&amp;gt;" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="591.25" y="433.75" width="47.5" height="32.5" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-28" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="585" y="440" width="60" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-47" style="edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;strokeColor=#FFFFFF;" edge="1" source="GVMDcLo0JTW8xXX-t8_r-49" target="GVMDcLo0JTW8xXX-t8_r-52" parent="1">
 <mxGeometry relative="1" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-48" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="535" y="470" width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-49" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-48">
 <mxGeometry width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-50" value="SK" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-48">
 <mxGeometry x="2.5" y="1.8799999999999955" width="25" height="16.25" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-51" value="Set&amp;lt;PK&amp;gt;" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="591.25" y="463.75" width="47.5" height="32.5" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-52" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="585" y="470" width="60" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-53" style="edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=1;exitY=0.5;exitDx=0;exitDy=0;entryX=0;entryY=0.5;entryDx=0;entryDy=0;strokeColor=#FFFFFF;" edge="1" source="GVMDcLo0JTW8xXX-t8_r-55" target="GVMDcLo0JTW8xXX-t8_r-58" parent="1">
 <mxGeometry relative="1" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-54" value="" style="group" vertex="1" connectable="0" parent="1">
 <mxGeometry x="535" y="500" width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-55" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-54">
 <mxGeometry width="30" height="20" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-56" value="SK" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="GVMDcLo0JTW8xXX-t8_r-54">
 <mxGeometry x="2.5" y="1.8799999999999955" width="25" height="16.25" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-57" value="Set&amp;lt;PK&amp;gt;" style="text;html=1;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;fontColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="591.25" y="493.75" width="47.5" height="32.5" as="geometry" />
 </mxCell>
 <mxCell id="GVMDcLo0JTW8xXX-t8_r-58" value="" style="whiteSpace=wrap;html=1;fillColor=none;strokeColor=#FFFFFF;" vertex="1" parent="1">
 <mxGeometry x="585" y="500" width="60" height="20" as="geometry" />
 </mxCell>
 </root>
 </mxGraphModel>
 </diagram>
</mxfile>
"><defs/><g><g data-cell-id="0"><g data-cell-id="1"><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-1"><g><rect x="0" y="0" width="140" height="160" fill="#000000" stroke="none" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-2"><g><rect x="30" y="0" width="80" height="35" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 78px; height: 1px; padding-top: 18px; margin-left: 31px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Primary index</div></div></div></foreignObject><text x="70" y="21" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Primary index</text></switch></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-8"><g><path d="M 45 70 L 68.63 70" fill="none" stroke="#ffffff" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 73.88 70 L 66.88 73.5 L 68.63 70 L 66.88 66.5 Z" fill="#ffffff" stroke="#ffffff" stroke-miterlimit="10" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-7"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-5"><g><rect x="75" y="60" width="50" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-6"><g><rect x="76.25" y="53.75" width="47.5" height="32.5" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 46px; height: 1px; padding-top: 70px; margin-left: 77px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Record</div></div></div></foreignObject><text x="100" y="74" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Record</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-9"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-3"><g><rect x="15" y="60" width="30" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-4"><g><rect x="17.5" y="61.88" width="25" height="16.25" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 23px; height: 1px; padding-top: 70px; margin-left: 19px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">PK</div></div></div></foreignObject><text x="30" y="74" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">PK</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-10"><g><path d="M 45 100 L 68.63 100" fill="none" stroke="#ffffff" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 73.88 100 L 66.88 103.5 L 68.63 100 L 66.88 96.5 Z" fill="#ffffff" stroke="#ffffff" stroke-miterlimit="10" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-11"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-12"><g><rect x="75" y="90" width="50" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-13"><g><rect x="76.25" y="83.75" width="47.5" height="32.5" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 46px; height: 1px; padding-top: 100px; margin-left: 77px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Record</div></div></div></foreignObject><text x="100" y="104" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Record</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-14"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-15"><g><rect x="15" y="90" width="30" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-16"><g><rect x="17.5" y="91.88" width="25" height="16.25" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 23px; height: 1px; padding-top: 100px; margin-left: 19px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">PK</div></div></div></foreignObject><text x="30" y="104" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">PK</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-17"><g><path d="M 45 130 L 68.63 130" fill="none" stroke="#ffffff" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 73.88 130 L 66.88 133.5 L 68.63 130 L 66.88 126.5 Z" fill="#ffffff" stroke="#ffffff" stroke-miterlimit="10" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-18"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-19"><g><rect x="75" y="120" width="50" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-20"><g><rect x="76.25" y="113.75" width="47.5" height="32.5" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 46px; height: 1px; padding-top: 130px; margin-left: 77px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Record</div></div></div></foreignObject><text x="100" y="134" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Record</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-21"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-22"><g><rect x="15" y="120" width="30" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-23"><g><rect x="17.5" y="121.88" width="25" height="16.25" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 23px; height: 1px; padding-top: 130px; margin-left: 19px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">PK</div></div></div></foreignObject><text x="30" y="134" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">PK</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-24"><g><rect x="165" y="0" width="140" height="160" fill="#000000" stroke="none" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-25"><g><rect x="185" y="0" width="100" height="35" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 98px; height: 1px; padding-top: 18px; margin-left: 186px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Secondary index</div></div></div></foreignObject><text x="235" y="21" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Secondary index</text></switch></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-26"><g><path d="M 210 70 L 223.63 70" fill="none" stroke="#ffffff" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 228.88 70 L 221.88 73.5 L 223.63 70 L 221.88 66.5 Z" fill="#ffffff" stroke="#ffffff" stroke-miterlimit="10" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-30"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-31"><g><rect x="180" y="60" width="30" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-32"><g><rect x="182.5" y="61.88" width="25" height="16.25" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 23px; height: 1px; padding-top: 70px; margin-left: 184px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">SK</div></div></div></foreignObject><text x="195" y="74" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">SK</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-29"><g><rect x="236.25" y="53.75" width="47.5" height="32.5" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 46px; height: 1px; padding-top: 70px; margin-left: 237px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Set<PK></div></div></div></foreignObject><text x="260" y="74" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Set<PK></text></switch></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-28"><g><rect x="230" y="60" width="60" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-47"><g><path d="M 210 100 L 223.63 100" fill="none" stroke="#ffffff" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 228.88 100 L 221.88 103.5 L 223.63 100 L 221.88 96.5 Z" fill="#ffffff" stroke="#ffffff" stroke-miterlimit="10" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-48"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-49"><g><rect x="180" y="90" width="30" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-50"><g><rect x="182.5" y="91.88" width="25" height="16.25" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 23px; height: 1px; padding-top: 100px; margin-left: 184px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">SK</div></div></div></foreignObject><text x="195" y="104" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">SK</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-51"><g><rect x="236.25" y="83.75" width="47.5" height="32.5" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 46px; height: 1px; padding-top: 100px; margin-left: 237px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Set<PK></div></div></div></foreignObject><text x="260" y="104" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Set<PK></text></switch></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-52"><g><rect x="230" y="90" width="60" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-53"><g><path d="M 210 130 L 223.63 130" fill="none" stroke="#ffffff" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 228.88 130 L 221.88 133.5 L 223.63 130 L 221.88 126.5 Z" fill="#ffffff" stroke="#ffffff" stroke-miterlimit="10" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-54"><g/><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-55"><g><rect x="180" y="120" width="30" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-56"><g><rect x="182.5" y="121.88" width="25" height="16.25" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 23px; height: 1px; padding-top: 130px; margin-left: 184px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">SK</div></div></div></foreignObject><text x="195" y="134" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">SK</text></switch></g></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-57"><g><rect x="236.25" y="113.75" width="47.5" height="32.5" fill="none" stroke="none" pointer-events="all"/></g><g><g transform="translate(-0.5 -0.5)"><switch><foreignObject style="overflow: visible; text-align: left;" pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 46px; height: 1px; padding-top: 130px; margin-left: 237px;"><div style="box-sizing: border-box; font-size: 0px; text-align: center;" data-drawio-colors="color: #FFFFFF; "><div style="display: inline-block; font-size: 12px; font-family: "Helvetica"; color: rgb(255, 255, 255); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">Set<PK></div></div></div></foreignObject><text x="260" y="134" fill="#FFFFFF" font-family=""Helvetica"" font-size="12px" text-anchor="middle">Set<PK></text></switch></g></g></g><g data-cell-id="GVMDcLo0JTW8xXX-t8_r-58"><g><rect x="230" y="120" width="60" height="20" fill="none" stroke="#ffffff" pointer-events="all"/></g></g></g></g></g><switch><g requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"/><a transform="translate(0,-5)" xlink:href="https://www.drawio.com/doc/faq/svg-export-text-problems" target="_blank"><text text-anchor="middle" font-size="10px" x="50%" y="100%">Text is not SVG - cannot display</text></a></switch></svg>
\ No newline at end of file |
