DataStore over AppendableData design

The limit is not “too much for memory” though, which would be too slow in most cases as memory is often quite big, but a set size and / or time passing so that a fairly regular flush occurs.
But it’s a trade off of course, and yet to be seen if it can be sufficiently fast.

Don’t think this leads to data loss. If you have two writers, they see only the data they themselves have written. As soon as one has compacted, the other will need to merge its data with the first one.
The optimistic concurrency API of the ADs (TryAppend(value, expectedVersion) ) makes sure there is no concurrent compaction writing over a newly written one.

That’s what I think as well.

2 Likes

So for instance if you had a record with the seats available for an event, then 2 instances could not allocate specific seats and/or would have to read the record then write it back out. If upon writing the expected version is wrong then the instance that saw that would have to fail the attempt and the customer choose another seat. For most relational databases online this check for avail seats is quick and possible to keep real time updates showing seats as they are allocated and the customer experience is good. But for SAFE this has significant network lag times and your “in-memory” lag times.

3 Likes

Seat reservations (and similar) is an interesting area, because counter to common belief how these work in real world is often not by transactionally reserving the seats in real time.
Instead there is an eventual consistency and if there is over reservations it is solved by the business. (I.e. tough shit, we’ll compensate you with this or that).

But, there will still be business areas needing real time transactions requiring low latency full consistency with multiple writers. Those will not be looking at SAFE as a first option, as SQL on SAFE is probably not among the first things we get (due to these complications).

And this is also why it will be hard to get such businesses (or those who provide a nice customer experience with booking systems relying on real time updates) to move onto SAFE.
The pain of data breach epidemic hitting them will be pushing them towards SAFE, but the latency / performance will be a repellant.

4 Likes

Actually there has been changes since transaction rate of online server systems has increased. Now it more depends on industry and type of seat reservations needed. Its now very bad business here to over book seats and they typically use real time bookings. For instance a simple example is cinema bookings where you can see the actual reservations on line and if you stuff your booking then those seats you choose are frozen till they time out after 15 minutes. Our airlines are the same.

Actually I am at a loss to find any examples of the “olden” time seat reservations in our country like we had in my younger days. Not sure if we have legislation here that outlaws over booking as a method to handle bookings. Ticketmaster actually handles some events that sees the occassional large event booked out in minutes without the complaints of overbooking. And within those minutes you get your actual seat (section/row/seat) allocated and ticket with the actual seat specified in PDF form. So they must be using transactions per (set of) seat allocation

I am thinking that a system that allocates one AD per seat available would not have such speed performance issues since a seat allocation requires only one append with the expect version (ver 1 I suppose) and the value for that AD would be customer details. The very small fraction of cent per AD would not be an issue since we have large ticket processing fees of some $3 to $7 here.

3 Likes

Yep, and if it includes multiple businesses (flight, hotel, car) theres often a Saga handling it, i.e. it goes from one to the other, and if any fails, it issues compensating actions (unbook), all of which looks like a single succeed or fail to end user.

Yes that could be a good way for such.
So when you have a set to make available for bookings, you add those ValueAD addresses to a StreamAD, and that address you insert in some index hierarchy (you want to be able to find it later, so that you have this event/flight/whatever in your db).

Then you share this StreamAD address with the public and they can race to get the index 0 of any ValueAD in it.

So, any indexing of such bookings is done afterwards if they are needed. Not all things need full indexing immediately, and those are better suited to go straight into append only streams (which themselves would have to be pre-allocated into some sort of db structure).

2 Likes

Yes if you are crossing businesses. Holiday plan booking of flights+hotels+car is understandable. But here within the one business (eg airline, event booking, cinema, or …) they can do the booking immediately without over bookings.

Actually remembering my trip last year, they actually now have a “hold” system which holds the booking temporary allowing the agent to do the other books in sequence and not try all at once, but they know immediately if any is not possible. With the hold system then once they have all the bookings on hold they can then finalise the bookings without any overbooking which is the major problem.

Yes true, indexing can be done later.

But my thought is that when the seller’s APP sets up for an event it will allocate all the ADs prior to opening for bookings. Thus there is no issue to finding ADs (since someone else may have the AD at the address their algorithm uses) and primary indexing can be pre done. Only customer (etc) indexing would be delayed if needed. Remember the APP runs on the customer’s PC and so all this is done through their Machine so

  • AD allocations needs to be done by the ticket seller prior to opening the event for bookings
  • indexing is best done after by the ticket seller so that the customer has less opportunity to hack the system (hacking the booking APP)
  • encryption of the indexing is wise to prevent hacking/snooping

