addfile ./docs/lossmodel.lyx hunk ./docs/lossmodel.lyx 1 +#LyX 1.6.1 created this file. For more info see http://www.lyx.org/ +\lyxformat 345 +\begin_document +\begin_header +\textclass amsart +\use_default_options true +\begin_modules +theorems-ams +theorems-ams-extended +\end_modules +\language english +\inputencoding auto +\font_roman default +\font_sans default +\font_typewriter default +\font_default_family default +\font_sc false +\font_osf false +\font_sf_scale 100 +\font_tt_scale 100 + +\graphics default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_amsmath 1 +\use_esint 1 +\cite_engine basic +\use_bibtopic false +\paperorientation portrait +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\defskip medskip +\quotes_language english +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\author "" +\author "" +\end_header + +\begin_body + +\begin_layout Title +Tahoe Distributed Filesharing System Loss Model +\end_layout + +\begin_layout Author +Shawn Willden +\end_layout + +\begin_layout Email +shawn@willden.org +\end_layout + +\begin_layout Abstract +The abstract goes here +\end_layout + +\begin_layout Section +Problem Statement +\end_layout + +\begin_layout Standard +The allmydata Tahoe distributed file system uses Reed-Solomon erasure coding + to split files into +\begin_inset Formula $N$ +\end_inset + + shares, each of which is then delivered to a randomly-selected peer in + a distributed network. + The file can later be reassembled from any +\begin_inset Formula $k\leq N$ +\end_inset + + of the shares, if they are available. +\end_layout + +\begin_layout Standard +Over time shares are lost for a variety of reasons. + Storage servers may crash, be destroyed or simply be removed from the network. + To mitigate such losses, Tahoe network clients employ a repair agent which + scans the peers once per time period +\begin_inset Formula $A$ +\end_inset + + and determines how many of the shares remain. + If less than +\begin_inset Formula $R$ +\end_inset + + ( +\begin_inset Formula $k\leq R\leq N$ +\end_inset + +) shares remain, then the repairer reconstructs the file shares and redistribute +s the missing ones, bringing the availability back up to full. +\end_layout + +\begin_layout Standard +The question we're trying to answer is "What's the probability that we'll + be able to reassemble the file at some later time +\begin_inset Formula $T$ +\end_inset + +?". + We'd also like to be able to determine what values we should choose for + +\begin_inset Formula $k$ +\end_inset + +, +\begin_inset Formula $N$ +\end_inset + +, +\begin_inset Formula $A$ +\end_inset + +, and +\begin_inset Formula $R$ +\end_inset + + in order to ensure +\begin_inset Formula $Pr[loss]\leq t$ +\end_inset + + for some threshold probability +\begin_inset Formula $t$ +\end_inset + +. + This is an optimization problem because although we could obtain very low + +\begin_inset Formula $Pr[loss]$ +\end_inset + + by choosing small +\begin_inset Formula $k,$ +\end_inset + + large +\begin_inset Formula $N$ +\end_inset + +, small +\begin_inset Formula $A$ +\end_inset + +, and setting +\begin_inset Formula $R=N$ +\end_inset + +, these choices have costs. + The peer storage and bandwidth consumed by the share distribution process + are approximately +\begin_inset Formula $\nicefrac{N}{k}$ +\end_inset + + times the size of the original file, so we would like to reduce this ratio + as far as possible consistent with +\begin_inset Formula $Pr[loss]\leq t$ +\end_inset + +. + Likewise, frequent and aggressive repair process can be used to ensure + that the number of shares available at any time is very close to +\begin_inset Formula $N,$ +\end_inset + + but at a cost in bandwidth. +\end_layout + +\begin_layout Section +Reliability +\end_layout + +\begin_layout Standard +The probability that the file becomes unrecoverable is dependent upon the + probability that the peers to whom we send shares are able to return those + copies on demand. + Shares that are returned in corrupted form can be detected and discarded, + so there is no need to distinguish between corruption and loss. +\end_layout + +\begin_layout Standard +There are a large number of factors that affect share availability. + Availability can be temporarily interrupted by peer unavailability, due + to network outages, power failures or administrative shutdown, among other + reasons. + Availability can be permanently lost due to failure or corruption of storage + media, catastrophic damage to the peer system, administrative error, withdrawal + from the network, malicious corruption, etc. +\end_layout + +\begin_layout Standard +The existence of intermittent failure modes motivates the introduction of + a distinction between +\noun on +availability +\noun default + and +\noun on +reliability +\noun default +. + Reliability is the probability that a share is retrievable assuming intermitten +t failures can be waited out, so reliability considers only permanent failures. + Availability considers all failures, and is focused on the probability + of retrieval within some defined time frame. +\end_layout + +\begin_layout Standard +Another consideration is that some failures affect multiple shares. + If multiple shares of a file are stored on a single hard drive, for example, + failure of that drive may lose them all. + Catastrophic damage to a data center may destroy all shares on all peers + in that data center. +\end_layout + +\begin_layout Standard +While the types of failures that may occur are pretty consistent across + even very different peers, their probabilities differ dramatically. + A professionally-administered blade server with redundant storage, power + and Internet located in a carefully-monitored data center with automatic + fire suppression systems is much less likely to become either temporarily + or permanently unavailable than the typical virus and malware-ridden home + computer on a single cable modem connection. + A variety of situations in between exist as well, such as the case of the + author's home file server, which is administered by an IT professional + and uses RAID level 6 redundant storage, but runs on old, cobbled-together + equipment, and has a consumer-grade Internet connection. +\end_layout + +\begin_layout Standard +To begin with, let's use a simple definition of reliability: +\end_layout + +\begin_layout Definition + +\noun on +Reliability +\noun default + is the probability +\begin_inset Formula $p_{i}$ +\end_inset + + that a share +\begin_inset Formula $s_{i}$ +\end_inset + + will surve to (be retrievable at) time +\begin_inset Formula $T=A$ +\end_inset + +, ignoring intermittent failures. + That is, the probability that the share will be retrievable at the end + of the current repair cycle, and therefore usable by the repairer to regenerate + any lost shares. +\end_layout + +\begin_layout Definition +Reliability is clearly dependent on +\begin_inset Formula $A$ +\end_inset + +. + Short repair cycles offer less time for shares to +\begin_inset Quotes eld +\end_inset + +decay +\begin_inset Quotes erd +\end_inset + + into unavailability. +\end_layout + +\begin_layout Subsection +Fixed Reliability +\end_layout + +\begin_layout Standard +In the simplest case, the peers holding the file shares all have the same + reliability +\begin_inset Formula $p$ +\end_inset + +, and are all independent from one another. + Let +\begin_inset Formula $K$ +\end_inset + + be a random variable that represents the number of shares that survive + +\begin_inset Formula $A$ +\end_inset + +. + Each share's survival can be viewed as an indepedent Bernoulli trial with + a succes probability of +\begin_inset Formula $p$ +\end_inset + +, which means that +\begin_inset Formula $K$ +\end_inset + + follows the binomial distribution with paramaters +\begin_inset Formula $N$ +\end_inset + + and +\begin_inset Formula $p$ +\end_inset + + ( +\begin_inset Formula $K\sim B(N,p)$ +\end_inset + +). + The probability mass function (PMF) of the binomial distribution is: +\begin_inset Formula \begin{equation} +Pr(K=i)=f(i;N,p)=\binom{n}{i}p^{i}(1-p)^{n-i}\label{eq:binomial-pdf}\end{equation} + +\end_inset + + +\end_layout + +\begin_layout Standard +A file survives if at least +\begin_inset Formula $k$ +\end_inset + + of the +\begin_inset Formula $N$ +\end_inset + + shares survive. + Equation +\begin_inset CommandInset ref +LatexCommand ref +reference "eq:binomial-pdf" + +\end_inset + + gives the probability that exactly +\begin_inset Formula $i$ +\end_inset + + shares survive, so the probability that fewer than +\begin_inset Formula $k$ +\end_inset + + survive is the sum of the probabilities that +\begin_inset Formula $0,1,2,\ldots,k-1$ +\end_inset + + shares survive. + That is: +\end_layout + +\begin_layout Standard +\begin_inset Formula \begin{equation} +Pr[failure]=\sum_{i=0}^{k-1}\binom{n}{i}p^{i}(1-p)^{n-i}\label{eq:simple-failure}\end{equation} + +\end_inset + + +\end_layout + +\begin_layout Subsection +Independent Reliability +\end_layout + +\begin_layout Standard +Equation +\begin_inset CommandInset ref +LatexCommand ref +reference "eq:simple-failure" + +\end_inset + + assumes that each share has the same probability of survival, but as explained + above, this is not typically true. + A more accurate model allows each share +\begin_inset Formula $s_{i}$ +\end_inset + + an independent probability of survival +\begin_inset Formula $p_{i}$ +\end_inset + +. + Each share's survival can still be treated as an independent Bernoulli + trial, but with success probability +\begin_inset Formula $p_{i}$ +\end_inset + +. + Under this assumption, +\begin_inset Formula $K$ +\end_inset + + follows a generalized distribution with parameters +\begin_inset Formula $N$ +\end_inset + + and +\begin_inset Formula $p_{i},1\leq i\leq N$ +\end_inset + +. +\end_layout + +\begin_layout Standard +The PMF for this generalized +\begin_inset Formula $K$ +\end_inset + + does not have a simple closed-form representation. + However, the PMFs for random variables representing individual share survival + do. + Let +\begin_inset Formula $S_{i}$ +\end_inset + + be a random variable such that: +\end_layout + +\begin_layout Standard +\begin_inset Formula \[ +S_{i}=\begin{cases} +1 & \textnormal{if }s_{i}\textnormal{ survives}\\ +0 & \textnormal{if }s_{i}\textnormal{ fails}\end{cases}\] + +\end_inset + + +\end_layout + +\begin_layout Standard +The PMF for +\begin_inset Formula $Si$ +\end_inset + + is very simple, +\begin_inset Formula $Pr(S_{i}=1)=p_{i}$ +\end_inset + + and +\begin_inset Formula $Pr(S_{i}=0)=p_{i}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Observe that +\begin_inset Formula $\sum_{i=1}^{N}S_{i}=K$ +\end_inset + +. + Effectively, +\begin_inset Formula $K$ +\end_inset + + has just been separated into the series of Bernoulli trials that make it + up. +\end_layout + +\begin_layout Standard +The discrete convolution theorem states that given random variables +\begin_inset Formula $X$ +\end_inset + + and +\begin_inset Formula $Y$ +\end_inset + + and their sum +\begin_inset Formula $Z=X+Y$ +\end_inset + +, if +\begin_inset Formula $Pr[X=x]=f(x)$ +\end_inset + + and +\begin_inset Formula $Pr[Y=y]=f(y)$ +\end_inset + + then +\begin_inset Formula $Pr[Z=z]=(f\star g)(z)$ +\end_inset + + where +\begin_inset Formula $\star$ +\end_inset + + denotes the convolution operation. + Stated in English, the probability mass function of the sum of two random + variables is the convolution of the probability mass functions of the two + random variables. +\end_layout + +\begin_layout Standard +Discrete convolution is defined as +\end_layout + +\begin_layout Standard +\begin_inset Formula \[ +(f\star g)(n)=\sum_{m=-\infty}^{\infty}f(m)\cdot g(n-m)\] + +\end_inset + + +\end_layout + +\begin_layout Standard +The infinite summation is no problem because the probability mass functions + we need to convolve are zero outside of a small range. +\end_layout + +\begin_layout Standard +According to the discrete convolution theorem, then, if +\begin_inset Formula $Pr[K=i]=f(i)$ +\end_inset + + and +\begin_inset Formula $Pr[S_{i}=j]=g_{i}(j)$ +\end_inset + +, then +\begin_inset Formula $ $ +\end_inset + + +\begin_inset Formula $f=g_{1}\star g_{2}\star g_{3}\star\ldots\star g_{N}$ +\end_inset + +. + Since convolution is associative, this can also be written as +\begin_inset Formula $ $ +\end_inset + + +\begin_inset Formula \begin{equation} +f=(g_{1}\star g_{2})\star g_{3})\star\ldots)\star g_{N})\label{eq:convolution}\end{equation} + +\end_inset + +which enables +\begin_inset Formula $f$ +\end_inset + + to be implemented as a sequence of convolution operations on the simple + PMFs of the random variables +\begin_inset Formula $S_{i}$ +\end_inset + +. + In fact, as values of +\begin_inset Formula $N$ +\end_inset + + get large, equation +\begin_inset CommandInset ref +LatexCommand ref +reference "eq:convolution" + +\end_inset + + turns out to be a more effective means of computing the PMF of +\begin_inset Formula $K$ +\end_inset + + even in the case of the standard bernoulli distribution, primarily because + the binomial calculation in equation +\begin_inset CommandInset ref +LatexCommand ref +reference "eq:binomial-pdf" + +\end_inset + + produces very large values that overflow unless arbitrary precision numeric + representations are used, or unless the binomial calculation is very cleverly + interleaved with the powers of +\begin_inset Formula $p$ +\end_inset + + and +\begin_inset Formula $1-p$ +\end_inset + + to keep the values manageable. +\end_layout + +\begin_layout Standard +Note also that it is not necessary to have very simple PMFs like those of + the +\begin_inset Formula $S_{i}$ +\end_inset + +. + Any share or set of shares that has a known PMF can be combined with any + other set with a known PMF by convolution, as long as the two share sets + are independent. + Since PMFs are easily represented as simple lists of probabilities, where + the +\begin_inset Formula $i$ +\end_inset + +th element in the list corresponds to +\begin_inset Formula $Pr[K=i]$ +\end_inset + +, these functions are easily managed in software, and computing the convolution + is both simple and efficient. +\end_layout + +\begin_layout Subsection +Multiple Failure Modes +\end_layout + +\begin_layout Standard +In modeling share survival probabilities, it's useful to be able to analyze + separately each of the various failure modes. + If reliable statistics for disk failure can be obtained, then a probability + mass function for that form of failure can be generated. + Similarly, statistics on other hardware failures, administrative errors, + network losses, etc., can all be estimated independently. + If those estimates can then be combined into a single PMF for that server, + then we can use it to predict failures for that server. +\end_layout + +\begin_layout Standard +In the case of independent failure modes for a single server, this is very + simple to do. + If +\begin_inset Formula $p_{i,j}$ +\end_inset + + is the probability of survival of the +\begin_inset Formula $j$ +\end_inset + +th failure mode of server +\begin_inset Formula $i$ +\end_inset + +, and there are +\begin_inset Formula $m$ +\end_inset + + failure modes then +\begin_inset Formula \[ +p_{i}=\prod_{j=1}^{m}p_{i,j}\] + +\end_inset + + is the probability of server +\begin_inset Formula $i$ +\end_inset + +'s survival and +\begin_inset Formula \[ +Pr[S_{i}=k]=f(k)=\begin{cases} +1-p_{i} & k=0\\ +p_{i} & k=1\end{cases}\] + +\end_inset + + is the full survival PMF. +\end_layout + +\begin_layout Standard + +\end_layout + +\end_body +\end_document hunk ./src/allmydata/test/test_util.py 4 -import os, time +import os, time, random hunk ./src/allmydata/test/test_util.py 12 +from allmydata.util import statistics hunk ./src/allmydata/test/test_util.py 167 + def test_round_sigfigs(self): + f = mathutil.round_sigfigs + self.failUnlessEqual(f(22.0/3, 4), 7.3330000000000002) + +class Statistics(unittest.TestCase): + def should_assert(self, msg, func, *args, **kwargs): + try: + func(*args, **kwargs) + self.fail(msg) + except AssertionError, e: + pass + + def failUnlessListEqual(self, a, b, msg = None): + self.failUnlessEqual(len(a), len(b)) + for i in range(len(a)): + self.failUnlessEqual(a[i], b[i], msg) + + def failUnlessListAlmostEqual(self, a, b, places = 7, msg = None): + self.failUnlessEqual(len(a), len(b)) + for i in range(len(a)): + self.failUnlessAlmostEqual(a[i], b[i], places, msg) + + def test_binomial_coeff(self): + f = statistics.binomial_coeff + self.failUnlessEqual(f(20, 0), 1) + self.failUnlessEqual(f(20, 1), 20) + self.failUnlessEqual(f(20, 2), 190) + self.failUnlessEqual(f(20, 8), f(20, 12)) + self.should_assert("Should assert if n < k", f, 2, 3) + + def test_binomial_distribution_pmf(self): + f = statistics.binomial_distribution_pmf + + pmf_comp = f(2, .1) + pmf_stat = [0.81, 0.18, 0.01] + self.failUnlessListAlmostEqual(pmf_comp, pmf_stat) + + # Summing across a PMF should give the total probability 1 + self.failUnlessAlmostEqual(sum(pmf_comp), 1) + self.should_assert("Should assert if not 0<=p<=1", f, 1, -1) + self.should_assert("Should assert if n < 1", f, 0, .1) + + def test_survival_pmf(self): + f = statistics.survival_pmf + # Cross-check binomial-distribution method against convolution + # method. + p_list = [.9999] * 100 + [.99] * 50 + [.8] * 20 + pmf1 = statistics.survival_pmf_via_conv(p_list) + pmf2 = statistics.survival_pmf_via_bd(p_list) + self.failUnlessListAlmostEqual(pmf1, pmf2) + self.failUnlessTrue(statistics.valid_pmf(pmf1)) + self.should_assert("Should assert if p_i > 1", f, [1.1]); + self.should_assert("Should assert if p_i < 0", f, [-.1]); + + + def test_convolve(self): + f = statistics.convolve + v1 = [ 1, 2, 3 ] + v2 = [ 4, 5, 6 ] + v3 = [ 7, 8 ] + v1v2result = [ 4, 13, 28, 27, 18 ] + # Convolution is commutative + r1 = f(v1, v2) + r2 = f(v2, v1) + self.failUnlessListEqual(r1, r2, "Convolution should be commutative") + self.failUnlessListEqual(r1, v1v2result, "Didn't match known result") + # Convolution is associative + r1 = f(f(v1, v2), v3) + r2 = f(v1, f(v2, v3)) + self.failUnlessListEqual(r1, r2, "Convolution should be associative") + # Convolution is distributive + r1 = f(v3, [ a + b for a, b in zip(v1, v2) ]) + tmp1 = f(v3, v1) + tmp2 = f(v3, v2) + r2 = [ a + b for a, b in zip(tmp1, tmp2) ] + self.failUnlessListEqual(r1, r2, "Convolution should be distributive") + # Convolution is scalar multiplication associative + tmp1 = f(v1, v2) + r1 = [ a * 4 for a in tmp1 ] + tmp2 = [ a * 4 for a in v1 ] + r2 = f(tmp2, v2) + self.failUnlessListEqual(r1, r2, "Convolution should be scalar multiplication associative") + + def test_find_k(self): + f = statistics.find_k + g = statistics.pr_file_loss + plist = [.9] * 10 + [.8] * 10 + t = .0001 + k = f(plist, t) + self.failUnlessEqual(k, 10) + self.failUnless(g(plist, k) < t) + + def test_pr_file_loss(self): + f = statistics.pr_file_loss + plist = [.5] * 10 + self.failUnlessEqual(f(plist, 3), .0546875) + + def test_pr_backup_file_loss(self): + f = statistics.pr_backup_file_loss + plist = [.5] * 10 + self.failUnlessEqual(f(plist, .5, 3), .02734375) + hunk ./src/allmydata/util/mathutil.py 77 +def round_sigfigs(f, n): + fmt = "%." + str(n-1) + "e" + return float(fmt % f) + addfile ./src/allmydata/util/statistics.py hunk ./src/allmydata/util/statistics.py 1 +# Copyright (c) 2009 Shawn Willden +# mailto:shawn@willden.org + +from __future__ import division +from mathutil import round_sigfigs +import math +import array + +def pr_file_loss(p_list, k): + """ + Probability of single-file loss for shares with reliabilities in + p_list. + + Computes the probability that a single file will become + unrecoverable, based on the individual share survival + probabilities and and k (number of shares needed for recovery). + + Example: pr_file_loss([.9] * 5 + [.99] * 5, 3) returns the + probability that a file with k=3, N=10 and stored on five servers + with reliability .9 and five servers with reliability .99 is lost. + + See survival_pmf docstring for important statistical assumptions. + + """ + assert 0 < k <= len(p_list) + assert valid_probability_list(p_list) + + # Sum elements 0 through k-1 of the share set PMF to get the + # probability that less than k shares survived. + return sum(survival_pmf(p_list)[0:k]) + +def survival_pmf(p_list): + """ + Return the collective PMF of share survival count for a set of + shares with the individual survival probabilities in p_list. + + Example: survival_pmf([.99] * 10 + [.8] * 6) returns the + probability mass function for the number of shares that will + survive from an initial set of 16, 10 with p=0.99 and 6 with + p=0.8. The ith element of the resulting list is the probability + that exactly i shares will survive. + + This calculation makes the following assumptions: + + 1. p_list[i] is the probability that any individual share will + will survive during the time period in question (whatever that may + be). + + 2. The share failures are "independent", in the statistical + sense. Note that if a group of shares are stored on the same + machine or even in the same data center, they are NOT independent + and this calculation is therefore wrong. + """ + assert valid_probability_list(p_list) + + pmf = survival_pmf_via_conv(p_list) + + assert valid_pmf(pmf) + return pmf + +def survival_pmf_via_bd(p_list): + """ + Compute share survival PMF using the binomial distribution PMF as + much as possible. + + This is more efficient than the convolution method below, but + doesn't work for large numbers of shares because the + binomial_coeff calculation blows up. Since the efficiency gains + only matter in the case of large numbers of shares, it's pretty + much useless except for testing the convolution methond. + + Note that this function does little to no error checking and is + intended for internal use and testing only. + """ + pmf_list = [ binomial_distribution_pmf(p_list.count(p), p) + for p in set(p_list) ] + return reduce(convolve, pmf_list) + +def survival_pmf_via_conv(p_list): + """ + Compute share survival PMF using iterated convolution of trivial + PMFs. + + Note that this function does little to no error checking and is + intended for internal use and testing only. + """ + pmf_list = [ [1 - p, p] for p in p_list ]; + return reduce(convolve, pmf_list) + +def print_pmf(pmf, n): + """ + Print a PMF in a readable form, with values rounded to n + significant digits. + """ + for k, p in enumerate(pmf): + print "i=" + str(k) + ":", round_sigfigs(p, n) + +def pr_backup_file_loss(p_list, backup_p, k): + """ + Probability of single-file loss in a backup context + + Same as pr_file_loss, except it factors in the probability of + survival of the original source, specified as backup_p. Because + that's a precondition to caring about the availability of the + backup, it's an independent event. + """ + assert valid_probability_list(p_list) + assert 0 < backup_p <= 1 + assert 0 < k <= len(p_list) + + return pr_file_loss(p_list, k) * (1 - backup_p) + + +def find_k(p_list, target_loss_prob): + """ + Find the highest k value that achieves the targeted loss + probability, given the share reliabilities given in p_list. + """ + assert valid_probability_list(p_list) + assert 0 < target_loss_prob < 1 + + pmf = survival_pmf(p_list) + return find_k_from_pmf(pmf, target_loss_prob) + +def find_k_from_pmf(pmf, target_loss_prob): + """ + Find the highest k value that achieves the targeted loss + probability, given the share survival PMF given in pmf. + """ + assert valid_pmf(pmf) + assert 0 < target_loss_prob < 1 + + loss_prob = 0.0 + for k, p_k in enumerate(pmf): + loss_prob += p_k + if loss_prob > target_loss_prob: + return k + + k = len(pmf) - 1 + return k + +def valid_pmf(pmf): + """ + Validate that pmf looks like a proper discrete probability mass + function in list form. + + Returns true if the elements of pmf sum to 1. + """ + return round(sum(pmf),5) == 1.0 + +def valid_probability_list(p_list): + """ + Validate that p_list is a list of probibilities + """ + for p in p_list: + if p < 0 or p > 1: + return False + + return True + +def convolve(list_a, list_b): + """ + Returns the discrete convolution of two lists. + + Given two random variables X and Y, the convolution of their + probability mass functions Pr(X) and Pr(Y) is equal to the + Pr(X+Y). + """ + n = len(list_a) + m = len(list_b) + + result = [] + for i in range(n + m - 1): + sum = 0.0 + + lower = max(0, i - n + 1) + upper = min(m - 1, i) + + for j in range(lower, upper+1): + sum += list_a[i-j] * list_b[j] + + result.append(sum) + + return result + +def binomial_distribution_pmf(n, p): + """ + Returns Pr(K), where K ~ B(n,p), as a list of values. + + Returns the full probability mass function of a B(n, p) as a list + of values, where the kth element is Pr(K=k), or, in the Tahoe + context, the probability that exactly k copies of a file share + survive, when placed on n independent servers with survival + probability p. + """ + assert p >= 0 and p <= 1, 'p=%s must be in the range [0,1]'%p + assert n > 0 + + result = [] + for k in range(n+1): + result.append(math.pow(p , k ) * + math.pow(1 - p, n - k) * + binomial_coeff(n, k)) + + assert valid_pmf(result) + return result; + +def binomial_coeff(n, k): + """ + Returns the number of ways that k items can be chosen from a set + of n. + """ + assert n >= k + + if k > n: + return 0 + + if k > n/2: + k = n - k + + accum = 1.0 + for i in range(1, k+1): + accum = accum * (n - k + i) // i; + + return int(accum + 0.5) hunk ./docs/lossmodel.lyx 23 +\float_placement h hunk ./docs/lossmodel.lyx 58 +\begin_layout Date +01/14/2009 +\end_layout + +\begin_layout Address +South Weber, Utah +\end_layout + hunk ./docs/lossmodel.lyx 103 -\begin_inset Formula $R$ +\begin_inset Formula $L$ hunk ./docs/lossmodel.lyx 107 -\begin_inset Formula $k\leq R\leq N$ +\begin_inset Formula $k\leq L\leq N$ hunk ./docs/lossmodel.lyx 135 -\begin_inset Formula $R$ +\begin_inset Formula $L$ hunk ./docs/lossmodel.lyx 165 -\begin_inset Formula $R=N$ +\begin_inset Formula $L=N$ hunk ./docs/lossmodel.lyx 185 - but at a cost in bandwidth. + but at a cost in bandwidth as the repair agent downloads +\begin_inset Formula $k$ +\end_inset + + shares to reconstruct the file and uploads new shares to replace those + that are lost. hunk ./docs/lossmodel.lyx 300 +\begin_inset CommandInset label +LatexCommand label +name "sub:Fixed-Reliability" + +\end_inset + + hunk ./docs/lossmodel.lyx 343 - ( +. + That is, hunk ./docs/lossmodel.lyx 348 -). - The probability mass function (PMF) of the binomial distribution is: +. +\end_layout + +\begin_layout Theorem +Binomial Distribution Theorem +\end_layout + +\begin_layout Theorem +Consider +\begin_inset Formula $n$ +\end_inset + + independent Bernoulli trials +\begin_inset Foot +status collapsed + +\begin_layout Plain Layout +A Bernoulli trial is simply a test of some sort that results in one of two + outcomes, one of which is designated success and the other failure. + The classic example of a Bernoulli trial is a coin toss. +\end_layout + +\end_inset + + that succeed with probability +\begin_inset Formula $p$ +\end_inset + +, and let +\begin_inset Formula $K$ +\end_inset + + be a random variable that represents the number of successes. + We say that +\begin_inset Formula $K$ +\end_inset + + follows the Binomial Distribution with parameters n and p, denoted +\begin_inset Formula $K\sim B(n,p)$ +\end_inset + +. + The probability that +\begin_inset Formula $K$ +\end_inset + + takes a particular value +\begin_inset Formula $m$ +\end_inset + + (the probability that there are exactly +\begin_inset Formula $m$ +\end_inset + + successful trials, and therefore +\begin_inset Formula $n-m$ +\end_inset + + failures) is called the probability mass function and is given by: hunk ./docs/lossmodel.lyx 408 -Pr(K=i)=f(i;N,p)=\binom{n}{i}p^{i}(1-p)^{n-i}\label{eq:binomial-pdf}\end{equation} +Pr[K=m]=f(m;n,p)=\binom{n}{p}p^{m}(1-p)^{n-m}\label{eq:binomial-pmf}\end{equation} + +\end_inset + + +\end_layout + +\begin_layout Proof +Consider the specific case of exactly +\begin_inset Formula $m$ +\end_inset + + successes followed by +\begin_inset Formula $n-m$ +\end_inset hunk ./docs/lossmodel.lyx 424 + failures, because each success has probability +\begin_inset Formula $p$ hunk ./docs/lossmodel.lyx 428 +, each failure has probability +\begin_inset Formula $1-p$ +\end_inset + +, and the trials are independent, the probability of this exact case occurring + is +\begin_inset Formula $p^{m}\left(1-p\right)^{\left(n-m\right)}$ +\end_inset + +, the product of the probabilities of the outcome of each trial. +\end_layout + +\begin_layout Proof +Now consider any reordering of these +\begin_inset Formula $m$ +\end_inset + + successes and +\begin_inset Formula $n$ +\end_inset + + failures. + Any such reordering occurs with the same probability +\begin_inset Formula $p^{m}\left(1-p\right)^{\left(n-m\right)}$ +\end_inset + +, but with the terms of the product reordered. + Since multiplication is commutative, each such reordering has the same + probability. + There are n-choose-m such orderings, and each ordering is an independent + event, so the probability that any ordering of +\begin_inset Formula $m$ +\end_inset + + successes and +\begin_inset Formula $n-m$ +\end_inset + + failures occurs is given by +\begin_inset Formula \[ +\binom{n}{m}p^{m}\left(1-p\right)^{\left(n-m\right)}\] + +\end_inset + +which is the right-hand-side of equation +\begin_inset CommandInset ref +LatexCommand ref +reference "eq:binomial-pmf" + +\end_inset hunk ./docs/lossmodel.lyx 479 +. hunk ./docs/lossmodel.lyx 495 -reference "eq:binomial-pdf" +reference "eq:binomial-pmf" hunk ./docs/lossmodel.lyx 503 - shares survive, so the probability that fewer than + shares survive, for any +\begin_inset Formula $1\leq i\leq n$ +\end_inset + +, so the probability that fewer than hunk ./docs/lossmodel.lyx 521 -Pr[failure]=\sum_{i=0}^{k-1}\binom{n}{i}p^{i}(1-p)^{n-i}\label{eq:simple-failure}\end{equation} +Pr[file\, lost]=\sum_{i=0}^{k-1}\binom{n}{i}p^{i}(1-p)^{n-i}\label{eq:simple-failure}\end{equation} hunk ./docs/lossmodel.lyx 530 +\begin_inset CommandInset label +LatexCommand label +name "sub:Independent-Reliability" + +\end_inset + + hunk ./docs/lossmodel.lyx 548 - above, this is not typically true. + above, this is not necessarily true. hunk ./docs/lossmodel.lyx 568 - follows a generalized distribution with parameters + follows a generalized binomial distribution with parameters hunk ./docs/lossmodel.lyx 573 -\begin_inset Formula $p_{i},1\leq i\leq N$ +\begin_inset Formula $p_{i}$ +\end_inset + + where +\begin_inset Formula $1\leq i\leq N$ hunk ./docs/lossmodel.lyx 611 -\begin_inset Formula $Si$ +\begin_inset Formula $S_{i}$ hunk ./docs/lossmodel.lyx 614 - is very simple, -\begin_inset Formula $Pr(S_{i}=1)=p_{i}$ -\end_inset + is very simple: +\begin_inset Formula \[ +Pr[S_{i}=j]=\begin{cases} +1-p_{i} & j=0\\ +p_{i} & j=1\end{cases}\] hunk ./docs/lossmodel.lyx 620 - and -\begin_inset Formula $Pr(S_{i}=0)=p_{i}$ hunk ./docs/lossmodel.lyx 622 -. + hunk ./docs/lossmodel.lyx 626 -Observe that -\begin_inset Formula $\sum_{i=1}^{N}S_{i}=K$ +Note that since each +\begin_inset Formula $S_{i}$ hunk ./docs/lossmodel.lyx 630 -. - Effectively, + represents the count of shares +\begin_inset Formula $s_{i}$ +\end_inset + + that survives (either 0 or 1), if we add up all of the individual survivor + counts, we get the group survivor count. + That is: +\begin_inset Formula \[ +\sum_{i=1}^{N}S_{i}=K\] + +\end_inset + +Effectively, hunk ./docs/lossmodel.lyx 650 -\begin_layout Standard -The discrete convolution theorem states that given random variables +\begin_layout Theorem +Discrete Convolution Theorem +\end_layout + +\begin_layout Theorem +Let hunk ./docs/lossmodel.lyx 663 - and their sum -\begin_inset Formula $Z=X+Y$ + be discrete random variables with probability mass functions given by +\begin_inset Formula $Pr\left[X=x\right]=f(x)$ hunk ./docs/lossmodel.lyx 667 -, if -\begin_inset Formula $Pr[X=x]=f(x)$ + and +\begin_inset Formula $Pr\left[Y=y\right]=g(y).$ hunk ./docs/lossmodel.lyx 671 - and -\begin_inset Formula $Pr[Y=y]=f(y)$ + Let +\begin_inset Formula $Z$ hunk ./docs/lossmodel.lyx 675 - then -\begin_inset Formula $Pr[Z=z]=(f\star g)(z)$ + be the discrete random random variable obtained by summing +\begin_inset Formula $X$ hunk ./docs/lossmodel.lyx 679 - where -\begin_inset Formula $\star$ + and +\begin_inset Formula $Y$ hunk ./docs/lossmodel.lyx 683 - denotes the convolution operation. - Stated in English, the probability mass function of the sum of two random - variables is the convolution of the probability mass functions of the two - random variables. +. hunk ./docs/lossmodel.lyx 686 -\begin_layout Standard -Discrete convolution is defined as -\end_layout +\begin_layout Theorem +The probability mass function of +\begin_inset Formula $Z$ +\end_inset hunk ./docs/lossmodel.lyx 691 -\begin_layout Standard + is given by hunk ./docs/lossmodel.lyx 693 -(f\star g)(n)=\sum_{m=-\infty}^{\infty}f(m)\cdot g(n-m)\] +Pr[Z=z]=h(z)=\left(f\star g\right)(z)\] hunk ./docs/lossmodel.lyx 697 +where +\begin_inset Formula $\star$ +\end_inset + + denotes the discrete convolution operation: +\begin_inset Formula \[ +\left(f\star g\right)\left(n\right)=\sum_{m=-\infty}^{\infty}f\left(m\right)g\left(m-n\right)\] + +\end_inset hunk ./docs/lossmodel.lyx 707 -\end_layout hunk ./docs/lossmodel.lyx 708 -\begin_layout Standard -The infinite summation is no problem because the probability mass functions - we need to convolve are zero outside of a small range. hunk ./docs/lossmodel.lyx 711 -According to the discrete convolution theorem, then, if +Applying to the discrete convolution theorem, if hunk ./docs/lossmodel.lyx 720 -\begin_inset Formula $ $ -\end_inset - - hunk ./docs/lossmodel.lyx 734 -which enables +Therefore, hunk ./docs/lossmodel.lyx 738 - to be implemented as a sequence of convolution operations on the simple - PMFs of the random variables + can be computed as a sequence of convolution operations on the simple PMFs + of the random variables hunk ./docs/lossmodel.lyx 744 - In fact, as values of + In fact, for large hunk ./docs/lossmodel.lyx 748 - get large, equation + equation hunk ./docs/lossmodel.lyx 763 -reference "eq:binomial-pdf" +reference "eq:binomial-pmf" hunk ./docs/lossmodel.lyx 805 +\begin_inset CommandInset label +LatexCommand label +name "sub:Multiple-Failure-Modes" + +\end_inset + + hunk ./docs/lossmodel.lyx 821 - If those estimates can then be combined into a single PMF for that server, - then we can use it to predict failures for that server. + If those estimates can then be combined into a single PMF for a share, + then we can use it to predict failures for that share. hunk ./docs/lossmodel.lyx 826 -In the case of independent failure modes for a single server, this is very - simple to do. +Combining independent failure modes for a single share is straightforward. hunk ./docs/lossmodel.lyx 835 -th failure mode of server +th failure mode of share hunk ./docs/lossmodel.lyx 839 -, and there are -\begin_inset Formula $m$ +, +\begin_inset Formula $1\leq j\leq m$ hunk ./docs/lossmodel.lyx 843 - failure modes then +, then hunk ./docs/lossmodel.lyx 845 -p_{i}=\prod_{j=1}^{m}p_{i,j}\] +Pr[S_{i}=k]=f_{i}(k)=\begin{cases} +\prod_{j=1}^{m}p_{i,j} & k=1\\ +1-\prod_{j=1}^{m}p_{i,j} & k=0\end{cases}\] hunk ./docs/lossmodel.lyx 851 - is the probability of server +is the survival PMF. +\end_layout + +\begin_layout Subsection +Multi-share failures +\begin_inset CommandInset label +LatexCommand label +name "sub:Multi-share-failures" + +\end_inset + + +\end_layout + +\begin_layout Standard +If there are failure modes that affect multiple computers, we can also construct + the PMF that predicts their survival. + The key observation is that the PMF has non-zero probabilities only for + +\begin_inset Formula $0$ +\end_inset + + survivors and +\begin_inset Formula $n$ +\end_inset + + survivors, where +\begin_inset Formula $n$ +\end_inset + + is the number of shares in the set. + If +\begin_inset Formula $p$ +\end_inset + + is the probability of survival, the PMF of +\begin_inset Formula $K$ +\end_inset + +, a random variable representing the number of surviors is +\begin_inset Formula \[ +Pr[K=i]=f(i)=\begin{cases} +p & i=n\\ +0 & 0 + + + + + + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $k$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $Pr[K=k]$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $Pr[file\, loss]=Pr[K + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $N/k$ +\end_inset + + +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +1 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $1.60\times10^{-9}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $2.53\times10^{-11}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +12 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +2 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $3.80\times10^{-8}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $1.63\times10^{-9}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +6 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +3 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $4.04\times10^{-7}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $3.70\times10^{-8}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +4 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +4 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $2.06\times10^{-6}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $4.44\times10^{-7}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +3 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +5 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $2.10\times10^{-5}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $2.50\times10^{-6}$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +2.4 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +6 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.000428$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $2.35\times10^{-5}$ +\end_inset + + +\end_layout hunk ./docs/lossmodel.lyx 1491 + + +\begin_inset Text + +\begin_layout Plain Layout +2 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +7 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.00417$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.000452$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1.7 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +8 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.0157$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.00462$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1.5 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +9 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.00127$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.0203$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1.3 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +10 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.0230$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.0216$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1.2 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +11 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.208$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.0446$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1.1 +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout +12 +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.747$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +\begin_inset Formula $0.253$ +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +1 +\end_layout + +\end_inset + + + + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption + +\begin_layout Plain Layout +\align left +\begin_inset CommandInset label +LatexCommand label +name "tab:Example-PMF" + +\end_inset + +Example PMF +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\end_layout + +\end_inset + hunk ./docs/lossmodel.lyx 1799 - is the full survival PMF. hunk ./docs/lossmodel.lyx 1802 +The table demonstrates the importance of the selection of +\begin_inset Formula $k$ +\end_inset + +, and the tradeoff against file size expansion. + Note that the survival of exactly 9 servers is significantly less likely + than the survival of 8 or 10 servers. + This is, again, an artifact of the group failure modes. + Because of this, there is no reason to choose +\begin_inset Formula $k=9$ +\end_inset hunk ./docs/lossmodel.lyx 1814 + over +\begin_inset Formula $k=10$ +\end_inset + +. + Normally, reducing the number of shares needed for reassembly improve the + file's chances of survival, but in this case it provides a miniscule gain + in reliability at the cost of a 10% increase in bandwidth and storage consumed. +\end_layout + +\begin_layout Section +Long-Term Reliability +\end_layout + +\begin_layout Standard +Thus far, we've focused entirely on the probability that a file survives + the interval +\begin_inset Formula $A$ +\end_inset + + between repair times. + The probability that a file survives long-term, though, is also important. + As long as the probability of failure during a repair period is non-zero, + a given file will eventually be lost. + We want to know what the probability of surviving for time +\begin_inset Formula $T$ +\end_inset + + is, and how the parameters +\begin_inset Formula $A$ +\end_inset + + (time between repairs) and +\begin_inset Formula $L$ +\end_inset + + (share low watermark) affect survival time. +\end_layout + +\begin_layout Standard +To model file survival time, let +\begin_inset Formula $T$ +\end_inset + + be a random variable denoting the time at which a given file becomes unrecovera +ble, and +\begin_inset Formula $R(t)=Pr[T>t]$ +\end_inset + + be a function that gives the probability that the file survives to time + +\begin_inset Formula $t$ +\end_inset + +. + +\begin_inset Formula $R(t)$ +\end_inset + + is the cumulative distribution function of +\begin_inset Formula $T$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Most survival functions are continuous, but +\begin_inset Formula $R(t)$ +\end_inset + + is inherently discrete, and stochastic. + The time steps are the repair intervals +\end_layout + +\begin_layout Section +Time-Sensitive Retrieval +\end_layout + +\begin_layout Standard +The above work has almost entirely ignored the distinction between availability + and reliability. + In reality, temporary and permanent failures need to be modeled separately, + and hunk ./docs/lossmodel.lyx 710 +\begin_layout Proof +The proof is beyond the scope of this paper. +\begin_inset Foot +status collapsed + +\begin_layout Plain Layout +\begin_inset Quotes eld +\end_inset + +Beyond the scope of this paper +\begin_inset Quotes erd +\end_inset + + usually means +\begin_inset Quotes eld +\end_inset + +Too long and nasty to bore you with +\begin_inset Quotes erd +\end_inset + +. + In this case it means +\begin_inset Quotes eld +\end_inset + +The author hasn't the foggiest idea why this is true, or how to prove it, + but reliable authorities say it's real, and in practice it works a treat. +\begin_inset Quotes erd +\end_inset + + +\end_layout + +\end_inset + + If you don't believe it's true, look it up on Wikipedia, which is never + wrong. +\end_layout + hunk ./docs/lossmodel.lyx 751 -Applying to the discrete convolution theorem, if +Applying the discrete convolution theorem, if hunk ./docs/lossmodel.lyx 770 -f=(g_{1}\star g_{2})\star g_{3})\star\ldots)\star g_{N})\label{eq:convolution}\end{equation} +f=(\ldots((g_{1}\star g_{2})\star g_{3})\star\ldots)\star g_{N})\label{eq:convolution}\end{equation} hunk ./docs/lossmodel.lyx 788 - equation +, equation hunk ./docs/lossmodel.lyx 799 - even in the case of the standard bernoulli distribution, primarily because + even in the case of the standard binomial distribution, primarily because hunk ./docs/lossmodel.lyx 808 - representations are used, or unless the binomial calculation is very cleverly - interleaved with the powers of -\begin_inset Formula $p$ -\end_inset - - and -\begin_inset Formula $1-p$ -\end_inset - - to keep the values manageable. + representations are used. hunk ./docs/lossmodel.lyx 1175 - to computer the PMF + to compute the PMF hunk ./docs/lossmodel.lyx 1855 +\begin_layout Subsection +Share Duplication +\end_layout + +\begin_layout Standard +Before moving on to consider issues other than single-interval file loss, + let's analyze one more possibility, that of +\begin_inset Quotes eld +\end_inset + +cheap +\begin_inset Quotes erd +\end_inset + + file repair via share duplication. +\end_layout + +\begin_layout Standard +Initially, files are split using erasure coding, which creates +\begin_inset Formula $N$ +\end_inset + + unique shares, any +\begin_inset Formula $k$ +\end_inset + + of which can be used to to reconstruct the file. + When shares are lost, proper repair downloads some +\begin_inset Formula $k$ +\end_inset + + shares, reconstructs the original file and then uses the erasure coding + algorithm to reconstruct the lost shares, then redeploys them to peers + in the network. + This is a somewhat expensive process. +\end_layout + +\begin_layout Standard +A cheaper repair option is simply to direct some peer that has share +\begin_inset Formula $s_{i}$ +\end_inset + + to send a copy to another peer, thus increasing by one the number of shares + in the network. + This is not as good as actually replacing the lost share, though. + Suppose that more shares were lost, leaving only +\begin_inset Formula $ $ +\end_inset + + +\begin_inset Formula $k$ +\end_inset + + shares remaining. + If two of those shares are identical, because one was duplicated in this + fashion, then only +\begin_inset Formula $k-1$ +\end_inset + + shares truly remain, and the file can no longer be reconstructed. +\end_layout + +\begin_layout Standard +However, such cheap repair is not completely pointless; it does increase + file survivability. + The question is: By how much? +\end_layout + +\begin_layout Standard +Effectively, share duplication simply increases the probability that +\begin_inset Formula $s_{i}$ +\end_inset + + will survive, by providing two locations from which to retrieve it. + We can view the two copies of the single share as one, but with a higher + probability of survival than would be provided by either of the two peers. + In particular, if +\begin_inset Formula $p_{1}$ +\end_inset + + and +\begin_inset Formula $p_{2}$ +\end_inset + + are the probabilities that the two peers will survive, respectively, then +\begin_inset Formula \[ +Pr[s_{i}\, survives]=p_{1}+p_{2}-p_{1}p_{2}\] + +\end_inset + + +\end_layout + +\begin_layout Standard +More generally, if a single share is deployed on +\begin_inset Formula $n$ +\end_inset + + peers, each with a PMF +\begin_inset Formula $f_{i}(j),0\leq j\leq1,1\leq i\leq n$ +\end_inset + +, the share survival count is a random variable +\begin_inset Formula $S$ +\end_inset + + and the probability of share loss is +\begin_inset Formula \[ +Pr[S=0]=(f_{1}\star f_{2}\star\ldots\star f_{n})(0)\] + +\end_inset + + +\end_layout + +\begin_layout Standard +From that, we can construct a share PMF in the obvious way, which can then + be convolved with the other share PMFs to produce the share set PMF. +\end_layout + +\begin_layout Example +Suppose a file has +\begin_inset Formula $N=10,k=3$ +\end_inset + + and that all servers have survival probability +\begin_inset Formula $p=.9$ +\end_inset + +. + Given a full complement of shares, +\begin_inset Formula $Pr[\textrm{file\, loss}]=3.74\times10^{-7}$ +\end_inset + +. + Suppose that four shares are lost, which increases +\begin_inset Formula $Pr[\textrm{file\, loss}]$ +\end_inset + + to +\begin_inset Formula $.00127$ +\end_inset + +, a value +\begin_inset Formula $3400$ +\end_inset + + times greater. + Rather than doing a proper reconstruction, we could direct four peers still + holding shares to send a copy of their share to new peer, which changes + the composition of the shares from one of six, unique +\begin_inset Quotes eld +\end_inset + +standard +\begin_inset Quotes erd +\end_inset + + shares, to one of two standard shares, each with survival probability +\begin_inset Formula $.9$ +\end_inset + + and four +\begin_inset Quotes eld +\end_inset + +doubled +\begin_inset Quotes erd +\end_inset + + shares, each with survival probability +\begin_inset Formula $2p-p^{2}\approx.99$ +\end_inset + +. +\end_layout + +\begin_layout Example +Combining the two single-peer share PMFs with the four double-share PMFs + gives a new file survival probability of +\begin_inset Formula $6.64\times10^{-6}$ +\end_inset + +. + Not as good as a full repair, but still quite respectable. + Also, if storage were not a concern, all six shares could be duplicated, + for a +\begin_inset Formula $Pr[file\, loss]=1.48\times10^{-7}$ +\end_inset + +, which is actually three time better than the nominal case. +\end_layout + +\begin_layout Example +The reason such cheap repairs may be attractive in many cases is that distribute +d bandwidth is cheaper than bandwidth through a single peer. + This is particularly true if that single peer has a very slow connection, + which is common for home computers -- especially in the outbound direction. +\end_layout + hunk ./docs/lossmodel.lyx 2117 - The time steps are the repair intervals + The time steps are the repair intervals, each of length +\begin_inset Formula $A$ +\end_inset + +, so +\begin_inset Formula $T$ +\end_inset + +-values are multiples of +\begin_inset Formula $A$ +\end_inset + +. + During each interval, the file's shares degrade according to the probability + mass function of +\begin_inset Formula $K$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Aggressive Repairs +\end_layout + +\begin_layout Standard +Let's first consider the case of an aggressive repairer. + Every interval, this repairer checks the file for share losses and restores + them. + Thus, at the beginning of each interval, the file always has +\begin_inset Formula $N$ +\end_inset + + shares, distributed on servers with various individual and group failure + probalities, which will survive or fail per the output of random variable + +\begin_inset Formula $K$ +\end_inset + +. +\end_layout + +\begin_layout Standard +For any interval, then, the probability that the file will survive is +\begin_inset Formula $f\left(k\right)=Pr[K\geq k]$ +\end_inset + +. + Since each interval success or failure is independent, and assuming the + share reliabilities remain constant over time, +\begin_inset Formula \begin{equation} +R\left(t\right)=f(k)^{t}\end{equation} + +\end_inset + + +\end_layout + +\begin_layout Standard +This simple survival function makes it simple to select parameters +\begin_inset Formula $N$ +\end_inset + + and +\begin_inset Formula $K$ +\end_inset + + such that +\begin_inset Formula $R(t)\geq r$ +\end_inset + +, where +\begin_inset Formula $r$ +\end_inset + + is a user-specified parameter indicating the desired probability of survival + to time +\begin_inset Formula $t$ +\end_inset + +. + Specifically, we can solve for +\begin_inset Formula $f\left(k\right)$ +\end_inset + + in +\begin_inset Formula $r\leq f\left(k\right)^{t}$ +\end_inset + +, giving: +\begin_inset Formula \begin{equation} +f\left(k\right)\geq\sqrt[t]{r}\end{equation} + +\end_inset + + +\end_layout + +\begin_layout Standard +So, given a PMF +\begin_inset Formula $f\left(k\right)$ +\end_inset + +, to assure the survival of a file to time +\begin_inset Formula $t$ +\end_inset + + with probability at least +\begin_inset Formula $r$ +\end_inset + +, choose +\begin_inset Formula $k:f\left(k\right)\geq\sqrt[t]{r}$ +\end_inset + +. + For example, if +\begin_inset Formula $A$ +\end_inset + + is one month, and +\begin_inset Formula $r=1-\nicefrac{1}{1000000}$ +\end_inset + + and +\begin_inset Formula $t=120$ +\end_inset + +, or 10 years, we calculate +\begin_inset Formula $f\left(k\right)\geq\sqrt[120]{.999999}\cong0.999999992$ +\end_inset + +. + Per the PMF of table +\begin_inset CommandInset ref +LatexCommand ref +reference "tab:Example-PMF" + +\end_inset + +, this means +\begin_inset Formula $k=2$ +\end_inset + +, achieves the goal, at the cose of a six-fold expansion in stored file + size. + If the lesser goal of no more than +\begin_inset Formula $\nicefrac{1}{1000}$ +\end_inset + + probability of loss is taken, then since +\begin_inset Formula $\sqrt[120]{.9999}=.999992$ +\end_inset + +, +\begin_inset Formula $k=5$ +\end_inset + + achieves the goal with an expansion factor of +\begin_inset Formula $2.4$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Repair Cost +\end_layout + +\begin_layout Standard +The simplicity and predictability of aggressive repair is attractive, but + there is a downside: Repairs cost processing power and bandwidth. + The processing power is proportional to the size of the file, since the + whole file must be reconstructed and then re-processed using the Reed-Solomon + algorithm, while the bandwidth cost is proportional to the number of missing + shares that must be replaced, +\begin_inset Formula $N-K$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Let +\begin_inset Formula $c\left(s,d,k\right)$ +\end_inset + + be a cost function that combines the processing cost of regenerating a + file of size +\begin_inset Formula $s$ +\end_inset + + and the bandwidth cost of downloading a file of size +\begin_inset Formula $s$ +\end_inset + + and uploading +\begin_inset Formula $d$ +\end_inset + + shares each of size +\begin_inset Formula $\nicefrac{s}{k}$ +\end_inset + +. + Also, let +\begin_inset Formula $D$ +\end_inset + + denote the random variable +\begin_inset Formula $N-K$ +\end_inset + +, which is the number of shares that must be redistributed to bring the + file share set back up to +\begin_inset Formula $N$ +\end_inset + + after degrading during an interval. + The probability mass function of +\begin_inset Formula $D$ +\end_inset + + is +\begin_inset Formula \[ +Pr[D=d]=f(d)=\begin{cases} +Pr\left[K=N\right]+Pr[K check_period: + last_check = t + # we do a check-and-repair this frequently + need_repair = my_dot(maintained_state, REPAIRp) + + P_repaired_last_check_period = need_repair + new_shares = my_dot(maintained_state, REPAIR_newshares) + needed_repairs.append(need_repair) + needed_new_shares.append(new_shares) + + maintained_state = mm(maintained_state, repair) + + if (t-last_report) > report_period: + last_report = t + P_dead_unmaintained = my_dot(unmaintained_state, DEAD) + P_dead_maintained = my_dot(maintained_state, DEAD) + cumulative_number_of_repairs = sum(needed_repairs) + cumulative_number_of_new_shares = sum(needed_new_shares) + report.add_sample(t, unmaintained_state, maintained_state, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) + + # record one more sample at the end of the run + P_dead_unmaintained = my_dot(unmaintained_state, DEAD) + P_dead_maintained = my_dot(maintained_state, DEAD) + cumulative_number_of_repairs = sum(needed_repairs) + cumulative_number_of_new_shares = sum(needed_new_shares) + report.add_sample(t, unmaintained_state, maintained_state, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) + + #needed_repairs_total = sum(needed_repairs) + #needed_new_shares_total = sum(needed_new_shares) + #print "at 2y:" + #print " unmaintained", unmaintained_state + #print " maintained", maintained_state + #print " number of repairs", needed_repairs_total + #print " new shares generated", needed_new_shares_total + #repair_rate_inv = report_span / needed_repairs_total + #print " avg repair rate: once every %s" % yandm(repair_rate_inv) + #print " avg repair download: one share every %s" % yandm(repair_rate_inv/k) + #print " avg repair upload: one share every %s" % yandm(report_span / needed_new_shares_total) + + return report + + def p_in_period(self, avg_lifetime, period): + """Given an average lifetime of a disk (using an exponential model), + what is the chance that a live disk will survive the next 'period' + seconds?""" + + # eg p_in_period(8*YEAR, MONTH) = 98.94% + return math.exp(-1.0*period/avg_lifetime) + + def build_decay_matrix(self, N, P): + """Return a decay matrix. decay[start_shares][end_shares] is the + conditional probability of finishing with end_shares, given that we + started with start_shares.""" + decay_rows = [] + decay_rows.append( [0.0]*(N+1) ) + for start_shares in range(1, (N+1)): + end_shares = self.build_decay_row(start_shares, P) + decay_row = end_shares + [0.0] * (N-start_shares) + assert len(decay_row) == (N+1), len(decay_row) + decay_rows.append(decay_row) + + decay = array(decay_rows) + return decay + + def build_decay_row(self, start_shares, P): + """Return a decay row 'end_shares'. end_shares[i] is the chance that + we finish with i shares, given that we started with start_shares, for + all i between 0 and start_shares, inclusive. This implementation + assumes that all shares are independent (IID), but a more complex + model could incorporate inter-share failure correlations like having + two shares on the same server.""" + end_shares = statistics.binomial_distribution_pmf(start_shares, P) + return end_shares + + def build_repair_matrix(self, k, N, R): + """Return a repair matrix. repair[start][end]: is the conditional + probability of the repairer finishing with 'end' shares, given that + it began with 'start' shares (repair if fewer than R shares). The + repairer's behavior is deterministic, so all values in this matrix + are either 0 or 1. This matrix should be applied *after* the decay + matrix.""" + new_repair_rows = [] + for start_shares in range(0, N+1): + new_repair_row = [0] * (N+1) + if start_shares < k: + new_repair_row[start_shares] = 1 + elif start_shares < R: + new_repair_row[N] = 1 + else: + new_repair_row[start_shares] = 1 + new_repair_rows.append(new_repair_row) + + repair = array(new_repair_rows) + return repair + +class ReliabilityReport: + def __init__(self): + self.samples = [] + + def add_sample(self, when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained): + """ + when: the timestamp at the end of the report period + unmaintained_shareprobs: a vector of probabilities, element[S] + is the chance that there are S shares + left at the end of the report period. + This tracks what happens if no repair + is ever done. + maintained_shareprobs: same, but for 'maintained' grids, where + check and repair is done at the end + of each check period + P_repaired_last_check_period: a float, with the probability + that a repair was performed + at the end of the most recent + check period. + cumulative_number_of_repairs: a float, with the average number + of repairs that will have been + performed by the end of the + report period + cumulative_number_of_new_shares: a float, with the average number + of new shares that repair proceses + generated by the end of the report + period + P_dead_unmaintained: a float, with the chance that the file will + be unrecoverable at the end of the period + P_dead_maintained: same, but for maintained grids + + """ + row = (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) + self.samples.append(row) addfile ./src/allmydata/web/reliability.py hunk ./src/allmydata/web/reliability.py 1 + +from nevow import rend, inevow, tags as T +reliability = None # might not be usable +try: + from allmydata import reliability # requires Numeric and PIL +except ImportError: + pass +from allmydata.web.common import getxmlfile, get_arg + + +DAY=24*60*60 +MONTH=31*DAY +YEAR=365*DAY + +def yandm(seconds): + return "%dy.%dm" % (int(seconds/YEAR), int( (seconds%YEAR)/MONTH)) + +class ReliabilityTool(rend.Page): + addSlash = True + docFactory = getxmlfile("reliability.xhtml") + + DEFAULT_PARAMETERS = [ + ("drive_lifetime", "8Y", "time"), + ("k", 3, "int"), + ("R", 7, "int"), + ("N", 10, "int"), + ("delta", "1M", "time"), + ("check_period", "1M", "time"), + ("report_period", "3M", "time"), + ("report_span", "5Y", "time"), + ] + + def parse_time(self, s): + if s.endswith("M"): + return int(s[:-1]) * MONTH + if s.endswith("Y"): + return int(s[:-1]) * YEAR + return int(s) + + def format_time(self, s): + if s%YEAR == 0: + return "%dY" % (s/YEAR) + if s%MONTH == 0: + return "%dM" % (s/MONTH) + return "%d" % s + + def get_parameters(self, ctx): + req = inevow.IRequest(ctx) + parameters = {} + for name,default,argtype in self.DEFAULT_PARAMETERS: + v = get_arg(ctx, name, default) + if argtype == "time": + value = self.parse_time(v) + else: + value = int(v) + parameters[name] = value + return parameters + + def renderHTTP(self, ctx): + print "renderHTTP" + print "two" + self.parameters = self.get_parameters(ctx) + print "parms", self.parameters + self.results = reliability.ReliabilityModel.run(**self.parameters) + print "got results" + return rend.Page.renderHTTP(self, ctx) + + def make_input(self, name, old_value): + return T.input(name=name, type="text", + value=self.format_time(old_value)) + + def render_forms(self, ctx, data): + f = T.form(action=".", method="get") + table = [] + for name, default_value, argtype in self.DEFAULT_PARAMETERS: + old_value = self.parameters[name] + i = self.make_input(name, old_value) + table.append(T.tr[T.td[name+":"], T.td[i]]) + go = T.input(type="submit", value="Recompute") + return [T.h2["Simulation Parameters:"], + f[T.table[table], go], + ] + + def data_simulation_table(self, ctx, data): + for row in self.results.samples: + yield row + + def render_simulation_row(self, ctx, row): + (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) = row + ctx.fillSlots("t", yandm(when)) + ctx.fillSlots("P_repair", "%.6f" % P_repaired_last_check_period) + ctx.fillSlots("P_dead_unmaintained", "%.6g" % P_dead_unmaintained) + ctx.fillSlots("P_dead_maintained", "%.6g" % P_dead_maintained) + return ctx.tag + + def render_report_span(self, ctx, row): + (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) = self.results.samples[-1] + return ctx.tag[yandm(when)] + + def render_P_loss_unmaintained(self, ctx, row): + (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) = self.results.samples[-1] + return ctx.tag["%.6g (%1.8f%%)" % (P_dead_unmaintained, + 100*P_dead_unmaintained)] + + def render_P_loss_maintained(self, ctx, row): + (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) = self.results.samples[-1] + return ctx.tag["%.6g (%1.8f%%)" % (P_dead_maintained, + 100*P_dead_maintained)] + + def render_P_repair_rate(self, ctx, row): + (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) = self.results.samples[-1] + freq = when / cumulative_number_of_repairs + return ctx.tag["%.6g" % freq] + + def render_P_repair_shares(self, ctx, row): + (when, unmaintained_shareprobs, maintained_shareprobs, + P_repaired_last_check_period, + cumulative_number_of_repairs, + cumulative_number_of_new_shares, + P_dead_unmaintained, P_dead_maintained) = self.results.samples[-1] + generated_shares = cumulative_number_of_new_shares / cumulative_number_of_repairs + return ctx.tag["%1.2f" % generated_shares] + + addfile ./src/allmydata/web/reliability.xhtml hunk ./src/allmydata/web/reliability.xhtml 1 + + + AllMyData - Tahoe - Provisioning Tool + + + + + + +

