-
Notifications
You must be signed in to change notification settings - Fork 1
/
2024-07-24-parallel-evm:-reth.html
403 lines (400 loc) · 18.9 KB
/
2024-07-24-parallel-evm:-reth.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="description" content="This is a personal note for [[https://www.paradigm.xyz/2024/04/reth-perf][Reth-performance-blog]]">
<link rel="alternate"
type="application/rss+xml"
href="https://chenyo.me/rss.xml"
title="RSS feed for https://chenyo.me">
<title>Parallel EVM: Reth scaling plan</title>
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'],['\\(','\\)']]}});
</script>
<meta name="author" content="chenyo">
<meta name="referrer" content="no-referrer">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="assets/style.css" type="text/css"/>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css"/>
<link rel="favicon" type="image/x-icon" href="favicon.ico">
<script src="assets/search.js"></script></head>
<body>
<div id="preamble" class="status">
<header>
<h1><a href="https://chenyo.me">Chenyo's org-static-blog</a></h1>
<nav>
<a href="https://chenyo.me">Home</a>
<a href="archive.html">Archive</a>
<a href="tags.html">Tags</a>
<div id="search-container">
<input type="text" id="search-input" placeholder="Search anywhere...">
<i class="fas fa-search search-icon"></i>
</div>
</nav>
</header></div>
<div id="content">
<div class="post-date">24 Jul 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-07-24-parallel-evm:-reth.html">Parallel EVM: Reth scaling plan</a></h1>
<nav id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org20950c8">1. Blockchain fundamentals</a>
<ul>
<li><a href="#orgf59b06d">1.1. Ethereum engine API</a></li>
<li><a href="#org6a6169c">1.2. Foundry</a></li>
<li><a href="#org97695c9">1.3. Revm</a></li>
<li><a href="#org97ce1ae">1.4. Alloy</a></li>
<li><a href="#org88dd316">1.5. Erigon & Staged sync</a></li>
<li><a href="#org21fc794">1.6. Storage engines</a>
<ul>
<li><a href="#orgf604566">1.6.1. ACID</a></li>
<li><a href="#org737338e">1.6.2. MVCC (Multi-version concurrency control)</a></li>
<li><a href="#orge0cbff7">1.6.3. Common database models</a></li>
<li><a href="#orgceb3dd0">1.6.4. Common storage engines</a></li>
</ul>
</li>
<li><a href="#org6b0a87a">1.7. Reth</a></li>
<li><a href="#org478ab9b">1.8. Why gas per second as the performance metric</a></li>
<li><a href="#org3e971b2">1.9. EVM cost models</a></li>
<li><a href="#orged77b07">1.10. TPC benchmark</a></li>
<li><a href="#org89f5af9">1.11. State growth</a></li>
<li><a href="#orgdf456e7">1.12. JIT (Just-In-Time) and AOT (Ahead-of-Time) EVM</a></li>
<li><a href="#orgf3797a6">1.13. Actor model</a></li>
<li><a href="#orge6bfe92">1.14. Storage trie</a></li>
<li><a href="#org9662699">1.15. Serverless database</a></li>
</ul>
</li>
<li><a href="#orgb4b09e9">2. Reth scaling plan</a>
<ul>
<li><a href="#org1900484">2.1. Vertical scaling (2024)</a>
<ul>
<li><a href="#org61d0655">2.1.1. JIT/AOT EVM</a></li>
<li><a href="#org05122cc">2.1.2. Parallel EVM</a></li>
<li><a href="#org6bffaf9">2.1.3. Optimized state commitment</a></li>
</ul>
</li>
<li><a href="#org266842c">2.2. Horizontal scaling (2025)</a>
<ul>
<li><a href="#org729b06d">2.2.1. Multi-Rollup (?)</a></li>
<li><a href="#orgb4aacf1">2.2.2. Cloud-Native nodes.</a></li>
</ul>
</li>
<li><a href="#org2b8c868">2.3. Open questions</a></li>
</ul>
</li>
</ul>
</div>
</nav>
<p>
This is a personal note for <a href="https://www.paradigm.xyz/2024/04/reth-perf">Reth-performance-blog</a> as well as some terminology explain online, e.g., <a href="https://github.com/paradigmxyz/reth">Reth-repo</a> and <a href="https://claude.ai/chat/6364436f-d279-4c6b-947e-237bfea26409">Claude.ai</a>.
</p>
<div id="outline-container-org20950c8" class="outline-2">
<h2 id="org20950c8"><span class="section-number-2">1.</span> Blockchain fundamentals</h2>
<div class="outline-text-2" id="text-1">
</div>
<div id="outline-container-orgf59b06d" class="outline-3">
<h3 id="orgf59b06d"><span class="section-number-3">1.1.</span> <a href="https://github.com/ethereum/execution-apis/blob/a0d03086564ab1838b462befbc083f873dcf0c0f/src/engine/paris.md">Ethereum engine API</a></h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>A collection of JSON-RPC methods that all execution clients implement.</li>
<li>Specify the interfaces between consensus and execution layers.</li>
</ul>
</div>
</div>
<div id="outline-container-org6a6169c" class="outline-3">
<h3 id="org6a6169c"><span class="section-number-3">1.2.</span> <a href="https://github.com/foundry-rs/foundry/">Foundry</a></h3>
<div class="outline-text-3" id="text-1-2">
<ul class="org-ul">
<li>A Rust-written toolkit for Ethereum application development.</li>
<li>Consists of an Ethereum testing framework Forge; a framework to interact with the chain Cast; a local Ethereum node Anvil; and a Solidity REPL (Read-Eval-Print-Loop: an interactive environment) Chisel.</li>
</ul>
</div>
</div>
<div id="outline-container-org97695c9" class="outline-3">
<h3 id="org97695c9"><span class="section-number-3">1.3.</span> <a href="https://github.com/bluealloy/revm/">Revm</a></h3>
<div class="outline-text-3" id="text-1-3">
<ul class="org-ul">
<li>A Rust-written EVM; responsible for executing transactions and contracts.</li>
</ul>
</div>
</div>
<div id="outline-container-org97ce1ae" class="outline-3">
<h3 id="org97ce1ae"><span class="section-number-3">1.4.</span> <a href="https://github.com/alloy-rs">Alloy</a></h3>
<div class="outline-text-3" id="text-1-4">
<ul class="org-ul">
<li>A library to interact with the Ethereum and other EVM-base chains.</li>
</ul>
</div>
</div>
<div id="outline-container-org88dd316" class="outline-3">
<h3 id="org88dd316"><span class="section-number-3">1.5.</span> <a href="https://erigon.tech/">Erigon</a> & Staged sync</h3>
<div class="outline-text-3" id="text-1-5">
<ul class="org-ul">
<li>Erigon: a Go-written Ethereum client implementation (execution layer).</li>
<li>Staged sync: break the chain synchronization process into distinct stages in order to achieve better efficiency.</li>
</ul>
</div>
</div>
<div id="outline-container-org21fc794" class="outline-3">
<h3 id="org21fc794"><span class="section-number-3">1.6.</span> Storage engines</h3>
<div class="outline-text-3" id="text-1-6">
</div>
<div id="outline-container-orgf604566" class="outline-4">
<h4 id="orgf604566"><span class="section-number-4">1.6.1.</span> ACID</h4>
<div class="outline-text-4" id="text-1-6-1">
<ul class="org-ul">
<li>A set of properties for database transactions: atomicity, consistency, isolation, duration.</li>
<li>Atomicity: a transaction is treated as an indivisible unit; if any part of the transaction fails, the entire transaction is rolled back.</li>
<li>Consistency: a transaction brings the database from one valid state to another.</li>
<li>Isolation: concurrent transaction execution leave the database in the same state as if transactions are executed sequentially</li>
<li>Duration: a committed transaction remains committed even when the system fails.</li>
</ul>
</div>
</div>
<div id="outline-container-org737338e" class="outline-4">
<h4 id="org737338e"><span class="section-number-4">1.6.2.</span> MVCC (Multi-version concurrency control)</h4>
<div class="outline-text-4" id="text-1-6-2">
<ul class="org-ul">
<li>A concurrency control model used in DBMS.</li>
<li>MVCC keeps multiple version of data simultaneously, each transaction sees a snapshot of the database.</li>
</ul>
</div>
</div>
<div id="outline-container-orge0cbff7" class="outline-4">
<h4 id="orge0cbff7"><span class="section-number-4">1.6.3.</span> Common database models</h4>
<div class="outline-text-4" id="text-1-6-3">
<ul class="org-ul">
<li>Relational model, e.g., SQL.</li>
<li>Document model.</li>
<li>Network model.</li>
<li>key-value, e.g., NoSQL.</li>
</ul>
</div>
</div>
<div id="outline-container-orgceb3dd0" class="outline-4">
<h4 id="orgceb3dd0"><span class="section-number-4">1.6.4.</span> Common storage engines</h4>
<div class="outline-text-4" id="text-1-6-4">
<ul class="org-ul">
<li>MDBX: Ultra-fate key-value embedded database with ACID and MVCC supported.</li>
<li>LevelDB: Google-developed key-value store using log-structured merge-tree for high write throughput.</li>
<li>RocksDB: Meta’s fork of LevelDB, optimized for fast storage.</li>
<li>LSM-based DBs, e.g., BadgerDB: optimized for write-heavy workloads with log-structured merge-tree.</li>
<li>BoltDB: Go-written key-value database with optimized B+ tree, ACID supported.</li>
<li>LMDB: memory-mapped key-value store with ACID and MVCC supported.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org6b0a87a" class="outline-3">
<h3 id="org6b0a87a"><span class="section-number-3">1.7.</span> Reth</h3>
<div class="outline-text-3" id="text-1-7">
<ul class="org-ul">
<li>A Rust implementation of an Ethereum full node; allows users to interact with the Ethereum blockchain.</li>
<li>An execution layer that implements all Ethereum engine APIs.</li>
<li>Modularity: every component is built as a library.</li>
<li>Performance: uses Erigon staged-sync node architecture and other Rust libraries (e.g., Alloy, revm); tests and optimizes on Foundry.</li>
<li>Database/Storage engine: MDBX.</li>
</ul>
</div>
</div>
<div id="outline-container-org478ab9b" class="outline-3">
<h3 id="org478ab9b"><span class="section-number-3">1.8.</span> Why gas per second as the performance metric</h3>
<div class="outline-text-3" id="text-1-8">
<ul class="org-ul">
<li>More nuanced than TPS.</li>
<li>Allows for a clear understanding for the capacity and efficiency.</li>
<li>Helps assessing the cost implications, e.g., DoS attacks.</li>
</ul>
</div>
</div>
<div id="outline-container-org3e971b2" class="outline-3">
<h3 id="org3e971b2"><span class="section-number-3">1.9.</span> EVM cost models</h3>
<div class="outline-text-3" id="text-1-9">
<ul class="org-ul">
<li>Determines the computational and storage costs for the execution.</li>
<li>Key aspects: gas, gas cost (for each operation), gas price (in Wei), gas limit.</li>
</ul>
</div>
</div>
<div id="outline-container-orged77b07" class="outline-3">
<h3 id="orged77b07"><span class="section-number-3">1.10.</span> TPC benchmark</h3>
<div class="outline-text-3" id="text-1-10">
<ul class="org-ul">
<li>Standardized performance tests for transaction processing and databases, e.g., how many transactions a system can process in a given period.</li>
<li>Offer benchmarks for different scenarios, e.g., TPC-C for online transaction processing.</li>
</ul>
</div>
</div>
<div id="outline-container-org89f5af9" class="outline-3">
<h3 id="org89f5af9"><span class="section-number-3">1.11.</span> State growth</h3>
<div class="outline-text-3" id="text-1-11">
<ul class="org-ul">
<li>State: the set of data for building and validating new Ethereum blocks.</li>
<li>State growth: the accumulation of new account and new contract storage.</li>
</ul>
</div>
</div>
<div id="outline-container-orgdf456e7" class="outline-3">
<h3 id="orgdf456e7"><span class="section-number-3">1.12.</span> JIT (Just-In-Time) and AOT (Ahead-of-Time) EVM</h3>
<div class="outline-text-3" id="text-1-12">
<ul class="org-ul">
<li>JIT: convert bytecode to native machine code just before execution to bypass the VM’s interpretative process.</li>
<li>AOT: compile the highest demand contracts and store them on disk, to avoid untrusted bytecode absuing native-code compilation.</li>
</ul>
</div>
</div>
<div id="outline-container-orgf3797a6" class="outline-3">
<h3 id="orgf3797a6"><span class="section-number-3">1.13.</span> Actor model</h3>
<div class="outline-text-3" id="text-1-13">
<ul class="org-ul">
<li>A paradigm/framework for designing distributed systems.</li>
<li>Actor: each actor is an independent entity to receive, process and send messages; create new actors or modify its state.</li>
</ul>
</div>
</div>
<div id="outline-container-orge6bfe92" class="outline-3">
<h3 id="orge6bfe92"><span class="section-number-3">1.14.</span> Storage trie</h3>
<div class="outline-text-3" id="text-1-14">
<ul class="org-ul">
<li>Each contract account has its own storage trie, which is usually stored in a KV database.</li>
</ul>
</div>
</div>
<div id="outline-container-org9662699" class="outline-3">
<h3 id="org9662699"><span class="section-number-3">1.15.</span> Serverless database</h3>
<div class="outline-text-3" id="text-1-15">
<ul class="org-ul">
<li>Allow developers to focus on writing queries without managing database servers.</li>
<li>Automatically scales up or down base on the workload.</li>
<li>Pay-per-use pricing.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-orgb4b09e9" class="outline-2">
<h2 id="orgb4b09e9"><span class="section-number-2">2.</span> Reth scaling plan</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Current status (April 2024): achieves 100-200 mg/s during live sync, including sender recovery, transaction execution and block trie calculation.</li>
<li>The scaling plan does not involve solving state growth.</li>
</ul>
</div>
<div id="outline-container-org1900484" class="outline-3">
<h3 id="org1900484"><span class="section-number-3">2.1.</span> Vertical scaling (2024)</h3>
<div class="outline-text-3" id="text-2-1">
<ul class="org-ul">
<li>Optimize how each system handle transactions and data.</li>
</ul>
</div>
<div id="outline-container-org61d0655" class="outline-4">
<h4 id="org61d0655"><span class="section-number-4">2.1.1.</span> JIT/AOT EVM</h4>
<div class="outline-text-4" id="text-2-1-1">
<ul class="org-ul">
<li>Reduce EVM interpreter overhead to speed up single-threaded transaction processing.</li>
<li>The processing costs \(\approx\) 50% EVM time</li>
<li>Released on <a href="https://www.paradigm.xyz/2024/06/revmc">June 2024</a>.</li>
</ul>
<figure id="org2993c7d">
<img src="https://www.paradigm.xyz/static/reth-perf/3.png" alt="3.png" align="center" width="500px">
<figcaption><span class="figure-number">Figure 1: </span>The JIT/AOT compiler (<a href="https://www.paradigm.xyz/static/reth-perf/3.png">source</a>)</figcaption>
</figure>
</div>
</div>
<div id="outline-container-org05122cc" class="outline-4">
<h4 id="org05122cc"><span class="section-number-4">2.1.2.</span> Parallel EVM</h4>
<div class="outline-text-4" id="text-2-1-2">
<ul class="org-ul">
<li>Utilize multiple cores during EVM execution.</li>
<li><80% of historical transactions have non-conflicting dependencies.</li>
<li>Historical sync: can calculate the best parallelization schedule offline; an early attempt is <a href="https://github.com/paradigmxyz/reth/tree/rkrasiuk/parallel">available</a>.</li>
<li>Live sync: combine serial and parallel execution based on static analysis, since Block STM has poor performance during heavy state contention periods; an early attempt is <a href="https://github.com/risechain/pevm">available</a>.</li>
</ul>
</div>
</div>
<div id="outline-container-org6bffaf9" class="outline-4">
<h4 id="org6bffaf9"><span class="section-number-4">2.1.3.</span> Optimized state commitment</h4>
<div class="outline-text-4" id="text-2-1-3">
<ul class="org-ul">
<li>Traditional EVM implementation <b><b>couples</b></b> the transaction execution and the state root computation: the state root is updated whenever a transaction updates a trie, since the state root computation has to be sequential from the updated node to the root, this is slow.</li>
<li>Reth <b><b>decouples</b></b> the process: raw state data is stored in KV databases, and each trie is <b><b>re-built</b></b> for each block from the databases in the end.
<ul class="org-ul">
<li>Pro: can use more efficient databases.</li>
<li>Con: need to re-calculate the entire trie, which costs >75% of end-to-end block production time.</li>
</ul></li>
<li>Optimizations:
<ul class="org-ul">
<li>Now already re-calculate the storage trie for each updated contract in parallel.</li>
<li>Can also calculate the account trie when the storage tries are computed.</li>
<li>Pre-fetch cached trie nodes (cached by the state root computation) by tracking updated accounts and storage, e.g., a part of the trie may remain the same hash.</li>
</ul></li>
<li>Going beyond:
<ul class="org-ul">
<li>Only calculate the state root every \(T\) blocks.</li>
<li><b><b>Lag</b></b> the state root computation a few blocks behind to advance executions.</li>
<li>Use a cheaper encoder and hash function (Blake3).</li>
<li>Use wider branch nodes.</li>
</ul></li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org266842c" class="outline-3">
<h3 id="org266842c"><span class="section-number-3">2.2.</span> Horizontal scaling (2025)</h3>
<div class="outline-text-3" id="text-2-2">
<ul class="org-ul">
<li>Spread the workload across multiple systems.</li>
</ul>
</div>
<div id="outline-container-org729b06d" class="outline-4">
<h4 id="org729b06d"><span class="section-number-4">2.2.1.</span> Multi-Rollup (?)</h4>
<div class="outline-text-4" id="text-2-2-1">
<ul class="org-ul">
<li>Reduce operational overhead of running multiple rollups.</li>
</ul>
</div>
</div>
<div id="outline-container-orgb4aacf1" class="outline-4">
<h4 id="orgb4aacf1"><span class="section-number-4">2.2.2.</span> Cloud-Native nodes.</h4>
<div class="outline-text-4" id="text-2-2-2">
<ul class="org-ul">
<li>Deploy the heavy node (e.g., sequencer) as a service stack that can autoscale with compute demand and use cloud storage for persistence.</li>
<li>Similar to serverless database projects, e.g., NeonDB.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org2b8c868" class="outline-3">
<h3 id="org2b8c868"><span class="section-number-3">2.3.</span> Open questions</h3>
<div class="outline-text-3" id="text-2-3">
<ul class="org-ul">
<li>Second order effects of above changes, e.g., on light clients.</li>
<li>What is the best, average and worst case scenarios for each optimization.</li>
</ul>
</div>
</div>
</div>
<div class="taglist"><a href="https://chenyo.me/tags.html">Tags</a>: <a href="https://chenyo.me/tag-evm.html">evm</a> <a href="https://chenyo.me/tag-parallel-evm.html">parallel-evm</a> <a href="https://chenyo.me/tag-reth.html">reth</a> </div></div>
<div id="postamble" class="status"><div id="search-results"></div>
<footer>
<div class="footer-content">
<div class="footer-left">
<p>© 2024 chenyo. Some rights reserved.</p>
<a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width: 0"
src="https://i.creativecommons.org/l/by-nc/4.0/88x31.png"/>
</a>
</div>
<div class="social-links">
<a href="https://t.me/chenyo17" target="_blank" rel="noopener noreferrer">
<i class="fab fa-telegram"></i>
</a>
<a href="https://github.com/chenyo-17" target="_blank" rel="noopener noreferrer">
<i class="fab fa-github"></i>
</a>
</div>
</footer></div>
</body>
</html>