Anyhow I guess this is getting a little off the central theme you wanted to discuss, so I’ll leave it there since this is more implementation.

2 Likes

This happens too, but it is 2PC which gives n log n, so those who require higher throughput I’ve seen more recently use Saga.

Exactly, pre allocating the ads, then sharing the collection address (and releasing the key for the entries).
But I always use random MD addresses (and would expect to do the same with AD) as to never have to care for conflicts. So that is why the primary index is important at every level.
Otherwise you can also go by a consistent hashing scheme at various levels, that was used throughout by my first SAFE datastore implementation.

I’m trying to find what problems AD will give for the data store I’m implementing, and how those can be solved, so it’s all good.

3 Likes

Additional thoughts

Clarification

I have here been investigating how the data storage implementation I currently work on, would need to change as to work with AppendableData instead of MutableData, given a specific solution for append only data storage (LSM trees).

I.e.:

  • How could an LSM tree backed storage be designed
  • How would it work if we had AD instead of MD
    and
  • What would I assume of AD functionality for it to hold

Mostly I thought about this because I wanted to know how I should continue the development of it even after such a change, and naturally because it is just as fun to solve this problem as it has been to try solve the problem with MD the first time.

What this is NOT (if anyone thought so), is a proposal for AD or really an opinion at all about AD. It is NOT a proposal for MaidSafe on something they (or anyone else) should implement. Its not a proposal at all. This is just me sharing my work on the data store, and possible solutions I see for it and ways to adapt my code and design to potential changes in SAFENetwork.

Implications of the design

Now of course, in doing that work, it also leads my thoughts further on what the change means in a larger scope than my own implementation.

The data store I design, is not assuming limitations in what SAFENetwork is suitable for. That means: it assumes that it can be used for anything that people use for example MongoDb or Cassandra, etc. etc. for. (LSM trees are used in data stores such as Bigtable, HBase, LevelDB, MongoDB, SQLite4[5], Tarantool [6], RocksDB, WiredTiger[7], Apache Cassandra, InfluxDB[8] and VictoriaMetrics[9].)

One thing that came up when I was thinking about problems with this data store design, in the larger scope, is exactly this fundamental difference in the existence of garbage collection or not.
LSM trees are implemented as write only, but they are not implemented (as far as I know) on media that cannot be garbage collected.
That is quite a fundamental difference.

I am assuming here that data storage capacity growth, and need for garbage collection, operates at different levels. What makes individual hard drives working with log structured filesystems, not to fill up on day-to-day basis, is not solved by data storage capacity growth (which obviously also happens in parallel out in the world, but is not what in practice avoids the fill up). On a macro level, would the constant upgrades (replacing) of storage media by vaults in the network have this effect? My initial feeling - without having checked the numbers - is that the orders of magnitude are different, so that it wouldn’t work. (Anyone up for some back of the envelope estimations are welcome to come forth!)

The data storage with LSM trees over appendable data design, that I have described above, would give a very large production of waste data.
Now, it is of course one technical approach to emulating mutability in a 100% immutable setting.
It assumes that we for our applications do need to emulate mutability, and that it is a fundamental necessity as to produce software that we can use for everything we need.
It seems to me that it touches on the fundamental issue, that it is not a property of this specific implementation, but indeed a property of any system trying to emulate mutability in 100% immutable setting.
I would be interested in hearing other approaches, ideas and suggestions, as to either show that my suspicions are wrong, or maybe to confirm them, whatever might bring us any step closer to knowing how to best deal with it.

Dynamic, static or something else?

There’s also the possibility to view the SAFENetwork as not supposed to deal with that kind of data handling, i.e. large amounts of dynamic data, and instead more of a static data store.
Technical boundaries would lead to some limitations in use cases, and there’s nothing wrong with that.
A space rocket is very good for taking things out to space, but not very good for plowing or harvesting lands in agriculture. (Well, maybe you could do some controlled shock-wave harvesting with a SpaceX rocket and a joy-stick, piling up crops in nice heaps at the edges of the fields. But I guess there’s a big risk of just a very expensive sea of fire and chaos :smile: )
Point being, maybe this advanced rocket shouldn’t be used for everything, as a versatile multi tool, but to solve specific problems. And so, such insights would guide us better in our efforts, with what we try to do. Now, I still hope and wish that the full spectrum of possibilities will still be there, but I don’t demand of the flowers to be trees, or the sun to be the sea. Everything is what it is :slight_smile: and the best way to use it is to know things for what they really are. I guess that way of seeing things is a big part of what makes me like exploration and problem solving.

