There is exactly one ROT for each PSpace. The ROT has a member std::map > m_map This map is only accessed by a thread which has exclusive locked the CSpace. Scenario: client: Lock CSPace auto& obj = *mypref; <--- blocks until object loaded in memory Proposed changes: 1. Don't use AsyncJobQueue. Instead use a thread pool and post tasks in a more normal manner. 2. Currently PersistStore has these members - meaning each PersistStore creates two threads. We must instead use a thread pool, and avoid creating threads like this. AsyncLoadThread asyncLoadThread_; AsyncUpdateRotThread asyncUpdateRotThread_; The interface to the thread pool is just to post a task. Tasks should preferably avoid doing I/O. However the LSS doesn't provide an async I/O capability. Maybe it should? Let's start with a correct design and worry about optimising it later. Building blocks: - CSpace mutex - map> : objects which are resident in memory functions: ptr FindResidentObject(OID oid); bool AddResidentObject(OID oid, ptr po); - LSS object loader this takes on responsibility for async loading objects from the LSS. functions: void AsyncLoad(OID oid); callback: void OnLoadObject(ptr po) The synchronous function on the LSS is ReadContiguousSerialElement ILogStructuredStore* lss; if (IContiguousSerialElement* cse = lss->ReadContiguousSerialElement(oid)) { callback->OnLoadObject(oid, cse); } else { // notify not found } - object loader This uses the LSS loader to perform the async I/O then executes a CPU job to deserialise into an object in memory. functions: void AddObjectToLoad(OID oid); callback: void OnFailedToLoadObject(OID oid); void OnLoadObject(ptr po); - map : indep DGS nodes ---------------------------------------------------- Async functions It would be nice to use std::promise/std::future but these are not efficient. Also they allow for waiting "out of the box" - because a future has get() and wait() methods. But the whole point of async API is to avoid explicit blocking calls in your code. So instead, we emphasise the call back concept. void AsyncReadContiguousSerialElement( std::function_ref callback, OID oid); Note that function_ref is very fast, almost no overhead. However, it is a little fragile. In the LSS: class LSS can have a member AsyncJobQueue which runs jobs to load serial elements and send notifications. Questions: How is abort done? Do we pair callbacks with AsyncXXX calls, regardless of whether the LSS is closed? Do we batch sets of OIDs? Lss lss; PersitStore ps(&lss); ps.AsyncLoad(cb1, oid1); --> lss.AsyncLoad(cb1, oid1); ps.AsyncLoad(cb2, oid2); --> lss.AsyncLoad(cb2, oid2); // Hmmm : before doing this want to abort all async functions, but we can't because // they are across all PSpaces in the PersistStore pspace.Close() lss.AbortAndJoin(); <--- abort and wait for LSS async loads to complete ps.AbortAndJoin(); ps.Close(); lss.Close(); --------------------------------------------------------------------------------------------------- Philosophy of how to develop great code --------------------------------------- We will avoid the front end compiler Xcpp as much as we can - even within the CEDA core libraries. Significant testing can be done without Xcpp. The code Xcpp generates should be simple and straightforward. For example - assignable fields are implemented fully with C++ templates, before involving Xcpp. - B+Tree must be proper C++ template code, not a big macro using the Xcpp preprocesor. Most code should go into pure header libraries and allow for heavy independent unit testing and performance testing. We must have high confidence in correctness. We don't want to develop throw away prototypes. Instead we aim to write production ready code the first time. We try to test in a simplified context. In a sense we have a prototype in the simplified test environment. For example - an algorithm might be parameterised in a SiteId type. We might test with an int even though in production we use a GUID. - A B+Tree might support optional persistence but we test a transient version - We test that all the calls to MarkAsDirty have been made appropriately using a test framework Using pure headers allows us to control when we "switch over" from an old system to a new one because we only bloat the dlls when we instantiate the templates. We fully develop/test/bake a new system before we swap it in. --------------------------------------------------------------------------------------------------- Async approach... It encompasses async functions, DGS, LRU eviction, evictability, MVCC, multiple readers, serialised writers, async I/O for LSS, ROT, synchronous versions of async functions, ensuring CSpace can be closed and everything cleans up without issues. For performance we prefer all information about a field to be recorded there with the field. For example the DGS change count, or the vector time for an assignable field. This avoids the need for so many maps. We want to avoid having complex untested algorithms/structures - such as we see with the ROT. The ROT is just an example of a $cache function - at least in principle. Therefore it shiould be using the same algorithms, at some abstract level. Hopefully we use very well tested template code to generate the implementation, so we have very high confidence in its correctness. Fragile code is not an option. - no coroutines - no futures/promises - async functions do the posting and polling - allow for multiple reader threads - emphasis on polling - no blocking on anything, no condition variables - LSS is just an example of a $cache function, so just make sure we solve async $cache functions - ROT is just an example of a $cache function Consider that we use continuations where possible for the underlying implementation, but this is hidden from the users of the DGS. For example, when async load of object from LSS completes, the continuation runs which deserialises it and puts it into the ROT? $cache async IContiguousSerialElement* AsyncReadContiguousSerialElement(OID oid); $cache async ptr AsyncBind(OID oid) with IContiguousSerialElement* cse = AsyncReadContiguousSerialElement(oid) { return cse ? DeserialiseObject(cse) : null; } How do we support concurrency? We seem to need maps that support MVCC, by using COW on the nodes of the tree. But that means readers need to open writer txns to update the cache maps. We can't do that, unless we have a separate mutex to protect the map, not to be confused with the CSpace mutex. An alternative might be to somehow batch up the changes to a map for the next writer. So... a map uses a tree of nodes, and the nodes are not updated by readers. However readers can batch up changes to be applied by the next writer. This approach can also be used to batch up the deletions. Each reader has a private batch it is creating. When it reaches a threshold size it is swapped with an empty one and ownership of the full batch is given to the CSpace, so that it can be applied by the next writer. Note therefore that to some extent long running readers have their work made available as they go. The batches amortise the number of times we need to lock any mutexes. Note that as readers provide their private B-Trees to the CSpace, the CSpace can accumulate (i.e. merge) them into a single delta to be applied by the next writer. This is how the ROT updates over time. Arrays and vectors for cache maps --------------------------------- We should support arrays and vectors for cache maps, where the key is an integer, or can be mapped to an integer. The latter allows two parameters regarded as an index into a 2D array to be mapped to an index into a 1D array. Xcpp could support a syntax to allow the cache map implementation to be selected. E.g. the following selects an array of size 256. $cache <> f(int i) const { ... } Bytewise maps ------------- The RPM is a hierarchical map using the bytes in an OID. It needs to be implemented with templates, so it can be used by both the LSS and the ROT. We want C++ template code that allows for bytewise maps to be implemented which support optional persistence and MVCC. This can be used to implement the RPM of the LSS, and the ROT of the PSpace of a PersistStore, and for cache maps of $cache functions. The key type can be an uint32_t or uint64_t. B+Tree using C++ templates supporting optional persistence, optional typeops and MVCC ------------------------------------------------------------------------------------- A great general purpose ordered map in memory is a B+Tree. We want a pure header C++ template implementation of a B+Tree which supports - optional persistence - MVCC - batched inserts - batched deletes - last-accessed-time - either on internal nodes or cache map elements A batch of inserts is represented using a second B+Tree. Batch inserting is a merge operation on two B-Trees. This is analogous to external sorting which is based on merge sorting. It also aligns with level DB approach to high ingestion rates on key value stores. A batch of deletes can be represented using a set of keys to be deleted. We need to reconcile the MVCC requirement with the idiom that we prefer data types that only support a single thread. Posted tasks are readers ------------------------ A posted task to calculate a cache map entry is by definition a "reader". A reader is able to see a consistent snapshot of the data, and enjoys full concurrency with other readers. It makes sense for it to do all its CPU work itself, or else give tasks to be run by other readers which enjoy the same ability to see a consistent snapshot - indeed the same snapshot of the reader which created the task. Currently the DGS has an arkward "with" syntax on async dep nodes, to allow for inputs to be read with a CSpace lock in which time dependency edges are formed, before posting a task to be done without the CSpace lock. This won't be necessary with MVCC. CSpace garbage collection ------------------------- The CSpace garbage collector has some disadvantages: - a lot of complexity - potential for pauses while GC holds a lock - complicates other aspects like MVCC - not needed for our data model which emphasises value types implemented with recursive structures - not needed for tree structures of views - not needed for cache maps - not needed for persistent objects - has to be done manually anyway - requires writing all the visit methods It has questionable benefits. Conclusion: we drop the whole idea of a CSpace garbage collector. --------------------------------------------------------------------------------------------------- DGS --- The DGS has fundamental importance to writing applications in CEDA. DGS nodes can be async/sync indep/dep (4 combinations) The DGS is associated with cache functions and cache maps/arrays. Allowing for MVCC ----------------- Under MVCC the writers are serialised, i.e. there's a linear sequence of updates by the writers. The updates in this sequence are identified by a Transaction Sequence Number (TSN). Therefore a TSN uniquely identifies a snapshot of all the objects in the CSpace for a reader. The writer TSN represents the "change-count" assigned by the writer to nodes of the DGS as they are updated. To allow MVCC the DGS dep nodes only record the in-nodes, not the out-nodes. A reader is not allowed to update the existing objects, other than set atomic pointers or set atomic last access times. A reader cannot insert into the cache maps. Consider a $cache function is called and no entry is found in the cache map. Then the reader needs to create a private mapped value - e.g. a dep node and calculated value. The dep node can record its in-nodes as the read barriers are called on its inputs. Since all this state is private to the reader there are no concurrency issues. Later these calculations are moved to the CSpace and eventually they are merged in by a writer. A writer can create new objects, delete existing objects and update objects. When an independent variable is updated the change count is assigned a new value. There is no concept of propagating dirtiness. A writer produces a new snapshot of objects with updated change counts on the indeps. This can mean many of its cached values are actually stale, but the writer doesn't generally recalculate anything. A reader works on a snapshot and easily runs the risk of calculating deps which are already dirty. What does it mean for a reader to merge in its calculations? We could use the change-count on the calculated values to see whether a reader is providing something more up to date. Private reader data structures for recording its calculations ------------------------------------------------------------- A reader only sees a snapshot of the objects. Therefore the cache-maps have a stable address in memory. Therefore their memory address can be used to identify them. This allows a reader to index all the calculations it has performed. Each reader has a hashmap to map each cache map to a local version of that cache map used to represent the batch inserts. Cache maps for parameterless cache functions -------------------------------------------- A "null tuple type" (null_t) has a single value of that type. Such a type cannot convey information, but it can for example be used as a type of a variable, a return type, an argument type or either the K or T in a map. Cache maps are associated with $cache functions. Conceptually a parameterless $cache function has a cache map with a null key type. Now a map is similar to a optional in that it either caches a value or it doesn't. Support for using mapped value for either DGS node or the value that was calculated ----------------------------------------------------------------------------------- The ROT has a fancy optimisation where the ptr is also used to point at a DGS node. This concept should be generalised by using std::variant so it is available whenever we have an async indep DGS node. There are two reasons: - we want it to be available whenever we have an async indep cache function - we want that aspect to be properly tested - we want the full complexity to be broken down into unit testable parts. --------------------------------------------------------------------------------------------------- Synchronous calls on top of async functions ------------------------------------------- A future provides wait() and get() methods which block until the result is available. We'd like to support synchronous function (blocking) on async function anywhere, layered on top of async version? To wait efficiently there needs to be a waitable object, such as a condition variable or a manual reset event. Waitable objects are expensive to create so we'd like to create them only when they're needed - i.e. because there's a client that wants to wait on a result being ready. Cleanup might be challenging - we don't want a race between deleting and waiting on a waitable object. It raises a question about how it can be cancelled, and might need a concept of throwing some kind of operation cancelled exception. It greatly increased the complexity of the ROT. We want to come up with a simpler solution. The synchronous call may be by a writer that has locked the CSpace. A cache map can only be changed by a writer which has locked the CSpace. Radical simplifying idea: Consider that the caller either a) returns the existing cached result in the map; or b) assumes it needs to be calculated itself (too bad if another thread is doing it at the same time). If it's a writer then it can update the map with the cached result. Otherwise if it's a reader then the update to the cache map is batched. This means we support synchronous "calculation" but there is no waitable object! --------------------------------------------------------------------------------------------------- Cleanup ------- When the CSpace is closed we want to: 1. Send cancel requests for all async tasks or async I/O requests 2. Wait for all tasks to complete 3. Delete the CSpace, including all objects in it. The CSpace can do (1) by sending CancelAsyncTasks() to all objects registered with the CSpace. The CSpace can do (2) by stopping the TaskExecuters owned by the CSpace. Note that the task executer in effect monitors which tasks are pending, however it can choose to not run them at all? Note that objects don't generally own the task executers, instead the CSpace does, and we don't allow for synchronously stopping an object? --------------------------------------------------------------------------------------------------- Eviction -------- Eviction is about cache maps ---------------------------- Currently to be evictable is to be an RPM node, IObject or a DGS node: - The LSS RPM has a concept of eviction in order to have a target memory usage. - The CSpace GC supports eviction of IObjects, and this is used to implement eviction of the IPersistable objects referenced by the ROT - All DGS nodes form a single global eviction queue using a double linked list of nodes. That won't allow eviction in cases where a DGS node isn't needed after binding a value in the map. For example, this is the case with the ROT. It makes more sense to speak of eviction of elements of cache maps. To be evictable is to be an element of a cache map. This is consistent with individual cached values corresponding to parameterless cache functions. For example, we need eviction of: - RPM nodes - IPersistable objects which are referenced by the ROT - maps used by $cache functions in application code We shall ignore the concept of GC eviction of IObjects - except where there is some kind of map. Cached pointers in prefs ------------------------ Currently the prefs are treated as strong references which pin objects in memory. The GC was used to zero the prefs in order to allow an object to be reclaimed. Consider a radical simplification: we don't have prefs/crefs. Instead we either have OIDs or pointers or variants over them, or cache maps. Getting rid of prefs/crefs fits in well with the idea that location transparancy is an antipattern. Do we even want a ROT for all objects in a database? Why do we make the objects form a tree under the UTroot, and also they're referenced in a "flat" manner by the ROT? The ROT is handy when we have an incoming operation which identifies an object with an OID. The ROT allows for binding to the object in memory. The pointers in a pref are actually bad for MVCC, because they mean writers have to make copies of parent objects on the basis of COW just in case there's a pref pointing at a child which has changed. So if we want MVCC we really need to drop the cached pointers to objects in memory, and instead let the ROT be responsible for tracking object versions in memory. Conclusion: - No pref/cref - Only ROT is allowed to cache pointers to IPersistable objects - Persistent objects only record OIDs in order to reference persistent objects. There are no cached pointers. But this raises a serious issue: what happens with $cache functions that return pointers to objects? Don't these cause problems with MVCC? It depends on whether they are pointers to immutable objects. If not then COW needs to copy the cache map itself. Sizes of cache map elements --------------------------- Since cache map elements are evictable, we need a reasonable estimate of their size in bytes in system memory, or on a video card etc, so we can calculate how many need to be evicted in order to reach a target memory footprint. Pin counts on cache map entries ------------------------------- Sometimes it is not allowable for a cache map entry to be evicted. For example: - it may be associated with an async task that has been posted to a thread pool. - it may be associated with a dirty IPersistable object that hasn't been written out to disk yet. A possible way to support pinning of cached objects in memory is to have a concept of a pin count which is incremented/decremented - such as when an object in the ROT becomes dirty or clean, or while there's an async task being posted. An alternative is a virtual IsEvictable function on a given cache map entry. The evictor skips cache map elements that are not evictable. Objects having cache maps registry ---------------------------------- Every object that has one or more cache maps needs to register itself with the CSpace. A reader has a private list of objects having cache maps it has created. When this reaches a threshold it is swapped into the CSpace. The CSpace accumulates these into its registry. An object implements a function to visit all its cache maps $interface ICacheMapVisitor { void VisitCacheMap(); } $interface ObjectHavingCacheMaps { void VisitCacheMaps(ICacheMapVisitor*); } Using time sequence numbers for LRU eviction -------------------------------------------- We want to roughly speaking achieve global LRU eviction of cache map entries. By global we mean over all cache maps under a given CSpace. 32 bit numbers provide a basis for recording the time when an object was last "touched". A reader records the "current time" (maybe in TLS?). This is updated periodically when its batches become full. i.e. the readers current time is read from the CSpace's current time. The current time doesn't advance very quickly - perhaps every 100msec is ok. That wraps around every 13.6 years. Consider an application that is sometimes active and sometimes inactive. Rather than use a wall clock time which advances during inactive periods, it's more approprite to use a logical time sequence number where is incremented at the rate objects are being accessed. For example, consider that the target cache size is 4GB. We could divide this by 256 to get 16MB and increment the time after 16MB = 2^24 has been accessed since the last time. This notion of time wraps around after 2^32 x 2^24 = 2^56 bytes = 64 petabytes has been accessed. The CSpace records information about how much data is cached, as a function of the time the data was last accessed, using an array with 1024 elements to record the following function: s(t) = S[current-time - t] = SUM { size-in-bytes(cached-obj) | time-last-accessed(cached-obj) = t } Using an array S is great for performance. S allows for picking a suitable time threshold for evicting objects, in order to reach a target memory footprint: SUM { s(t) | t > time-threshold } = target-cache-size --------------------------------------------------------------------------------------------------- Rejected ideas -------------- Consider that every cache map is "registered" with the CSpace using a double linked list. The order doesn't matter. When a cache map is created it adds itself to the CSpace's linked list. When a cache map destructs it removes itself. Hmmmm - how do we make that threadsafe - the adds need to be batched by the reader. To do eviction the CSpace writer: - picks some of the registered cache maps - for each of these cache maps, it scans it, and evicts elements which are marked as evictable and have a time which is older than some threshold. eviction of nodes of cache maps ------------------------------- If we want coarse level eviction then we can evict at the granularity of leaf nodes of the BTree - which might correspond to many keys. We can for example evict at granularity of 256 IPersistable objects at a time, rather than individual IPersistable objects. Let's not make assumptions about the right granularity, and allow the most appropriate to be used on a case by case basis.