Why? I'm not sure. I came across an implementation of it in JavaScript, and even though I don't really have much time, I decided to rewrite it in Go.
The timeline for this project isn't yet decided, so I don't have the exact number of episodes that will be produced. This means that, as of writing this post, no code for this project has been written. So, I wholeheartedly invite you to join the journey, learn, offer criticism (which is very important), and contribute.
What now? Before we call this episode 1, let me do a brief introduction about DAG, and what we might end up building.
But first, let's discuss about Directed Graph (DG). A directed graph is simply a collection of nodes and edges that has a starting node and an ending node. For your imagination, just think of arrows pointing from a starting node to an ending node.
Next, let me introduce you to DAG. But before that, there's an 'A' existing within the term, and it's key for understanding. The 'A' stands for "Acyclic", meaning no cycles. In a typical graph settings with sequences of nodes, the first node is also the last node, and the consecutive nodes are connected by an edge.
So, DAG simply refers to a graph that is directed (edges have directions) and acyclic (no cycles).
Phew!
By now, you might be wondering, "So what?". What purpose are you lurking at here? And a short answer to that is dependency (relationship). For some examples
-
Dependency Resolution: If task A must be completed before task B, and task B must be completed before task C, then we can represent these tasks and their dependencies as a DAG.
-
Shortest Path Algorithms: DAGs can be used to find the shortest path between two nodes when weights are assigned to edges.
-
Topological Sorting: This is a linear ordering of nodes such that for every directed edge (u, v), node u comes before node v in the ordering. This is useful in scheduling tasks and build systems.
A "weight" can signify the time it takes to complete a task, or any other metric of interest.
Having covered that, you might wonder how the KV store fits into this, especially since I haven't mentioned its relation to DAG yet. Let's conclude this episode with that.
The beauty of a Directed Acyclic Graph (DAG) lies in its ability to represent relationships and dependencies in a clear and structured manner. And, when you talk about a key-value (KV) store, at its core, it's a system that maps keys to values. But what if you want to track the history of these values? What if you want to understand the evolution of data, or maintain versions of it? This is where the concept of a DAG comes into play.
Imagine each node in the DAG as a snapshot of your KV store at a particular point in time. Each edge represents a change or transition from one state to another. When you add a new key-value pair, modify an existing one, or delete a pair, you're essentially transitioning from one state of your store to another. This transition can be represented as a directed edge in your DAG.
And so what?
By structuring the KV store in this manner, I gain the following advantages:
-
Versioning: I can easily track different versions of the data. If there's ever a need to roll back to a previous state or understand the history of a particular key-value pair, the DAG provides a clear and efficient way to do so.
-
Auditability: Every change is recorded, making it easier to audit and trace back operations. This is especially valuable in systems where data integrity and traceability are crucial.
-
Concurrency: DAGs inherently support concurrent operations. Multiple changes can be represented as separate branches in the DAG, which can later be merged if needed. This makes the KV store highly scalable and adaptable to concurrent operations.
-
Efficiency: By only storing the differences or 'deltas' between versions, I can achieve significant storage savings, especially in scenarios where changes are incremental.
Phew! x2
I didn't expect this post to be this lengthy. But yeah, this is it. Hopefully I get to add this to list of completed projects or sadly it becomes an X in the chronicle of abandoned ones.