Changes between Version 4 and Version 5 of VolunteerDataArchival

Timestamp:

Nov 25, 2011, 12:45:03 AM (13 years ago)

Author:

davea

Comment:

--

VolunteerDataArchival

@@ -65 +65 @@
 required to maintain reliability.
 
+Also, note that data recovery uses network bandwidth.
+It's conceivable that the capacity of the system is limited
+not by client disk space, but by network bandwidth at the server.
+
 == Increasing reliability ==
 
@@ -108 +112 @@
 
  * Regenerating a chunk requires reassembling the entire file on the server,
-  defeating the purpose of distributed storage.
+  imposing a high storage and network communication overhead.
 
 == Hybrid reliability mechanisms ==
@@ -118 +122 @@
 === Multi-level coding ===
 
+One way to reduce the reconstruction overhead of coding
+is to divide the file into M parts, and encode each part separately.
+That way, if a packet is lost, only 1/M of the file needs to be reconstructed on the server.
+
+However, if one of these M parts is lost, the file is lost.
+To remedy this, we can use coding at the top level as well:
+in addition to the M parts, generate an additional K "checksum parts",
+and encode these parts in the same way.
+
+If we use this 2-level encoding scheme with parameters M=40 and N=20,
+we can recover from any 400 simultaneous host failures,
+with a space overhead of 125%.
+
+The scheme can be extended to any number of levels of encoding.
+
 === Coding plus replication ===
 
+To achieve high reliability, we need to use fairly large values of coding's N and K parameters,
+like 10-50.
+This means that recovering from a packet loss requires uploading and downloading
+10-50 packets, which is a large overhead.
+
+We can potentially use replication at the bottom level to reduce this overhead.
+Suppose, for example, that we use 2-fold replication for the bottom-level
+packets of multi-level encoding.
+Then, in many (and maybe even almost all) cases
+we'll just have to do 1 upload and 2 download to restore the packet.
+Although this doubles the client storage requirement,
+it could potentially increase system capacity
+by reducing network bandwidth at the server.
+
 == The VDAB simulator ==
+
+We have developed a simulator for VDAB.
+The simulator models a set of hosts.
+The parameters of the host population include:
+
+ * Arrival rate of hosts
+ * Distribution of host lifetimes (currently exponential, with adjustable mean)
+ * Distribution of upload and download network bandwidth
+ * Distribution of amount of free disk space
+
+The simulator models the arrival of one or more files,
+each with a given size.
+
+The simulator is able to model the following storage policies:
+
+ * M-level coding
+ * Different values of N and K at each level of coding
+ * R-fold replication at the bottom level
+
+The simulator outputs:
+ * statistics of server disk space usage
+ * statistics of network bandwidth usage
+ * statistics of "vulnerability": how many host failures would be needed
+   to cause the loss of each file.