prataprc / rdms Goto Github PK
View Code? Open in Web Editor NEWStorage library (Work In Progress)
License: GNU Affero General Public License v3.0
Storage library (Work In Progress)
License: GNU Affero General Public License v3.0
An undo()
API make sense in LSM mode. The behavior should be such that:
seqno
of that mutation.seqno
of that mutation.Intelligently handle maximum footprint limit for m0
level. Once the footprint() reaches 90% of the limit, trigger a auto_commit() and slow down the write ingestion rate.
Read-Write-Spinlock implements the idea of latch-and-spin mechanism normally used for non-blocking concurrency.
Blocking concurrency can have impact on latency. When operations that require rw-exclusion is going to be quick and short, we can use non-blocking primitives like latch-and-spin.
What is Latch and spin ?
In typical multi-core processors, concurrent read operations are always safe and consistent. But it becomes unsafe, when there is a writer concurrently modifying data while readers are loading it from memory.
Latch-and-lock mechanism can be used when we want to allow one or more concurrent writer(s) along with readers.
Imagine a door leading into a room. This door has some special properties:
Sharded-robt index is built once and used as immutable index there after. During the build phase, if there is a crash, there needs to be a recovery plan.
When replication has to be supported for Rdms indexes, a separate sequence-number tree need to be implemented as part of the every level.
This issue is applicable only when rdms
indexes are
configured to manage older versions for each entries.
Following are the read APIs defined by the Reader
trait.
Above APIs are the faster variant of reading into indexes,
which means, returned Entry
may or may-not include all its
previous versions (mutations).
Add a variant of these APIs like:
where the returned Entry shall always include all available
previous version, but can be slower due to disk-lookup and
merge cost.
Rdms, when configured with version control, won't destory older values for index entries. In other words, from the first mutation that CREATE a {key,value} entry in the index, to all subsequent DELETE and UPDATE mutations, can be preserved in the index.
There are two flavours to version control, centralised and distributed.
centralised version control assume a single instance of serialized writes into index. This implies that, for every version of value, its parent version is its previous version stored in the index, and shall remain so for rest of the index's life. Rdms's centralised version control has following properties:
distributed version control assumes multiple instance of an index, replicated across different nodes, and atleast two or more instances can injest write operations. This has few additional requirements on the version control system:
distributed version control won't be part of Milestone-1
Several crates like llrb, wral, robt are moved back into rdms crate, keeping it fairly independent modules. We are still planning to maintain them as independent crate for foreseeable future. But these crates have proper package management in-place. We have to check their independent crate from and make sure that they are migrated to rdms
crate.
bin/rdms
as the validation program.bin/rdms
as the validation program.An purge() API make sense in LSM mode. The behavior should be such that:
A variant of this API, purge_key() should should apply the above behaviour for
a single specified key.
Right now mmap
is implemented for index-file. robt
can be configured to use a separate value-log-file and mmap
feature is not implemented for value-log file. We should experiment an implementation of mmap for value-log file and measure read performance.
Using trait object gives convenience of abstraction. But performance can be an issue. Once such design choice is core::IndexIter trait object.
Validate the performance penalty in using IndexIter and if possible replace it with concrete types/traits.
We use Empty type across rdms
type mechanics to fill implementation gaps. Although it works well, we would like to consider using the !
(never_type) instead of Empty. One immediate challenge is
the conversion constraint that we have for instance trait Index { type O: From<ffi::OsString> }
.
Recent abstractions in compute design and architecture, has delegated memory/network/disk corruption detection and recovery to H/W later and Firmware layer. Nevertheless it is worth brainstorming this problem in application space.
A potential solution would be to Box and duplicate the reference when doing copy-on-write for Node type.
Goal for Milestone-1 is to provide a minimum viable product for enthusiastic users and early adopters.
diff()
API to create a delta between old
and new
value.merge()
API to create old-value
from delta
and new-value
...._with_versions()
flavor for read-api to fetch all the versions of index-value.Best case
, if memory-index can allow concurrent full-table-scan without any additional penalties.Better case
, if memory-index can allow concurrent full-table-scan without blocking writes.Good case
, if memory-index can allow concurrent full-table-scan without blocking write for too-long (< 1ms).count()
can only be approximate.Footnotes:
LlrbDepth calculates minimum, maximum, average and percentile of leaf-node depth in the LLRB tree.
Would be nice to have some rigorous test cases for this type.
Rdms indexes can support full table scan, by providing an iterator handle to iterate over every single entry in sort order. Since by design rdms also provide concurrent write operation, while the scan is in progress, this may lead to unstable scan if not implemented properly.
One mechanism used by Rdms to implement stable scan is piece-wise
scan. Again this mechanism is applicable only when entries are indexed in lsm mode. The basic idea is to do range scan in short batches, say 1000 entries for each batch, and drop the read-handler after the batch is read. There by, avoiding resource pressure on index and/or holding its rw-locks. To begin with caller should compute the seq.no. range (start, end]
that should be picked from the index and a begin-key
:
begin-key
would be Bound::Unbounded
.(start, end]
sequence number are returned.begin-key
are returned.rdms
index, by default, support concurrent thread safe API. Also some components within rdms spawn threads. This means, both locally spawned threads and rdms-handles that are used by application threads can suffer failure, in which case the failure must cascade across all the thread.
IMHO this is a bit early to work out a cascading failure mechanics. We may first have characterize the index functions and performance to implement the right method for cascading.
Robt index is built once and used as immutable index there after. During the build phase, if there is a crash, there needs to be a recovery plan.
Create a separate write-up documenting ROBT file-format, and clean up module level documentation.
Unlike Robt instances, Dgm has multiple levels of disk snapshot. And cutoff is only applied to the final and highest disk-level. Validation for this needs to be done by parsing the disk files outside the Dgm instance.
Given that footprint calculation need to be managed across set/set_cas/delete and its entry variant along with managing previous delta versions, it gets quite complicated. Review the present implementation for correctness and document the same.
Subsequently replace {:?}
formatting with {}
across the source base.
Goal for milestone-2 is to ensure production ready product, with beta testing.
Following test-suite, listed one per line below, shall be run on rdms
artifacts.
At present we have reached a state where there are enough unit test suite and a large source base to build momentum for this project. This is a tracking issue to figure out a nightly-continuous-integration process, targeted for Milestone-1
Steps of executions.
Organisation of nightly-repository
rdms-nightly/
bin/nightly-script
out/<yyyy>/<yyyy-mm-dd>-nightly.log
out/<yyyy>/<yyyy-mm-dd>-nightly.status
out/<yyyy>/<yyyy-mm-dd>-nightly.log, shall contain the stdout/stderr messages from nightly script. out/<yyyy>/<yyyy-mm-dd>-nightly.status, shall contain parsed result from out/<yyyy>/<yyyy-mm-dd>-nightly.log.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.