packages feed

haskoin-store-1.16.1: src/Haskoin/Store/BlockStore/Sync.hs

-- |
-- Module      : Haskoin.Store.BlockStore.Sync
-- Copyright   : (c) Haskoin Developers
-- License     : MIT
-- Maintainer  : jprupp@protonmail.ch
-- Stability   : experimental
-- Portability : POSIX
--
-- The state of the block download, as a pure state machine.
--
-- The block store asks one peer at a time for blocks, the syncing peer. The
-- state holds the blocks that are wanted, in chain order, the peer that is
-- being asked, and the peers that were asked before it and have yet to
-- deliver. Every change of that state is one of the transitions of this
-- module, and the block store only carries out what they decide: lock or
-- release a peer, send a request, disconnect a peer.
--
-- = Why a state machine
--
-- The block store used to keep this state in a @TVar (Maybe Syncing)@ that a
-- dozen functions changed in place, each with its own check of who the peer
-- was and what had been asked. Bugs in such code, like a peer left locked or
-- a block accepted that nobody asked for, show up as a sync that stops for no
-- visible reason. Pure transitions can be tested on their own, with any
-- sequence of events, and the rules are in one place:
--
-- * There is at most one syncing peer, and only 'start' and 'pass' set one.
-- * A block is accepted only from a peer that was asked for it ('accept'),
--   so a block that nobody asked that peer for is a reason to disconnect it.
-- * A block is wanted at most once ('request').
-- * A peer that has delivered nothing for a while is passed over
--   ('stalled', 'pass'), and one that has delivered nothing for long is
--   disconnected ('timedOut', 'expired').
--
-- = A peer that does not deliver
--
-- A peer may announce a block and never send it, or send it slowly. There
-- used to be one timeout for that, the one that says a peer is dead, of two
-- minutes: the store waited it out, disconnected the peer, and asked the
-- next. A new block could take two minutes and six seconds to arrive on a
-- store with twenty good peers.
--
-- Now a peer that delivers nothing for a short time, the stall, is passed
-- over: the next peer is asked for the same blocks, and becomes the syncing
-- peer. The one before is not disconnected. It is still owed its blocks,
-- and if it sends one that is still wanted, the block is imported: whoever
-- delivers first wins. One that is not wanted any more is dropped, and is
-- no reason to disconnect anyone. Only a peer that has still not delivered
-- when the long timeout runs out is disconnected, as before.
--
-- = How long a stall is
--
-- The stall follows the syncing peer's own pace ('patience'): four times
-- the recent gap between the blocks that it delivered ('gap'), but at least
-- 'stallFloor' and at most the stall that the store was given. A store that
-- imports hundreds of small blocks a second sees a peer that has gone quiet
-- in two seconds, not ten; one that takes seconds over each large block is
-- given longer. A fixed stall was the alternative: short enough to catch a
-- quiet peer quickly, it passes over every peer on a slow link, and long
-- enough for a slow link, it leaves a fast store idle for most of the time.
-- Until a block is imported, there is no pace to go by, and the stall is
-- the one given.
--
-- The stall doubles each time a peer is passed over, up to the long
-- timeout, and goes back to its start when a block is imported. A store on
-- a link that cannot bring a block within the first stall therefore still
-- gets it, from the first peer that it asked, at the price of having asked
-- others too. Making the single timeout short was the alternative: it
-- disconnects every peer in turn on such a link, each before its block is
-- whole, and the store never syncs.
--
-- = Who is asked
--
-- A peer is asked for a block only if it answers a ping first ('ping',
-- 'pong'). The peers that could be asked are all pinged at once, and the
-- first to answer becomes the syncing peer: the one that is quickest now,
-- which the median of its old pings, by which the node sorts its peers,
-- does not tell. A peer that takes longer than the wait to answer is not
-- asked while another may still answer in time. Only when every peer that
-- was pinged is late is one of them asked all the same ('overdue'): a
-- store on a slow link has only late peers, and must still sync.
--
-- Which peers could be asked is not decided here: the block store pings
-- only those that have announced the block that it needs.
--
-- The peer is a type parameter so that the tests can use plain numbers.
module Haskoin.Store.BlockStore.Sync
  ( -- * State
    Sync (..),
    Asked (..),
    idle,
    syncingPeer,
    outstanding,
    lastRequested,
    passedPeers,
    Probe (..),
    Pinged (..),
    probing,

    -- * Transitions
    start,
    pass,
    release,
    Accept (..),
    accept,
    imported,
    request,
    forgetRequests,
    ping,
    pong,
    skip,
    settle,

    -- * Decisions
    wantsMore,
    needsMoreBlocks,
    patience,
    stallFloor,
    stallFactor,
    stalled,
    timedOut,
    expired,
    overdue,
  )
