Performance measurements of Radix History

[hilltracer]

Overview

RSpace data is stored as a collection of key-value pairs (tuple space). For each distinct state of this collection we should be able to calculate a hash to uniquely define it and to provide a way to verify the integrity of the data.

Implementation of Merkle-Patricia Trie is used for this purpose in RNode (currently v0.10.2) written in class. It's implementation of History interface with two basic operations, to update (process) and read key-value pairs.

rchain/rspace/src/main/scala/coop/rchain/rspace/history/History.scala

Lines 12 to 17 in a9c0f7d

	trait History[F[_]] {
	def process(actions: List[HistoryAction]): F[History[F]]
	def root: Blake2b256Hash
	def find(key: KeyPath): F[(TriePointer, Vector[Trie])]
	def reset(root: Blake2b256Hash): History[F]
	}

In its core it's a Radix Tree structure that enables storing keys in a tree with branch nodes representing common key prefixes and with leaf nodes holding values. Each node has a key which is hash of its children nodes (references).

Test conditions

• System parameters: CPU - AMD Ryzen™ 7 3700U, RAM - 16GB DDR4, SSD - M.2 PCIe 3.0x2
• Java heap size 2048MB
• Average - 10 experiences
• WarmUp - 10 first experiences
• Data sets - random (Identical in all experiments)

Comparative testing of different implementations of History

This chapter provides information about performance of insert, read, delete operations and database size. Below are the comparative results of testing 3 implementations of history:

• previous implementation MergingHistory;
• new implementation RadixHistory with scodec for serializing data in KVDB;
• new implementation RadixHistory with manual codec for serializing data in KVDB.

The following code was used for testing.

LMDB was used for data storage in time comparison tests.

InMemoryKeyValueStore was used for data storage in data size comparison tests.

numInit	numIRD	timeI(sec)	timeR(sec)	timeD(sec)	size(MB)	num
MergingHistory
1	300	1.409	0.086	0.385	0.05	389
1	1000	8.483	0.296	0.833	0.159	1245
1	5000	36.554	1.61	5.451	0.699	5450
1	10000	73.577	3.231	14.055	1.405	10972
1	30000	234.569	11.983	66.003	4.512	35373
RadixHistoryScodec
1	300	0.018	0.012	0.004	0.045	87
1	1000	0.025	0.018	0.004	0.136	244
1	5000	0.062	0.045	0.013	0.443	449
1	10000	0.145	0.103	0.035	0.906	967
1	30000	0.719	0.531	0.098	3.465	5355
RadixHistoryManualCodec
1	300	0.009	0.007	0.004	0.024	87
1	1000	0.009	0.006	0.005	0.076	244
1	5000	0.032	0.015	0.014	0.333	449
1	10000	0.055	0.043	0.029	0.67	967
1	30000	0.137	0.213	0.085	2.158	5355

Where

• numInit - initial number of records;
• numIRD - number of Insert Read and Delete records;
• timeI - insert time;
• timeR - read time;
• timeD - delete time;
• size - size of serialized Data in KVDB after insert
• num - number of nodes in KVDB after insert.

RadixHistory perfomance testing

Below are the results of testing implementations of RadixHistory.
A manually created codec is used to serialize the data.

The following code used for testing.
LMDB used as KVDB

numInit	numIRD	timeI(sec)	timeR(sec)	timeD(sec)
1	100000	0.758	0.788	0.45
1	200000	1.629	1.627	0.793
1	300000	2.494	2.389	1.416
1	400000	3.297	3.319	2.022
1	500000	4.671	4.161	2.494
1	600000	4.943	4.753	2.936
1	700000	5.225	5.391	3.594
1	800000	6.263	6.519	4.611
100000	100000	1.333	1.134	0.687
200000	100000	1.627	1.426	0.953
300000	100000	1.915	1.335	1.091
400000	100000	2.461	1.482	1.23
500000	100000	2.536	2.11	1.21
600000	100000	2.797	1.868	1.391
700000	100000	3.05	2.003	1.437
800000	100000	3.498	2.177	1.367

InMemoryKeyValueStore used as KVDB

numInit	numIRD	timeI(sec)	timeR(sec)	timeD(sec)	size(MB)	num
1	100000	0.7	0.692	0.373	7.916	29991
1	200000	1.561	1.309	0.756	15.446	54383
1	300000	2.185	2.244	1.316	22.096	64713
1	400000	2.926	2.747	1.709	28.397	69461
1	500000	3.525	3.964	2.358	34.609	72789
1	600000	3.884	4.097	2.891	40.822	76151
1	700000	4.697	4.793	3.132	47.06	79913
1	800000	5.08	5.674	4.016	53.331	84216

