AllocationStrategy Performance

AllocationStrategy Performance#

allocation_strategy_bench evaluates the allocation-routing overhead and behavior of RandomAllocationStrategy and FreeRatioFirstAllocationStrategy across multiple Mooncake Store segments.

Execution#

./mooncake-store/benchmarks/allocation_strategy_bench --workload=dsa

Workload#

The benchmark compares two workload types:

KV-only: a general single-object-size allocation workload without indexer objects. This is used as the non-DSA baseline.
Paired KV+Indexer: a DSA-style workload where KV cache objects and indexer objects are allocated together.
KV cache object size: 3,274,752 B (3.12 MB)
Indexer object size: 658,432 B (643 KB)
Each round samples N uniformly from [1, 128].
In KV-only mode, each round issues N KV allocations.
In paired KV+Indexer mode, each round issues N KV allocations followed by N indexer allocations.
Segment capacity: 1 TB per segment by default.
Segment counts: 1, 2, 4, 8, 16.
Replica counts: 1, 2, 3 when enough segments are available.
On allocation failure, the benchmark randomly evicts 5% of all live objects and retries.
UtilRatio_* is sampled only when eviction is triggered, immediately before evicting objects.

skewed=no uses uniform segment capacity. skewed=yes alternates segment capacity between 1.5x and 0.5x the base capacity.

Summary#

For KV-only, utilization reaches about 96.1%. For the DSA paired KV+indexer workload, both strategies reach about 95.2% utilization. The difference mainly comes from mixed object sizes in the paired workload. RandomAllocationStrategy generally has higher throughput and lower latency, while FreeRatioFirstAllocationStrategy tends to keep segment utilization more balanced.

Result#

KV-only is the non-DSA baseline. It represents the common case where Mooncake Store allocates only one object size.

KV-only / Skewed=no / Random#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198KB	1024.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	1015964	953	231	1132	1694	0.0000	63	1007262/1007262
1	2	3198KB	2048.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	857559	1135	331	1633	2324	0.0001	63	2014525/2014525
2	2	3198KB	2048.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	555934	1767	681	912	4388	0.0000	63	1007262/1007262
1	4	3198KB	4096.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	809246	1204	340	1994	2435	0.0006	63	4029050/4029050
2	4	3198KB	4096.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	503007	1957	772	1002	7545	0.0004	63	2014525/2014525
3	4	3198KB	4096.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	377095	2620	1112	1412	6613	0.0002	63	1343016/1343016
1	8	3198KB	8192.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	751926	1299	351	2124	2534	0.0004	63	8058100/8058100
2	8	3198KB	8192.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	471589	2089	831	1053	7063	0.0002	63	4029050/4029050
3	8	3198KB	8192.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	346496	2855	1203	1513	7133	0.0008	63	2686033/2686033
1	16	3198KB	16384.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	691790	1409	371	2274	2835	0.0003	63	16116200/16116200
2	16	3198KB	16384.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	434370	2271	892	1163	8135	0.0003	63	8058100/8058100
3	16	3198KB	16384.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	322012	3074	1292	1613	8326	0.0006	63	5372067/5372067

KV-only / Skewed=no / FreeRatioFirst#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	Evictions(round)	Succ/Total
1	1	3198KB	1024.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	887098	1096	361	1293	1894	63	1007262/1007262
1	2	3198KB	2048.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	768834	1269	461	1803	2475	63	2014525/2014525
2	2	3198KB	2048.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	499411	1971	882	1152	4219	63	1007262/1007262
1	4	3198KB	4096.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	680538	1438	561	2234	2685	63	4029050/4029050
2	4	3198KB	4096.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	441341	2235	1052	1272	8336	63	2014525/2014525
3	4	3198KB	4096.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	328024	3017	1533	1844	6682	63	1343016/1343016
1	8	3198KB	8192.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	608814	1611	661	2435	2985	63	8058100/8058100
2	8	3198KB	8192.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	387271	2551	1292	1554	5621	63	4029050/4029050
3	8	3198KB	8192.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	295263	3355	1743	2014	7685	63	2686033/2686033
1	16	3198KB	16384.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	571007	1720	671	2645	3186	63	16116200/16116200
2	16	3198KB	16384.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	343893	2876	1503	1773	7825	63	8058100/8058100
3	16	3198KB	16384.0	0.960935	0.960935	0.960935	0.960935	0.960935	0.960935	251734	3941	2124	2524	8346	63	5372067/5372067