where

import Data.List (delete, find, nub, sortOn)
import Data.Maybe (isJust, isNothing)
import Data.Time.Clock (NominalDiffTime, UTCTime, diffUTCTime)
import Data.Word (Word64)
import Haskoin (BlockHash)

-- | State of the block download from peers of type @p@.
data Sync p = Sync
  { -- | blocks requested and not yet imported, in chain order
    wanted :: ![BlockHash],
    -- | the syncing peer, locked for the block store, if there is one
    current :: !(Maybe (Asked p)),
    -- | when a block was last imported, or the syncing peer last changed
    time :: !UTCTime,
    -- | syncing peers passed over since a block was last imported
    passes :: !Int,
    -- | the recent gap between imported blocks, a moving average, if a
    -- block was imported: the pace that 'patience' follows
    gap :: !(Maybe NominalDiffTime),
    -- | peers that were passed over and still owe blocks
    passed :: ![Asked p],
    -- | the peers that were pinged to find the next syncing peer, if one
    -- is being looked for
    probe :: !(Maybe (Probe p))
  }
  deriving stock (Eq, Show)

-- | Peers that were pinged, one of which is to be asked for blocks. All
-- are pinged with the same nonce, so that their answers are told from
-- those to the pings of the node.
data Probe p = Probe
  { nonce :: !Word64,
    -- | never empty, and in the order that they were pinged
    pinged :: ![Pinged p]
  }
  deriving stock (Eq, Show)

-- | A peer that was pinged, when, and when it answered if it was too late
-- to be chosen for it.
data Pinged p = Pinged
  { peer :: !p,
    at :: !UTCTime,
    answered :: !(Maybe UTCTime)
  }
  deriving stock (Eq, Show)

-- | A peer and the blocks that it was asked for and has not sent.
data Asked p = Asked
  { peer :: !p,
    -- | when it became the syncing peer or, once passed over, when it
    -- last delivered: the start of its silence
    since :: !UTCTime,
    owes :: ![BlockHash]
  }
  deriving stock (Eq, Show)

-- | No syncing peer, and nothing wanted.
idle :: UTCTime -> Sync p
idle now =
  Sync {wanted = [], current = Nothing, time = now, passes = 0, gap = Nothing, passed = [], probe = Nothing}

-- | The syncing peer, if any.
syncingPeer :: Sync p -> Maybe p
syncingPeer s = (.peer) <$> s.current

-- | Blocks requested and not yet imported.
outstanding :: Sync p -> [BlockHash]
outstanding = (.wanted)

-- | The last block requested, if any is outstanding: the next request
-- starts after it.
lastRequested :: Sync p -> Maybe BlockHash
lastRequested s = case outstanding s of
  [] -> Nothing
  bs -> Just (last bs)

-- | The peers that were passed over and still owe blocks.
passedPeers :: Sync p -> [p]
passedPeers s = map (.peer) s.passed

-- | Whether peers were pinged and none was chosen yet.
probing :: Sync p -> Bool
probing s = isJust s.probe

-- | Start syncing from a peer, if there is no syncing peer. The caller must
-- have locked the peer, and releases it if this gives 'Nothing'. The search
-- for a peer is over.
start :: (Eq p) => UTCTime -> p -> Sync p -> Maybe (Sync p)
start now p s = case s.current of
  Nothing -> Just (enlist now p [] s) {time = now, wanted = [], passes = 0}
  Just _ -> Nothing

-- | Make a peer the syncing peer, owed some blocks. If it was passed over
-- before, it still owes what it owed then: a peer is in the state once.
enlist :: (Eq p) => UTCTime -> p -> [BlockHash] -> Sync p -> Sync p
enlist now p hs s =
  s
    { current = Just (Asked p now (before <> filter (`notElem` before) hs)),
      passed = filter ((/= p) . (.peer)) s.passed,
      probe = Nothing
    }
  where
    before = concat [a.owes | a <- s.passed, a.peer == p]

-- | Pass over the syncing peer for another, which the caller has locked,
-- and gives what the new peer is to be asked for: the blocks that are
-- wanted. The peer passed over is given too, for the caller to release; it
-- stays owed its blocks, and has been silent since the clock last started.
-- Nothing changes without a syncing peer, or if the peer is the syncing peer.
pass :: (Eq p) => UTCTime -> p -> Sync p -> (Maybe (p, [BlockHash]), Sync p)
pass now p s = case s.current of
  Nothing -> (Nothing, s)
  Just old
    | old.peer == p -> (Nothing, s)
    | otherwise ->
        ( Just (old.peer, s.wanted),
          (enlist now p s.wanted s {passed = [old {since = s.time} | not (null old.owes)] <> s.passed})
            { time = now,
              passes = s.passes + 1
            }
        )

