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.

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}$$

• Awesome - that works out great! – MikeyB Jul 29 '13 at 19:32

$$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)

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