Line data Source code
1 : #ifndef HEADER_fd_src_choreo_rotor_fd_rotor_strat_h
2 : #define HEADER_fd_src_choreo_rotor_fd_rotor_strat_h
3 :
4 : /* fd_rotor_strat picks the repair peer for each request. It does no
5 : I/O: the rotor tile feeds it contact infos, epoch stakes and request
6 : outcomes. Peers sit in slots by stake rank, unstaked last, and in
7 : latency buckets by srtt+rttvar/4. A pick takes the fastest
8 : bucket's cheaper of the next two peers by srtt*(inflight+1), the
9 : cursor advancing one peer so every peer meets every neighbor,
10 : every FD_ROTOR_STRAT_EXPLORE-th pick tries an unmeasured peer first,
11 : and a request is hedged after srtt+4*rttvar (RFC 6298). It also
12 : estimates each leader's turbine time, which decides how long a
13 : missing FEC set waits for turbine before it is repaired. */
14 :
15 : #include "../../flamenco/gossip/fd_gossip_message.h"
16 : #include "../../flamenco/stakes/fd_stake_weight.h"
17 :
18 0 : #define FD_ROTOR_STRAT_PEER_MAX FD_CONTACT_INFO_TABLE_SIZE
19 0 : #define FD_ROTOR_STRAT_INFLIGHT_MAX (8U)
20 0 : #define FD_ROTOR_STRAT_EXPLORE (16UL) /* every 16th pick tries an unmeasured peer first */
21 0 : #define FD_ROTOR_STRAT_ESCAPE_TOP (100UL) /* an escape pick draws only from the top stake ranks, small stakers are often far or offline */
22 0 : #define FD_ROTOR_STRAT_EXPIRED_MAX (32U) /* requests in a row a peer leaves unanswered before it is banned */
23 0 : #define FD_ROTOR_STRAT_BYID_MAX (4U) /* by-id requests in a row, other replies aside */
24 0 : #define FD_ROTOR_STRAT_HEDGE_NS (100L*1000000L) /* hedge time of an unmeasured peer, and the longest any request waits for a retry */
25 0 : #define FD_ROTOR_STRAT_EAGER_MIN_NS (20L*1000000L)
26 0 : #define FD_ROTOR_STRAT_EAGER_MAX_NS (250L*1000000L) /* also the eager wait until turbine is measured */
27 0 : #define FD_ROTOR_STRAT_TURBINE_MIN (8UL) /* samples before a leader's own estimate is used */
28 :
29 : /* Latency buckets, fastest first. UNMEASURED holds peers with no rtt
30 : sample yet. */
31 :
32 0 : #define FD_ROTOR_STRAT_BUCKET_25MS (0UL)
33 0 : #define FD_ROTOR_STRAT_BUCKET_50MS (1UL)
34 0 : #define FD_ROTOR_STRAT_BUCKET_100MS (2UL)
35 0 : #define FD_ROTOR_STRAT_BUCKET_200MS (3UL)
36 0 : #define FD_ROTOR_STRAT_BUCKET_SLOW (4UL)
37 0 : #define FD_ROTOR_STRAT_BUCKET_UNMEASURED (5UL)
38 0 : #define FD_ROTOR_STRAT_BUCKET_CNT (6UL)
39 :
40 : struct fd_rotor_strat_peer {
41 : fd_pubkey_t id_key;
42 : ulong next; /* map chain */
43 : uint ip4; /* 0 while gossip has no address for it */
44 : ushort port;
45 : uint inflight; /* requests in flight */
46 : ulong bucket; /* the bucket of its rtt */
47 : long srtt; /* smoothed round trip in ns, 0 if never measured */
48 : long rttvar; /* its mean deviation */
49 : long ping_ts; /* last ping, 0 if none */
50 : long ban_ts; /* skipped until this time */
51 : uint expired_cnt; /* requests in a row it left unanswered */
52 : uint byid_expired_cnt; /* by-id requests in a row it left unanswered */
53 : long turbine_srtt; /* as leader, smoothed time from a FEC set's first shred to complete, 0 if never measured */
54 : long turbine_rttvar; /* its mean deviation */
55 : ulong turbine_cnt; /* its samples */
56 : };
57 : typedef struct fd_rotor_strat_peer fd_rotor_strat_peer_t;
58 :
59 : #define MAP_NAME fd_rotor_strat_peer_map
60 : #define MAP_ELE_T fd_rotor_strat_peer_t
61 : #define MAP_KEY_T fd_pubkey_t
62 0 : #define MAP_KEY id_key
63 0 : #define MAP_KEY_EQ(k0,k1) (!memcmp( (k0), (k1), sizeof(fd_pubkey_t) ))
64 0 : #define MAP_KEY_HASH(key,seed) fd_ulong_hash( (seed)^FD_LOAD( ulong, (key)->uc ) )
65 : #include "../../util/tmpl/fd_map_chain.c"
66 :
67 : #define SET_NAME fd_rotor_strat_set
68 : #define SET_MAX FD_ROTOR_STRAT_PEER_MAX
69 : #include "../../util/tmpl/fd_set.c"
70 :
71 : /* Slots and their map are double buffered so the epoch re-sort can
72 : read the old order while it builds the new one. */
73 :
74 : struct fd_rotor_strat_order {
75 : fd_rotor_strat_peer_t * peers; /* FD_ROTOR_STRAT_PEER_MAX slots */
76 : fd_rotor_strat_peer_map_t * map;
77 : };
78 : typedef struct fd_rotor_strat_order fd_rotor_strat_order_t;
79 :
80 : struct fd_rotor_strat_private {
81 : fd_rotor_strat_order_t cur;
82 : fd_rotor_strat_order_t old;
83 : ulong staked_cnt;
84 : uint * free; /* unstaked slots not in use, a stack */
85 : ulong free_cnt;
86 : fd_rotor_strat_set_t * buckets[ FD_ROTOR_STRAT_BUCKET_CNT ];
87 : ulong cursor [ FD_ROTOR_STRAT_BUCKET_CNT ]; /* slot last picked in each bucket */
88 : ulong pick_cnt;
89 : ulong seed;
90 : ulong epoch_cnt;
91 : long turbine_srtt; /* over all leaders */
92 : long turbine_rttvar;
93 : };
94 : typedef struct fd_rotor_strat_private fd_rotor_strat_t;
95 :
96 : FD_PROTOTYPES_BEGIN
97 :
98 : FD_FN_CONST ulong
99 : fd_rotor_strat_align( void );
100 :
101 : FD_FN_CONST ulong
102 : fd_rotor_strat_footprint( void );
103 :
104 : void *
105 : fd_rotor_strat_new( void * shmem,
106 : ulong seed );
107 :
108 : fd_rotor_strat_t *
109 : fd_rotor_strat_join( void * shstrat );
110 :
111 : /* fd_rotor_strat_epoch_advanced re-sorts the peers by the epoch's
112 : identity stakes, ids sorted by stake descending. Peers keep their
113 : address, rtt and ping state. Invalidates peer pointers. */
114 :
115 : void
116 : fd_rotor_strat_epoch_advanced( fd_rotor_strat_t * strat,
117 : fd_stake_weight_t const * ids,
118 : ulong id_cnt );
119 :
120 : /* fd_rotor_strat_contact_info_updated records a peer's repair address
121 : from gossip. A new address resets its rtt and ping. A new unstaked
122 : peer is dropped if every unstaked slot is in use. */
123 :
124 : void
125 : fd_rotor_strat_contact_info_updated( fd_rotor_strat_t * strat,
126 : fd_pubkey_t const * id_key,
127 : uint ip4,
128 : ushort port );
129 :
130 : /* fd_rotor_strat_contact_info_removed forgets a peer's address. A
131 : staked peer keeps its slot. */
132 :
133 : void
134 : fd_rotor_strat_contact_info_removed( fd_rotor_strat_t * strat,
135 : fd_pubkey_t const * id_key );
136 :
137 : /* fd_rotor_strat_pick returns the peer for a request and counts it in
138 : flight, or NULL if none is available. staked restricts it to staked
139 : peers. The fastest bucket with an available peer wins; within it the
140 : cheaper of the next two peers after its cursor, in stake order.
141 : Banned peers are skipped, and slot avoid unless no other peer is
142 : available (ULONG_MAX for none). */
143 :
144 : fd_rotor_strat_peer_t *
145 : fd_rotor_strat_pick( fd_rotor_strat_t * strat,
146 : long now,
147 : int staked,
148 : ulong avoid );
149 :
150 : /* fd_rotor_strat_pick_staked returns a staked peer at random among the
151 : top FD_ROTOR_STRAT_ESCAPE_TOP stake ranks, higher ranks likelier,
152 : other than slot avoid, for a request the bucket
153 : order keeps failing, and counts it in flight. r is a random number.
154 : NULL if none is available. */
155 :
156 : fd_rotor_strat_peer_t *
157 : fd_rotor_strat_pick_staked( fd_rotor_strat_t * strat,
158 : long now,
159 : ulong avoid,
160 : ulong r );
161 :
162 : /* fd_rotor_strat_request_done ends a request picked from id_key with a
163 : reply that verified. rtt is its round trip, byid if it answered a
164 : by-id request. */
165 :
166 : void
167 : fd_rotor_strat_request_done( fd_rotor_strat_t * strat,
168 : fd_pubkey_t const * id_key,
169 : long rtt,
170 : int byid );
171 :
172 : /* fd_rotor_strat_request_failed ends a request picked from id_key with
173 : a reply that failed to verify, or no reply at all, and skips the peer
174 : until ban_ts. It takes no rtt sample. */
175 :
176 : void
177 : fd_rotor_strat_request_failed( fd_rotor_strat_t * strat,
178 : fd_pubkey_t const * id_key,
179 : long ban_ts );
180 :
181 : /* fd_rotor_strat_request_expired ends a request picked from id_key that
182 : a live peer should have answered but did not. It takes no rtt
183 : sample; after FD_ROTOR_STRAT_EXPIRED_MAX in a row with no reply, or
184 : FD_ROTOR_STRAT_BYID_MAX by-id ones (byid) with no by-id reply, the
185 : peer is skipped until ban_ts. Returns 1 if the by-id run banned it,
186 : -1 if the run of any kind did, 0 if not banned. */
187 :
188 : int
189 : fd_rotor_strat_request_expired( fd_rotor_strat_t * strat,
190 : fd_pubkey_t const * id_key,
191 : long ban_ts,
192 : int byid );
193 :
194 : /* fd_rotor_strat_turbine_done records t, the time from a FEC set's
195 : first shred to its completion, for the slot's leader id_key. */
196 :
197 : void
198 : fd_rotor_strat_turbine_done( fd_rotor_strat_t * strat,
199 : fd_pubkey_t const * id_key,
200 : long t );
201 :
202 : /* fd_rotor_strat_eager_ns returns how long a missing FEC set of
203 : leader id_key waits for turbine before it is repaired: about the p95
204 : of its turbine time, from all leaders until it has
205 : FD_ROTOR_STRAT_TURBINE_MIN samples. id_key may be NULL. */
206 :
207 : long
208 : fd_rotor_strat_eager_ns( fd_rotor_strat_t * strat,
209 : fd_pubkey_t const * id_key );
210 :
211 : /* fd_rotor_strat_hedge_ns returns how long a request to peer may be
212 : outstanding before it is hedged to another peer. */
213 :
214 : static inline long
215 0 : fd_rotor_strat_hedge_ns( fd_rotor_strat_peer_t const * peer ) {
216 0 : return fd_long_if( !!peer->srtt, peer->srtt+4L*peer->rttvar, FD_ROTOR_STRAT_HEDGE_NS );
217 0 : }
218 :
219 : fd_rotor_strat_peer_t *
220 : fd_rotor_strat_query( fd_rotor_strat_t * strat,
221 : fd_pubkey_t const * id_key );
222 :
223 : /* fd_rotor_strat_slot_remap returns the slot now held by the peer that
224 : held slot idx before the last epoch re-sort, or ULONG_MAX if it is
225 : gone or idx is ULONG_MAX. */
226 :
227 : ulong
228 : fd_rotor_strat_slot_remap( fd_rotor_strat_t const * strat,
229 : ulong idx );
230 :
231 : FD_PROTOTYPES_END
232 :
233 : #endif /* HEADER_fd_src_choreo_rotor_fd_rotor_strat_h */
|