7 Likes

Just for my understanding, is the basic issue here that SAFE (and presumably other decentralised systems) cannot be garbage collected because memory is not pooled? So all data would need to get written to disk?

1 Like

No because garbage cannot be deleted.

The problem revolves around deleting data. It becomes very complex to do it safely (meaning: not causing anyone who would expect to find it to later not find it) when data is stored in a network like this, since you need enormous amount of tracking to see who uses it. So a much simpler approach (needing less code, i.e. more robust) is to not allow any deletion.
But, then we don’t have any garbage collection either (i.e. removal of completely worthless, unused data, which would - as far as I can see - be produced when trying to emulate mutability, and which log structured filesystems and databases rely on as to not very quickly run out of space.)

Well, it’s the story of life, where ever you go there’s daemons to fight, they just come in different shapes and colors.

But, if I were to choose, I would prefer immutability as to start building on something simpler, and eventually investigate possibilities to allow mutability in some way.

I can think of much less complicated ways to build an indexed and searchable datastore than the OP example, that would perhaps have OK time complexity for reads and writes.

For example, just make everything streams. If we assume that AD will be based on fix size segments that will be allocated in different sections (like a chain of MDs), then we can optimize for that size, and make a snapshot so that it lands on the next-to-last slot (version), right before the link slot to next segment.
And if we assume that there’s a fast and simple way to get most recent value (version) of an AD when you hold a reference, then you know you just need to load all values from that segment, follow the link on first slot in the segment (pointing to previous segment), and pick the snapshot on the next-to-last-version on that segment, and then you can always restore some state with no more than n = [segment size] apply-operations of events since the snapshot - regardless of the AD version length.

So, every change to a primary/secondary index in the datastore, is appended to such an AD. Let’s say the segments will be 1k entries. At version 0 would be nothing, since there are no previous segments in this AD. At version 1-997 (inclusive upper bound) you would place the serialized data of every change (small changes, so < 100Kb size, which is still plenty for an event, which is more likely to be ~1Kb). At version 998 of the very first segment, you’d insert a snapshot. So what that means is: you’d apply all the 997 events through what ever function models your state, and get your current state. That current state you serialize and put to an ImD, whose datamap goes into version 998. Then version 999 takes the link to next segment.

Anything can be built with this (in principal, but maybe not getting it as efficient as we have become used to, that would be left to see). We wouldn’t avoid the garbage collection problem, but I think the data buildup would be at a slower rate than with OP example, and it is much simpler.

EDIT: disambiguation index / version for clarity

6 Likes

Is this kept by the consumer app (run by the consumer, eg ticket purchaser) or the owner app (run by the owner, eg the ticket seller) or by the vaults?

This is fine in non-SAFE applications because the person operating on the data (ie user or operating system or server administrator or app itself etc) has authority over what is defined as garbage. But on a distributed permanent network, what’s garbage to one person is valuable history to another - there’s no authority over garbage. ‘Unused’ needs to be the subject of a detailed debate here I feel (more broadly than just the context of LSM Trees), and ultimately will form the parameters around what the SAFE network is and isn’t meant to be for.

This is a good point, and depends on how we define mutability and the purpose of that mutation. If the purpose is to stay up to date, AD can emulate it perfectly. But if the purpose is to preserve privacy by deletion, then obviously AD cannot emulate that.

I think the main issue with AD is a performance one - clients need to compromise between staying up to date but not consuming lots of storage space or request bandwidth to achieve that.

My proposal is not very fancy - a binary tree structure containing a list of pointers to IDs (except the first entry is a config for the tree, and the last entry points to the next AD tree structure in case this tree fills up). The config entry contains a ‘predetermined’ depth depending on expected usage and lifetime. (The predetermined depth may be chosen algorithmically, it does not need to be chosen by the app creator).

If I have a very slowly updating datasource like my personal webpage then a single level tree is enough (approx 32K entries per AD). I can update the site 32K times before history spills over into a second AD (I call the spillover event a new ‘epoch’, current users can stop tracking the first epoch but new users will need to traverse from the first epoch to the latest). If I update the webpage once a day on average, this is about 90 years of updates in a single AD.

