Hi Henry,

Henry Roeland wrote:
It would be greet if I can focus on storage allocator and leave the rtree part to you or somebody else.


Ok, let's do it this way. FYI, I won't have time this week to work on this. But at least I'll answer on this email briefly.

I hope I can still ask you guys questions concerning this storage allocator? I have some global Idea’s and probably need help both on design level and implementation.


Questions so far:

1. Is paging the only mechanism to get memory growth under control for an rtree? Its the only one I can think of, but maybe there are other ways to explore?


For the first version I think that our design should be as generic as possible:
- the Storage concept should be an abstraction of a persistent storage, just like an Allocator is an abstraction of "directly-accessible" memory.
- the rtree would request something or notify the storage about some events but it wouldn't have to know anything about the internal structure, techniques, heuristics, etc. E.g. the rtree wouldn't know anything about paging.
- the interfaces should probably be as compact as possible, e.g. as I said before, I think that in addition to the Allocator's interface we'd need 2 functions:
  * storage_traits<StorageOrAllocator>::get_pointer(ptr)     - notify the Storage that data pointed by a pointer is needed
  * storage_traits<StorageOrAllocator>::release_pointers() - notify the Storage that pointers aren't used anymore
- the storage probably shouldn't write the data directly to persistent part, instead it should keep the modified data cached and then write them all in one go. It could depend on some heuristic, the Storage could write changes when release_pointers() was called or it could define flush() method which could be called explicitly by the user. Still, the changes of persistent data should be done only if all pointers was released. At all times the storage could choose to keep the data cached. It could choose to unload all of the nodes, or only some less frequently used ones.

Is it reasonable?


2. Is there any way an rtree can be read-only? Or set read-only after (bulk)insert?


It could be done either in run- or in compile-time.
The most obvious way would be to throw a run-time exception in the get_pointer() after some flag (rtree created) was set.
Another possibility could be to disable rtree mutable methods like insert() and remove() in compile-time if some specific parameters or Storage/Allocator was passed.
Do you have some specific use-case in mind?


3. One problem/challenge is how to get and keep region(box) coordinates “divided” over the page nodes. At least thats my understanding of an (r)tree. You need the region coordinates as fast lookup ID to know if a query should “dive” into the page or its sub pages or not. 
Crazy idea: Maybe the allocator should manage an rtree of pages with references/pointers to the “real” tree nodes?

Questions: 
 

Each node internal node (in a classic R-tree) is a container of (Box, Ptr) pairs. During any traversal (insert, query, etc.) the rtree probably should load the whole node to have access to all of the Boxes of children regions. AFAIR all traversing algorithms access all Boxes. Then it chooses which children should be traversed and it traverses into the next level using the corresponding pointers.


Lets discuss the different actions an storage allocator can/must handle:
So the load would potentially be done in the call to get_pointer(). AFAIU the Storage would have to check if the underlying data (identified by Ptr storing some ID or handle) isn't already loaded/cached. If it was it'd just return the Ptr, if not then it'd:
- load a file,
- (maybe somewhere cache the raw file),
- create a node from loaded data and keep it,
- return the pointer.

So in my scenario (release_pointers()) it'd have to keep some container of returned pointers and when release_pointers(), flush() was called then just iterate over them and save changed nodes or create new pages, etc. It should probably also be possible to search the specific pointer in this container, so it should probably be map or unordered_map, or sorted vector, etc. Or do you have other ideas?

E.g. when construct() was called the Storage probably shouldn't create a Page or other persistent data, it should be created later, e.g. on flush(). The same with destroy().

Btw, the Storage/Allocator would have to support rebinding and creation of various types, not only nodes. It'd have to know if a type is a node or some other type. So some types would be handled differently than other types. I'm not sure if this is a good or a bad thing. I guess it's possible even with std::allocator<> to specialize it for some specific type.

This isn't needed, the rtree would know exactly which child node must be accessed becaused the Ptr is bound with the region in the internal node.

Hmm, it could be done and potentially usable. Though it'd complicate the storage_traits (1 additional methog/overload). But do you think that we could gain anything from that? I mean, various pages would have to be loaded and cached anyway. This could be added later if needed.


So in my scenario the rtree would notify the Storage that all pointers are released and that the Storage may do whatever it like with them. So it could save changed nodes, unload some of them, etc.

Hmm, the Storage also probably should know that a node was modified, or that pointers are released after mutable operation like insert() or remove(). So e.g. in the first version after an insert() the Storage could just save all nodes.

NOTE: The storage allocator must, as Adam already pointed out, deliver an interface to make above points possible. But not implement them in anyway.


So as mentioned above I was thinking about storage_traits which could be specialized for some StorageOrAllocator. Some member functions would be empty for Allocators but for Storage would have to be implemented. They would probably call some Storage's methods which could be called whatever the implementor liked.

Other questions/points that come to my mind are: 


I see 2 ways how the ownership could be implemented:
1. Similar to Boost.Interprocess where there is a memory Manager owning the data and AFAIU an Allocator only wrapping some reference to this Manager. So AFAIU (I didn't check the code) the Allocator is only an interface between a Container and a Manager. This simplifies the copying of an Allocator, rebinding, etc.
2. An Allocator which is in the same time a Manager or rather owns a Manager, so also owns the data. This'd probably require that the Allocator would have to store a shared_pointer to some Manager internally. An instance of a Manager would be created under the hood and a pointer to it would be copied automatically.

1 is more clear but it'd require to design not only the interface for a Storage/Allocator but also for a Manager, like in the case of Interprocess. 2 would only require to design the interface of an Allocator/Storage. If we choose 1 we could divide the logic into 2 Concepts, the Allocator could implement the in-memory-part (pointers, memory allocation, construction, destruction, etc.) and the Manager the persistent part (some file IDs or handles, saving and loading files, nodes serialization, etc.). So as in the case of Interprocess we could have 1 Allocator and could have many Managers.

In general I propose to work iteratively, that is at the beginning support minimal set of required operations in the Storage/Allocator to be able to e.g. insert() values and perform a query() in the most simple, probably inefficient way, but with a simple and elegant interface. And then optimize operations and extend the interface. Or would you prefer to design the whole Storage/Allocator theoreticaly?

Regards,
Adam