CODEWITHSUNDEEP
c#.netdistributedkey-value
Paya
Paya

Reputation: 5222

How to implement ACID transactions on a custom key-value store

I have a server which exposes its storage similar to file system - it has files, folders, and you can upload files, download files, copy, move, delete, etc. There is absolutely no way to modify the server's interface (imagine FTP). There is also a limit for file name length.

I have multiple clients that need to use this storage simultaneously. The only means for them to communicate is through this file system interface. No custom central server for synchronization or peer-to-peer is allowed.

How can I implement remote key-value store from client-side, capable of ACID transactions, using this server's interface as a backend? Multiple clients can be accessing/modifying the key-value store at the same time, and the locking mechanism should be implemented only with the use of the exposed server file system interface.

I can easily turn that file system into custom key-value store, so what I really need is some C#/.NET library that adds transactions to an arbitrary key-value store. I don't need Facebook/Google-style performance, the key-value store will be used to save only dozens of GBs.

Suppose a remote key-value store allows me to string get(id), void put(id, string), and delete(id) entries. No other information is obtainable from the server (even no exceptions are thrown on errors). Given that the only clients accessing the store will be mine, how should I implement them such that only one can write/delete at the same time (write-locking)? Given the very very limited server interface, is it even possible? I suppose the solution would require some very nice cryptographic trick, but I haven't been able to come up with anything that would work yet.

Resources

Upvotes: 1

Views: 1862

Answers (2)

Ahmed Yasin Koculu
Ahmed Yasin Koculu

Reputation: 205

You may use ZoneTree, (https://github.com/koculu/ZoneTree) a persistent, high-performance, transactional, and ACID-compliant key-value database for .NET.

It supports Timestamp-based Concurrency Control. The algorithm is explained here: https://en.wikipedia.org/wiki/Timestamp-based_concurrency_control

OptimisticZoneTree converts non-transactional ZoneTree (LSM Tree) into ACID-compliant key-value store.

You may extract the transaction implementation (https://github.com/koculu/ZoneTree/tree/main/src/ZoneTree/Transactional) to transform your custom key-value store ACID-compliant.

Upvotes: 0

Scott Chamberlain
Scott Chamberlain

Reputation: 127563

This is just a rough idea but you basically need to implement a "Copy on Write" functionality wherein when you go to modify a file you would copy the file to a identical file name with a special extension, this would represent your working file you write your changes to and also represents your "lock". If someone detects that the "lock file" exists they can check the last write time to the lock file and if the last write is older than a pre-set timeout the lock can be assumed to be abandoned and delete the lock, if the last write is not older than the timeout access to the file is blocked.

When a client is done modifying the copied version of the file it renames the file back to the original "non locked" filename overwriting the unmodified original copy in a single atomic operation.

This gives you everything that is required for ACID with the only exception being Durability in that an abandoned lock takes a timeout period to be detected as abandoned.

If you did not have access to last write times from the files you could still use this structure but you would need to add a 3rd "metadata" file to represent the lock instead of your "in progress" copy of the file. That metadata file would just hold the timestamp of the lock's creation as its content.

Upvotes: 3

Related Questions