KV-only / Skewed=yes / Random#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198KB	1536.0	0.960937	0.960937	0.960937	0.960937	0.960937	0.960937	925104	1050	301	1393	2124	0.0000	63	1510893/1510893
1	2	3198KB	2048.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	846763	1149	331	1693	2354	0.0081	63	2014525/2014525
2	2	3198KB	2048.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	763883	1278	512	741	4468	0.0119	36	1007262/1007262
1	4	3198KB	4096.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	793128	1230	350	2014	2465	0.0078	63	4029050/4029050
2	4	3198KB	4096.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	495155	1988	841	1092	6463	0.0043	63	2014525/2014525
3	4	3198KB	4096.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	442797	2227	1001	1292	6593	0.0116	47	1343016/1343016
1	8	3198KB	8192.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	742956	1315	370	2135	2565	0.0083	63	8058100/8058100
2	8	3198KB	8192.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	449694	2192	912	1162	7835	0.0062	63	4029050/4029050
3	8	3198KB	8192.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	335572	2949	1333	1663	6973	0.0037	63	2686033/2686033
1	16	3198KB	16384.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	680546	1438	381	2295	2876	0.0081	63	16116200/16116200
2	16	3198KB	16384.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	419847	2350	952	1223	8747	0.0069	63	8058100/8058100
3	16	3198KB	16384.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	316027	3133	1403	1714	7764	0.0057	63	5372067/5372067

KV-only / Skewed=yes / FreeRatioFirst#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198KB	1536.0	0.960937	0.960937	0.960937	0.960937	0.960937	0.960937	828717	1176	431	1494	2265	0.0000	63	1510893/1510893
1	2	3198KB	2048.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	770115	1267	461	1774	2465	0.0000	63	2014525/2014525
2	2	3198KB	2048.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	655606	1492	731	981	4649	0.0119	36	1007262/1007262
1	4	3198KB	4096.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	691428	1415	541	2234	2675	0.0000	63	4029050/4029050
2	4	3198KB	4096.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	444332	2219	1062	1323	5570	0.0000	63	2014525/2014525
3	4	3198KB	4096.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	347967	2842	1493	1793	7003	0.0004	54	1343016/1343016
1	8	3198KB	8192.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	611508	1604	661	2445	2976	0.0000	63	8058100/8058100
2	8	3198KB	8192.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	383486	2576	1273	1513	8295	0.0000	63	4029050/4029050
3	8	3198KB	8192.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	292720	3385	1773	2054	7694	0.0000	63	2686033/2686033
1	16	3198KB	16384.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	573570	1712	671	2654	3196	0.0000	63	16116200/16116200
2	16	3198KB	16384.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	346109	2858	1503	1763	9328	0.0000	63	8058100/8058100
3	16	3198KB	16384.0	0.960936	0.960936	0.960936	0.960936	0.960936	0.960936	252816	3924	2144	2495	8496	0.0000	63	5372067/5372067

Paired KV+Indexer is the DSA workload. It allocates two object sizes in the same segment pool.