If I have a very fast updating thing like a database, the tree structure might be set at 10 levels deep. This means clients must fetch 10 AD to get to the latest entry, but it allows 32K ^ 10 updates (that’s insanely huge) before it spills over into a new epoch. The first level will update very rarely, the next level a bit faster, and the lowest levels will update very rapidly. But the user doesn’t need to traverse a linear history of all updates to get to the latest version. They just check if the top layer has changed - no? Second layer changed - no? Third layer changed - yes? Get the latest AD entry and follow the latest values down to the bottom of the tree; now the client is up to date with only 10 AD requests and have skipped potentially over billions of AD of history (which would be pointing to trillions of ID of data).

I think the binary tree structure has a good compromise for users to find the latest without too much storage or requesting. O(n) to traverse epochs, O(log(n)) to traverse within an epoch. It doesn’t even take any planning to get the depth right. If the root structure fills up too fast, the next epoch in the chain may be configured to use a more suitable depth. It can work with the AD API from the original post.

LSM Trees are fascinating but the need for duplicate data + garbage collection seems unsuited to AD.

8 Likes

Would it be credible for the binary tree depth to be adaptive, ie grow or shrink according to some control input, or would that always effectively mean rebuild from scratch?

2 Likes

OK, I need to clarify things that might not have been obvious in the OP.
So, the goal is to construct a datastore with indexed and searchable data.

Part 1

Goal: Indexed and searchable data.

Have a look at this chart to start with:

Comments

This falls under the very first [ NO ] in the diagram. This is not part of the problem I want to solve.

I am saying that this is not related to LSM trees, rather related to emulating mutability over immutable storage.

When we have copied the same data 1000 000 times (and far earlier than that IMO), then it’s quite fair to consider a few of those instances to be “garbage”. That is what I mean at least.
You’ll see further down, exactly what this duplication of data comes from.

The problem

Let’s continue with describing the problem:

The problem I want to solve, is to provide the kind of data storage (and access) that has been talked about during all development of SAFENetwork:

  • Autonomous cars data
  • SAFESearch
  • Token Exchange
  • Critical infrastructure (powerplants smart electricity grid etc.).
  • etc.

All of these go all the way down to the last [ YES ] in the chart:

  • Large amount of data - Check
  • Access data often or fast - Check
  • Continuous insert of new data - Check

So, these things seem to need indexes.

The problem we are solving is very similar to that of storing to disk. It is costly (in time or PUTs) to write, and we want to be able to access the data somehow afterwards. This is not a new problem and it has been studied in depth.

First of all, let’s go through a bit about the trees:

  1. Binary trrees are not suitable for for this since they have a very low fanout; only have 2 entries in a node. This gives a rapid increase in tree depth.
  2. BTrees can have n entries,which are stored at every level together with keys. This gives a bit better read performance than B+Trees, but is more complex and requires more merging and splitting of nodes.
  3. B+Trees can have n entries, which are all stored at leaf level. This is less complex to implement, utilizes the capacity of a node better and gives a larger fanout than BTrees and requires less rewrite of the tree as new data is inserted. This is the preferred solution for disks.

OK, so we have found a standard approach to build an index, which is B+Trees.

So, we need to look at why the B+Tree requires mutations.

To search for data, maybe all temperatures within a given range from a component in some powerplant for example, we need range queries.
If we are only indexing on a data id which is a monotonically increasing number, then there will be no problem, since every insert by default will result in ordered data.
But temperature measurements can come in any value. 123, 456, 234, 876, 345. They don’t happen in an ordered fashion. So every time we insert the data into a tree, if we are going to have an ordered tree, we will need to route it to it’s correct part in the tree. (This is what makes it fast to do a point query also, i.e. get where data equals an exact value.) But as new values come in, what once was the correct place for a previous value, will no longer be the correct place as to maintain a sequence. So as the new value should go there, we start re-arranging as to maintain the order.

^That there is mutation.


Part 2

Emulating mutability

The simplest way to do this, is to use MDs, and just rewrite the value in an entry. Done. Problem solved.
But, we are trying to solve the problem within the confines of immutable storage, so AD then.

