Update May 26, 2022

Our primary goal with Safe Network is data permanence. We store copies of data on devices that statistically are unlikely to be in the same region should, for example, a massive power cut or government-imposed internet take-down occur. For this purpose, the more copies the merrier, but that imposes demands on storage and, in particular, network bandwidth. This week we look at one approach to tackling this issue, which should allow more redundancy with less data flow.

General progress

@Anselme has fixed a consensus bug, implementing anti-entropy for handover as well as generations. More comprehensive join retries (where we ensure weā€™re in the current section state) have been merged too :muscle: .

@Chriso is digging into DBC implementation and has already completed all the CLI changes for passing a DBC to a new owner. Heā€™s now turning his attention to the sn_api side for assigning the change DBC owner.

We can also report progress on the observability front with @yogesh making nice headway with the traceroute messages, making sure all the message flows (file and register) have a traceroute response back to the client from the adults and are logged in the tests.

And @davidrusu has been spreading the word, attending another Toronto CompSci meetup to talk through Tree CRDTs. ā€œA great discussion all aroundā€, he reports, and a great place to recruit interested parties to Safe Labs.

In the wider safe-world, the ongoing community project to support MaidSafeCoin on the ERC20 protocol continues unabated, and we are please to announce these efforts continue to bear fruit! So in addition to Uniswap eMAID is now also open for trading on P2PB2B!

You can thank the dedicated community members such as @Sotros25 and @anon61899651 who have taken it upon themselves for pushing this topic forward continually :clap:

Optimising data transfer

When someone makes a GET request, that kick starts a number of processes. First, the request is relayed to the elders in which section the chunk is stored. The elders then calculate which four adults store the chunk - the four XOR-closest to the chunkā€™s address - and each of those adults pass their copy of the chunk back to the elders, who then return them to the requesting client.

This provides redundancy, there are always four adults with a copy of the chunk, and also gives us a way to monitor performance. If one adult is significantly slower or less reliable, it can be demoted. But it comes with a price tag.

If the client contacts all seven section elders asking for a 1MB chunk ā€˜Aā€™, and each elder in turn requests chunk A from the four adults holding it and returns them to the client, then potentially thatā€™s 28MB (4x7) passing across the network for a single 1MB GET request.

Currently, we are using a halfway-house system where the client contacts three elders at random and those elders contact the four adults holding chunk A - so we potentially have 12MB (3x4) of data flowing across the network for a 1MB request - better, but still not great. And reducing contacts to three elders comes at a cost: if we have only three elders interacting with the adults we no longer have a supermajority to decide if one of the adults is dysfunctional, making dysfunction tracking more complex.

A solution we are looking at now is information dispersal algorithms (IDA, also known as erasure coding). This could help us significantly reduce the volume of data transfer per GET, by having adults pass a share of the data to the elders rather than the whole thing. The elders then pass these data shares back to the client, who reassembles them and, voila, chunk A is recreated. Potentially this could reduce the flows on a GET to just 1.4MB for a 1MB chunk.

So how does it work? First things first, weā€™re not proposing replacing replication with an IDA. Some projects do this (e.g. Solana) but for us there are too many tradeoffs. So, just as now, if an adult goes offline its data is replicated in full to another adult. The change is that adults will be able to split chunk A into seven pieces using an IDA and pass just one piece back to the elders on request, rather than the whole chunk, meaning that much less data is exchanged.

Once it has collected five out of the seven pieces, the client can reassemble chunk A.

This five-out-of-seven figure doubtless switched on a few mental lightbulbs :bulb:, because itā€™s the same threshold that we use for BLS consensus, but IDA is a different beast from threshold cryptography, designed for optimising data storage and transfer rather than secret sharing. In case youā€™re wondering where the extra 0.4 comes from (transferring a 1MB chunk using IDA requires 1.4MB of data flows), this is an unavoidable overhead from the way the algorithm works.

So, less stress on the network and the client too, and of course all seven elders are now in contact with the adults, making consensus over dysfunction much simpler.

Further optimisations should also be possible with this architecture too. Because of recent Membership changes, we now know which adult of the three holding chunk A is actually closest. So rather than asking for chunk A, the client can ask it directly for the first piece A[0] and the elders will go straight to the closest adult; the second piece A[1], the elders will ask the next-closest adult, and so on. Any failures are simply retried at another adult. This is more efficient and means we can potentially increase the number of replicas - adults holding chunk A - without any significant extra stress on the network, with obvious gains for data redundancy.


Useful Links

Feel free to reply below with links to translations of this dev update and moderators will add them here:

:russia: Russian ; :germany: German ; :spain: Spanish ; :france: French; :bulgaria: Bulgarian

As an open source project, weā€™re always looking for feedback, comments and community contributions - so donā€™t be shy, join in and letā€™s create the Safe Network together!

63 Likes

Thanks so much to the entire Maidsafe team for all of your hard work! :racehorse:

And thanks so much for our new DEX functionality on Uniswap. It is very important for MAID holders to have DEX access. :racehorse:

20 Likes

Made the podium once more. Silver again!

15 Likes

Bronze better than nothing F5 hates Thursdays!!

Well done to all the team now to read :slight_smile:

13 Likes

just a random thought, that there is potential for an app that acknowledges userā€™s interest for priority and does not stress the network for large file retrieval if its not that urgentā€¦ but then the test of that would normally be price, yet GETs are for free. Free makes people and developers lazy?.. what negative feedback is there for selfish resource hogsā€¦ is there a burden on the user side for the number of chunks being requestedā€¦

Perhaps if streaming is made possible then seeking within files for just the bit thatā€™s of interest, will always be better performing and attractive because of that differenceā€¦ so, positive feedback through performance, rather than negative from price.