• numInit - initial number of records;
• numIRD - number of Insert Read and Delete records;
• timeI - insert time;
• timeR - read time;
• timeD - delete time;
• size - size of serialized Data in KVDB after insert;
• num - number of nodes in KVDB after insert.

Rnode testing (time performance)

We measured the size of the KVDB when we do 1000 deploys to Rnode. In the tests was compared two history implementations RadixHistory and MergingHistory.
List of modifications: Rnode works in memory. Rnode calculates size HistoryStore and returns this size in a log.
I ran Rnode in server as -standalone.
1000 deploys were created with the help of this python script

InMemoryKeyValueStore was used for data storage.

numDeploy	numNodes	sizeBytes	SizeMBytes	getCasperSnapshot (ms)	Create block (sec)	Replay block (sec)
RadixHistory
1	333	135958	0.1296596527	898	5.213935903	5.31701022
50	28919	61218201	58.38222599	448	4.006487815	4.333984095
100	76870	178894191	170.6067953	442	4.024983608	4.452010829
150	133716	311213257	296.7960901	489	4.181056331	4.78762488
200	194785	445742554	425.0932255	564	4.295921479	4.566550113
250	257761	579964786	553.0975208	560	4.40327212	4.52766222
300	321867	714312775	681.2217474	527	4.570871722	4.573860563
350	386501	849331529	809.9856653	626	4.590563634	4.54477788
400	451486	985782635	940.1155806	608	4.727267761	5.06983236
450	516816	1124234526	1072.153593	612	4.851073458	4.92934653
500	582356	1264633412	1206.048405	662	4.911088257	5.01573993
550	648026	1407211961	1342.021905	667	5.101803642	4.935184441
600	713804	1552265280	1480.35553	702	5.12896105	4.826301481
650	779755	1699445794	1620.717806	792	5.513805169	5.080979882
700	845820	1849009836	1763.353191	837	5.725439136	5.017994516
750	912118	2001331023	1908.617995	871	5.664018249	4.966611148
800	978604	2155973612	2056.096661	780	5.751871885	5.410526619
850	1045217	2312919341	2205.771771	737	5.937163427	6.054588751
900	1111970	2472269244	2357.739681	811	5.821930881	5.430252412
950	1178946	2634091886	2512.065779	824	6.399846666	5.380402995
1000	1245921	2798153938	2668.527544	845	6.183092196	5.843893294
MergingHistory
1	1861	257983	0.2460317612	913	8.633424697	8.068113819
50	93382	43417091	41.40576458	492	12.3342373	11.55016777
100	210885	129334535	123.3430243	544	14.84952942	13.60213798
150	333698	235121949	224.229764	649	15.80018404	14.2549839
200	456126	350803198	334.552	635	15.93214928	14.46560647
250	577238	471258232	449.4268723	696	15.79293897	14.07592433
300	697176	594434128	566.8965607	742	16.04548792	14.51033416
350	816242	719522303	686.1899405	918	16.53316916	13.82392244
400	935031	846554931	807.3376951	853	16.67378375	14.1185086
450	1053680	974907685	929.7444201	1150	16.62674194	14.82801764
500	1172598	1104550820	1053.381748	1020	17.52218625	14.46831574
550	1291745	1235652858	1178.410395	1125	17.31175249	14.4760636
600	1411043	1367945894	1304.574865	1068	17.9896305	14.50443867
650	1530500	1501437483	1431.882365	1289	18.06528749	14.84892837
700	1650411	1636568041	1560.752908	1340	18.34164365	15.04995655
750	1770746	1772923311	1690.791427	1258	18.53563859	15.43667642
800	1891068	1910278225	1821.78328	1050	18.21596493	15.36664238
850	2011902	2049229018	1954.297083	1242	18.51381443	15.4988917
900	2132885	2189218734	2087.80168	1138	18.82523492	16.53567935
950	2254366	2330647558	2222.678717	1169	19.08319625	15.81443598
1000	2375965	2473176936	2358.605324	1378	19.31733215	15.85080131

Rnode testing (LFS and database size)

