Line data Source code
1 : #ifndef HEADER_fd_src_discof_rotor_fd_rotor_tile_h
2 : #define HEADER_fd_src_discof_rotor_fd_rotor_tile_h
3 :
4 : #include "../../disco/tiles.h"
5 : #include "../../disco/shred/fd_shred_tile.h"
6 :
7 : /* Rotor OUTPUTS
8 :
9 : Rotor tile forwards FECs in replay order to replay tile with sig
10 : ROTOR_SIG_FEC_REPLAY.
11 :
12 : However since rotor is a direct drop in for repair tile, we have to make
13 : sure the sigs do not clobber the repair tile's sigs.
14 :
15 : See fd_repair_tile.h
16 : #define REPAIR_SIG_FEC_INVALID (2UL)
17 : #define REPAIR_SIG_FEC_LEADER (1UL)
18 : #define REPAIR_SIG_FEC (0UL)
19 :
20 : FECs are delivered in replay order. Blocks that were not repaired
21 : through verified (i.e., received through turbine) means are delivered
22 : with block_id = {0} until the last FEC in the block, in which the
23 : block_id is set to the computed DMR of the previously delivered FECs.
24 :
25 : Blocks that were repaired through verified means (i.e. using ag block
26 : id repair from a votor event) know the block_id immediately before
27 : the first FEC is delivered, so the block_id on the FECs of this slot
28 : is set to the correct value starting from fec 0. For these blocks,
29 : the verified bit is 1.
30 :
31 : A slot's turbine version (the eager blk, keyed {slot, 0} by replay)
32 : and its votor-driven versions (notar blks, keyed {slot, block_id})
33 : coexist, each delivered as its FECs complete. FEC sets with the
34 : same merkle root are shared between versions. When the turbine
35 : version completes and its DMR matches a notar blk, the notar blk is
36 : merged into it and freed (see dedup in fd_rotor.c). So in time of
37 : network blips replay may allocate two banks for the same block; the
38 : notar one never completes and is eventually evicted or pruned.
39 :
40 : INPUTS: REPLAY
41 :
42 : Rotor tile consumes from replay tile the sigs
43 : REPLAY_SIG_ROOT_ADVANCED, REPLAY_SIG_SLOT_DEAD and
44 : REPLAY_SIG_MISSING_FEC. REPLAY_SIG_SLOT_DEAD frees the dead blk; if
45 : it was the turbine version, turbine does not rebuild it.
46 :
47 : Pruning:
48 :
49 : Rooting is not done off of votor rooting messages, but by replay root
50 : advance updates. Consider the following case:
51 :
52 : The cluster is having trouble rooting, and so we have a long chain of
53 : unfinalized slots. Banks begins to evict arbitrarily. It evicts slot
54 : N and begins executing down a different fork, but then soon after a
55 : finalization arrives for slot N.
56 :
57 : Replay tile updates its consensus root, but can't advance to it yet,
58 : because the bank for it has not been executed. Rotor never evicts a
59 : blk, and thus could root from the finalized message immediately.
60 : This is clearly a problem; replay needs the consensus root data
61 : re-delivered for execution, so rotor cannot immediately prune based
62 : on the finalized message.
63 :
64 : Instead replay already does its own bookkeeping. It has a highest
65 : known consensus root, a storage root that is the earliest slot data
66 : maintained, and a notified root that is the highest consensus root
67 : that replay verifies is live and can't be evicted.
68 :
69 : Rotor can safely assume anything below the notified root is no longer
70 : needed.
71 :
72 : Eviction:
73 :
74 : Replay can evict leaf banks at will, without rotor's knowledge. This
75 : means rotor may continue deliverying down a lineage that banks cannot
76 : immediately replay, since it has evicted an ancestor. When that
77 : occurs, replay should drain the rotor in-link dcache and send a
78 : REPLAY_SIG_MISSING_FEC to rotor. Rotor then sends it's next FEC set
79 : with the full lineage starting from the rotor root. It does this
80 : only for the next FEC set to deliver. If repeated evictions occur,
81 : rotor can expect repeated REPLAY_SIG_MISSING_FEC messages to arrive,
82 : and many redundant FECs to be delivered.
83 :
84 : We assume currently that rotor will not require eviction. The
85 : default size is bounded to the Agave cap on future certs it tracks.
86 : We can bound rotor even tighter once dynamic vote timeouts are
87 : implemented, and thus rotor should always have all the data replay
88 : needs.
89 :
90 : INPUTS: NET
91 :
92 : Alpenglow introduces three new repair types: ShredForBlockId,
93 : ParentAndFecCount, and FecRoot. ShredForBlockId response type is a
94 : regular shred, similar to the legacy repair types, so those responses
95 : get routed through the shred tile and are matched by nonce for
96 : verification.
97 :
98 : ParentAndFecCount and FecRoot response types are metadata, not
99 : regular shreds. Thus the net tile routes them directly to the rotor
100 : tile. The routing is done entirely by packet size, so rotor tile
101 : filters and validates aggressively. The responses are matches by
102 : nonce and verified before being ingested by the rotor. */
103 :
104 : /* keep in line with repair tile sigs */
105 : #define REPAIR_SIG_FEC (0UL)
106 : #define REPAIR_SIG_FEC_LEADER (1UL)
107 : #define REPAIR_SIG_FEC_INVALID (2UL)
108 : /* alpenglow type - replayable fec */
109 0 : #define ROTOR_SIG_FEC_REPLAY (3UL)
110 : /* alpenglow type - completed block metadata, on rotor_rserve */
111 0 : #define ROTOR_SIG_BLOCK (4UL)
112 :
113 : struct fd_rotor_fec_metrics {
114 : uint stats_valid; /* 1 if the counters below are populated */
115 :
116 : /* 1 if the FEC was delivered under a votor-driven version of its slot
117 : -- one the rotor created from a cert and filled by block id
118 : repair -- and 0 if it was delivered under the slot's turbine
119 : version, our own leader blocks included. */
120 : uchar votor_repaired;
121 :
122 : uint blk_turbine_cnt; /* block: data shreds received via turbine, plus every coding shred */
123 : uint blk_repair_cnt; /* block: data shreds received via repair */
124 : uint blk_recovered_cnt; /* block: shreds recovered via reed-solomon */
125 : uint blk_data_cnt; /* block: data shreds held */
126 : uint blk_parity_cnt; /* block: coding shreds received */
127 : uchar blk_slot_complete; /* block: 1 if the end of the block is known */
128 : uint blk_last_completed_fec_idx; /* block: fec_set_idx of the set that most recently completed reception, UINT_MAX if none */
129 :
130 : uint blk_req_window_cnt; /* block: positional specific-shred requests sent */
131 : uint blk_req_highest_cnt; /* block: highest-shred requests sent */
132 : uint blk_req_orphan_cnt; /* block: orphan requests sent */
133 : uint blk_req_shred_bid_cnt; /* block: ShredForBlockId requests sent */
134 : uint blk_req_parent_cnt; /* block: ParentAndFecCount requests sent */
135 : uint blk_req_fec_root_cnt; /* block: FecRoot requests sent */
136 : uint blk_req_retransmit_cnt; /* block: requests re-issued after a timeout or bad response */
137 : uint blk_repair_responses; /* block: repair responses matched to an outstanding request */
138 :
139 : ulong blk_first_shred_ts_nanos; /* block: when the first shred arrived, 0 if never stamped */
140 : ulong blk_last_shred_ts_nanos; /* block: when the block became contiguous, 0 if it has not */
141 : ulong blk_first_req_ts_nanos; /* block: when the first specific-shred repair request was sent, 0 if none */
142 : ulong blk_last_repair_resp_ts_nanos; /* block: when the most recent matched repair response arrived, 0 if none */
143 :
144 : long fec_completed_ts_nanos; /* this FEC: network arrival (wallclock ns) of the shred that completed it, 0 if unavailable */
145 :
146 : /* Highest slot rotor has completed a FEC set for off the network, our
147 : own leader FEC sets excluded: the cluster tip. Not a per-block
148 : figure like the rest of these metrics. */
149 : ulong highest_fec_complete_slot;
150 : };
151 : typedef struct fd_rotor_fec_metrics fd_rotor_fec_metrics_t;
152 :
153 : struct fd_rotor_replay_fec {
154 : ulong slot;
155 : uint fec_set_idx;
156 : fd_hash_t mr;
157 :
158 : /* conditional fields */
159 :
160 : ulong parent_slot; /* only present if fec_set_idx is 0 or has
161 : parentUpdate. TBD, could also just have
162 : replay do parent reparsing */
163 : fd_hash_t parent_block_id;
164 :
165 : int slot_complete;
166 : int data_complete;
167 : int is_leader;
168 :
169 : /* known_id. This is not the same as slot_complete = 1. known_id
170 : should be set always to 1 if the block id was known from the
171 : start, i.e. these FECs were recovered through block_id repair of a
172 : votor event. known_id should be 0 always for blocks that were received
173 : through turbine.
174 :
175 : In other words, known_id is a keying instruction, not a statement about whether the block id is known:
176 : - known_id set: Replay keys the block by {slot, block_id} starting at FEC 0 and looks up its parent element by that key for every later FEC.
177 : - known_id clear: the block is a turbine version. Replay keys it by {slot, 0} until it processes the slot-complete FEC, then re-keys it to {slot, dmr}.
178 : This holds for every FEC of the block, including redelivered copies, so all FECs of one block always resolve to the same element.
179 :
180 : This exists currently because replay keys incoming FECs by {slot,
181 : block_id} to lookup its parent element. For blocks where known_id
182 : is 1 (block_id) known from the beginning, it must always use the
183 : block_id key. Otherwise, for a turbine block whose known_id is 0,
184 : it should always lookup by {slot, 0}.
185 :
186 : Redelivery from root never changes known_id. It only affects
187 : block_id. Neither does a merge: when a turbine copy completes as
188 : a block whose repaired copy is also delivering, the surviving
189 : turbine copy keeps known_id 0, and replay keeps building its
190 : {slot, 0} bank, abandoning the notarized copy's bank. */
191 : int known_id;
192 : fd_hash_t block_id; /* always populated if known_id is 1, or if slot_complete is 1. Otherwise could be populated on redelivery or as soon as the block_id is computed. */
193 :
194 : fd_rotor_fec_metrics_t metrics;
195 : };
196 : typedef struct fd_rotor_replay_fec fd_rotor_replay_fec_t;
197 :
198 : /* fd_rotor_block is published to rserve when a block's slot-complete
199 : FEC is delivered. merkle_roots holds the first 20B of each FEC
200 : root. The frag is variable length, see FD_ROTOR_BLOCK_SZ. */
201 :
202 : struct fd_rotor_block {
203 : ulong slot;
204 : fd_hash_t block_id;
205 : ulong parent_slot;
206 : fd_hash_t parent_block_id;
207 : uint fec_set_cnt;
208 : uchar merkle_roots[ FD_FEC_BLK_MAX ][ FD_SHRED_MERKLE_NODE_SZ ];
209 : };
210 : typedef struct fd_rotor_block fd_rotor_block_t;
211 :
212 0 : #define FD_ROTOR_BLOCK_SZ(fec_set_cnt) (offsetof(fd_rotor_block_t, merkle_roots) + (ulong)(fec_set_cnt)*FD_SHRED_MERKLE_NODE_SZ)
213 :
214 : #endif /* HEADER_fd_src_discof_rotor_fd_rotor_tile_h */
|
