Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_gossip_fd_active_set_h
       2             : #define HEADER_fd_src_flamenco_gossip_fd_active_set_h
       3             : 
       4             : #include "fd_bloom.h"
       5             : #include "crds/fd_crds.h"
       6             : 
       7             : /* fd_active_set provides APIs for tracking the active set of nodes we
       8             :    should push messages to in a gossip network.
       9             : 
      10             :    In the Solana gossip protocol, each node selects a random set of up
      11             :    to 300 peers to send messages to, and then rotates one of the nodes
      12             :    out for a new, randomly selected one every so often.
      13             : 
      14             :    This is simple enough: just keep a list of the peer pubkeys, and
      15             :    occasionally replace one?
      16             : 
      17             :    There's two complications:
      18             : 
      19             :     (1) We want to select peers with a good distribution of stakes, so
      20             :         that we don't end up sending to a lot of low-stake peers if
      21             :         someone pollutes the gossip table with junk.
      22             : 
      23             :     (2) Peers sometimes request that we don't forward messages from
      24             :         other originating (origin) nodes to them, because they already
      25             :         have a lot of paths from that node.  This is called a prune.
      26             : 
      27             :    Complication (1) is handled by keeping a list of the top 12 peers
      28             :    (sorted by stake) for each of 25 buckets of stakes.  These buckets
      29             :    are all rotated together.
      30             : 
      31             :    And problem (2) is solved by keeping a bloom filter for each of the
      32             :    12 peers in each bucket.  The bloom filter is used to track which
      33             :    origins the peer has pruned. */
      34             : 
      35           0 : #define FD_ACTIVE_SET_STAKE_ENTRIES    (25UL)
      36           0 : #define FD_ACTIVE_SET_PEERS_PER_ENTRY  (12UL)
      37           0 : #define FD_ACTIVE_SET_MAX_PEERS        (FD_ACTIVE_SET_STAKE_ENTRIES*FD_ACTIVE_SET_PEERS_PER_ENTRY) /* 300 */
      38             : struct fd_active_set_peer {
      39             :   uchar        pubkey[ 32UL ];
      40             :   fd_bloom_t * bloom;
      41             : };
      42             : 
      43             : typedef struct fd_active_set_peer fd_active_set_peer_t;
      44             : 
      45             : struct fd_active_set_entry {
      46             :   ulong                nodes_idx; /* points to oldest entry in set */
      47             :   ulong                nodes_len;
      48             :   fd_active_set_peer_t nodes[ FD_ACTIVE_SET_PEERS_PER_ENTRY ][ 1UL ];
      49             : };
      50             : 
      51             : typedef struct fd_active_set_entry fd_active_set_entry_t;
      52             : 
      53           9 : #define FD_ACTIVE_SET_ALIGN     (64UL)
      54             : 
      55             : struct __attribute__((aligned(FD_ACTIVE_SET_ALIGN))) fd_active_set_private {
      56             :   fd_active_set_entry_t entries[ FD_ACTIVE_SET_STAKE_ENTRIES ][ 1UL ];
      57             : 
      58             :   fd_rng_t * rng;
      59             : 
      60             :   ulong magic; /* ==FD_ACTIVE_SET_MAGIC */
      61             : };
      62             : 
      63             : typedef struct fd_active_set_private fd_active_set_t;
      64             : 
      65             : #define FD_ACTIVE_SET_FOOTPRINT (sizeof(fd_active_set_t))
      66             : 
      67           3 : #define FD_ACTIVE_SET_MAGIC (0xF17EDA2CEA5E1000) /* FIREDANCE ASET V0 */
      68             : 
      69             : FD_PROTOTYPES_BEGIN
      70             : 
      71             : FD_FN_CONST ulong
      72             : fd_active_set_align( void );
      73             : 
      74             : FD_FN_CONST ulong
      75             : fd_active_set_footprint( void );
      76             : 
      77             : void *
      78             : fd_active_set_new( void *     shmem,
      79             :                    fd_rng_t * rng );
      80             : 
      81             : fd_active_set_t *
      82             : fd_active_set_join( void * shas );
      83             : 
      84             : /* fd_active_set_nodes retrieves the list of nodes that we should push
      85             :    messages from the origin to.  The list will not include peers that
      86             :    have pruned the origin, except if ignore_prunes_if_peer_is_origin
      87             :    is non-zero, in which case the list will include a peer if its pubkey
      88             :    matches the origin pubkey.
      89             : 
      90             :    Up to 12 peer nodes will be returned in out_nodes.  The values
      91             :    returned in out_nodes are an internal peer index of the active set
      92             :    and should not be used for anything other than calling
      93             :    fd_active_set_node_pubkey to get the pubkey of the peer.  The
      94             :    peer index is only valid for the current active set and should not be
      95             :    used after a call to fd_active_set_rotate or fd_active_set_prune. */
      96             : 
      97             : ulong
      98             : fd_active_set_nodes( fd_active_set_t * active_set,
      99             :                      uchar const *     identity_pubkey,
     100             :                      ulong             identity_stake,
     101             :                      uchar const *     origin,
     102             :                      ulong             origin_stake,
     103             :                      int               ignore_prunes_if_peer_is_origin,
     104             :                      ulong             out_nodes[ static 12UL ] );
     105             : 
     106             : uchar const *
     107             : fd_active_set_node_pubkey( fd_active_set_t * active_set,
     108             :                            ulong             peer_idx );
     109             : 
     110             : void
     111             : fd_active_set_prune( fd_active_set_t * active_set,
     112             :                      uchar const *     push_dest,
     113             :                      uchar const *     origin,
     114             :                      ulong             origin_stake,
     115             :                      uchar const *     identity_pubkey,
     116             :                      ulong             identity_stake );
     117             : 
     118             : /* fd_active_set_rotate chooses a random active set entry to swap/introduce
     119             :    a peer into. The peer is sampled from a distribution
     120             :    (provided by crds) specific to the active set bucket.
     121             : 
     122             :    returns the index that is being replaced within the
     123             :    300 peer set. This allows users to maintain data structures that track the
     124             :    active set. Returns ULONG_MAX if no peer replacement is found. */
     125             : 
     126             : ulong
     127             : fd_active_set_rotate( fd_active_set_t *     active_set,
     128             :                       fd_crds_t *           crds );
     129             : 
     130             : FD_PROTOTYPES_END
     131             : 
     132             : #endif /* HEADER_fd_src_flamenco_gossip_fd_active_set_h */