A way to emulate mutation is to combine the two ways we can use ADs, i.e. as a value with opaque history, or as a collection of values. When combining them, we can store a collection at fix address, and by appending a new pointer, we can emulate that the collection is changing. What is really happening is that we are producing a new collection (new AD), and pointing to it.
Now, this doesn’t need to mean enormous data duplication, since the actual data need not be in that AD collection, only the pointers to it. The data is in ImDs, and that we don’t duplicate. The AD collection with pointers isn’t very big in comparison to the actual data. But still, over time, this will risk building up a lot of duplicated unused and meaningless data.

I’m a fan of event sourcing, so I’m not the least unfamiliar with the notion of the potential value of keeping ALL history (that’s how event sourcing people feel generally). But history is one thing, duplication is another. One copy of the history is good enough. Trillions and quadrillions and so on, of them is not needed.

Speed vs storage overhead

With or without out indexing, we stand before this problem:

For those applications that don’t need indexing, this is the problem with regards to the actual data.
For those applications that will use indexing, this is the problem with regards to the indexes as well.

  • When we go to the right end (append every change), we are not duplicating any data at all, and have minimal serialization costs when writing (so, high write throughput), at the cost of ever degrading access times (slower and slower queries).

  • When we go to the left (say, when you update email address on a Person model, you store the entire person model again, with Name, Address, Phone numbers, Birthdate, etc. etc. etc. i.e. constant duplication of data), we get fast access, since you just fetch the Person with one request (especially if you store the address as a hash of a unique value of the Person model, so you just calculate the hash, and access the data). But this comes at the cost of tremendous duplication of data, waste data. There is no need for more than one copy of the Phone or Address data, but we can’t avoid it. Also, writing is slower, since we need to load, deserialize, mutate, serialize and then insert large amounts of unrelated data with every little change.

There is no other dimension to the above, that is the physical reality we are stuck in when we go the immutable path. That is what I say seems to be the case at least, and ask of others to show that it is wrong.
We could cheat of course, and not store the data in the network, but we are assuming here that 100% data storage in the data network is the requirement.

LSM Trees

This is a way to increase write throughput, and is not exactly the same problem as this post covers. It’s a subset of it. If we have large amounts of data to store, then we will need higher throughput.
But LSM Trees are also best served with B+Trees for indexing. The OP described an idea to implement this combination, over AD - and during that work, the more fundamental problem emerged; the three data storage requirements in the flow chart; mutability over immutability, and it’s implications.


Summary

So, if we want to be able to do these things:

  • Autonomous cars data
  • SAFESearch
  • Token Exchange
  • Critical infrastructure (powerplants, smart electricity grid etc.).

… it seems we have to solve this problem. I.e. efficiently emulating mutability. Or not go immutable. (Or what ever?)

We could also say that No, those things are not what SAFENetwork is supposed to do, i.e. we only want to do things like:

  • Backup Internet Archive as to ensure it lives on.
  • Individual websites that we modify now and then.
  • etc.

But that doesn’t seem to be what most people around here believe or wishes that SAFENetwork will do. It sure isn’t the only thing I wish for it to do.

Decisions, decisions…

I think if the decision is being made to go over to AD, then at least we must assess what that means for what SAFENetwork can do, and try to investigate if and how we can solve the problem that arises with regards to what we have imagined to implement on the network.

Solutions

Now, if anyone out there, has a solution to the problem, I would be very interested in hearing it, so that I can go ahead and implement it.
Because that’s what I want to do! :slight_smile:

21 Likes

Thanks for the detailed clarifications I really appreciate it, especially the detail around BTrees.

I’m just going to braindump here to see if it pokes any thoughts in a useful direction for anyone, ie a bit rhetorical.

Yes the sequence part is really the issue. For chronologically sequential data AD is fine enough, but for other sequences (eg sort by temperature ascending) AD is quite prickly. The concept of sequences seems fundamental to this problem.

Problem1 is “fast and efficient data storage and retrieval”. The proposal is to use indexes stored on the network. Problem2 is that indexes change regularly but on SAFE (especially with AD) old indexes can’t be discarded which creates waste and/or leads to performance issues.

And this topic is about problem2, with problem1 acting only as a motivator… I just can’t help coming back to bitcoin blockchain + bitcoin lightning network, this feels so similar regarding the performance and permanence compromises.


