Model

Conflict grows with the square of throughput

Ten times the throughput buys a hundred times the conflict.

conflicts \approx \frac{L ^{2} k ^{2}}{2 N}, L = λW

$L$: In flight; live transactions (Little's Law: arrival rate × duration)
$k$: Items per transaction; items each transaction touches
$N$: Key space; the effective key space (skew shrinks it)
$λ, W$: Rate and duration; transactions per second and how long each holds its items

Recurring principle: Variance costs more than volume

How it behaves

One input on the horizontal axis, the others held fixed.

N = 10⁶ itemseffective N = 10⁴ (skewed keys)

Data table

Expected conflicts at any moment, by throughput (k = 10, W = 5 ms)
Throughput λ (transactions per second)	series	Conflicts at any moment
1K	N = 10⁶ items	0.001
1.09K	N = 10⁶ items	0.001
1.19K	N = 10⁶ items	0.002
1.3K	N = 10⁶ items	0.002
1.41K	N = 10⁶ items	0.002
1.54K	N = 10⁶ items	0.003
1.68K	N = 10⁶ items	0.004
1.83K	N = 10⁶ items	0.004
2K	N = 10⁶ items	0.005
2.18K	N = 10⁶ items	0.006
2.37K	N = 10⁶ items	0.007
2.59K	N = 10⁶ items	0.008
2.82K	N = 10⁶ items	0.01
3.07K	N = 10⁶ items	0.012
3.35K	N = 10⁶ items	0.014
3.65K	N = 10⁶ items	0.017
3.98K	N = 10⁶ items	0.02
4.34K	N = 10⁶ items	0.024
4.73K	N = 10⁶ items	0.028
5.16K	N = 10⁶ items	0.033
5.62K	N = 10⁶ items	0.04
6.13K	N = 10⁶ items	0.047
6.68K	N = 10⁶ items	0.056
7.29K	N = 10⁶ items	0.066
7.94K	N = 10⁶ items	0.079
8.66K	N = 10⁶ items	0.094
9.44K	N = 10⁶ items	0.111
10.3K	N = 10⁶ items	0.132
11.2K	N = 10⁶ items	0.157
12.2K	N = 10⁶ items	0.187
13.3K	N = 10⁶ items	0.222
14.5K	N = 10⁶ items	0.264
15.8K	N = 10⁶ items	0.314
17.3K	N = 10⁶ items	0.373
18.8K	N = 10⁶ items	0.444
20.5K	N = 10⁶ items	0.527
22.4K	N = 10⁶ items	0.626
24.4K	N = 10⁶ items	0.745
26.6K	N = 10⁶ items	0.885
29K	N = 10⁶ items	1.05
31.6K	N = 10⁶ items	1.25
34.5K	N = 10⁶ items	1.49
37.6K	N = 10⁶ items	1.77
41K	N = 10⁶ items	2.1
44.7K	N = 10⁶ items	2.49
48.7K	N = 10⁶ items	2.96
53.1K	N = 10⁶ items	3.52
57.9K	N = 10⁶ items	4.19
63.1K	N = 10⁶ items	4.98
68.8K	N = 10⁶ items	5.91
75K	N = 10⁶ items	7.03
81.8K	N = 10⁶ items	8.35
89.1K	N = 10⁶ items	9.93
97.2K	N = 10⁶ items	11.8
106K	N = 10⁶ items	14
115K	N = 10⁶ items	16.7
126K	N = 10⁶ items	19.8
137K	N = 10⁶ items	23.5
150K	N = 10⁶ items	28
163K	N = 10⁶ items	33.3
178K	N = 10⁶ items	39.5
194K	N = 10⁶ items	47
211K	N = 10⁶ items	55.8
230K	N = 10⁶ items	66.4
251K	N = 10⁶ items	78.9
274K	N = 10⁶ items	93.7
299K	N = 10⁶ items	111
325K	N = 10⁶ items	132
355K	N = 10⁶ items	157
387K	N = 10⁶ items	187
422K	N = 10⁶ items	222
460K	N = 10⁶ items	264
501K	N = 10⁶ items	314
546K	N = 10⁶ items	373
596K	N = 10⁶ items	444
649K	N = 10⁶ items	527
708K	N = 10⁶ items	626
772K	N = 10⁶ items	745
841K	N = 10⁶ items	885
917K	N = 10⁶ items	1,050
1M	N = 10⁶ items	1,250
1K	effective N = 10⁴ (skewed keys)	0.125
1.09K	effective N = 10⁴ (skewed keys)	0.149
1.19K	effective N = 10⁴ (skewed keys)	0.177
1.3K	effective N = 10⁴ (skewed keys)	0.21
1.41K	effective N = 10⁴ (skewed keys)	0.249
1.54K	effective N = 10⁴ (skewed keys)	0.296
1.68K	effective N = 10⁴ (skewed keys)	0.352
1.83K	effective N = 10⁴ (skewed keys)	0.419
2K	effective N = 10⁴ (skewed keys)	0.498
2.18K	effective N = 10⁴ (skewed keys)	0.591
2.37K	effective N = 10⁴ (skewed keys)	0.703
2.59K	effective N = 10⁴ (skewed keys)	0.835
2.82K	effective N = 10⁴ (skewed keys)	0.993
3.07K	effective N = 10⁴ (skewed keys)	1.18
3.35K	effective N = 10⁴ (skewed keys)	1.4
3.65K	effective N = 10⁴ (skewed keys)	1.67
3.98K	effective N = 10⁴ (skewed keys)	1.98
4.34K	effective N = 10⁴ (skewed keys)	2.35
4.73K	effective N = 10⁴ (skewed keys)	2.8
5.16K	effective N = 10⁴ (skewed keys)	3.33
5.62K	effective N = 10⁴ (skewed keys)	3.95
6.13K	effective N = 10⁴ (skewed keys)	4.7
6.68K	effective N = 10⁴ (skewed keys)	5.58
7.29K	effective N = 10⁴ (skewed keys)	6.64
7.94K	effective N = 10⁴ (skewed keys)	7.89
8.66K	effective N = 10⁴ (skewed keys)	9.37
9.44K	effective N = 10⁴ (skewed keys)	11.1
10.3K	effective N = 10⁴ (skewed keys)	13.2
11.2K	effective N = 10⁴ (skewed keys)	15.7
12.2K	effective N = 10⁴ (skewed keys)	18.7
13.3K	effective N = 10⁴ (skewed keys)	22.2
14.5K	effective N = 10⁴ (skewed keys)	26.4
15.8K	effective N = 10⁴ (skewed keys)	31.4
17.3K	effective N = 10⁴ (skewed keys)	37.3
18.8K	effective N = 10⁴ (skewed keys)	44.4
20.5K	effective N = 10⁴ (skewed keys)	52.7
22.4K	effective N = 10⁴ (skewed keys)	62.6
24.4K	effective N = 10⁴ (skewed keys)	74.5
26.6K	effective N = 10⁴ (skewed keys)	88.5
29K	effective N = 10⁴ (skewed keys)	105
31.6K	effective N = 10⁴ (skewed keys)	125
34.5K	effective N = 10⁴ (skewed keys)	149
37.6K	effective N = 10⁴ (skewed keys)	177
41K	effective N = 10⁴ (skewed keys)	210
44.7K	effective N = 10⁴ (skewed keys)	249
48.7K	effective N = 10⁴ (skewed keys)	296
53.1K	effective N = 10⁴ (skewed keys)	352
57.9K	effective N = 10⁴ (skewed keys)	419
63.1K	effective N = 10⁴ (skewed keys)	498
68.8K	effective N = 10⁴ (skewed keys)	591
75K	effective N = 10⁴ (skewed keys)	703
81.8K	effective N = 10⁴ (skewed keys)	835
89.1K	effective N = 10⁴ (skewed keys)	993
97.2K	effective N = 10⁴ (skewed keys)	1,180
106K	effective N = 10⁴ (skewed keys)	1,400
115K	effective N = 10⁴ (skewed keys)	1,670
126K	effective N = 10⁴ (skewed keys)	1,980
137K	effective N = 10⁴ (skewed keys)	2,350
150K	effective N = 10⁴ (skewed keys)	2,800
163K	effective N = 10⁴ (skewed keys)	3,330
178K	effective N = 10⁴ (skewed keys)	3,950
194K	effective N = 10⁴ (skewed keys)	4,700
211K	effective N = 10⁴ (skewed keys)	5,580
230K	effective N = 10⁴ (skewed keys)	6,640
251K	effective N = 10⁴ (skewed keys)	7,890
274K	effective N = 10⁴ (skewed keys)	9,370
299K	effective N = 10⁴ (skewed keys)	11.1K
325K	effective N = 10⁴ (skewed keys)	13.2K
355K	effective N = 10⁴ (skewed keys)	15.7K
387K	effective N = 10⁴ (skewed keys)	18.7K
422K	effective N = 10⁴ (skewed keys)	22.2K
460K	effective N = 10⁴ (skewed keys)	26.4K
501K	effective N = 10⁴ (skewed keys)	31.4K
546K	effective N = 10⁴ (skewed keys)	37.3K
596K	effective N = 10⁴ (skewed keys)	44.4K
649K	effective N = 10⁴ (skewed keys)	52.7K
708K	effective N = 10⁴ (skewed keys)	62.6K
772K	effective N = 10⁴ (skewed keys)	74.5K
841K	effective N = 10⁴ (skewed keys)	88.5K
917K	effective N = 10⁴ (skewed keys)	105K
1M	effective N = 10⁴ (skewed keys)	125K

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Transactions & Concurrency Control
What happens when many users change the same data at the same time, and how do we keep the result correct?
$L^{2} k^{2} /2 N$
Read it in place →