There are two related changes here. Neither one involves a change to the function of the code. Both are localized to the src/structure directory to reduce the number of changes to review.

The first change is to run rustfmt over all of the source files in the directory. This is mostly a whitespace change.

The second is reduce the usage of trait bounds to only where they are needed. The main changes were:

• In general, the structs did not need trait bounds. I removed all except one, which was necessary.
• There were a large number of Clone bounds that were not needed. I removed all except the necessary ones, which I attached to functions instead of the implementation.
• I reduced the number of AsRef<[u8]> bounds to make it clear which functions used it and which did not.

https://github.com/spacejam/sled

Sled is an ACID kv-database with LSM/B+Tree performance characteristics written in rust. It's uses prefix encoding for keys which strikes me as very well aligned with terminusdb's storage strategy. It is currently in beta, though some of its caveats wouldn't really apply to tdb currently; e.g. its GC isn't very advanced, but that doesn't matter for tdb since we don't have a GC yet either. :) Sled's readme has a great overview of the project's goals and implementation.

I think it would be interesting to explore using sled as a (/ an alternative) storage backend for terminusdb-store.

I'm opening up this issue to discuss the appropriate representation for a buffer (i.e. an arbitrary contiguous sequence of bytes) in terminus-store. This discussion will help me to get an understanding for the motivation and mechanics of the current approach and to probe for reactions to an alternative approach, which I propose at the end. Please feel free to comment on anything or to correct my understanding if necessary.

Currently, the predominant view of a buffer appears to be M: AsRef<[u8]>. This type implies two things:

1. A given data: M has the operation data.as_ref() that returns &[u8]. This gives a read-only view of a buffer that can be shared between threads without the option of writing to it.
2. The struct containing the data: M owns the value referencing the buffer. There is no borrowing of references here.

This appears to have been changed from a previously predominant view of a buffer as a slice: data: &'a [u8] (1deedbf3e73d99012e70d96fe821cbc7b26d454e, bf6416bc6cf4c83b9a179e0a6a41dd21b000c69b, ad7dd425e85f75d9bdb7336a54a5e3560acbfed2, e5a50a00338ee5304327e424b72ca7eaf584eccc, c6a14f90b505efba9571da19e6f7f3faa84be5f7). This view meant:

1. The data: &'a [u8] cannot be shared between threads.
2. The view into the data lasts no longer than the buffer's owner, who has the 'a lifetime.

Now, given that the buffers currently seem to be backed by one of the two following structs:

• pub struct SharedVec(pub Arc<Vec<u8>>);
• pub struct SharedMmap(Option<Arc<FileBacking>>);

which both have Arc, I presume that the data is being shared read-only between threads. (I'm actually not yet clear on where the sharing is occurring, so if you want to enlighten me, I'd appreciate it!) If there was no sharing, I think the slice approach is better, since (a) there is less runtime work to manage usage of the buffers and (b) the type system keeps track of the lifetimes.

I think using M: AsRef<[u8]> is somewhat painful as schema for typing a buffer. It's too general and leads to trait bounds such as M: 'static + AsRef<[u8]> + Clone + Send + Sync in many places.

After doing some research, I think something like Bytes from the bytes crate would work better. Bytes is a thread-shareable container representing a contiguous sequence of bytes. It satisfies 'static + AsRef<[u8]> + Clone + Send + Sync. It also supports operations like split_to and split_off, which I think would work well when you want to segment a buffer into different representations. Replacing data: M with data: Bytes would make many of the trait bounds disappear.

Unfortunately, Bytes does not support memmap::Mmap, which means it would not suit terminus-store's current usage of AsRef<[u8]>. However, I've already implemented an adaptation of Bytes that does support memmap::Mmap. Others have, too. See https://github.com/tokio-rs/bytes/issues/359.

Here are some questions prompted by the above:

• What's the best way to represent a contiguous sequence of bytes in terminus-store?
• Does it need to be read-only?
• Does it need to be shared between threads?
• Would it be useful to use a less general type than AsRef<[u8]>? Could that type be a struct instead of a set of trait bounds?

• Transition all uses of AsRef<[u8]> to Bytes
• Use clone in LogArrayIterator, remove OwnedLogArrayIterator
• Track first element in LogArray, remove LogArraySlice
• Use Bytes in FileLoad, remove Map associated type
• Read files into memory, remove memmap::Mmap

Closes #39

• More documentation
• More tests
• Consistent naming
• More error checking
• Better error reporting
• Cleaned up and unified entry and decode functions
• Cleaned up future-based functions (removed Box/dyn, used combinators)
• Increased code coverage in tests
• Fixed monotonic check

At some point, I suppose terminus-store should be migrated from tokio 0.1 to 0.2.

See the following related items:

• https://users.rust-lang.org/t/failed-to-port-mononoke-to-tokio-0-2-experience-report/32478
• https://qiita.com/zenixls2/items/c594c87bf208a7094905
• https://www.ncameron.org/blog/migrating-a-crate-from-futures-0-1-to-0-3/

Consider this snippet of the implementation of the FileLoad trait for MemoryBackedStore (src/storage/memory.rs):