I’m curious with MD mutations, it leaves garbage, eg if I mutate my DNS entry to point from ID AB12CD... to ID 34EF56... it would leave ID AB12CD... unreferenced and unused and presumably subject to garbage collection under non-SAFE conditions (but in SAFE it’s ID so can’t be removed). AB12CD... becomes garbage. This doesn’t affect read or write throughput, but it does affect storage. AD also create garbage but it remains readable garbage, whereas MD creates unreadable garbage. How do you rate the magnitude of the MD garbage problem in relation to the AD garbage problem? I feel this is more a political question than performance.

Do I understand correctly that the main issue with LSM Trees is the quantity of garbage rather than the mere existence of it?


Another suggestion for a solution…

Solve indexes as a ‘communication’ problem rather than ‘storage’ problem, which is probably as you say to “cheat of course, and not store the data in the network”! The idea being vaults use the network structure to arrange non-SAFE data (ie the indexes) which are read and stored with much weaker guarantees than SAFE chunks. Not very satisfying… This form of indexing seems a bit like torrent trackers, acting merely as a gateway into the p2p data. Solves problem1 but not problem2.

Thanks again for your clarifications, you’ve put an amazing amount of thought into this problem and it’s a pleasure to read about it!

8 Likes

Thanks @oetyng for the clarification. This was one area I was bad at articulating and is an important consideration for the use of ADs.

Although I would say that the types of applications affected are much more than you described. And even some day to day applications for personal use will be affected too, albeit much less, but multiplied across the desired userbase of the world amounts to a big amount. (eg account keeping for homes to multi billion dollar industries where data is always entered in no particular order)

5 Likes

I agree. This here, how to efficiently maintain sequences in the immutable storage, when inserts are in any order.

We have the compromise between appending changes and storing current state. In the most extreme case, we have the entire current state of our application that we serialize and store it as an ImD - very impractical of course. And at the other end, every little change is inserted to network, which is impractical in its own ways (maximum number of network requests), but also has benefits, (gives no duplication and minimal serialization overhead for example).
So as you say, that’s basically unchanged whether AD or MD. And AD can be used almost exactly as an MD. Except for adding entries instead of overwriting. So if the value is only a pointer, that is not much size to talk about (even though, in the large scale, maybe it actually is, that I don’t know yet).

I guess that is partly an answer to your question. For the design where AD/MD is holding pointers, and all data is ultimately in ImDs, they have the same basic problem of append every change or store current state (in that ImD), and that would mean the magnitude of differences between AD/MD is the size of 1 pointer more in overhead for every change for AD vs MD.

But if we look at how MD are also used today, the difference is (?) bigger:

An MD can keep quite a lot of data, so it doesn’t need to be pointers to ImD. If we are comparing storing actual data in MD (chunked if larger files), to storing it in AD, then we’re really seeing a difference. Each entry in an MD could be up to 1 Kb which would be like a simple row, could be an instance of a simple entity, and storing that as an ImD might be a bit overkill. (I’m not that familiar yet with the optimal sizes, when it is more performant to store in ImD instead of in MD).
So in this latest case, we could store up to 1Kb of current state in an entry, and modify just 100 bytes say of that current state, then store it again, but not incur that storage overhead of duplicating all the other 900 bytes + leaving the 100 previous bytes as history.

I didn’t look it up in the source code, but I have interpreted it as that MD actually has been immutable all the time, only that it has been completely opaque to the end user. I.e. that we didn’t actually overwrite the values in the entries, just append. If that’s so, then there is only the difference in the first example. And it might well be completely tolerable. But, the question could still be asked of course, if that is wise in the large picture, vs actually overwriting, with regards to garbage build up.

I think that is the full picture… Let me know if I’m missing something.

Spot on. And two problems indeed.

That’s what I would say. Problem2 is about the mere existence. And perhaps Problem2 is even more specifically about potentially detrimental excess of the garbage, not only the existence of it.

I say this because I also have in mind the estimations you did on sync times of data between nodes when joining sections; how much time they would spend downloading data before they could be productive, and what bandwidths were needed. I think there wasn’t any conclusion at that time, but IIRC it looked a little bit worrisome.
So my thinking is, we should not be adding to that problem, and my impressions here was that we would risk adding big time to it. (In case that time spent syncing really was a problem, I don’t know now).

