0
$\begingroup$

I need to model data access for a storage system where I have:

  • $S = $ Number of Server Nodes (that hand out data to clients and store data)
  • $D = $ Number of Data Nodes (that do not hand out data to clients and only store data)
  • $F = $ Number of Frontend Nodes (that hand out data to clients and do not store data)
  • $R = $ Replication factor (copies of the data, no more than one copy per node)

For my purposes, either $D$ or $F$ will be $0$ (not sure if that affects the formula but it makes thinking about it easier). What I am trying to model is the probability that on any given I/O operation (read or write), the $S$ or $F$ node being accessed by a client will have NO local copy of the data.

$\endgroup$
2
$\begingroup$

I take it we're assuming uniform distributions for the various random choices (which server we're accessing, which servers hold the specific datum). I don't think that your formula's quite right; if we simplify by assuming that D=F=0, consider the case where S=4 and R=3. Then clearly we should have a 1/4 probability of hitting the server without the data, as opposed to the 6/64 that your formula gives.

If D=0 then I think just replacing the middle bit with (S-R)/S should serve. For positive D we need to worry about inaccessible data copies; I think you should get something like: $$\sum_{i=0}^R\frac{\binom{S}{i}\binom{D}{R-i}}{\binom{S+D}{R}}\cdot \frac{S-i}{S}$$ Here $i$ represents the number of copies of the data stored across the server nodes; for each such possible value we compute the probability of such a distribution between server and data nodes, and then (assuming that condition) finding the probability of getting a server node without the data.

So your full formula:$$\frac{S}{S+F}\sum_{i=0}^R\left(\frac{\binom{S}{i}\binom{D}{R-i}}{\binom{S+D}{R}}\cdot \frac{S-i}{S}\right)+\frac{F}{S+F}$$

$\endgroup$
  • $\begingroup$ Awesome - that works out great! $\endgroup$ – MikeyB Jul 29 '13 at 19:32
1
$\begingroup$

$$P(no local copy) = \frac{S}{S+F} × \frac{\prod_{i=1}^{R} (S+D-i)}{(S+D)^R} + \frac{F}{S+F}$$

My reasoning is:

$\frac{S}{S+F}$ : probability of hitting a $S$ node

$\frac{\prod_{i=1}^{R} (S+D-i)}{(S+D)^R}$ : There are $S+D$ nodes on which the data could be stored, and it will be stored on $R$ of them. Standard binomial test.

$\frac{F}{S+F}$ : probability of hitting a $F$ node (with no local data)

$\endgroup$
  • $\begingroup$ I'm not actually sure if this is right. Looking for a second opinion :D $\endgroup$ – MikeyB Jul 18 '13 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.