Figure out efficient skiplist serialization technique
Reported by Yurii Rashkovskii | April 27th, 2008 @ 12:53 PM
Currently we have FixedLengthSkiplistVolume which might be efficient enough for skiplist with fixed length key and value — but we need to "invent" a format for efficient serialization of generic skiplist
Comments and changes to this ticket
-
Oleg Andreev April 28th, 2008 @ 01:44 AM
Some thoughts on skiplist serialization strategy:
1) Skiplist must be mapped to memory.
2) On modification we write to the end of "operation log".
3) Time to time we dump skiplist to the disk and create a new empty operation log.
4) When we open a skiplist file:
1. Map skiplist to the memory
2. Read the latest log and apply it to the in-memory skiplist.
3. Allow operations on it.
The only case when we don't have to write anything to the disk is when we run a distributed system with concurrent reliable writes. In such case, each node can avoid using operation log and in case of crash, retrieve a data from the survived nodes.
While it is good in theory, there's always a case of the whole datacenter power outage which must not result in data loss or data inconsistensies.
Since skiplists could be partitioned very well, it is recommended to support operation log all the time and scale horizontally by adding new machines and spreading the data between them.
-
Yurii Rashkovskii May 10th, 2008 @ 03:18 AM
Irrelevant to serialization, but might have sense to read: http://citeseer.ist.psu.edu/sund...
Please Sign in or create a free account to add a new ticket.
With your very own profile, you can contribute to projects, track your activity, watch tickets, receive and update tickets through your email and much more.
Create new ticket
Create your profile
Help contribute to this project by taking a few moments to create your personal profile. Create your profile »
StrokeDB is an embeddable distributed document database written in Ruby
Oleg Andreev
Yurii Rashkovskii