In the tests was compared two history inplementations RadixHistory and MergingHistory.
InMemoryKeyValueStore was used for data storage.

Sequentially doing 1000 deploy with the help of this python script.

			All database size			LFS size
numDeploy	numNodes	sizeBytes	SizeMBytes	numNodes	sizeBytes	SizeMBytes
RadixHistory
50	29007	61486611	58.63820171	12644	4131731	3.940325737
100	76983	179146268	170.8471947	30998	8589516	8.1916008
150	133725	311812794	297.3678532	45462	12785667	12.19336224
200	194779	446814354	426.1153736	55325	16678443	15.90580273
250	257896	581436547	554.5011015	61553	20332879	19.39094448
300	322002	715549070	682.4007702	65638	23846998	22.74226952
350	386740	850650932	811.2439461	68345	27270958	26.00761223
400	451828	987242624	941.5079346	70482	30657538	29.23730659
450	517121	1125510458	1073.370417	72346	34026119	32.44983578
500	582627	1265799464	1207.160439	74087	37386563	35.65460491
550	648207	1408290651	1343.050624	75802	40745165	38.85761738
600	713936	1553121855	1481.172423	77627	44110760	42.06729889
650	779897	1700405742	1621.633284	79602	47485891	45.28607464
700	845963	1850235437	1764.522016	81686	50867991	48.51149654
750	912261	2002318574	1909.559797	83941	54260996	51.74731827
800	978695	2157199685	2057.265935	86286	57659765	54.98863697
850	1045260	2314183006	2206.976896	88767	61067214	58.23823357
900	1112025	2473713825	2359.117341	91436	64486685	61.49929523
950	1178826	2635482601	2513.392068	94136	67908134	64.76224327
1000	1245718	2799351276	2669.669415	97005	71340405	68.03551197
MergingHistory
50	93184	43409463	41.39848995	64556	8609942	8.211080551
100	210879	129365892	123.3729286	134349	17867715	17.03998089
150	333894	235001532	224.1149254	200512	26653778	25.41902351
200	456207	350228011	334.003459	261812	34814649	33.20183659
250	577100	470346744	448.5576096	319573	42520294	40.55051231
300	696757	593524000	566.028595	375110	49940123	47.62661266
350	815911	718849887	685.5486746	429456	57206289	54.55616856
400	934690	845691588	806.5143471	483109	64383290	61.40069008
450	1053465	974173348	929.0441017	536491	71525404	68.21194077
500	1172293	1103783287	1052.649772	589777	78654890	75.01114845
550	1291354	1235041506	1177.827364	643092	85787855	81.81367397
600	1410415	1367156217	1303.821771	696405	92920156	88.61556625
650	1529991	1500967034	1431.43371	749912	100077165	95.44102192
700	1649971	1635964165	1560.177007	803622	107259654	102.2907772
750	1770183	1772413849	1690.305566	857433	114455024	109.1528168
800	1890549	1909964776	1821.484352	911306	121658610	116.0226917
850	2011400	2048947286	1954.028402	965407	128890946	122.9199848
900	2132383	2189072853	2087.662557	1019589	136133103	129.8266439
950	2253721	2330240068	2222.290104	1073953	143398688	136.7556458
1000	2375372	2472981432	2358.418877	1128466	150683141	143.7026415

Below is the data on the number of nodes in the database at the moment.

Below is the data on the number of nodes in the LFS of the current block.

Below is the data on database size at the moment.

Below is the data on the size of the LFS of the current block.

Below is the data on the number of nodes in the LFS vs the number of nodes in the database.

Below is the data on the size of the LFS vs on database size.

Rnode testing (History data compression experiments)

We tested this history with and without compression.

BlockNumber	No compression (MB)	Compression (MB)
50	58.63820171	59.09181118
100	170.8471947	172.6651392
150	297.3678532	300.3029089
200	426.1153736	429.5011892
250	554.5011015	558.4797096
300	682.4007702	687.5497265
350	811.2439461	817.1383886
400	941.5079346	948.1761875
450	1073.370417	1080.934837
500	1207.160439	1215.424046
550	1343.050624	1352.111368
600	1481.172423	1491.250567
650	1621.633284	1632.774341
700	1764.522016	1776.637619
750	1909.559797	1922.72753
800	2057.265935	2071.091148
850	2206.976896	2221.55691
900	2359.117341	2374.472316
950	2513.392068	2529.759994
1000	2669.669415	2687.387953