tldr; would be nice if GETs were efficient for the real need for the file.

Thanks as always for the hard work :+1:

8 Likes

Getting an error trying to click the like button on the OP!?
:heart:
capture

5 Likes

What prevents the client from GETting from a different number of elders? Like, if it chooses to only ask 1 elder, or all the elders, how could the client be punished?

Maybe the client has to send a number specifying which subchunk to request from each elder, and then some spam-suppression can be in place for requesting from too many elders?

4 Likes

I have seen that sporadically too

9 Likes

:point_up_2: awesome

is it a mountain or a mole hill to implement? next week, next month or next year? yes I know , when is not really permitted. :slight_smile:

:partying_face:

18 Likes

My understanding is the client would not be able to do that as the logic is handled at the section level. So the client requests a chunk, and all the elders (or three currently) receive the request and then decide how to proceed.

5 Likes

Data being spread out geographically is obviously good for making sure data is always available / never lost. When retrieving data response times are also important, asking all nodes to provide a part of the data seems like it it would be slow and detecting failures at the point the data is required.

You could just ask the closest node for the data?

To validate all nodes have the chunk you can periodically ask them all too hash a random section with a random integer. (This can also be used to keep statistics of who is closest to that that elder).

Ideally you want to encourage the nodes that hold a chunk to be as far away from each other as possible, but also know the fastest path to retrieve the data. Makes me think of the Babel Routing Protocol

9 Likes

It does sound fantastic.

But yeah, is this potentially a year fix?

Overall, well done team

5 Likes

There are already libs for this. So itā€™s a matter of the Adults encoding the data and giving the correct piece to each elder who then returns these to the client. So much more mole hill than a mountain. It should be 1-2 weeks man hours I think. At least of that order.

18 Likes

Iā€™m sorry iā€™m confused. How do you break a file into 7 pieces then reassemble it with only 5/7 of those pieces? That doesnā€™t seem logically possible. Where does the receiver get the 2/7 missing data from? I must have missed something.

3 Likes

Basically think of it as the file gets made larger by circa 40% and split in such a way that you can lose some pieces and still have the file reconstituted. Hereā€™s a quick and easy paper on it https://www.eecs.harvard.edu/~michaelm/TALKS/RabinIDA.pdf Note we donā€™t have a large file issue and a normal Rabin ID A(or even reed Solomon) algo is enough

12 Likes

I appreciate the link but this is supposed to be easy reading? This is on par with reading a physics paper.

6 Likes

Thanks, but no thanks David. I stopped reading (due to sudden onset of migraine) at page 3, Abstract. An Information Dispersal Algorithm (IDA) is developedā€¦ :sunglasses: Southside! Beer Me!

4 Likes

For a quick read I recommend the Erasure Code page on Wikipedia:-

Skip the maths! I am not a mathematician and I refuse to try to understand the weird squiggles.

The key part of the explanation is:-

Alice wants to send her telephone number (555629) to Bob using err-mail. Err-mail works just like e-mail, except

  1. About half of all the mail gets lost.[1]
  2. Messages longer than 5 characters are illegal.
  3. It is very expensive (similar to air-mail).

Instead of asking Bob to acknowledge the messages she sends, Alice devises the following scheme.

  1. She breaks her telephone number up into two parts a = 555, b = 629, and sends 2 messages ā€“ ā€œA=555ā€ and ā€œB=629ā€ ā€“ to Bob.
  2. She constructs a linear function, f(i) = a + (b-a)(i-1), in this case f(i) = 555 + 74(i-1), such that f(1) = 555 and f(2) = 629.

Code d'effacement optimal 1.gif

  1. She computes the values f (3), f (4), and f (5), and then transmits three redundant messages: ā€œC=703ā€, ā€œD=777ā€ and ā€œE=851ā€.

Bob knows that the form of f ( k ) is f(i) = a + (b-a)(i-1), where a and b are the two parts of the telephone number. Now suppose Bob receives ā€œD=777ā€ and ā€œE=851ā€.

Code d'effacement optimal 2.gif

Bob can reconstruct Aliceā€™s phone number by computing the values of a and b from the values ( f (4) and f (5)) he has received. Bob can perform this procedure using any two err-mails, so the erasure code in this example has a rate of 40%.

The key point is that in order to transmit (in our case store) the information data has been created that is not the information but can be used to reconstruct the information.

Note that none of the fragments Alice sent:-
C=703", ā€œD=777ā€ and ā€œE=851ā€

are the actual information - her actual phone number:-
555629

or even contain any of the same data!

The downside is that more data has to be transmitted or stored to guarantee the integrity of the information.

I work in IT and have to explain object storage which uses erasure codes to protect data rather than RAID. In fact, RAID is a subset of erasure coding apparently. If you do the mathsā€¦

And talking of doing the maths - constructing this synthetic data to store the information and then recreating the information from it uses needs more processing and takes longer than just storing it. And that is why it is slower and generally has to have a cache layer in front of it to get any kind of performance.

The attraction is that it is more space efficient than using RAID and definitely more space efficient than replication. When the data is being accessed across the internet the speed of reconstructing the information isnā€™t generally an issue.

14 Likes

But if Iā€™m understanding this correctly you arenā€™t actually reconstructing the information youā€™re just creating a map to where the information is located. Itā€™s like transmitting torn map fragments or gps coordinates to where the data is hidden in XOR space. And since SAFE stores everything ad infinitum itā€™s just a matter of pointing to the right file location in order to retrieve the data. So perhaps the confusion lies in that you arenā€™t actually having the end user reconstruct the file at all but rather the coordinates for the file location. Or am I again missing something?

1 Like