source file: /home/buildslave/tahoe/edgy/build/src/allmydata/util/statistics.py
file stats: 97 lines, 95 executed: 97.9% covered
coverage versus previous test: 62 lines added, 62 lines removed
1. # Copyright (c) 2009 Shawn Willden
2. # mailto:shawn@willden.org
3. # I hereby license all patches I have contributed or will contribute to
- 4. # the Allmydata Tahoe-LAFS project, including the file 'statistics.py',
- 5. # under both the GNU General Public License, version 2 or later, and
- 6. # under the Transitive Grace Period Public License, version 1 or later.
- 7.
+ 8. from __future__ import division
9. from mathutil import round_sigfigs
+ 10. import math
+ 11. import sys
12.
+ 13. def pr_file_loss(p_list, k):
14. """
15. Probability of single-file loss for shares with reliabilities in
16. p_list.
17.
18. Computes the probability that a single file will become
19. unrecoverable, based on the individual share survival
20. probabilities and and k (number of shares needed for recovery).
21.
22. Example: pr_file_loss([.9] * 5 + [.99] * 5, 3) returns the
23. probability that a file with k=3, N=10 and stored on five servers
24. with reliability .9 and five servers with reliability .99 is lost.
- 25.
- 26. See survival_pmf docstring for important statistical assumptions.
27.
28. """
+ 29. assert 0 < k <= len(p_list)
30. assert valid_probability_list(p_list)
31.
- 32. # Sum elements 0 through k-1 of the share set PMF to get the
33. # probability that less than k shares survived.
+ 34. return sum(survival_pmf(p_list)[0:k])
35.
+ 36. def survival_pmf(p_list):
37. """
38. Return the collective PMF of share survival count for a set of
39. shares with the individual survival probabilities in p_list.
40.
41. Example: survival_pmf([.99] * 10 + [.8] * 6) returns the
42. probability mass function for the number of shares that will
43. survive from an initial set of 16, 10 with p=0.99 and 6 with
44. p=0.8. The ith element of the resulting list is the probability
45. that exactly i shares will survive.
46.
47. This calculation makes the following assumptions:
48.
49. 1. p_list[i] is the probability that any individual share will
50. will survive during the time period in question (whatever that may
51. be).
52.
53. 2. The share failures are "independent", in the statistical
- 54. sense. Note that if a group of shares are stored on the same
55. machine or even in the same data center, they are NOT independent
- 56. and this calculation is therefore wrong.
57. """
58. assert valid_probability_list(p_list)
- 59.
+ 60. pmf = survival_pmf_via_conv(p_list)
- 61.
+ 62. assert valid_pmf(pmf)
+ 63. return pmf
64.
+ 65. def survival_pmf_via_bd(p_list):
66. """
67. Compute share survival PMF using the binomial distribution PMF as
68. much as possible.
69.
70. This is more efficient than the convolution method below, but
71. doesn't work for large numbers of shares because the
72. binomial_coeff calculation blows up. Since the efficiency gains
73. only matter in the case of large numbers of shares, it's pretty
74. much useless except for testing the convolution methond.
- 75.
76. Note that this function does little to no error checking and is
- 77. intended for internal use and testing only.
78. """
79. pmf_list = [ binomial_distribution_pmf(p_list.count(p), p)
80. for p in set(p_list) ]
+ 81. return reduce(convolve, pmf_list)
82.
+ 83. def survival_pmf_via_conv(p_list):
84. """
85. Compute share survival PMF using iterated convolution of trivial
86. PMFs.
- 87.
- 88. Note that this function does little to no error checking and is
89. intended for internal use and testing only.
- 90. """
+ 91. pmf_list = [ [1 - p, p] for p in p_list ];
+ 92. return reduce(convolve, pmf_list)
93.
+ 94. def print_pmf(pmf, n=4, out=sys.stdout):
- 95. """
- 96. Print a PMF in a readable form, with values rounded to n
97. significant digits.
- 98. """
+ 99. for k, p in enumerate(pmf):
+ 100. print >>out, "i=" + str(k) + ":", round_sigfigs(p, n)
101.
+ 102. def pr_backup_file_loss(p_list, backup_p, k):
103. """
104. Probability of single-file loss in a backup context
105.
106. Same as pr_file_loss, except it factors in the probability of
- 107. survival of the original source, specified as backup_p. Because
- 108. that's a precondition to caring about the availability of the
- 109. backup, it's an independent event.
110. """
111. assert valid_probability_list(p_list)
+ 112. assert 0 < backup_p <= 1
+ 113. assert 0 < k <= len(p_list)
- 114.
+ 115. return pr_file_loss(p_list, k) * (1 - backup_p)
116.
117.
+ 118. def find_k(p_list, target_loss_prob):
- 119. """
- 120. Find the highest k value that achieves the targeted loss
121. probability, given the share reliabilities given in p_list.
- 122. """
123. assert valid_probability_list(p_list)
+ 124. assert 0 < target_loss_prob < 1
- 125.
+ 126. pmf = survival_pmf(p_list)
+ 127. return find_k_from_pmf(pmf, target_loss_prob)
128.
+ 129. def find_k_from_pmf(pmf, target_loss_prob):
- 130. """
- 131. Find the highest k value that achieves the targeted loss
132. probability, given the share survival PMF given in pmf.
- 133. """
134. assert valid_pmf(pmf)
135. assert 0 < target_loss_prob < 1
- 136.
137. loss_prob = 0.0
+ 138. for k, p_k in enumerate(pmf):
+ 139. loss_prob += p_k
+ 140. if loss_prob > target_loss_prob:
+ 141. return k
142.
- 143. # we shouldn't be able to get here, since sum(pmf)==1.0
144. k = len(pmf) - 1
145. return k
146.
+ 147. def repair_count_pmf(survival_pmf, k):
148. """
- 149. Return Pr[D=d], where D represents the number of shares that have
150. to be repaired at the end of an interval, starting with a full
151. set and subject to losses described in survival_pmf.
152. """
153. n = len(survival_pmf) - 1
154.
155. # Probability of 0 to repair is the probability of all shares
- 156. # surviving plus the probability of less than k surviving.
157. pmf = [ survival_pmf[n] + sum(survival_pmf[0:k]) ]
158.
159. # Probability of more than 0, up to N-k to repair
+ 160. for i in range(1, n-k+1):
161. pmf.append(survival_pmf[n-i])
- 162.
163. # Probability of more than N-k to repair is 0, because that means
- 164. # there are less than k available and the file is irreparable.
165. for i in range(n-k+1, n+1):
+ 166. pmf.append(0.0)
- 167.
168. assert(valid_pmf(pmf))
+ 169. return pmf
- 170.
+ 171. def bandwidth_cost_function(file_size, shares, k, ul_dl_ratio):
+ 172. return file_size + float(file_size) / k * shares * ul_dl_ratio
173.
+ 174. def mean_repair_cost(cost_function, file_size, survival_pmf, k, ul_dl_ratio):
175. """
- 176. Return the expected cost for a repair run on a file with the given
- 177. survival_pmf and requiring k shares, in which upload cost is
178. 'ul_dl_ratio' times download cost.
179. """
180. repair_pmf = repair_count_pmf(survival_pmf, k)
+ 181. expected_cost = sum([cost_function(file_size, new_shares, k, ul_dl_ratio)
- 182. * repair_pmf[new_shares]
183. for new_shares in range(1, len(repair_pmf))])
+ 184. return expected_cost
185.
+ 186. def eternal_repair_cost(cost_function, file_size, survival_pmf, k,
187. discount_rate=0, ul_dl_ratio=1.0):
- 188. """
- 189. Calculate the eternal repair cost for a file that is aggressively
- 190. repaired, i.e. the sum of repair costs until the file is dead.
191. """
192. c = mean_repair_cost(cost_function, file_size, survival_pmf, k, ul_dl_ratio)
+ 193. f = 1 - sum(survival_pmf[0:k])
194. r = float(discount_rate)
195.
+ 196. return (c * (1-r)) / (1 - (1-r) * f)
197.
+ 198. def valid_pmf(pmf):
199. """
200. Validate that pmf looks like a proper discrete probability mass
- 201. function in list form.
202.
- 203. Returns true if the elements of pmf sum to 1.
204. """
+ 205. return round(sum(pmf),5) == 1.0
206.
207. def valid_probability_list(p_list):
- 208. """
- 209. Validate that p_list is a list of probibilities
210. """
211. for p in p_list:
+ 212. if p < 0 or p > 1:
213. return False
214.
+ 215. return True
216.
+ 217. def convolve(list_a, list_b):
218. """
219. Returns the discrete convolution of two lists.
220.
- 221. Given two random variables X and Y, the convolution of their
- 222. probability mass functions Pr(X) and Pr(Y) is equal to the
223. Pr(X+Y).
- 224. """
225. n = len(list_a)
226. m = len(list_b)
227.
228. result = []
229. for i in range(n + m - 1):
+ 230. sum = 0.0
- 231.
232. lower = max(0, i - n + 1)
+ 233. upper = min(m - 1, i)
- 234.
+ 235. for j in range(lower, upper+1):
236. sum += list_a[i-j] * list_b[j]
237.
238. result.append(sum)
239.
+ 240. return result
241.
+ 242. def binomial_distribution_pmf(n, p):
243. """
244. Returns Pr(K), where K ~ B(n,p), as a list of values.
245.
246. Returns the full probability mass function of a B(n, p) as a list
247. of values, where the kth element is Pr(K=k), or, in the Tahoe
- 248. context, the probability that exactly k copies of a file share
- 249. survive, when placed on n independent servers with survival
250. probability p.
- 251. """
252. assert p >= 0 and p <= 1, 'p=%s must be in the range [0,1]'%p
253. assert n > 0
254.
+ 255. result = []
+ 256. for k in range(n+1):
257. result.append(math.pow(p , k ) *
- 258. math.pow(1 - p, n - k) *
259. binomial_coeff(n, k))
- 260.
+ 261. assert valid_pmf(result)
+ 262. return result;
263.
+ 264. def binomial_coeff(n, k):
- 265. """
266. Returns the number of ways that k items can be chosen from a set
- 267. of n.
- 268. """
+ 269. assert n >= k
- 270.
271. if k > n/2:
272. k = n - k
273.
274. accum = 1.0
+ 275. for i in range(1, k+1):
+ 276. accum = accum * (n - k + i) // i;
277.
+ 278. return int(accum + 0.5)