haskoin-store-1.16.0: test/Haskoin/Store/XPub/IndexerSpec.hs
-- | The indexer of xpubs: its decisions, as a pure function, and its queue,
-- its waits and its lock, with jobs run one by one on a clock that the tests
-- move by hand, and once with its own threads on the clock of the system.
module Haskoin.Store.XPub.IndexerSpec (spec) where
import Control.Concurrent (threadDelay)
import Control.Concurrent.Async (async, forConcurrently, wait, withAsync)
import Control.Concurrent.MVar (newEmptyMVar, putMVar, readMVar)
import Control.Monad (forM_, replicateM, void, when)
import Data.IORef (IORef, atomicModifyIORef', modifyIORef', newIORef, readIORef, writeIORef)
import Data.List (sort)
import GHC.Clock (getMonotonicTimeNSec)
import Haskoin.Store.XPub (Budget (..), noBudget)
import Haskoin.Store.XPub.Indexer
import Haskoin.Store.XPub.Lock (Lock (..), Taken (..), noLock)
import Test.Hspec
spec :: Spec
spec = do
describe "the decision for a key that the cache does not have" $ do
let s holder est room = Situation {expected = est, patience = 5, reach = 30, hasRoom = room, holder}
it "takes nothing when another store holds the key, and retries from its lock" $ do
decide (s (AnotherStore 7) 1 True) `shouldBe` RefuseNothing OtherStore 7
decide (s (AnotherStore (-3)) 1 True) `shouldBe` RefuseNothing OtherStore 0
it "joins the job of this store within the wait, whatever the room" $ do
decide (s ThisStore 5 False) `shouldBe` Wait
decide (s ThisStore 1 True) `shouldBe` Wait
it "keeps the job of this store beyond the wait, and retries from the estimate" $ do
decide (s ThisStore 6 True) `shouldBe` RefuseKeep 6
decide (s ThisStore 60 False) `shouldBe` RefuseKeep 60
it "takes nothing with a full queue, and retries at the horizon" $ do
decide (s Nobody 1 False) `shouldBe` RefuseNothing QueueFull 30
decide (s Nobody 60 False) `shouldBe` RefuseNothing QueueFull 30
it "takes nothing beyond the horizon, and retries at the horizon" $
decide (s Nobody 31 True) `shouldBe` RefuseNothing BeyondHorizon 30
it "queues, locks and waits within the wait" $ do
decide (s Nobody 5 True) `shouldBe` Wait
decide (s Nobody 0 True) `shouldBe` Wait
it "queues and locks, and retries from the estimate, within the horizon" $ do
decide (s Nobody 6 True) `shouldBe` RefuseKeep 6
decide (s Nobody 30 True) `shouldBe` RefuseKeep 30
it "estimates a place in the queue from the median and the threads" $ do
estimate 100 4 0 `shouldBe` 100
estimate 100 4 4 `shouldBe` 200
estimate 100 4 6 `shouldBe` 250
estimate 100 1 3 `shouldBe` 400
it "says Retry-After in whole seconds, at least one" $
map retryAfter [0, 1, 999999, 1000000, 1000001, 4200000] `shouldBe` [1, 1, 1, 1, 2, 5]
describe "the indexer" $ do
it "runs one job for a key however many requests ask, and wakes them all when it is done" $ do
t <- testbed settings
answers <- withAsync (forConcurrently [1 .. 20] (\n -> request t.indexer 'x' [n])) $ \a -> do
waiting t 20
runNext t.indexer `shouldReturn` True
runNext t.indexer `shouldReturn` False
wait a
-- each told that the cache has the key now, to read it there
answers `shouldBe` replicate 20 Indexed
-- the job with what each request brought
map (fmap sort) <$> readIORef t.ran `shouldReturn` [('x', [1 .. 20])]
readIORef t.locks `shouldReturn` ["take x", "release x"]
s <- indexerStats t.indexer
(s.counts.done, s.counts.answered, s.waiting) `shouldBe` (1, 20, 0)
it "runs the jobs that requests wait for before upkeep, in the order they came" $ do
t <- testbed settings
upkeep t.indexer 'a' [1]
upkeep t.indexer 'b' [2]
upkeep t.indexer 'c' [3]
r1 <- async (request t.indexer 'd' [4])
waiting t 1
-- a request for a key queued for upkeep moves it to the first part
r2 <- async (request t.indexer 'c' [5])
waiting t 2
replicateM 5 (runNext t.indexer) `shouldReturn` [True, True, True, True, False]
map fst <$> readIORef t.ran `shouldReturn` "dcab"
lookup 'c' <$> readIORef t.ran `shouldReturn` Just [3, 5]
mapM wait [r1, r2] `shouldReturn` [Indexed, Indexed]
it "goes on with a job after the requests that wait for it are refused" $ do
t <- testbed settings
gate <- newEmptyMVar
writeIORef t.during (readMVar gate)
r <- async (request t.indexer 'x' [])
waiting t 1
job <- async (runNext t.indexer)
waitFor (not . null <$> readIORef t.started)
t.advance (settings.wait + 1)
sweep t.indexer
wait r >>= (`shouldSatisfy` refusedFor WaitedOut)
putMVar gate ()
wait job `shouldReturn` True
readIORef t.ran `shouldReturn` [('x', [])]
readIORef t.locks `shouldReturn` ["take x", "release x"]
it "refuses a waiting request at a sweep once its time is up, by its own clock" $ do
t <- testbed settings
r <- async (request t.indexer 'x' [])
waiting t 1
-- nothing is refused before its time, however often the sweeper runs
t.advance (settings.wait - 1)
forM_ [1 .. 3 :: Int] $ \_ -> sweep t.indexer
threadDelay 20000
(.waiting) <$> indexerStats t.indexer `shouldReturn` 1
t.advance 1
sweep t.indexer
a <- wait r
a `shouldSatisfy` refusedFor WaitedOut
-- the job has not run, so it is still where the request found it
a `shouldBe` Refused WaitedOut settings.guess
(.counts.refused.waitedOut) <$> indexerStats t.indexer `shouldReturn` 1
it "refuses a waiting request in time with its own threads, which set no timer" $ do
gate <- newEmptyMVar
let runner = (plainRunner (\_ _ () -> readMVar gate) :: Runner Char ()) {ready = return True}
withIndexer settings {wait = 300000, workers = 1} noLock runner $ \i -> do
asked <- now
a <- request i 'x' ()
told <- now
putMVar gate ()
a `shouldSatisfy` refusedFor WaitedOut
-- the sweeper runs ten times a second
(told - asked) `shouldSatisfy` (\d -> d >= 300000 && d < 1500000)
it "estimates from the median time of recent jobs and the place in the queue" $ do
t <- testbed settings {workers = 2}
-- each job takes as long as its payload says, on the hand clock
writeIORef t.length' True
forM_ (zip "abc" [100, 300, 200]) $ \(k, d) -> do
void (prefetch t.indexer k [d])
void (runNext t.indexer)
(.median) <$> indexerStats t.indexer `shouldReturn` 200
-- a request that does not wait is told the estimate: the median for
-- the first in the queue, then a half more for each, two threads
prefetch t.indexer 'd' [200] `shouldReturn` Refused TooLong 200
prefetch t.indexer 'e' [200] `shouldReturn` Refused TooLong 300
prefetch t.indexer 'f' [200] `shouldReturn` Refused TooLong 400
-- and a request that joins one of them, its place
prefetch t.indexer 'e' [] `shouldReturn` Refused TooLong 300
-- the jobs of upkeep are not timed
upkeep t.indexer 'g' [1000000]
void (runNext t.indexer >> runNext t.indexer >> runNext t.indexer >> runNext t.indexer)
(.median) <$> indexerStats t.indexer `shouldReturn` 200
it "takes nothing for a key that another store holds, and gives the payload of upkeep back" $ do
t <- testbed settings
writeIORef t.other (Just 4000000)
request t.indexer 'x' [1] `shouldReturn` Refused OtherStore 4000000
upkeep t.indexer 'y' [2]
-- the payloads of both come back, that of upkeep to be queued again
readIORef t.blocked `shouldReturn` [('x', [1], 4000000), ('y', [2], 4000000)]
runNext t.indexer `shouldReturn` False
s <- indexerStats t.indexer
(s.forRequests, s.forUpkeep, s.counts.refused.otherStore) `shouldBe` (0, 0, 1)
it "joins upkeep to a queued job, and runs a key again when upkeep comes while it runs" $ do
t <- testbed settings
upkeep t.indexer 'x' [1]
upkeep t.indexer 'x' [2]
gate <- newEmptyMVar
writeIORef t.during (readMVar gate)
job <- async (runNext t.indexer)
waitFor (not . null <$> readIORef t.started)
upkeep t.indexer 'x' [3]
upkeep t.indexer 'x' [4]
putMVar gate ()
wait job `shouldReturn` True
writeIORef t.during (return ())
runNext t.indexer `shouldReturn` True
runNext t.indexer `shouldReturn` False
readIORef t.ran `shouldReturn` [('x', [1, 2]), ('x', [3, 4])]
-- the lock is kept from one run to the next
readIORef t.locks `shouldReturn` ["take x", "release x"]
it "answers a request while it lets go of a lock, and takes it anew for upkeep that came meanwhile" $ do
t <- testbed settings
gate <- newEmptyMVar
writeIORef t.onRelease (readMVar gate)
void (prefetch t.indexer 'x' [1])
job <- async (runNext t.indexer)
waitFor ((== ["take x", "release x"]) <$> readIORef t.locks)
request t.indexer 'x' [2] `shouldReturn` Indexed
upkeep t.indexer 'x' [3]
writeIORef t.onRelease (return ())
putMVar gate ()
wait job `shouldReturn` True
runNext t.indexer `shouldReturn` True
readIORef t.ran `shouldReturn` [('x', [1]), ('x', [3])]
readIORef t.locks `shouldReturn` ["take x", "release x", "take x", "release x"]
it "takes nothing with a full queue, or beyond the horizon" $ do
t <- testbed settings {room = 1}
prefetch t.indexer 'a' [] `shouldReturn` Refused TooLong settings.guess
request t.indexer 'b' [] `shouldReturn` Refused QueueFull settings.horizon
u <- testbed settings {guess = settings.horizon + 1}
request u.indexer 'b' [] `shouldReturn` Refused BeyondHorizon settings.horizon
readIORef u.locks `shouldReturn` []
it "counts prefetches apart from the refusals of requests" $ do
t <- testbed settings {room = 1}
-- a prefetch that queues a job, and one that finds it
prefetch t.indexer 'a' [] `shouldReturn` Refused TooLong settings.guess
prefetch t.indexer 'a' [] `shouldReturn` Refused TooLong settings.guess
-- one that takes nothing, the queue being full
prefetch t.indexer 'b' [] `shouldReturn` Refused QueueFull settings.horizon
c <- (.counts) <$> indexerStats t.indexer
(c.prefetched, c.declined, c.refused) `shouldBe` (2, 1, Refusals 0 0 0 0 0 0)
-- a request is refused, and counted so
request t.indexer 'b' [] `shouldReturn` Refused QueueFull settings.horizon
d <- (.counts) <$> indexerStats t.indexer
(d.prefetched, d.declined, d.refused.queueFull) `shouldBe` (2, 1, 1)
it "takes no job while the store is not ready, and drops those it has" $ do
t <- testbed settings
upkeep t.indexer 'a' [1]
writeIORef t.ready' False
request t.indexer 'b' [2] `shouldReturn` Refused NotInSync settings.horizon
upkeep t.indexer 'c' [3]
runNext t.indexer `shouldReturn` True
readIORef t.ran `shouldReturn` []
sort <$> readIORef t.abandoned `shouldReturn` [('a', [1]), ('c', [3])]
readIORef t.locks `shouldReturn` ["take a", "release a"]
it "answers a request whose job failed, and goes on" $ do
t <- testbed settings
writeIORef t.during (fail "the database is gone")
r <- async (request t.indexer 'x' [1])
waiting t 1
runNext t.indexer `shouldReturn` True
wait r `shouldReturn` Failed
readIORef t.failures `shouldReturn` [('x', [1])]
readIORef t.locks `shouldReturn` ["take x", "release x"]
it "tells a request that joins a running job what its size leaves of it, never more as it runs" $ do
t <- testbed settings
-- a job of 1,000 transactions that takes 100 ms: 100 microseconds each
writeIORef t.length' True
writeIORef t.size (Just 1000)
void (prefetch t.indexer 'a' [100000])
void (runNext t.indexer)
-- a job of 50,000, which should take five seconds
writeIORef t.length' False
writeIORef t.size (Just 50000)
gate <- newEmptyMVar
writeIORef t.during (readMVar gate)
void (prefetch t.indexer 'b' [])
job <- async (runNext t.indexer)
waitFor (elem 'b' <$> readIORef t.started)
-- two seconds in, three are left
t.advance 2000000
prefetch t.indexer 'b' [] `shouldReturn` Refused TooLong 3000000
-- six seconds in, it has run longer than its size says: the median
t.advance 4000000
prefetch t.indexer 'b' [] `shouldReturn` Refused TooLong 100000
putMVar gate ()
wait job `shouldReturn` True
it "puts the estimate of a job in its lock when it starts, and when it tells its size" $ do
t <- testbed settings {workers = 1}
writeIORef t.size (Just 5000)
upkeep t.indexer 'a' [1]
void (runNext t.indexer)
-- the median at the start, then 5,000 transactions at the first
-- guess of the rate, 100 microseconds each
readIORef t.renewed `shouldReturn` [[('a', 100000)], [('a', 500000)]]
it "joins and waits for the job of this store when the door decided so, whatever its estimate" $ do
t <- testbed settings {workers = 1}
-- a job that tells it has 50,000 transactions: five seconds
writeIORef t.size (Just 50000)
upkeep t.indexer 'a' [5000000]
gate <- newEmptyMVar
writeIORef t.during (readMVar gate)
job <- async (runNext t.indexer)
waitFor ((== "a") <$> readIORef t.started)
-- this store's own estimate is beyond the wait of a second
request t.indexer 'a' [] `shouldReturn` Refused TooLong 5000000
-- but the door read the estimate in the lock, and decided to wait
waiter <- async (requestWithin t.indexer 1000000 'a' [])
waitFor ((== 1) . (.waiting) <$> indexerStats t.indexer)
putMVar gate ()
void (wait job)
wait waiter `shouldReturn` Indexed
it "renews the locks of the jobs that it holds, with their estimates" $ do
t <- testbed settings {workers = 1}
upkeep t.indexer 'a' [1]
void (prefetch t.indexer 'b' [2])
renewHeld t.indexer
readIORef t.renewed `shouldReturn` [[('a', 200000), ('b', 100000)]]
sort <$> readIORef t.kept `shouldReturn` [('a', [1]), ('b', [2])]
where
settings = defaultSettings {workers = 1, wait = 1000000, horizon = 30000000, room = 10, guess = 100000}
refusedFor why = \case
Refused w _ -> w == why
_ -> False
now = (`div` 1000) . fromIntegral <$> getMonotonicTimeNSec :: IO Int
-- | An indexer of characters with lists of numbers as payloads, on a hand
-- clock, with no threads of its own, and what it did.
data Testbed = Testbed
{ indexer :: Indexer Char [Int],
advance :: Int -> IO (),
-- | the jobs run, in order, with their payloads
ran :: IORef [(Char, [Int])],
-- | jobs started
started :: IORef [Char],
-- | what a job does before it ends
during :: IORef (IO ()),
-- | whether a job moves the clock on by the sum of its payload
length' :: IORef Bool,
-- | the size that a job tells, if any
size :: IORef (Maybe Int),
-- | what the lock did
locks :: IORef [String],
-- | what letting go of a lock does after it is noted
onRelease :: IORef (IO ()),
-- | when another store holds every lock, until when
other :: IORef (Maybe Int),
ready' :: IORef Bool,
abandoned :: IORef [(Char, [Int])],
blocked :: IORef [(Char, [Int], Int)],
failures :: IORef [(Char, [Int])],
renewed :: IORef [[(Char, Int)]],
kept :: IORef [(Char, [Int])]
}
testbed :: Settings -> IO Testbed
testbed s = do
clock <- newIORef 0
ran <- newIORef []
started <- newIORef []
during <- newIORef (return ())
length' <- newIORef False
size <- newIORef Nothing
locks <- newIORef []
onRelease <- newIORef (return ())
other <- newIORef Nothing
ready' <- newIORef True
abandoned <- newIORef []
blocked <- newIORef []
failures <- newIORef []
renewed <- newIORef []
kept <- newIORef []
let note r x = atomicModifyIORef' r (\xs -> (xs <> [x], ()))
lock =
Lock
{ acquire = \k _ ->
readIORef other >>= \case
Just t -> return (Held t)
Nothing -> note locks ("take " <> [k]) >> return Took,
renew = \ks -> note renewed (sort ks) >> return 0,
release = \k -> note locks ("release " <> [k]) >> (readIORef onRelease >>= id),
holder = \_ -> return Nothing,
every = 10000000
}
runner =
Runner
{ index = \b k p -> do
readIORef size >>= mapM_ b.sized
note started k
readIORef during >>= id
moves <- readIORef length'
when moves $ modifyIORef' clock (+ sum p)
note ran (k, p),
budget = \_ -> return noBudget,
ready = readIORef ready',
abandon = \k p -> note abandoned (k, p),
blocked = \k p t -> note blocked (k, p, t),
failed = \k p _ -> note failures (k, p),
renew = \jobs -> forM_ jobs (note kept)
}
i <- newIndexerWith (readIORef clock) s lock runner
return
Testbed
{ indexer = i,
advance = \d -> modifyIORef' clock (+ d),
ran,
started,
during,
length',
size,
locks,
onRelease,
other,
ready',
abandoned,
blocked,
failures,
renewed,
kept
}
-- | Wait until so many requests wait for a job.
waiting :: Testbed -> Int -> IO ()
waiting t n = waitFor ((== n) . (.waiting) <$> indexerStats t.indexer)
-- | Wait for something, for up to five seconds.
waitFor :: IO Bool -> IO ()
waitFor check = go (5000 :: Int)
where
go k =
check >>= \case
True -> return ()
False
| k <= 0 -> expectationFailure "timed out"
| otherwise -> threadDelay 1000 >> go (k - 1)