pub struct MemoryBackedStore {
    vec: Arc<sync::RwLock<Vec<u8>>>,
}

impl FileLoad for MemoryBackedStore {
    // ...
    fn map(&self) -> Box<dyn Future<Item = SharedVec, Error = std::io::Error> + Send> {
        let vec = self.vec.clone();
        Box::new(future::lazy(move || {
            future::ok(SharedVec(Arc::new(vec.read().unwrap().clone())))
        }))
    }
}

In the expression vec.read().unwrap().clone() here, if my understanding is correct, it appears that the Vec<u8> underlying the RwLock is being cloned.

I understand that MemoryBackedStore may be primarily intended for testing and, therefore, for relatively small vectors. However, that may not always be the case, and I'd guess that a clone like this could result in excessive memory usage and possibly even a surprise out-of-memory error. (Then again, I could be blowing things out of proportion, pun intended! 💥)

Would it be a good idea to avoid the .clone() here?

Lookups have been refactored.

For each lookup type (SubjectLookup, SubjectPredicateLookup, PredicateLookup, ObjectLookup) there is now a 'Layer' version (LayerSubjectLookup, LayerSubjectPredciateLookup, LayerPredicateLookup, LayerObjectLookup) which represents a lookup in either the layer's additions or the layer's removals, without taking parent layers into account.

The original implementations for SubjectLookup, SubjectPredicateLookup, PredicateLookup and ObjectLookup have been removed, and have been replaced by single implementations, GenericSubjectLookup, GenericSubjectPredicateLookup, GenericPredicateLookup and GenericObjectLookup. These are implemented in terms of the new Layer Lookup traits.

Unlike the old Lookups these are not implemented recursively, so stack exhaustion should no longer be an issue.

This implements layer export and import for the PersistentLayerStore, which currently backs both the memory and the directory layer store (yes it is a bit of a misnomer).

This closes #58. It is also an initial step towards #62, implementing the pack functionality as a separate trait in its own file instead of as part of a bigger trait. It also makes use of the async_trait macro as mentioned in #56.

We have a large triple store (over 50 billion triples) in virtuoso and want to know if terminudb can handle graph of this size or plan to do this. Thanks!

• Remove unnecessary VByte struct
• Add error checking to decode
• Optimize encode loop
• Add slice wrapper for encoding that does error checking
• Add Vec wrapper for encoding that ensures the right size buffer
• Fix encoding_len for 0
• Lots of documentation
• Lots of tests

This pull implements typed dictionaries, a new dictionary type for terminusdb values which uses a different efficient encoding for different types, is able to retrieve by type, and is able to do ranged queries over ordered types. It avoids linear-time operations, making every lookup constant-time or logaritmic-time. It is intended to replace the existing pfc implementation, at least for the values, but probably also for the nodes and predicates.

This is a work in progress.

A lot of the data structures are currently written around the idea that we're persisting layers directly to some persistent storage. The memory store is then implemented as a special kind of persistence which just saves things in a hashmap.

This is kinda weird and the wrong way around. We actually almost always want to build up stuff in memory first, and only then (possibly after some more checks, like schema checking) persist to disk.

Therefore, we should consider refactoring terminusdb-store to be in-memory first. That means that none of the data structures, nor the layer structures, should have to know about an underlying storage method (FileLoad, FileStore, etc), but instead directly work on Bytes. Builders likewise should not have to know anything about storage, but build directly into Bytes.

Doing all this will also reduce the complexity of the typing in store, as a lot of that is now complicated by the fact that in many places we want to work with builders without knowing this underlying storage method. If all actual persisting logic is moved into the various LayerStores, we probably don't have to include FileLoad or FileStore in any of the typing anymore.

When creating a new base or child layer, the PersistentLayerStore opens the files sequentially. They should be opened concurrently to prevent unnecessary waiting.

Currently deletes are per-triple. This means that deleting all triples for a particular subject has to be done by querying that subject's triples, and deleting them all individually. Besides being an annoying way of deleting, it also leads to a duplication of all the data being deleted, and we lose semantic value, as we do not save the fact that we deleted everything related to a particular subject.

I propose we implement wildcard deletes. Wildcard deletes would assert that for a particular subject, predicate, or object, or for a particular subject-predicate or predicate-object pair, all triples have been deleted in a particular layer.

Additionally, it should be possible to insert such a wildcard delete even if there's no previous insert that'd match the wildcard. This would allow us to shortcut many queries searching for data by specifying at a certain layer that this data will not be found no matter how deep the query drills into the layer stack.

I'm not sure if we can implement wildcard deletes with the present structures or if a new set of structures will be needed.

Our current iterators drill down the entire layer stack to find triples, returning them in a stable order. This order is stable even if you do delta rollups, which allows fast comparisons in some cases.

In the majority of cases though, the benefits of this approach are irrelevant, and we get to our first result much slower than we would otherwise. It'd be good if we have an iteration strategy which recursively descends through the layers, returning triples as they are found.

This is especially useful for cases where we're really only interested in a single result, such as when there can be only one result due to a cardinality constraint enforced externally.

Implement this new iteration strategy as a new set of iterators accessible through a new set of methods in layer.