Tahoe Reliability Tool

+ +

Given certain assumptions, this page calculates probability of share loss +over time, to help make informed decisions about how much redundancy and +repair bandwidth to configure on a Tahoe grid.

+ +
+ +

Simulation Results

+ +

At the end of the report span (elapsed time ), the simulated file had the following properties:

+ +
    +
  • Probability of loss (no maintenance): +
    • +
  • Probability of loss (with maintenance): +
    • +
  • Average repair frequency: + once every secs
    • +
  • Average shares generated per repair: +
    • +
+ +

This table shows how the following properties change over time:

+
    +
  • P_repair: the chance that a repair was performed in the most recent + check period.
    • +
  • P_dead (unmaintained): the chance that the file will be unrecoverable + without periodic check+repair
    • +
  • P_dead (maintained): the chance that the file will be recoverable even + with periodic check+repair
    • +
+ +
+ + + + + + + + + + + + + + +
tP_repairP_dead (unmaintained)P_dead (maintained)
no simulation data!
+
+ + + hunk ./src/allmydata/web/root.py 5 -from nevow import rend, url, tags as T +from nevow import rend, url, loaders, tags as T hunk ./src/allmydata/web/root.py 14 +reliability = None +try: + from allmydata.web import reliability # requires Numeric and PIL +except ImportError: + pass # might not be usable hunk ./src/allmydata/web/root.py 119 +class NoReliability(rend.Page): + docFactory = loaders.xmlstr('''\ + + + AllMyData - Tahoe + + + + +

"Reliability" page not available

+

Please install the python "Numeric" module to enable this page.

+ + +''') hunk ./src/allmydata/web/root.py 152 + if reliability: + child_reliability = reliability.ReliabilityTool() + else: + child_reliability = NoReliability() hunk ./src/allmydata/web/welcome.xhtml 78 -
The provisioning tool may also be useful.
+
The provisioning tool and reliability calculator may also be useful.