I think it’s a good suggestion for an avenue to explore, I’ve been thinking about it as well.
We might need to think about indexes as a more transient form of data. It then really is a problem of communication as you say. If we can collaborate on the indexes out of band, easily and securely, then we can minimize the garbage load on the network, and have performant read and write. Maybe the indexes could be gossiped between participants as well (CRDT graphs) if we need to distribute it.
And for a single client to the data (which is not the end goal use case, almost ever I think, with regards to SAFENetwork) that would be much simpler, since no collaboration needed on the indexes .

One small-ish problem is that the indexes might in many cases be the actual key to reaching the data at all. Just putting the data in the network and then not knowing where it is, is actually not at all making it secured. It would be equal to erasing it (in fact, that is how erasing of data in the network is suggested to be done). So, theoretically, you could say that the data is not at all stored and secured in the network, unless the indexes as well are. But, that line of thought is not perfect, since at some point you will always reach the situation when the key into the data is not stored in the network, but as the login credentials to the network. It’s maybe more a philosophical issue.

Thanks to you for your input, and it’s fantastic to know that you enjoy it!
It’s a pleasure to work with these problems :slight_smile: and it’s even better when others join in.

5 Likes

I’m wondering if we are not considering that we will also have the transient data mechanisms, which may be more suitable for these type of things, once the data transmitted through that other type of comm channel and it’s fully processed, then it’s when it becomes stored, versioned, and immutable on the Network…?

I know that feeling :smiley:

3 Likes

Not sure how you mean. If you mean the data transfer between clients then we are talking about different things. I am talking about large amounts of stored data, in OP about ways to insert it, and following posts more about the data structures used to efficiently access that data.

Indexes are normally kept in the database. If that database uses SAFENetwork as underlying storage, then the changing nature of indexes (they are constantly re-arranged) for one, but generally all data actually, leads to more duplicate data produced on 100% immutable storage (i.e. not even garbage collection). Append only storage (other than event stores) is not uncommon, but it always has garbage collection as far as I can see.

There is a reason we think immutable data deduplication is something cool, a great feature of the network. If we end up producing loads of duplicate data anyway, then that isn’t exactly coherent in aspirations.

If the benefits still are greater than the drawbacks (going full on immutable), then to me it seems minimum duplication is achieved with only storing changes to the network. The more granular the less duplication, but also the more network requests.
Then combining that with keeping current state and indexes locally, we would still be able to effectively manage large amount of data on the network. With more than one client needing that access, it becomes significantly more complicated I would guess. But CRDT graphs could maybe be used. Don’t know. (And for that the other comm capabilities of the network, that you mentioned, could be perfect.)

But we have introduced a small weak spot there, since the indexes themselves are often the only access to the data, and also contain sensitive information. So it needs to be replicated and backed up securely etc. some other way. So we introduce a need for another layer with high security and reliability, since the reason we wanted it for the main data, probably reflects at least a bit also on the indexes.

6 Likes

I am wondering @oetyng

One of the goals is to not have so much garbage (wasted index ADs)

What if you push some of the work onto each and every instance of the APP. In other words the indexes are not fully formed/sorted in data store and when they are read from the network the APP does any needed sorting and building of the final form for the index.

A very simple example of what I mean.

  • records are added randomly and you want to process the records sequentially on some key
  • for this simple example just have one index AD
  • Each record is added to ImD and the key added (appended) to the index AD
  • When the APP wants to access the index it reads the MD and does a sort on the entries in the AD.
    • 32000 sort on most computers is probably much shorter than the potential lag time of access from the network.
    • so for one AD index its extra time, but for multiple AD index then it can be done while waiting for the next and so on merging/sorting the ADs as we wait for the next AD
  • Database engines were/are built with the view that the client PCs do not have great processing power and one powerful box was cheaper than having everybody in the company having powerful PCs. Also the security & other things, but SAFE itself solves much of that and the APP runs on the user PC anyhow. So decades later the PCs (and phones) are quite powerful and shoving some work onto them is not unreasonable.

For much larger databases we can have a system where the index ADs created with the initial data are only partly filled which allows plenty of additions (append style) in each AD before a rebuild of (a section of) the particular index is required. This method increases the number of index ADs existing within the index structure, but reduces the number of rebuilds of the index structure.

Thus even for large data bases with plenty of “mutations”, the indexes can be updated often without the need to rebuild them as often. This saves on the worthless garbage residing on the network.

tl;dr
Remove the requirement for particular index ADs or group of ADs to be sorted and place the sorting requirement onto the APP device. This saves creating a new AD just because you add an index entry.

5 Likes