Paired (KV + Indexer) / Skewed=no / Random#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198+643KB	1024.0	0.952089	0.952089	0.952183	0.952498	0.952621	0.952437	921322	1049	310	1412	2164	0.0000	62	1677285/1677285
1	2	3198+643KB	2048.0	0.952162	0.952162	0.952250	0.952451	0.952627	0.952426	810735	1197	340	1964	2435	0.0001	64	3354570/3354570
2	2	3198+643KB	2048.0	0.952089	0.952089	0.952183	0.952498	0.952621	0.952437	517602	1901	761	1042	5049	0.0000	62	1677285/1677285
1	4	3198+643KB	4096.0	0.952316	0.952316	0.952360	0.952464	0.952611	0.952467	701903	1387	371	2164	3025	0.0003	63	6709139/6709139
2	4	3198+643KB	4096.0	0.952195	0.952195	0.952286	0.952501	0.952607	0.952459	429714	2292	852	1132	5821	0.0005	63	3354570/3354570
3	4	3198+643KB	4096.0	0.952201	0.952201	0.952322	0.952515	0.952627	0.952488	360298	2744	1173	1473	7574	0.0002	63	2236380/2236380
1	8	3198+643KB	8192.0	0.952320	0.952320	0.952351	0.952421	0.952586	0.952428	701440	1389	361	2234	2846	0.0005	63	13418278/13418278
2	8	3198+643KB	8192.0	0.952322	0.952322	0.952345	0.952424	0.952618	0.952449	435206	2266	882	1222	6001	0.0005	63	6709139/6709139
3	8	3198+643KB	8192.0	0.952278	0.952278	0.952318	0.952444	0.952618	0.952456	330833	2991	1272	1574	8035	0.0004	63	4472760/4472760
1	16	3198+643KB	16384.0	0.952246	0.952246	0.952310	0.952412	0.952580	0.952395	643565	1517	380	2534	3196	0.0004	64	26836557/26836557
2	16	3198+643KB	16384.0	0.952338	0.952338	0.952386	0.952448	0.952580	0.952449	405947	2432	942	1313	6803	0.0005	63	13418278/13418278
3	16	3198+643KB	16384.0	0.952169	0.952169	0.952259	0.952434	0.952622	0.952423	313732	3156	1323	1654	9017	0.0005	63	8945519/8945519

Paired (KV + Indexer) / Skewed=no / FreeRatioFirst#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198+643KB	1024.0	0.952089	0.952089	0.952183	0.952498	0.952621	0.952437	823450	1183	431	1584	2344	0.0000	62	1677285/1677285
1	2	3198+643KB	2048.0	0.952172	0.952172	0.952349	0.952462	0.952627	0.952452	740063	1320	472	2084	2575	0.0000	63	3354570/3354570
2	2	3198+643KB	2048.0	0.952089	0.952089	0.952183	0.952498	0.952621	0.952437	470878	2093	982	1242	6462	0.0000	62	1677285/1677285
1	4	3198+643KB	4096.0	0.952345	0.952345	0.952395	0.952481	0.952575	0.952471	659232	1484	551	2305	2785	0.0000	64	6709139/6709139
2	4	3198+643KB	4096.0	0.952323	0.952323	0.952393	0.952493	0.952627	0.952490	429940	2295	1092	1313	7514	0.0000	63	3354570/3354570
3	4	3198+643KB	4096.0	0.952180	0.952180	0.952356	0.952509	0.952606	0.952481	318057	3113	1554	1864	7564	0.0000	63	2236380/2236380
1	8	3198+643KB	8192.0	0.952316	0.952316	0.952349	0.952459	0.952594	0.952455	580198	1692	671	2585	3126	0.0002	64	13418278/13418278
2	8	3198+643KB	8192.0	0.952221	0.952221	0.952316	0.952486	0.952606	0.952450	371743	2659	1332	1593	6593	0.0002	64	6709139/6709139
3	8	3198+643KB	8192.0	0.952215	0.952215	0.952316	0.952470	0.952618	0.952455	282562	3508	1814	2114	8115	0.0000	63	4472760/4472760
1	16	3198+643KB	16384.0	0.952328	0.952328	0.952368	0.952423	0.952570	0.952436	546995	1797	682	2825	3466	0.0000	63	26836557/26836557
2	16	3198+643KB	16384.0	0.952288	0.952288	0.952343	0.952419	0.952589	0.952435	325312	3043	1583	1894	10300	0.0000	63	13418278/13418278
3	16	3198+643KB	16384.0	0.952282	0.952282	0.952355	0.952458	0.952615	0.952453	242750	4088	2245	2585	10350	0.0000	63	8945519/8945519

