Line data Source code
1 : #ifndef HEADER_fd_src_flamenco_runtime_fd_txncache_h
2 : #define HEADER_fd_src_flamenco_runtime_fd_txncache_h
3 :
4 : /* A txn cache is a concurrent set storing the message hashes of
5 : transactions which have already executed. Note the structure is
6 : keyed by message hash, not signature, otherwise a double spend might
7 : be possible due to signature malleability.
8 :
9 : The txn cache is designed to do two operations fast,
10 :
11 : (a) Insertion. Insertion is done by both the leader pipeline and
12 : the replay stage, with an insertion for every transaction that
13 : is executed, potentially over 1M per second.
14 :
15 : (b) Query. The leader pipeline queries the status of transactions
16 : before executing them to ensure that it does not execute
17 : anything twice. The replay stage queries to make sure that
18 : blocks do not contain duplicate transactions.
19 :
20 : Queries and inserts on resident pages run concurrently under the
21 : shared lock. A cache miss takes the exclusive lock only to reserve a
22 : frame and reads or writes the spill file without the lock, so it
23 : usually does not stall other threads. After a few failed fetches it
24 : falls back to loading under the exclusive lock, which does.
25 : Structural operations take the exclusive lock. Dirty pages are
26 : written back on eviction.
27 :
28 : The txn cache is somewhat CPU and memory sensitive. To store message
29 : hashes requires 20 bytes (only the first 20 of the 32 bytes of the
30 : hash are used, since this is sufficient to avoid collisions).
31 : Without any other overhead, and 31 unrooted blocks with 41,019
32 : transactions each (the current maximum), the txn cache would need to
33 : store
34 :
35 : 31 * 41,019 * 20 = 0.025 GB
36 :
37 : Of memory. But, we can't query, insert, and remove quickly from a
38 : flat array. We make a few trade-offs to achieve good performance
39 : without bloating memory completely. In particular the transactions
40 : to be queried are stored in a structure that looks like a
41 :
42 : multi_map<blockhash, hash_map<txnhash, vec<fork_idx>>>
43 :
44 : Note that there can be multiple duplicate blockhashes in the map, so
45 : it is a multimap. This is to handle the extremely rare degenerate
46 : case where a leader equivocates a block, but keeps the transactions
47 : the same and just fiddles with the shred data or padding a little
48 : bit. This keeps blockhash the same, but creates a new block ID
49 : (fork). We cannot stick both forks in the same blockhash entry
50 : because later, when one fork is rooted, we need to be able to purge
51 : all transactions in the non-rooted equivocation, otherwise we would
52 : violate our own invariants around the max active banks. (Rooting one
53 : equivocation should fully evict transactions belonging to the other
54 : equivocations, which would be impossible if they were under one
55 : blockhash).
56 :
57 : Both hash maps are chained hash maps, and for the txnhash map items
58 : come from a pool of pages of transactions. We use pages of
59 : transactions to support fast removal of a blockhash from the top
60 : level map.
61 :
62 : This adds additional memory overhead, a blockhash with only one
63 : transaction in it will still consume a full page (16,384) of
64 : transactions of memory. Allocating a new transaction page to a
65 : chained map is rare (once every 16,384 inserts) so the cost amortizes
66 : to zero. Creating a blockhash happens once per blockhash, so also
67 : amortizes to zero, the only operation we care about is then the
68 : simple insert case with an unfull transaction page into an existing
69 : blockhash. This can be done with two compare-and-swaps,
70 :
71 : // 1. Find the blockhash in the probed hash map.
72 :
73 : let by_blockhash = multi_map[ blockhash ];
74 :
75 : // 2. Request space for the transaction from the current page
76 :
77 : let page = by_blockhash.pages.back();
78 : let idx = page.used.compare_and_swap( current, current+1 );
79 :
80 : // 3. Write the transaction into the page and the map
81 :
82 : page.txns[ idx ] = txn;
83 : page.txns[ idx ].next = by_blockhash.txns[ txnhash ].idx;
84 : by_blockhash.txns[ txnhash ].head.compare_and_swap( current, idx );
85 :
86 : Step 1 is fast assuming equivocation is rare, since there will only
87 : ever be one matching blockhash in the multi map.
88 :
89 : Removal of a blockhash from this structure is simple because it does
90 : not need to be concurrent (it is once per slot). We take a write
91 : lock, restore the pages in the blockhash to the pool, and then mark
92 : the space in the hash_map as empty. Page restoration is a simple
93 : memcpy.
94 :
95 : All of this would be complicated by nonce transactions, which can
96 : reference any blockhash, and so a transaction could appear in the
97 : txn cache under any blockhash. But when dealing with these we make
98 : a simple observation: double spend is already cryptographically
99 : prevented by the nonce mechanism itself, so we do not need to store
100 : or check them. Agave does store them for RPC related reasons (they
101 : want to be able to query the status of nonce transactions that have
102 : already executed). It is therefore an error to insert any nonce
103 : transactions into the txn cache, and the caller is responsible for
104 : ensuring this does not happen.
105 :
106 : There is one minor complication with this, which is that Agave
107 : snapshots serve out the status cache with nonce transactions already
108 : in it. This structure assumes these will not get inserted, so it is
109 : up to the snapshot loading code to filter out all blockhashes which
110 : are nonce blockhashes (not in the recent blockhashes sysvar). */
111 :
112 : #include "fd_txncache_shmem.h"
113 : #include "../../util/hist/fd_histf.h"
114 :
115 1500 : #define FD_TXNCACHE_ALIGN (128UL)
116 :
117 : /* 123454 is vote stakes, 123455 is cost tracker, 123456 is epoch
118 : credits, 123457 is stake delegations, 123458/123459 are store,
119 : 123460/123461 are accdb, and 123462+ are reserved by XDP. */
120 :
121 132 : #define FD_TXNCACHE_FD (123453)
122 :
123 : struct fd_txncache_private;
124 : typedef struct fd_txncache_private fd_txncache_t;
125 :
126 : FD_PROTOTYPES_BEGIN
127 :
128 : /* fd_txncache_align gives the needed alignment of the caller-provided
129 : local join region (ljoin). This returns FD_TXNCACHE_ALIGN.
130 :
131 : fd_txncache_footprint gives the needed footprint of the local join
132 : region for a txn cache configured for max_live_slots live slots
133 :
134 : A txn cache uses two backing regions:
135 :
136 : (1) Shared memory region, formatted by fd_txncache_shmem_new and
137 : joined as an fd_txncache_shmem_t * (see
138 : fd_txncache_shmem_{align,footprint}).
139 :
140 : (2) Local join region, formatted by fd_txncache_new and joined via
141 : fd_txncache_join.
142 :
143 : fd_txncache_new formats the caller-provided local join region ljoin
144 : and attaches it to the shared region shmem. Assumes ljoin points to
145 : the first byte of a memory region owned by the caller with suitable
146 : alignment and footprint. Assumes shmem is a valid joined txn cache
147 : shared-memory region (typically from fd_txncache_shmem_join) created
148 : with a matching max_live_slots. Returns ljoin on success and NULL
149 : on failure (logs details). The caller is not joined on return.
150 :
151 : spill_fd is the read/write spill file shared by all joins, opened
152 : with O_DIRECT and kept open by the caller. Pass -1 if the cache is
153 : fully in memory.
154 :
155 : fd_txncache_join joins the caller to a txn cache. Assumes ljoin
156 : points to the first byte of the local join region holding the state.
157 : Returns a local handle to the join on success (this is not
158 : necessarily a simple cast of the address) and NULL on failure (logs
159 : details). */
160 :
161 : FD_FN_CONST ulong
162 : fd_txncache_align( void );
163 :
164 : FD_FN_CONST ulong
165 : fd_txncache_footprint( ulong max_live_slots );
166 :
167 : void *
168 : fd_txncache_new( void * ljoin,
169 : fd_txncache_shmem_t * shmem,
170 : int spill_fd );
171 :
172 : fd_txncache_t *
173 : fd_txncache_join( void * ljoin );
174 :
175 : void
176 : fd_txncache_reset( fd_txncache_t * tc );
177 :
178 : /* fd_txncache_metrics_t holds the txncache's spill and lock metrics.
179 : Counts only grow; *_ticks are in fd_tickcount() units. */
180 :
181 : struct fd_txncache_metrics {
182 : ulong page_miss_cnt;
183 : ulong page_spilled_cnt;
184 : ulong page_spill_read_cnt;
185 : ulong frame_evicted_cnt;
186 : ulong spill_ticks;
187 : ulong lock_read_wait_ticks;
188 : ulong lock_write_wait_ticks;
189 : ulong page_used;
190 : ulong page_capacity;
191 : ulong frame_used;
192 : ulong frame_capacity;
193 : };
194 :
195 : typedef struct fd_txncache_metrics fd_txncache_metrics_t;
196 :
197 : /* fd_txncache_metrics_snap copies the metrics of tc into out without
198 : taking the lock, so values from different fields may be slightly
199 : out of step. */
200 :
201 : void
202 : fd_txncache_metrics_snap( fd_txncache_t const * tc,
203 : fd_txncache_metrics_t * out );
204 :
205 : /* fd_txncache_join_metrics_t holds the metrics of the queries and
206 : inserts made through one join, so each tile can report its own.
207 : Counts only grow. The histograms sample fd_tickcount() durations;
208 : fd_txncache_new formats them with placeholder buckets, which the
209 : tile reformats with its metric's edges before its first query. */
210 :
211 : struct fd_txncache_join_metrics {
212 : ulong query_miss_cnt; /* Queries that found a page not resident. */
213 : ulong insert_miss_cnt; /* Inserts that found a page not resident. */
214 : ulong stalled_cnt; /* Queries and inserts that fell back to the write lock. */
215 : fd_histf_t query_ticks [1]; /* Duration of each query. */
216 : fd_histf_t insert_ticks[1]; /* Duration of each insert. */
217 : };
218 :
219 : typedef struct fd_txncache_join_metrics fd_txncache_join_metrics_t;
220 :
221 : /* fd_txncache_join_metrics returns the metrics of the join tc. */
222 :
223 : fd_txncache_join_metrics_t *
224 : fd_txncache_join_metrics( fd_txncache_t * tc );
225 :
226 : /* FD_TXNCACHE_SNAPIN_STAGE_ALIGN is the alignment of the offsets,
227 : sizes and buffers of fd_txncache_snapin_stage. */
228 :
229 3252 : #define FD_TXNCACHE_SNAPIN_STAGE_ALIGN (4096UL)
230 :
231 : /* fd_txncache_snapin_stage writes (write!=0) or reads sz bytes of buf
232 : at byte offset off of a staging area for snapshot loading. The area
233 : is the txncache's frames, then its spill file, which are unused
234 : between fd_txncache_reset and the first fd_txncache_insert. The
235 : first insert clobbers it. off, sz and buf must be multiples of
236 : FD_TXNCACHE_SNAPIN_STAGE_ALIGN. */
237 :
238 : void
239 : fd_txncache_snapin_stage( fd_txncache_t * tc,
240 : ulong off,
241 : void * buf,
242 : ulong sz,
243 : int write );
244 :
245 : /* fd_txncache_attach_child notifies the txncache that a new child bank
246 : has been created, off some parent. This must be called before any
247 : transaction executed on this child fork is inserted. The parent fork
248 : id must be a fork ID previously returned from attach child, which
249 : must be still valid (the current root bank or a child of it).
250 :
251 : It is assumed that there are less than max_live_slots number of
252 : unrooted (or the active root) banks active prior to calling,
253 : otherwise it is an error.
254 :
255 : Attaching a child takes a write lock on the entire structure, which
256 : is an expensive stall for any other concurrent operations, but it is
257 : OK because the operation is otherwise cheap and it is called rarely
258 : (once every 400ms or so). */
259 :
260 : fd_txncache_fork_id_t
261 : fd_txncache_attach_child( fd_txncache_t * tc,
262 : fd_txncache_fork_id_t parent_fork_id );
263 :
264 : void
265 : fd_txncache_attach_blockhash( fd_txncache_t * tc,
266 : fd_txncache_fork_id_t fork_id,
267 : uchar const * blockhash );
268 :
269 : void
270 : fd_txncache_finalize_fork( fd_txncache_t * tc,
271 : fd_txncache_fork_id_t fork_id,
272 : ulong txnhash_offset,
273 : uchar const * blockhash );
274 :
275 : /* fd_txncache_cancel_fork removes the provided fork and all of its
276 : descendants from the txncache. Forks in the subtree must be
277 : unrooted. Forks in the subtree may or may not have been finalized.
278 : Takes a write lock. */
279 :
280 : void
281 : fd_txncache_cancel_fork( fd_txncache_t * tc,
282 : fd_txncache_fork_id_t fork_id );
283 :
284 : /* fd_txncache_advance_root is called when the root slot of the chain
285 : has advanced, in which case old message hashes (referencing
286 : blockhashes that could no longer be valid) can be removed from the
287 : cache.
288 :
289 : Advancing the root takes a write lock on the structure, which is an
290 : expensive stall for any other concurrent operations, but it is OK
291 : because the operation is otherwise cheap and it is called rarely
292 : (once every 400ms or so). */
293 :
294 : void
295 : fd_txncache_advance_root( fd_txncache_t * tc,
296 : fd_txncache_fork_id_t fork_id );
297 :
298 : /* fd_txncache_insert inserts a transaction hash into the txn cache on
299 : the provided fork. The insert copies data from the hashes and does
300 : not have any lifetime interest in the hashes memory provided once
301 : this call returns.
302 :
303 : Insertion cannot fail, as it is assumed the caller is respecting the
304 : invariants of the structure. If there is no space internally to
305 : insert another transaction, stale entries from removed forks are
306 : purged and the insert retries. If the purge frees nothing the
307 : caller has exceeded the sizing bounds, which logs an error and
308 : exits.
309 :
310 : This is a cheap, high performance, concurrent operation and can occur
311 : at the same time as queries and arbitrary other insertions. */
312 :
313 : void
314 : fd_txncache_insert( fd_txncache_t * tc,
315 : fd_txncache_fork_id_t fork_id,
316 : uchar const * blockhash,
317 : uchar const * txnhash );
318 :
319 : /* fd_txncache_query queries the txncache to determine if the given
320 : txnhash (referencing the given blockhash) exists on the provided fork
321 : or not.
322 :
323 : Returns 1 if the transaction exists on the provided fork and 0 if it
324 : does not.
325 :
326 : This is a cheap, high performance, concurrent operation and can occur
327 : at the same time as queries and arbitrary other insertions. */
328 :
329 : int
330 : fd_txncache_query( fd_txncache_t * tc,
331 : fd_txncache_fork_id_t fork_id,
332 : uchar const * blockhash,
333 : uchar const * txnhash );
334 :
335 : FD_PROTOTYPES_END
336 :
337 : #endif /* HEADER_fd_src_flamenco_runtime_fd_txncache_h */
|