-- | Forget a peer, as when it disconnects. Says whether it was the syncing
-- peer, for the caller to unlock it; the blocks wanted are then forgotten
-- with it, for the next syncing peer to be asked from the best block on.
release :: (Eq p) => p -> Sync p -> (Bool, Sync p)
release p s = case s.current of
  Just a | a.peer == p -> (True, others {current = Nothing, wanted = [], passes = 0})
  _ -> (False, others)
  where
    others = skip p s {passed = filter ((/= p) . (.peer)) s.passed}

-- | What to do with a block that a peer sent.
data Accept
  = -- | this peer was asked for it and it is wanted: import it
    Requested
  | -- | this peer was asked for it, and another delivered it first: drop it
    Late
  | -- | the peer was not asked for any block
    NotSyncingPeer
  | -- | the peer was asked for blocks, and not for this one
    NotRequested
  deriving stock (Eq, Show)

-- | Decide what to do with a block that a peer sent, and note that the peer
-- no longer owes it.
accept :: (Eq p) => p -> BlockHash -> Sync p -> (Accept, Sync p)
accept p h s
  | Just a <- s.current,
    a.peer == p = case sent a of
      Nothing -> (NotRequested, s)
      Just a' -> (verdict, s {current = Just a'})
  | Just a <- lookupPassed = case sent a of
      Nothing -> (NotRequested, s)
      Just a' -> (verdict, s {passed = [a' | not (null a'.owes)] <> filter ((/= p) . (.peer)) s.passed})
  | otherwise = (NotSyncingPeer, s)
  where
    lookupPassed = case filter ((== p) . (.peer)) s.passed of
      a : _ -> Just a
      [] -> Nothing
    sent a
      | h `elem` a.owes = Just a {owes = delete h a.owes}
      | otherwise = Nothing
    verdict = if h `elem` s.wanted then Requested else Late

-- | A block was imported: it is no longer wanted, and the clock and the
-- stall start again. The time since the clock last started goes into the
-- recent gap between blocks, with a weight of a quarter, so that a few
-- slow blocks lengthen the stall and a burst of quick ones does not make it
-- jumpy.
imported :: UTCTime -> BlockHash -> Sync p -> Sync p
imported now h s = s {wanted = delete h s.wanted, time = now, passes = 0, gap = Just gap'}
  where
    sample = max 0 (now `diffUTCTime` s.time)
    gap' = maybe sample (\g -> (3 * g + sample) / 4) s.gap

-- | Blocks were requested from the syncing peer. Those already wanted are
-- not added again. Nothing changes without a syncing peer.
request :: [BlockHash] -> Sync p -> Sync p
request hs s = case s.current of
  Nothing -> s
  Just a -> s {wanted = s.wanted <> new, current = Just a {owes = a.owes <> new}}
  where
    new = foldl' (\bs h -> if h `elem` bs || h `elem` s.wanted then bs else bs <> [h]) [] hs

-- | Forget the blocks that are wanted, as when the chain is reorganised:
-- they will be asked for again from the new best block. The peers that
-- were asked still owe them, so that sending one is no fault of theirs.
forgetRequests :: Sync p -> Sync p
forgetRequests s = s {wanted = []}

-- | Peers are to be pinged, to ask the first that answers for blocks. Gives
-- the nonce to ping them with and those to ping: the ones that were not
-- pinged already in this search, which goes on with the nonce that it
-- started with. The nonce given is used if this starts the search.
ping :: (Eq p) => UTCTime -> Word64 -> [p] -> Sync p -> (Maybe (Word64, [p]), Sync p)
ping now fresh ps s = case new of
  [] -> (Nothing, s)
  _ -> (Just (n, new), s {probe = Just (Probe n (old <> [Pinged p now Nothing | p <- new]))})
  where
    (n, old) = maybe (fresh, []) (\b -> (b.nonce, b.pinged)) s.probe
    new = nub (filter (`notElem` map (.peer) old) ps)

-- | A peer answered a ping. Says whether it is to be asked for blocks: it
-- was pinged in this search and answered within the wait. It is then out
-- of the search, which the caller ends by making it the syncing peer
-- ('start', 'pass'), or which goes on without it if the peer cannot be
-- locked. A late answer is kept, for 'overdue' to prefer the peer to
-- those that never answered.
pong :: (Eq p) => NominalDiffTime -> UTCTime -> p -> Word64 -> Sync p -> (Bool, Sync p)
pong wait now p n s = case s.probe of
  Just b
    | b.nonce == n,
      Just g <- find ((== p) . (.peer)) b.pinged,
      isNothing g.answered ->
        if now `diffUTCTime` g.at <= wait
          then (True, skip p s)
          else (False, s {probe = Just (Probe n (map late b.pinged))})
  _ -> (False, s)
  where
    late g = if g.peer == p then Pinged p g.at (Just now) else g

-- | Leave a peer out of the search for a syncing peer, which ends if it
-- was the last one pinged.
skip :: (Eq p) => p -> Sync p -> Sync p
skip p s = case s.probe of
  Nothing -> s
  Just b -> case filter ((/= p) . (.peer)) b.pinged of
    [] -> s {probe = Nothing}
    rest -> s {probe = Just (Probe b.nonce rest)}

-- | End the search for a syncing peer.
settle :: Sync p -> Sync p
settle s = s {probe = Nothing}

-- | The syncing peer, if it should be asked for the next batch of blocks.
wantsMore :: Int -> Sync p -> Maybe p
wantsMore window s
  | needsMoreBlocks window (length s.wanted) = syncingPeer s
  | otherwise = Nothing

-- | Whether to ask for the next batch, given the window size and how many
-- requested blocks are still waiting to be imported. Asking once fewer than
-- a quarter of the window remain keeps the peer busy, while the queue of
-- downloaded blocks never grows much beyond one window. The threshold is at
-- least one, so that a window smaller than four still refills once empty.
needsMoreBlocks :: Int -> Int -> Bool
needsMoreBlocks window n = n < max 1 (window `div` 4)

-- | How long the syncing peer has to deliver a block before another is
-- asked: 'stallFactor' times the recent gap between blocks, at least
-- 'stallFloor' and at most the stall given, or the stall given if no block
-- was imported yet; doubled for each peer passed over since a block was
-- last imported, and never longer than the timeout.
patience :: NominalDiffTime -> NominalDiffTime -> Sync p -> NominalDiffTime
patience stall timeout s = min timeout (base * 2 ^ min 30 s.passes)
  where
    base = maybe stall (\g -> min stall (max stallFloor (stallFactor * g))) s.gap

-- | The shortest stall, however quick the peer was: long enough for a round
-- trip across the world and the next block of a quick peer, short enough
-- that a store importing hundreds of blocks a second idles only briefly.
stallFloor :: NominalDiffTime
stallFloor = 2

-- | How many of its recent gaps between blocks a peer may be silent before
-- it is passed over. Blocks come in bursts, so the gap varies; a factor of
-- four lets a peer take a pause well beyond its usual one.
stallFactor :: NominalDiffTime
stallFactor = 4

-- | The peers to ask all the same, best first, if none of those pinged
-- answered within the wait and none can any more: there is no other
-- option. Those that answered late come first, in the order that they
-- answered, then those that have not answered, in the order that they were
-- pinged. None while a peer that was pinged may still answer in time.
overdue :: NominalDiffTime -> UTCTime -> Sync p -> [p]
overdue wait now s = case s.probe of
  Just b
    | all late b.pinged ->
        map (.peer) (sortOn (.answered) (filter (isJust . (.answered)) b.pinged))
          <> map (.peer) (filter (isNothing . (.answered)) b.pinged)
  _ -> []
  where
    late g = isJust g.answered || now `diffUTCTime` g.at > wait

-- | The syncing peer, if blocks are wanted and none was imported for
-- longer than its 'patience': time to ask another peer, with 'pass'. The
-- block store asks this both when it starts a search and when a pinged peer
-- answers, and gets the same answer both times unless a block came in
-- between.
stalled :: NominalDiffTime -> NominalDiffTime -> UTCTime -> Sync p -> Maybe p
stalled stall timeout now s
  | null s.wanted = Nothing
  | now `diffUTCTime` s.time > patience stall timeout s = syncingPeer s
  | otherwise = Nothing

-- | The syncing peer, if no block was imported for longer than the
-- timeout: nobody could be asked in its place, and it is to be
-- disconnected.
timedOut :: NominalDiffTime -> UTCTime -> Sync p -> Maybe p
timedOut timeout now s
  | now `diffUTCTime` s.time > timeout = syncingPeer s
  | otherwise = Nothing

-- | The peers passed over that still owe blocks longer than the timeout
-- after they were asked: they are to be disconnected.
expired :: NominalDiffTime -> UTCTime -> Sync p -> [p]
expired timeout now s = [a.peer | a <- s.passed, now `diffUTCTime` a.since > timeout]