Paired (KV + Indexer) / Skewed=yes / Random#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198+643KB	1536.0	0.952196	0.952196	0.952295	0.952475	0.952628	0.952470	857346	1135	311	1643	2354	0.0000	63	2515927/2515927
1	2	3198+643KB	2048.0	0.952270	0.952270	0.952310	0.952441	0.952614	0.952444	805462	1210	341	1984	2474	0.0009	63	3354570/3354570
2	2	3198+643KB	2048.0	0.952421	0.952421	0.952443	0.952507	0.952630	0.952517	720532	1357	561	851	5120	0.0004	37	1677285/1677285
1	4	3198+643KB	4096.0	0.952181	0.952181	0.952313	0.952406	0.952634	0.952417	717110	1363	361	2235	2856	0.0001	63	6709139/6709139
2	4	3198+643KB	4096.0	0.952268	0.952268	0.952364	0.952494	0.952617	0.952484	458283	2151	901	1192	5511	0.0051	63	3354570/3354570
3	4	3198+643KB	4096.0	0.952307	0.952307	0.952409	0.952500	0.952630	0.952499	420616	2346	1052	1382	7073	0.0070	48	2236380/2236380
1	8	3198+643KB	8192.0	0.952310	0.952310	0.952340	0.952376	0.952612	0.952405	694136	1410	371	2244	2786	0.0003	64	13418278/13418278
2	8	3198+643KB	8192.0	0.952353	0.952353	0.952384	0.952445	0.952594	0.952456	433396	2276	942	1272	5931	0.0017	63	6709139/6709139
3	8	3198+643KB	8192.0	0.952324	0.952324	0.952357	0.952463	0.952608	0.952456	329256	3006	1363	1673	7003	0.0047	63	4472760/4472760
1	16	3198+643KB	16384.0	0.952264	0.952264	0.952299	0.952343	0.952590	0.952375	641829	1521	381	2565	3256	0.0003	63	26836557/26836557
2	16	3198+643KB	16384.0	0.952246	0.952246	0.952336	0.952423	0.952608	0.952426	399689	2470	1012	1403	6652	0.0011	63	13418278/13418278
3	16	3198+643KB	16384.0	0.952300	0.952300	0.952360	0.952451	0.952606	0.952447	303763	3261	1433	1763	9107	0.0021	63	8945519/8945519

Paired (KV + Indexer) / Skewed=yes / FreeRatioFirst#

Replica	Segments	AllocSize	Cluster(GB)	UtilRatio_min	UtilRatio_p99	UtilRatio_p90	UtilRatio_p50	UtilRatio_max	UtilRatio_avg	Throughput	Avg(ns)	P50(ns)	P90(ns)	P99(ns)	UtilStdDev	Evictions(round)	Succ/Total
1	1	3198+643KB	1536.0	0.952196	0.952196	0.952295	0.952475	0.952628	0.952470	775651	1258	441	1783	2525	0.0000	63	2515927/2515927
1	2	3198+643KB	2048.0	0.952206	0.952206	0.952284	0.952539	0.952758	0.952507	732598	1334	481	2064	2565	0.0000	64	3354570/3354570
2	2	3198+643KB	2048.0	0.952421	0.952421	0.952443	0.952507	0.952630	0.952517	624654	1570	791	1042	5070	0.0004	37	1677285/1677285
1	4	3198+643KB	4096.0	0.952378	0.952378	0.952465	0.952601	0.952898	0.952610	667880	1466	561	2304	2735	0.0000	63	6709139/6709139
2	4	3198+643KB	4096.0	0.952241	0.952241	0.952341	0.952545	0.952758	0.952532	424387	2325	1112	1373	5290	0.0006	64	3354570/3354570
3	4	3198+643KB	4096.0	0.952294	0.952294	0.952346	0.952524	0.952630	0.952503	332752	2974	1543	1864	7164	0.0075	55	2236380/2236380
1	8	3198+643KB	8192.0	0.952463	0.952463	0.952498	0.952691	0.953072	0.952725	584455	1679	671	2576	3116	0.0004	64	13418278/13418278
2	8	3198+643KB	8192.0	0.952329	0.952329	0.952433	0.952605	0.952899	0.952602	371745	2659	1323	1592	9427	0.0000	64	6709139/6709139
3	8	3198+643KB	8192.0	0.952365	0.952365	0.952410	0.952588	0.952800	0.952578	281189	3525	1853	2154	7875	0.0000	63	4472760/4472760
1	16	3198+643KB	16384.0	0.952303	0.952303	0.952374	0.952830	0.953388	0.952796	540381	1814	691	2875	3527	0.0003	64	26836557/26836557
2	16	3198+643KB	16384.0	0.952518	0.952518	0.952539	0.952636	0.953128	0.952681	320795	3086	1603	1974	7744	0.0005	64	13418278/13418278
3	16	3198+643KB	16384.0	0.952450	0.952450	0.952512	0.952592	0.952953	0.952614	240086	4134	2274	2625	10470	0.0000	63	8945519/8945519