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