Recently, after having written many articles, many concerned readers commented that they were worried about the issue of data loss when using decentralized storage. After I store the data in the decentralized system, they explained, although it’s cheaper, faster, and more private, the data is stored in miners’ machines, and therefore, due to the instability of the miners, the file may be lost. Just like Uber drivers, most of the time they are reliable, but occasionally they are not reliable. When this occurs, the Uber experience is highly unsatisfactory, and therefore, I am not willing to use such unreliable products. I am willing to use services provided by large companies, however, such as AWS S3, Microsoft Axure, and Google Cloud, because they have professional computer rooms, professional machines, and professional hard drives, and they are able to ensure that data is not lost.
In reality, the above understanding is not correct. Back when I was designing PP.io, I already considered this issue, so I decided to write this article to address this question.
To start out, I would like to correct a few common misperceptions:
- First of all, can companies like AWS S3 actually guarantee that 100% of the files are not lost? No, they cannot. They can only guarantee that 99.999999999% of the files are not lost, with 11 nines. The storage industry calls this Quality of Service (QoS) parameter “durability”.
- Secondly, although the individual miners may indeed be unstable, the core technology of P2P is to achieve stable services by using multiple nodes. For example, PPTV, the P2P live broadcast platform I developed, is a stable service completed on multiple unstable nodes.
Let me explain in detail how PP.io can maintain such high durability.
The 2 redundancy modes of PP.io
When designing PP.io, I designed two redundancy modes:
- Full copy mode
The full copy mode is to copy the file completely; the new file is the same as the old file. It does not save space, but P2P can download data more quickly. Doing so can improve the user’s download experience. - Erasure mode
The erasure mode is to do redundancy through the erasure technique. Simply put, the data is fragmented and encoded, using a configurable number of redundant erasure shares, and different erasure shares store on different miners. Although this is not conducive to the multi-point transmission of P2P, it can significantly save space.
PP.io is a combination of these two redundancy modes. Different scenarios emphasize the use of different redundancy methods.
Below I briefly talk about the mathematical characteristics of the erasure technique:
We use (k,n) erasure codes to encode data, in which there are a total of n erasure shares, and k indicates that in n erasure shares, any k erasure segments can completely recover the original data. If the data size is s bytes, the size of each erasure shares is approximately s/k bytes. If k = 1, it is equivalent to copying a full copy. For example, 1 MB of data, if (10, 16) erasure codes used, each erasure share size is 0.1 M, the total storage data size is 1.6 M. It uses a total of 1.6 times the size of the data space.
PP.io assumptions and calculations
PP.io assumes the following:
Let t represent an unit of time; here we assume t=24 hours.
Pt represents the daily drop rate of the miners; here we assume Pt = 5%. In other words, 5% of the copies may go offline every day.
τ is the repair time after the copy lost, that is, if the copy is lost, how much time does it take for it to be fixed. We assume τ = 2 hours.
If it is considered to be repairable, the above values will be included in the following formula, and the actual probability of loss per day will be calculated. This is p:
p = 1 — (1-Pt)^(τ/t) = 0.4265318778%
PP.io is designed so that the default full copy number redundancy is 2 times, and the erasure copy redundancy is 1.5 times.
Let’s first look at the full copy mode:
Since full copy refers to complete duplication, therefore the number redundancy of 2 times means that there are 2 copies. We call it N=2.
Durability during repair time is: Pa = 1- p² = 99.9981807056%
Annual durability is Pya = Pa^(365*t/τ) = 92.3406415922%
Let us now look at the erasure mode:
Suppose we define the erasure algorithm as (k,n)= (6,9). The 6 refers to 6M data where each erasure share is 1M. total of 9 erasure shares must be stored, and any 6 erasure shares can recover the complete data. This means that the data is stored in 9 miners, and the actual amount of space used is 9M. Once you have understood this, let us move one to the next part of the calculations..
Since the erasure algorithm is (k,n), the redundancy is F = n/k = 1.5.
The number of erasure shares lost during the repair time is m = n*p = 0.038387869 and is the known number of occurrences.
Here I explain the classic formula in probability theory, the Poisson distribution fitting formula:
Simply put, the Poisson distribution fitting formula is the probability that something occurs x times under the condition that its average occurrence is m times. To understand the details of how this formula is obtained, please refer to the final appendix.
Applying the Poisson distribution fitting formula, we can find:
Durability during repair time:
That is, Pb = 99.9999912252%
This means that the annual durability is: Pyb = Pb^(365*t/τ) = 99.9615738663%
It can be seen that, although the redundancy is smaller, the durability of the erasure mode is much higher than that of the full copy mode.
Calculation summary:
We combine the two redundancy modes to get the ultimate durability:
Durability during repair time: P = 1 — (1-Pa)(1-Pb) = 99.9999999998%
Annual durability: Py = P^(365*t/τ) = 99.9999993008%
We can see that the durability ratio has already reached 8 nines. In other words, if you store 100 million files, you only lose 1 file a year. Would you not say that is reliable?
It can be increased
The above assumption is based on the erasure elimination algorithm (k, n) = (6, 9) with the redundancy calculated as F =1.5. If the redundancy F is increased appropriately, or the k is increased appropriately, the annual durability Py can be significantly improved. The following table shows the effect that adjusting k and F has on the resulting annual durability. Here we used a new hypothesis in which there is no full copy at all, only the erasure shares. In doing so, we do not pursue speed, we simply pursue the lowest price. This means that Py is equal to Pyb, as demonstrated below.
We can see that the higher the redundancy F, the higher the durability. At the same time, the higher the number of erasure shares n, the higher the durability. n is more sensitive to the effects of durability, but the larger the n, the more miners are needed as well.
We can also see that in order to pursue 99.9999999999 (12 nines), the erasure mode is adopted, and in the case of a redundancy of 2, it can be done by dividing the copied data into 16 erasure shares. Similarly, in the case of a redundancy of 2.5, it can be done by dividing the copied data into 12 erasure shares. This exceeds the annual durability of the AWS S3 enterprise storage service (which has an accuracy of 11 nines).
It can be increased even more
In addition to adjusting the parameters of N, (k, n), and F to improve durability, you can also use manual optimization efforts. In fact, there is still significant improvement that can be made. As mentioned earlier, this calculation is based on two assumptions, and these two assumptions can still be significantly improved.
The daily loss rate of a single copy, Pt, I have assumed is 5%. This assumption itself can be reduced by the design of the token economic system. A more rational economic system can improve the stability and online rate of miners. The more stable the miner is, the lower the value of Pt; the lower the value Pt, the higher the annual durability. This value is expected to drop to 1% or even lower.
The repair time after the copy lost τ, I have assumed to be 2 hours. This assumption can also be optimized by the PP.io algorithm. If a copy is lost, as long as it can be detected and repaired more quickly to ensure that the number of copies is sufficient, the value of τ will be lower; the lower the value of τ, the higher the annual durability. If the algorithm is at its best, this value is expected to drop to 15 minutes.
Assume that the limit value Pt=1%, τ=0.25 hours, (k,n)=(6,9), F=1.5
Then: Pyb = 99.9999998852%
If you consider 2 full copy redundancy, the annual durability rate is Py = 99.9999999999% (12 nines).
PP.io will give developers the flexibility to set parameters
When designing the PP.io architecture, I gave the developer enough flexibility to set different parameters according to their conditions, including the full copy number N, and erasure algorithm parameters (k, n).
Developers can configure parameters based on their own needs, such as transmission speed, price (higher redundancy equals higher price), and acceptable durability to meet their product requirements.
PP.io provides developers with decentralized data storage and delivery platform that has greater affordability, speed, and privacy.
Appendix: Derivation of Poisson Distribution Fitting Formula
Assuming that p is the failure rate of a single device per unit time, the probability of a device f failure in n units per unit time is P(k)
Expand combination
Suppose p is small and n is large, generally when n > 20, p < 0.05
Let
Finally, the Poisson distribution formula is obtained, that is, there is an average of λ equipment failures per unit time, and the probability of having k equipment failures per unit time is calculated.
Reference:
- https://www.scality.com/blog/durability-availability-managing-fragile-scarce/
- Hakim Weatherspoon and John D. Kubiatowicz, Erasure Coding vs. Replication: A Quantitative Comparison.
- Byung-Gon Chun, Frank Dabek, Andreas Haeberlen, Emil Sit, Hakim Weatherspoon, M. Frans Kaashoek, John Kubiatowicz, and Robert Morris, Efficient Replica Maintenance for Distributed Storage Systems.
Wayne Wong