haskoin-store-1.16.0: src/Haskoin/Store/XPub/Indexer.hs
{-# LANGUAGE MultiWayIf #-}
-- |
-- Module : Haskoin.Store.XPub.Indexer
-- Copyright : (c) Haskoin Developers
-- License : MIT
-- Maintainer : jprupp@protonmail.ch
-- Stability : experimental
-- Portability : POSIX
--
-- The indexer of xpubs: threads that read xpubs from the database into a
-- cache in the background, so that no request reads an xpub itself
-- (@docs\/xpub-indexing.md@, The indexer).
--
-- A request for an xpub that the cache does not have hands it to the
-- indexer ('request'), and either waits for the job to be done, up to a
-- set time, or is told when to come back. The work goes on either way, so
-- the client that comes back finds the xpub in the cache. The queue can
-- also take upkeep, behind the jobs that requests wait for ('upkeep'); the
-- store queues none, as a move of the fleet tip updates the cache in Redis
-- itself ("Haskoin.Store.Fleet.Member").
--
-- = The queue
--
-- First in, first out, with no key in it twice, in two parts: the jobs that
-- a request asked for, then upkeep. A request for a key that is already
-- queued or running joins that job; one for a key that is queued for
-- upkeep moves it to the end of the first part. Upkeep for a key that is
-- queued adds to that job ('Semigroup' of the payload); for a key whose job
-- is running, it queues the key again for when the job is done, since that
-- job may have read the database before the change. A key never runs in two
-- threads at once, so two jobs of one xpub never race to write it.
--
-- = Deciding
--
-- When a request does not find its key in the queue, the store estimates
-- when a new job would be done ('estimate'): (place ÷ threads + 1) × the
-- median time of recent jobs. That is rough, since the size of an xpub is
-- not known until it is read, but it only has to tell soon from later.
-- 'decide' then picks one of three, a pure function of the estimate, the
-- wait, the horizon, the room in the queue and the lock:
--
-- * __wait__: queue and lock the key, or join its job, and wait for it;
-- * __refuse and keep the job__: queue and lock it, and answer 429 with
-- @Retry-After@ from the estimate;
-- * __refuse and take nothing__: beyond the horizon, with a full queue, or
-- with the key locked by another store of the fleet, which says when it
-- expects to be done.
--
-- The lock ("Haskoin.Store.XPub.Lock") is taken when the key is queued,
-- not when the job starts, renewed while the store holds the job, and let
-- go when the job is done. A store that loses the race for it takes
-- nothing.
--
-- = Waiting without timers
--
-- A request that waits sets no timer: it waits on a variable of its own,
-- which the job sets when it is done, and a sweeper thread, which sleeps in
-- the system ten times a second, refuses the requests whose time is up
-- ('sweep'). Every timer of a program, @threadDelay@, @registerDelay@ and
-- @timeout@ included, goes through one thread of GHC, its timer manager,
-- which was seen stuck for seconds under load ("Haskoin.Store.Web.Admission"
-- says how). Sleeping in a safe foreign call does not depend on it.
--
-- = What is a parameter
--
-- The job itself, a t'Runner': reading an xpub and writing it to Redis
-- ("Haskoin.Store.Fleet.XPub"); and
-- a t'Budget' per job, which it settles at its safe points and tells its
-- size through, from which the indexer estimates when it will be done.
module Haskoin.Store.XPub.Indexer
( -- * Settings
Settings (..),
defaultSettings,
-- * The jobs
Runner (..),
plainRunner,
-- * The indexer
Indexer,
newIndexer,
newIndexerWith,
withIndexer,
runIndexer,
-- * Asking for keys
Answer (..),
Refusal (..),
request,
requestWithin,
prefetch,
upkeep,
retryAfter,
-- * Deciding
Holder (..),
Situation (..),
Decision (..),
decide,
estimate,
median,
-- * Watching
IndexerStats (..),
Counts (..),
Refusals (..),
indexerStats,
indexerIdle,
-- * Paying
-- * Steps
sweep,
renewHeld,
runNext,
snooze,
)
where
import Control.Concurrent (getNumCapabilities)
import Control.Concurrent.Async (link, replicateConcurrently_, withAsync)
import Control.Concurrent.STM
( STM,
TVar,
atomically,
modifyTVar',
newTVar,
newTVarIO,
readTVar,
retry,
writeTVar,
)
import Control.Exception (SomeException)
import Control.Monad (forM_, replicateM_, unless, void, when)
import Data.HashMap.Strict (HashMap)
import Data.HashMap.Strict qualified as HashMap
import Data.Hashable (Hashable)
import Data.List (sort)
import Data.Map.Strict (Map)
import Data.Map.Strict qualified as Map
import Data.Maybe (fromMaybe, maybeToList)
import Data.Sequence (Seq, ViewL (..), (|>))
import Data.Sequence qualified as Seq
import Foreign.C.Types (CInt (..), CUInt (..))
import GHC.Clock (getMonotonicTimeNSec)
import Haskoin.Store.Common (loopForever)
import Haskoin.Store.Exception (catchAny, finally, tryAny)
import Haskoin.Store.XPub (Budget (..), noBudget)
import Haskoin.Store.XPub.Lock (Lock (..), Taken (..))
-------------------------------------------------------------------------------
-- Settings
-------------------------------------------------------------------------------
-- | Settings of the indexer. Times are in microseconds.
data Settings = Settings
{ -- | threads that run jobs; zero or less for one per core. They spend
-- much of their time waiting for RocksDB, so one per core keeps the
-- disk busy
workers :: !Int,
-- | how long a request may wait for its job
wait :: !Int,
-- | beyond this estimate, the store takes no new job
horizon :: !Int,
-- | most jobs that requests asked for in the queue; upkeep has no limit
-- but the number of cached xpubs, since no key is queued twice
room :: !Int,
-- | the median time of a job before any has been timed
guess :: !Int
}
deriving (Eq, Show)
-- | One thread per core, a wait of ten seconds, a horizon of thirty, room
-- for a thousand jobs, and a first guess of a tenth of a second a job.
defaultSettings :: Settings
defaultSettings =
Settings
{ workers = 0,
wait = 10000000,
horizon = 30000000,
room = 1000,
guess = 100000
}
-- | How many of the latest jobs that requests asked for make the median.
recentJobs :: Int
recentJobs = 31
-------------------------------------------------------------------------------
-- The jobs
-------------------------------------------------------------------------------
-- | What the indexer does with a key, and with the payload that came with
-- it: whatever the cache needs to know, such as the changes that upkeep is
-- for. Payloads of one key are joined with '<>'.
--
-- The fields are lazy, so that a cache can make a runner of itself before
-- it is built ('System.IO.fixIO').
data Runner k p = Runner
{ -- | read the key and write it to the cache, paying from the budget;
-- it throws if it fails. The requests that wait read the cache once it
-- is done, as every request does: nothing goes from the job to them
index :: Budget -> k -> p -> IO (),
-- | the budget of a job
budget :: k -> IO Budget,
-- | whether the store may take jobs: a store that is not in sync with
-- its node takes none, since it would write what knows less than the
-- others
ready :: IO Bool,
-- | a job that will not run, because the store is not ready: its
-- payload is given back
abandon :: k -> p -> IO (),
-- | another store holds the lock of the key, and expects to be done in
-- so many microseconds: the payload of the job that was not queued is
-- given back
blocked :: k -> p -> Int -> IO (),
-- | a job threw, or its lock could not be taken
failed :: k -> p -> SomeException -> IO (),
-- | called every time the locks are renewed, with the jobs that this
-- store holds, queued or running
renew :: [(k, p)] -> IO ()
}
-- | A runner that only runs the job: it is always ready, pays nothing, and
-- has nothing to give back.
plainRunner :: (Budget -> k -> p -> IO ()) -> Runner k p
plainRunner f =
Runner
{ index = f,
budget = \_ -> return noBudget,
ready = return True,
abandon = \_ _ -> return (),
blocked = \_ _ _ -> return (),
failed = \_ _ _ -> return (),
renew = \_ -> return ()
}
-- | Where a job is.
data Stage p
= -- | a request or upkeep reserved it, and is taking its lock
Pending
| -- | in the queue
Queued
| -- | being run, since a time if known, with upkeep that came meanwhile,
-- to run again once it is done
Running !(Maybe Int) !(Maybe p)
| -- | done, with what came of it, while its lock is let go, with upkeep
-- that came meanwhile, to queue again once the lock is gone
Finishing !Answer !(Maybe p)
-- | A job of the indexer.
data Job p = Job
{ payload :: !p,
-- | whether a request asked for it: then it is in the first part
asked :: !Bool,
-- | the requests that wait for it
waiters :: ![TVar Verdict],
stage :: !(Stage p)
}
-- | The queue: the keys of each part, in order, and every job, queued,
-- pending or running.
data Queue k p = Queue
{ first :: !(Seq k),
second :: !(Seq k),
jobs :: !(HashMap k (Job p))
}
-- | What a waiting request was told, if anything yet.
data Verdict = Waiting | Answered !Answer
-------------------------------------------------------------------------------
-- Answers and decisions
-------------------------------------------------------------------------------
-- | What became of a request for a key.
data Answer
= -- | the job wrote the key to the cache: the request reads it there
Indexed
| -- | refused, with how many microseconds to wait before asking again
Refused !Refusal !Int
| -- | the job failed, or its lock could not be taken
Failed
deriving (Eq, Show)
-- | Why a request was refused.
data Refusal
= -- | another store of the fleet holds the lock of the key
OtherStore
| -- | the queue has no room for another job
QueueFull
| -- | a new job would be done later than the horizon
BeyondHorizon
| -- | the job would be done later than the request may wait; it goes on
TooLong
| -- | the request waited as long as it may; the job goes on
WaitedOut
| -- | the store is not in sync with its node, and takes no job
NotInSync
deriving (Eq, Show, Enum, Bounded)
-- | Seconds for @Retry-After@ from microseconds: rounded up, at least one.
retryAfter :: Int -> Int
retryAfter us = max 1 ((us + 999999) `div` 1000000)
-- | Who has the job of a key.
data Holder
= -- | nobody
Nobody
| -- | this store, queued or running
ThisStore
| -- | another store of the fleet, which expects to be done in so many
-- microseconds
AnotherStore !Int
deriving (Eq, Show)
-- | What a decision is made from. Times are in microseconds. The fields
-- are named apart from those of t'Settings', so that an update of either is
-- never ambiguous.
data Situation = Situation
{ -- | when the job would be done: a new one, or the one of this store
expected :: !Int,
-- | how long the request may wait: the wait of the settings, or none
patience :: !Int,
-- | the horizon: beyond this estimate, take no new job
reach :: !Int,
-- | whether the queue has room for a new job
hasRoom :: !Bool,
holder :: !Holder
}
deriving (Eq, Show)
-- | What to do with a request for a key that the cache does not have.
data Decision
= -- | queue and lock a new job, or join the job of this store, and wait
Wait
| -- | queue and lock a new job, or keep the one of this store, and
-- refuse with this @Retry-After@ in microseconds: the estimate
RefuseKeep !Int
| -- | take nothing, and refuse with this @Retry-After@: from the lock of
-- another store, or the horizon
RefuseNothing !Refusal !Int
deriving (Eq, Show)
-- | The decision of @docs\/xpub-indexing.md@ (What a request for an xpub
-- does):
--
-- +------------------------+---------------------------+------------------------------------+
-- | Holder | Estimate | Decision |
-- +========================+===========================+====================================+
-- | another store | any | take nothing, retry from its lock |
-- +------------------------+---------------------------+------------------------------------+
-- | this store | within the wait | join and wait |
-- +------------------------+---------------------------+------------------------------------+
-- | this store | beyond the wait | keep the job, retry from estimate |
-- +------------------------+---------------------------+------------------------------------+
-- | nobody, no room | any | take nothing, retry at the horizon |
-- +------------------------+---------------------------+------------------------------------+
-- | nobody | beyond the horizon | take nothing, retry at the horizon |
-- +------------------------+---------------------------+------------------------------------+
-- | nobody | within the wait | queue, lock and wait |
-- +------------------------+---------------------------+------------------------------------+
-- | nobody | within the horizon | queue, lock, retry from estimate |
-- +------------------------+---------------------------+------------------------------------+
--
-- A store that takes nothing tells its client to come back at the horizon:
-- by then this store, or another store of the fleet, may have room. In a
-- fleet the estimate of a job that a store holds is the one in its lock in
-- Redis, which every store reads, and the door decides from it before it
-- asks ('Haskoin.Store.XPub.Service.xpubAsk', 'requestWithin').
decide :: Situation -> Decision
decide s = case s.holder of
AnotherStore t -> RefuseNothing OtherStore (max 0 t)
ThisStore
| s.expected <= s.patience -> Wait
| otherwise -> RefuseKeep s.expected
Nobody
| not s.hasRoom -> RefuseNothing QueueFull s.reach
| s.expected > s.reach -> RefuseNothing BeyondHorizon s.reach
| s.expected <= s.patience -> Wait
| otherwise -> RefuseKeep s.expected
-- | When a job at this place in the queue should be done, in the unit of
-- the median: the jobs ahead of it, shared between the threads, and then
-- its own, @(place ÷ threads + 1) × median@.
estimate :: Int -> Int -> Int -> Int
estimate med threads place = med + place * med `div` max 1 threads
-- | The median of some times, or the guess if there are none.
median :: Int -> Seq Int -> Int
median guess xs
| Seq.null xs = guess
| otherwise = sort (foldr (:) [] xs) !! (Seq.length xs `div` 2)
-------------------------------------------------------------------------------
-- The indexer
-------------------------------------------------------------------------------
-- | Requests refused since the start, by why.
data Refusals = Refusals
{ otherStore :: !Int,
queueFull :: !Int,
beyondHorizon :: !Int,
tooLong :: !Int,
waitedOut :: !Int,
notInSync :: !Int
}
deriving (Eq, Show)
-- | What the indexer has done since the start.
data Counts = Counts
{ -- | jobs done
done :: !Int,
-- | jobs that threw
errors :: !Int,
-- | jobs dropped because the store was not ready
dropped :: !Int,
-- | requests answered after waiting
answered :: !Int,
-- | locks found taken by another store when they were renewed
lost :: !Int,
-- | requests refused, by why
refused :: !Refusals,
-- | prefetches that queued a job or found one: they are not refusals,
-- since nobody waits for them
prefetched :: !Int,
-- | prefetches that took nothing: beyond the horizon, with a full queue,
-- with the key locked by another store, or with the store not ready
declined :: !Int
}
deriving (Eq, Show)
-- | The indexer of keys of type @k@, with payloads of type @p@.
data Indexer k p = Indexer
{ settings :: !Settings,
-- | microseconds of a monotonic clock; the tests have one that they
-- move by hand
clock :: !(IO Int),
lock :: !(Lock k),
runner :: Runner k p,
queue :: !(TVar (Queue k p)),
-- | the requests that wait, by when their time is up and a serial
-- number, with their keys
deadlines :: !(TVar (Map (Int, Int) (k, TVar Verdict))),
serial :: !(TVar Int),
-- | microseconds of the latest jobs that requests asked for
times :: !(TVar (Seq Int)),
-- | the size of each running job, in transactions, that told it
sizes :: !(TVar (HashMap k Int)),
-- | microseconds per thousand transactions of the latest jobs that
-- told their size
rates :: !(TVar (Seq Int)),
counts :: !(TVar Counts)
}
-- | An indexer on the monotonic clock of the system. Nothing runs until
-- 'runIndexer' does, or use 'withIndexer'.
newIndexer :: Settings -> Lock k -> Runner k p -> IO (Indexer k p)
newIndexer = newIndexerWith ((`div` 1000) . fromIntegral <$> getMonotonicTimeNSec)
-- | An indexer on this clock, which gives microseconds.
newIndexerWith :: IO Int -> Settings -> Lock k -> Runner k p -> IO (Indexer k p)
newIndexerWith clock s lock runner = do
n <- if s.workers > 0 then return s.workers else getNumCapabilities
Indexer s {workers = n, room = max 0 s.room, wait = max 0 s.wait} clock lock runner
<$> newTVarIO (Queue Seq.empty Seq.empty HashMap.empty)
<*> newTVarIO Map.empty
<*> newTVarIO 0
<*> newTVarIO Seq.empty
<*> newTVarIO HashMap.empty
<*> newTVarIO Seq.empty
<*> newTVarIO (Counts 0 0 0 0 0 (Refusals 0 0 0 0 0 0) 0 0)
-- | Run an indexer while an action runs: its threads, its sweeper and the
-- renewal of its locks.
withIndexer :: (Hashable k) => Settings -> Lock k -> Runner k p -> (Indexer k p -> IO a) -> IO a
withIndexer s lock runner action = do
i <- newIndexer s lock runner
withAsync (runIndexer i) $ \a -> link a >> action i
-- | Run the threads of an indexer, its sweeper and the renewal of its
-- locks, forever.
runIndexer :: (Hashable k) => Indexer k p -> IO ()
runIndexer i =
withAsync sweeper $ \a1 ->
withAsync renewer $ \a2 -> do
link a1
link a2
replicateConcurrently_ i.settings.workers (loopForever (next i >>= run i))
where
sweeper = loopForever (snooze 100000 >> sweep i)
renewer = loopForever (nap i.lock.every >> renewHeld i)
-- | Sleep so many microseconds, up to a second, in the system: a safe
-- foreign call, which gives the capability back while it sleeps, and sets
-- no timer of GHC ('Haskoin.Store.Web.Congestion.snooze' is the same).
snooze :: Int -> IO ()
snooze us = void (c_usleep (fromIntegral (max 0 (min 999999 us))))
foreign import ccall safe "usleep" c_usleep :: CUInt -> IO CInt
-- | Sleep so many microseconds, a tenth of a second at a time.
nap :: Int -> IO ()
nap us = replicateM_ (max 1 (us `div` 100000)) (snooze 100000)
-------------------------------------------------------------------------------
-- Asking
-------------------------------------------------------------------------------
-- | What a request does after it has looked at the queue.
data Step
= -- | it has its answer
Done !Answer
| -- | it waits for a job
Await !(Int, Int) !(TVar Verdict)
| -- | it reserved a new job, and takes its lock, then waits, or answers
Take !Decision !(Maybe ((Int, Int), TVar Verdict)) !Int
-- | Ask for a key that the cache does not have, as a request does: join
-- its job, or queue a new one, and wait for it, or be refused ('decide').
-- 'Indexed' means that the cache has the key now, and the request reads it
-- there, as every request does. Each refusal is counted by why, in a
-- t'Refusals'.
request :: (Hashable k, Semigroup p) => Indexer k p -> k -> p -> IO Answer
request i = asking False i i.settings.wait
-- | 'request', for a door that decided from the estimate in the lock of
-- the key, which every store of a fleet reads, that the request waits: it
-- joins a job of this store and waits, whatever this store's own estimate,
-- so that every store gives the same answer from the one estimate. It
-- waits at most so many microseconds, and no longer than the wait of the
-- settings, as for a request that waited for another store already and
-- takes the job over when that store let go of it. A new job is decided as
-- 'request' decides it.
requestWithin :: (Hashable k, Semigroup p) => Indexer k p -> Int -> k -> p -> IO Answer
requestWithin i = asking True i
-- | 'request' and 'requestWithin'.
asking :: (Hashable k, Semigroup p) => Bool -> Indexer k p -> Int -> k -> p -> IO Answer
asking decided i wait k p = do
a <- ask decided i (max 0 (min wait i.settings.wait)) k p
case a of
Refused why _ -> atomically (refuse i why)
_ -> return ()
return a
-- | Ask for a key without waiting: queue it if a request could, and answer
-- at once. For a request that was answered from elsewhere and wants the key
-- in the cache for next time. Nobody waits for the answer, so it is not a
-- refusal when it says to come back: it counts as 'prefetched' if a job is
-- queued for the key, and as 'declined' if not.
prefetch :: (Hashable k, Semigroup p) => Indexer k p -> k -> p -> IO Answer
prefetch i k p = do
a <- ask False i 0 k p
atomically . modifyTVar' i.counts $ \c -> case a of
Refused TooLong _ -> c {prefetched = c.prefetched + 1}
Refused _ _ -> c {declined = c.declined + 1}
_ -> c
return a
-- | Ask for a key, waiting so many microseconds at most. It counts nothing:
-- 'request' and 'prefetch' count what they were told.
ask :: (Hashable k, Semigroup p) => Bool -> Indexer k p -> Int -> k -> p -> IO Answer
ask decided i wait k p =
i.runner.ready >>= \case
False -> return (Refused NotInSync i.settings.horizon)
True -> do
now <- i.clock
step <- atomically $ do
q <- readTVar i.queue
med <- median i.settings.guess <$> readTVar i.times
expected <- expectedOf i k
case HashMap.lookup k q.jobs of
Just Job {stage = Finishing a _} -> return (Done a)
Just job -> do
let est = joinEstimate i.settings.workers q med expected now k job
case if decided && wait > 0 then Wait else decision est True ThisStore of
Wait -> do
(key, v) <- waiter i k (now + wait)
joinJob i k p (Just v)
return (Await key v)
RefuseKeep e -> do
joinJob i k p Nothing
return (Done (Refused TooLong e))
RefuseNothing why e -> return (Done (Refused why e))
Nothing -> do
let place = Seq.length q.first
est = estimate med i.settings.workers place
case decision est (place < i.settings.room) Nobody of
RefuseNothing why e -> return (Done (Refused why e))
d -> do
w <- if d == Wait then Just <$> waiter i k (now + wait) else return Nothing
let job = Job {payload = p, asked = True, waiters = maybeToList (snd <$> w), stage = Pending}
writeTVar i.queue q {jobs = HashMap.insert k job q.jobs}
return (Take d w est)
case step of
Done a -> return a
Await key v -> await i key v
Take d w est ->
acquireFor i k est >>= \case
Just a -> do
forM_ w (unwait i . fst)
return a
Nothing -> case (d, w) of
(Wait, Just (key, v)) -> await i key v
(RefuseKeep e, _) -> return (Refused TooLong e)
_ -> return Failed
where
-- a request that may not wait does not, even for a job due at once
decision est room holder =
case decide Situation {expected = est, patience = wait, reach = i.settings.horizon, hasRoom = room, holder} of
Wait | wait <= 0 -> RefuseKeep est
d -> d
-- | Queue a key for upkeep, behind the jobs that requests asked for, or
-- add the payload to its job. The payload is given back to the runner if
-- the store is not ready ('abandon'), if another store holds the lock
-- ('blocked'), or if the lock cannot be taken ('failed').
upkeep :: (Hashable k, Semigroup p) => Indexer k p -> k -> p -> IO ()
upkeep i k p =
i.runner.ready >>= \case
False -> do
atomically (modifyTVar' i.counts (\c -> c {dropped = c.dropped + 1}))
i.runner.abandon k p
True -> do
reserved <- atomically $ do
q <- readTVar i.queue
med <- median i.settings.guess <$> readTVar i.times
case HashMap.lookup k q.jobs of
Just job -> do
let job' = case job.stage of
Running t again -> job {stage = Running t (Just (maybe p (<> p) again))}
Finishing a again -> job {stage = Finishing a (Just (maybe p (<> p) again))}
_ -> job {payload = job.payload <> p}
writeTVar i.queue q {jobs = HashMap.insert k job' q.jobs}
return Nothing
Nothing -> do
let job = Job {payload = p, asked = False, waiters = [], stage = Pending}
place = Seq.length q.first + Seq.length q.second
writeTVar i.queue q {jobs = HashMap.insert k job q.jobs}
return (Just (estimate med i.settings.workers place))
forM_ reserved (void . acquireFor i k)
-- | Take the lock of a reserved job and queue it; or, if another store
-- holds the lock or it cannot be taken, drop the reservation, answer the
-- requests that joined it, and give its payload back. 'Nothing' once the
-- job is queued.
acquireFor :: (Hashable k) => Indexer k p -> k -> Int -> IO (Maybe Answer)
acquireFor i k est =
tryAny (i.lock.acquire k est) >>= \case
Right Took -> do
atomically . modifyTVar' i.queue $ \q -> case HashMap.lookup k q.jobs of
Just job@Job {stage = Pending}
| job.asked -> q {first = q.first |> k, jobs = HashMap.insert k job {stage = Queued} q.jobs}
| otherwise -> q {second = q.second |> k, jobs = HashMap.insert k job {stage = Queued} q.jobs}
_ -> q
return Nothing
Right (Held t) -> do
let a = case decide (Situation 0 0 0 False (AnotherStore t)) of
RefuseNothing why e -> Refused why e
_ -> Refused OtherStore (max 0 t)
gone <- atomically (unreserve a)
forM_ gone $ \j -> i.runner.blocked k j.payload t `catchAny` \_ -> return ()
return (Just a)
Left e -> do
gone <- atomically (unreserve Failed)
forM_ gone $ \j -> i.runner.failed k j.payload e `catchAny` \_ -> return ()
return (Just Failed)
where
unreserve a = do
q <- readTVar i.queue
case HashMap.lookup k q.jobs of
Just job@Job {stage = Pending} -> do
writeTVar i.queue q {jobs = HashMap.delete k q.jobs}
mapM_ (answer a) job.waiters
return (Just job)
_ -> return Nothing
-- | A request joins the job of a key: a queued job of upkeep moves to the
-- end of the first part, and takes the payload of the request; a running
-- job takes nothing but the waiter, since what the request adds would only
-- be read after the job is done.
joinJob :: (Hashable k, Semigroup p) => Indexer k p -> k -> p -> Maybe (TVar Verdict) -> STM ()
joinJob i k p v = do
q <- readTVar i.queue
forM_ (HashMap.lookup k q.jobs) $ \job -> do
let ws = maybeToList v <> job.waiters
joined = job {payload = job.payload <> p, asked = True, waiters = ws}
case job.stage of
Running {} -> writeTVar i.queue q {jobs = HashMap.insert k job {waiters = ws} q.jobs}
Queued
| not job.asked ->
writeTVar
i.queue
q
{ first = q.first |> k,
second = Seq.filter (/= k) q.second,
jobs = HashMap.insert k joined q.jobs
}
_ -> writeTVar i.queue q {jobs = HashMap.insert k joined q.jobs}
-- | When the job of a key that a request joins should be done: a queued
-- one from its place, the place at the end of the first part for upkeep,
-- which the request moves there; a running one from what it has left.
--
-- What a running job has left is what its size says it takes, at the rate
-- of the latest jobs that told theirs, less what it has run; without a
-- size, the median less what it has run; and once it has run longer than
-- either, the median again. It never grows with the time that the job has
-- run: an estimate that did, as long again as the job had run, sent clients
-- back at about twice its length.
joinEstimate :: (Hashable k) => Int -> Queue k p -> Int -> Maybe Int -> Int -> k -> Job p -> Int
joinEstimate threads q med expected now k job = case job.stage of
Running (Just t) _ ->
let e = max 0 (now - t)
in case expected of
Just total | total > e -> total - e
Nothing | med > e -> med - e
_ -> med
Running Nothing _ -> fromMaybe med expected
Finishing {} -> 0
Queued | job.asked -> estimate med threads (fromMaybe (Seq.length q.first) (Seq.elemIndexL k q.first))
_ -> estimate med threads (Seq.length q.first)
-- | What the running job of a key is expected to take in all, from the
-- size that it told and the rate of the latest jobs that told theirs; or
-- 'Nothing' if it told none.
expectedOf :: (Hashable k) => Indexer k p -> k -> STM (Maybe Int)
expectedOf i k = ($ k) <$> expectations i
-- | 'expectedOf' for every key at once.
expectations :: (Hashable k) => Indexer k p -> STM (k -> Maybe Int)
expectations i = do
sizes <- readTVar i.sizes
rate <- median rateGuess <$> readTVar i.rates
return $ \k -> (\n -> n * rate `div` 1000) <$> HashMap.lookup k sizes
-- | Microseconds per thousand transactions of a job, before any job has
-- told its size: 100 microseconds a transaction, about twice what the
-- Redis cache takes for a large wallet.
rateGuess :: Int
rateGuess = 100000
-- | A new waiter, whose time is up at the given time.
waiter :: Indexer k p -> k -> Int -> STM ((Int, Int), TVar Verdict)
waiter i k deadline = do
n <- readTVar i.serial
writeTVar i.serial (n + 1)
v <- newTVar Waiting
modifyTVar' i.deadlines (Map.insert (deadline, n) (k, v))
return ((deadline, n), v)
-- | Forget a waiter.
unwait :: Indexer k p -> (Int, Int) -> IO ()
unwait i key = atomically (modifyTVar' i.deadlines (Map.delete key))
-- | Wait for a verdict.
await :: Indexer k p -> (Int, Int) -> TVar Verdict -> IO Answer
await i key v = do
a <-
atomically
( readTVar v >>= \case
Waiting -> retry
Answered a -> return a
)
`finally` unwait i key
case a of
Indexed -> atomically (modifyTVar' i.counts (\c -> c {answered = c.answered + 1}))
_ -> return ()
return a
-- | Tell a waiting request, unless it was told already.
answer :: Answer -> TVar Verdict -> STM ()
answer a v =
readTVar v >>= \case
Waiting -> writeTVar v (Answered a)
_ -> return ()
-- | Count a refusal.
refuse :: Indexer k p -> Refusal -> STM ()
refuse i why = modifyTVar' i.counts $ \c ->
let r = c.refused
in c
{ refused = case why of
OtherStore -> r {otherStore = r.otherStore + 1}
QueueFull -> r {queueFull = r.queueFull + 1}
BeyondHorizon -> r {beyondHorizon = r.beyondHorizon + 1}
TooLong -> r {tooLong = r.tooLong + 1}
WaitedOut -> r {waitedOut = r.waitedOut + 1}
NotInSync -> r {notInSync = r.notInSync + 1}
}
-------------------------------------------------------------------------------
-- Running
-------------------------------------------------------------------------------
-- | Take the next job: the first that a request asked for, or the first of
-- upkeep. It blocks while there is none.
next :: (Hashable k) => Indexer k p -> IO (k, Job p)
next i = atomically (readTVar i.queue >>= pick)
where
pick q = do
(k, q') <- case (Seq.viewl q.first, Seq.viewl q.second) of
(k :< rest, _) -> return (k, q {first = rest})
(EmptyL, k :< rest) -> return (k, q {second = rest})
(EmptyL, EmptyL) -> retry
case HashMap.lookup k q'.jobs of
Just job -> do
writeTVar i.queue q' {jobs = HashMap.insert k job {stage = Running Nothing Nothing} q'.jobs}
return (k, job)
-- not possible: every key of the queue has a job
Nothing -> pick q'
-- | Run the next job in this thread, if there is one: for tests, which run
-- jobs one by one without the threads of 'runIndexer'. Returns whether
-- there was one.
runNext :: (Hashable k) => Indexer k p -> IO Bool
runNext i = do
q <- atomically (readTVar i.queue)
if Seq.null q.first && Seq.null q.second
then return False
else next i >>= run i >> return True
-- | Run a job, then let go of its lock and tell the requests that wait.
run :: (Hashable k) => Indexer k p -> (k, Job p) -> IO ()
run i (k, job) =
i.runner.ready >>= \case
False -> do
atomically (modifyTVar' i.counts (\c -> c {dropped = c.dropped + 1}))
i.runner.abandon k job.payload `catchAny` \_ -> return ()
finish i k (Refused NotInSync i.settings.horizon)
True -> do
t0 <- i.clock
atomically . modifyTVar' i.queue $ \q ->
q {jobs = HashMap.adjust (\j -> j {stage = started t0 j.stage}) k q.jobs}
-- the estimate in the lock, which the other stores read, from now
-- that the job runs, and again once it tells its size
publish i k
r <- tryAny $ do
b <- i.runner.budget k
let told n = do
atomically (modifyTVar' i.sizes (HashMap.insert k (max 0 n)))
publish i k
b.sized n
i.runner.index b {sized = told} k job.payload `finally` b.finish
t1 <- i.clock
size <- atomically $ do
sz <- HashMap.lookup k <$> readTVar i.sizes
modifyTVar' i.sizes (HashMap.delete k)
return sz
case r of
Right () -> do
atomically $ do
modifyTVar' i.counts (\c -> c {done = c.done + 1})
when job.asked $ modifyTVar' i.times (\ts -> Seq.take recentJobs ((t1 - t0) Seq.<| ts))
forM_ size $ \n ->
when (n > 0) $
modifyTVar' i.rates (\rs -> Seq.take recentJobs (((t1 - t0) * 1000 `div` n) Seq.<| rs))
finish i k Indexed
Left e -> do
atomically (modifyTVar' i.counts (\c -> c {errors = c.errors + 1}))
i.runner.failed k job.payload e `catchAny` \_ -> return ()
finish i k Failed
where
started t = \case
Running _ again -> Running (Just t) again
s -> s
-- | A job is done: tell the requests that wait, at once; then queue its key
-- again if upkeep came while it ran, keeping the lock, or let go of the
-- lock, then of the job.
--
-- The job stays, finishing, while its lock is let go, which is a call to
-- Redis: a request that comes meanwhile has its answer at once, and upkeep
-- that comes meanwhile is queued again once the lock is gone, taking it
-- anew. Without that, either would have found the lock of this store, and
-- taken it for that of another. The requests that waited do not wait for
-- that call: what they read was written before it.
finish :: (Hashable k) => Indexer k p -> k -> Answer -> IO ()
finish i k a = do
kept <- atomically $ do
q <- readTVar i.queue
case HashMap.lookup k q.jobs of
Nothing -> return (Just [])
Just job -> case job.stage of
Running _ (Just p) -> do
let job' = Job {payload = p, asked = False, waiters = [], stage = Queued}
writeTVar i.queue q {second = q.second |> k, jobs = HashMap.insert k job' q.jobs}
return (Just job.waiters)
_ -> do
mapM_ (answer a) job.waiters
writeTVar i.queue q {jobs = HashMap.insert k job {waiters = [], stage = Finishing a Nothing} q.jobs}
return Nothing
case kept of
Just ws -> atomically (mapM_ (answer a) ws)
Nothing -> do
i.lock.release k `catchAny` \_ -> return ()
again <- atomically $ do
q <- readTVar i.queue
med <- median i.settings.guess <$> readTVar i.times
case HashMap.lookup k q.jobs of
Just job -> do
mapM_ (answer a) job.waiters
case job.stage of
Finishing _ (Just p) -> do
let job' = Job {payload = p, asked = False, waiters = [], stage = Pending}
place = Seq.length q.first + Seq.length q.second
writeTVar i.queue q {jobs = HashMap.insert k job' q.jobs}
return (Just (estimate med i.settings.workers place))
_ -> do
writeTVar i.queue q {jobs = HashMap.delete k q.jobs}
return Nothing
Nothing -> return Nothing
forM_ again (void . acquireFor i k)
-- | Refuse the requests whose time is up, with the estimate of their jobs:
-- what the sweeper does ten times a second. Each request counts its own
-- refusal ('request').
sweep :: (Hashable k) => Indexer k p -> IO ()
sweep i = do
now <- i.clock
atomically $ do
ds <- readTVar i.deadlines
let (due, rest) = Map.spanAntitone (\(t, _) -> t <= now) ds
unless (Map.null due) $ do
writeTVar i.deadlines rest
q <- readTVar i.queue
med <- median i.settings.guess <$> readTVar i.times
forM_ due $ \(k, v) ->
readTVar v >>= \case
Waiting -> do
expected <- expectedOf i k
let e = maybe med (joinEstimate i.settings.workers q med expected now k) (HashMap.lookup k q.jobs)
writeTVar v (Answered (Refused WaitedOut e))
Answered _ -> return ()
-- | Put the estimate of the job of a key in its lock now, rather than at
-- the next renewal: when it starts to run, and when it tells its size. Every
-- store of a fleet decides from the estimate in the lock, and gives the
-- same @Retry-After@ from it.
publish :: (Hashable k) => Indexer k p -> k -> IO ()
publish i k = do
now <- i.clock
est <- atomically $ do
q <- readTVar i.queue
med <- median i.settings.guess <$> readTVar i.times
expected <- expectedOf i k
return (joinEstimate i.settings.workers q med expected now k <$> HashMap.lookup k q.jobs)
forM_ est $ \e -> void (i.lock.renew [(k, e)]) `catchAny` \_ -> return ()
-- | Renew the locks of the jobs that this store holds, queued or running,
-- each with its estimate, and tell the runner which they are: what the
-- indexer does every so often ('every' of the lock).
renewHeld :: (Hashable k) => Indexer k p -> IO ()
renewHeld i = do
now <- i.clock
(held, payloads) <- atomically $ do
q <- readTVar i.queue
med <- median i.settings.guess <$> readTVar i.times
expecting <- expectations i
let threads = i.settings.workers
places = HashMap.fromList (zip (foldr (:) [] (q.first <> q.second)) [0 :: Int ..])
estimateOf k job = case job.stage of
Running {} -> joinEstimate threads q med (expecting k) now k job
_ -> estimate med threads (HashMap.findWithDefault 0 k places)
mine = [(k, job) | (k, job) <- HashMap.toList q.jobs, holding job.stage]
return
( [(k, estimateOf k job) | (k, job) <- mine],
concat [(k, job.payload) : [(k, p) | Running _ (Just p) <- [job.stage]] | (k, job) <- mine]
)
n <- i.lock.renew held `catchAny` \_ -> return 0
when (n > 0) $ atomically (modifyTVar' i.counts (\c -> c {lost = c.lost + n}))
i.runner.renew payloads `catchAny` \_ -> return ()
where
-- a pending job has not taken its lock yet, and a finishing one is
-- letting go of it
holding = \case
Pending -> False
Finishing {} -> False
_ -> True
-------------------------------------------------------------------------------
-- Watching
-------------------------------------------------------------------------------
-- | What the indexer holds and has done.
data IndexerStats = IndexerStats
{ -- | jobs in the first part of the queue, which requests asked for
forRequests :: !Int,
-- | jobs of upkeep in the queue
forUpkeep :: !Int,
-- | jobs running
running :: !Int,
-- | requests waiting for a job
waiting :: !Int,
-- | what it has done since the start
counts :: !Counts,
-- | the median time of the latest jobs that requests asked for, in
-- microseconds
median :: !Int,
-- | threads that run jobs
threads :: !Int
}
deriving (Eq, Show)
-- | Whether the indexer has nothing to do: no job queued, waiting for its
-- lock, running or letting go of its lock. For tests, and for a store that
-- wants to know that its upkeep has caught up.
indexerIdle :: Indexer k p -> IO Bool
indexerIdle i = HashMap.null . (.jobs) <$> atomically (readTVar i.queue)
-- | What the indexer holds and has done now.
indexerStats :: Indexer k p -> IO IndexerStats
indexerStats i = atomically $ do
q <- readTVar i.queue
ds <- readTVar i.deadlines
ts <- readTVar i.times
c <- readTVar i.counts
return
IndexerStats
{ forRequests = Seq.length q.first,
forUpkeep = Seq.length q.second,
running = length [() | Job {stage = Running {}} <- HashMap.elems q.jobs],
waiting = Map.size ds,
counts = c,
median = median i.settings.guess ts,
threads = i.settings.workers
}