packages feed

memcache-0.5.0.0: test/RoutingSpec.hs

{-# LANGUAGE OverloadedStrings #-}
-- The tests of legacyServerForKey use it, although it is deprecated.
{-# OPTIONS_GHC -Wno-deprecations #-}

-- | Key routing: the ketama ring checked against libmemcached's choices, and
-- the cluster's use of it, including servers marked failed; and the router of
-- 0.4, checked against a copy of its code.
module RoutingSpec (routingSpec) where

import           Control.Concurrent.MVar   (newMVar, swapMVar)
import           Control.Monad             (void)
import qualified Data.ByteString.Char8     as C
import           Data.Foldable             (for_, toList)
import qualified Data.Hashable             as Hashable
import           Data.IORef                (readIORef, writeIORef)
import           Data.List                 (find, findIndex, group, nub, sort)
import           Data.Maybe                (fromMaybe, listToMaybe, maybeToList)
import           Data.Time.Clock.POSIX     (getPOSIXTime)
import           Data.Word                 (Word32)
import qualified Database.Memcache.Client  as Client
import           Database.Memcache.Cluster (Cluster, Options (..), getServers, isAlive,
                                            ketamaServerForKey, legacyServerForKey,
                                            newCluster, setServers)
import           Database.Memcache.Errors
import qualified Database.Memcache.Ketama  as K
import           Database.Memcache.Server  (Server, failed, serverHost, serverPort, sid)
import           Database.Memcache.Types   (Authentication (NoAuth), Key, ServerSpec (..))
import           KetamaVectors
import           Test.Hspec
import           Test.Hspec.QuickCheck     (prop)
import           Test.QuickCheck

routingSpec :: Spec
routingSpec = do
  describe "ketama ring" $ do
    it "hashes a key to the first four bytes of its MD5 digest, little-endian" $ do
      K.keyHash "foo" `shouldBe` 0xdb18bdac
      K.keyHash "key1" `shouldBe` 0x94d6adc2
      K.keyHash "SVa_]_V41)" `shouldBe` 0x1a7231c5
      K.keyHash "VDEAAAAA" `shouldBe` 0xfffcd1b5

    it "names a server by its host on port 11211 and host:port otherwise" $ do
      K.serverName "10.0.0.1" "11211" `shouldBe` "10.0.0.1"
      K.serverName "10.0.0.3" "11212" `shouldBe` "10.0.0.3:11212"
      K.serverName "localhost" "11212" `shouldBe` "localhost:11212"

    it "takes four little-endian points from the MD5 digest of each point name" $ do
      -- The digests of "10.0.0.1-0" and "10.0.0.3:11212-0".
      missingPoints "10.0.0.1" "11211" [0x2194783c, 0x36d6a85b, 0xf1edf592, 0x40a9b8cf]
        `shouldBe` []
      missingPoints "10.0.0.3" "11212" [0x0038906b, 0x901937a6, 0x4b190c65, 0x2e809329]
        `shouldBe` []

    it "shares out 160 points per server by weight" $ do
      pointCounts (ringOf (scenarioServers "fixture8_weighted"))
        `shouldBe` [176, 88, 56, 104, 296, 236, 280, 28]
      pointCounts (K.ring [("10.0.0.1", 1)]) `shouldBe` [160]

    it "rounds in single precision, giving 25 equal servers 156 points each" $ do
      pointCounts (ringOf (scenarioServers "eq25")) `shouldBe` replicate 25 156
      pointCounts (equalRing 24) `shouldBe` replicate 24 160
      pointCounts (equalRing 26) `shouldBe` replicate 26 160

    it "counts a weight below 1 as 1" $
      K.ringPoints (K.ring [("a", 0), ("b", -3)])
        `shouldBe` K.ringPoints (K.ring [("a", 1), ("b", 1)])

    for_ scenarios $ \(name, servers, keys) ->
      it ("routes keys as libmemcached does: " <> name) $ do
        let ring = ringOf servers
            hostPort i = let (host, port, _) = servers !! i in host <> ":" <> show port
        [(key, hostPort <$> K.owner ring (K.keyHash (C.pack key))) | (key, _) <- keys]
          `shouldBe` [(key, Just server) | (key, server) <- keys]

    it "gives a point two servers share to the server listed first" $ do
      -- Point 0 of "h8.example-20" and point 3 of "h256.example-34" are both
      -- 0xf53a3e63, and libmemcached gives it to whichever is listed first.
      let tiedOwners r = [o | (p, o) <- K.ringPoints r, p == 0xf53a3e63]
          h8First = ringOf [("h8.example", 11211, 1), ("h256.example", 11211, 1)]
          h256First = ringOf [("h256.example", 11211, 1), ("h8.example", 11211, 1)]
      tiedOwners h8First `shouldBe` [0, 1]
      tiedOwners h256First `shouldBe` [0, 1]
      K.owner h8First (K.keyHash "tie-10931") `shouldBe` Just 0
      K.owner h256First (K.keyHash "tie-10931") `shouldBe` Just 0

    it "wraps a hash after the last point round to the first point" $ do
      let ring = ringOf (scenarioServers "fixture8_weighted")
          firstOwner = snd <$> listToMaybe (K.ringPoints ring)
      K.keyHash "VDEAAAAA" `shouldSatisfy` (> maximum (map fst (K.ringPoints ring)))
      K.owner ring (K.keyHash "VDEAAAAA") `shouldBe` firstOwner
      K.owner ring maxBound `shouldBe` firstOwner

    it "moves only the removed server's keys when rebuilt without it" $ do
      -- libmemcached's choices with and without cache3 differ only for the
      -- keys that were on cache3.
      let withCache3 = scenarioKeys "host4"
          withoutCache3 = scenarioKeys "host4_minus_cache3"
          moved = [key | (key, server) <- withCache3, lookup key withoutCache3 /= Just server]
      moved `shouldBe` [key | (key, "cache3.example.com:11211") <- withCache3]
      -- The same holds for many more keys.
      let hostWith = hostFor (scenarioServers "host4")
          hostWithout = hostFor (scenarioServers "host4_minus_cache3")
          changes = filter (uncurry (/=)) [(hostWith key, hostWithout key) | key <- manyKeys]
      changes `shouldSatisfy` (not . null)
      map fst changes `shouldSatisfy` all (== Just "cache3.example.com")

    it "has no owner on an empty ring" $ do
      K.owner (K.ring []) 0 `shouldBe` Nothing
      K.owners (K.ring []) 0 `shouldBe` []

    let weighted = ringOf (scenarioServers "fixture8_weighted")
    it "gives a hash equal to a point to that point's owner" $ do
      let points = K.ringPoints weighted
          next = drop 1 points ++ take 1 points
      -- No two points share a value, so each point has a single owner.
      length (group (map fst points)) `shouldBe` length points
      [K.owner weighted p | (p, _) <- points] `shouldBe` [Just o | (_, o) <- points]
      [K.owner weighted (p + 1) | (p, _) <- points] `shouldBe` [Just o | (_, o) <- next]

    prop "falls back through every server once, starting with the owner" $ \hash ->
      let order = K.owners weighted hash
      in sort order === [0 .. 7] .&&. take 1 order === maybeToList (K.owner weighted hash)

    -- What libmemcached's auto-eject does, as long as the number of points
    -- per server stays the same (it does from 8 servers to 7).
    let names = map C.pack (equalHosts 8)
        withoutServer down = [name | (i, name) <- zip [0 ..] names, i /= down]
        ringsWithout = [K.ring [(name, 1) | name <- withoutServer down] | down <- [0 .. 7 :: Int]]
    prop "falls back to the server a ring rebuilt without the owner chooses" $ \hash ->
      case K.owners (equalRing 8) hash of
        down : next : _ ->
          ((withoutServer down !!) <$> K.owner (ringsWithout !! down) hash)
            === Just (names !! next)
        _ -> property False

  describe "cluster routing" $ do
    for_ [s | s@(_, servers, _) <- scenarios, all (\(_, _, w) -> w == 1) servers] $
      \(name, servers, keys) ->
        it ("routes keys as libmemcached does: " <> name) $ do
          cluster <- clusterOf servers
          routed <- mapM (route cluster . C.pack . fst) keys
          zip (map fst keys) routed `shouldBe` [(key, Just server) | (key, server) <- keys]

    it "gives a point two servers share to the server configured first" $ do
      -- The keys just below the tied point 0xf53a3e63 (see above).
      let keys = ["tie-10931", "tie-18872", "tie-235249", "tie-567986", "tie-706509"]
      h8First <- clusterOf [("h8.example", 11211, 1), ("h256.example", 11211, 1)]
      h256First <- clusterOf [("h256.example", 11211, 1), ("h8.example", 11211, 1)]
      mapM (route h8First) keys `shouldReturn` map (const (Just "h8.example:11211")) keys
      mapM (route h256First) keys `shouldReturn` map (const (Just "h256.example:11211")) keys

    it "names a server on the ring by its host in UTF-8" $ do
      -- Hosts with U+00E9 and U+20AC in them, and the UTF-8 bytes of their
      -- names written out.
      let servers = [ ("cach\233.example", "cach\195\169.example")
                    , ("cache\8364.example", "cache\226\130\172.example")
                    , ("10.0.1.3", "10.0.1.3") ]
          ring = K.ring [(C.pack utf8, 1) | (_, utf8) <- servers]
          expected key = (\i -> fst (servers !! i) <> ":11211") <$> K.owner ring (K.keyHash key)
      cluster <- clusterOf [(host, 11211, 1) | (host, _) <- servers]
      mapM (route cluster) manyKeys `shouldReturn` map expected manyKeys

    it "names a Unix socket on the ring by the bytes of its path" $ do
      -- Paths held a byte per Char, as the client connects to them and as
      -- parseServerSpec decodes memcached:///run/caf%C3%A9-a.sock: \195\169
      -- is U+00E9 in UTF-8. libmemcached names a socket by these bytes, so
      -- they mustn't be encoded in UTF-8 again, as a host's characters are.
      -- serverFor names each server by C.pack of its host, which keeps them.
      let sockets = [ ("/run/caf\195\169-a.sock", 11211, 1)
                    , ("/run/caf\195\169-b.sock", 11211, 1)
                    , ("/run/caf\195\169-c.sock", 0, 1) ]
      cluster <- clusterOf sockets
      mapM (route cluster) manyKeys `shouldReturn` map (serverFor sockets) manyKeys

    it "sends a failed server's keys to the next live server, and keeps the rest" $ do
      cluster <- clusterOf (scenarioServers "host4")
      cache3 <- serverNamed cluster "cache3.example.com:11211"
      let original = scenarioKeys "host4"
          routes = mapM (route cluster . C.pack . fst) original
          onCache3 (_, server) = server == "cache3.example.com:11211"
      markFailed cache3
      routed <- routes
      -- Where libmemcached sends them after ejecting cache3...
      routed `shouldBe` map (Just . snd) (scenarioKeys "host4_minus_cache3")
      -- ...which leaves every other key where it was.
      [r | (r, k) <- zip routed original, not (onCache3 k)]
        `shouldBe` [Just server | k@(_, server) <- original, not (onCache3 k)]
      writeIORef (failed cache3) 0
      routes `shouldReturn` map (Just . snd) original

    it "routes as a ring of only the live servers would, for many keys" $ do
      cluster <- clusterOf [(host, 11211, 1) | host <- equalHosts 8]
      down <- serverNamed cluster "10.0.1.6:11211"
      markFailed down
      let live = filter (/= "10.0.1.6") (equalHosts 8)
          ring = K.ring [(C.pack host, 1) | host <- live]
          expected key = (\i -> (live !! i) <> ":11211") <$> K.owner ring (K.keyHash key)
      routed <- mapM (route cluster) manyKeys
      routed `shouldBe` map expected manyKeys

    it "returns no server once every server is marked failed" $ do
      cluster <- clusterOf (scenarioServers "host4")
      mapM_ markFailed . toList =<< getServers cluster
      route cluster "key" `shouldReturn` Nothing
      Client.get cluster "key" `shouldThrow` (== ClientError NoServersReady)

    it "routes with ketamaServerForKey by default" $ do
      cluster <- clusterOf [(host, 11211, 1) | host <- equalHosts 8]
      markFailed =<< serverNamed cluster "10.0.1.6:11211"
      byName <- mapM (fmap (fmap serverLabel) . ketamaServerForKey cluster) manyKeys
      mapM (route cluster) manyKeys `shouldReturn` byName
      -- Every live server gets keys.
      length (nub byName) `shouldBe` 7

    it "isAlive counts a failed server as down until optsDeadRetryDelay has passed" $ do
      -- The cluster's delay is an hour, and the default 1.5 s.
      cluster <- clusterOf (scenarioServers "host4")
      server <- serverNamed cluster "cache3.example.com:11211"
      isAlive cluster server `shouldReturn` True
      now <- getPOSIXTime
      writeIORef (failed server) (now - 60)
      isAlive cluster server `shouldReturn` False
      readIORef (failed server) `shouldReturn` (now - 60)
      -- Once the delay has passed, the server is live again and the mark is
      -- cleared.
      writeIORef (failed server) (now - 7200)
      isAlive cluster server `shouldReturn` True
      readIORef (failed server) `shouldReturn` 0

    it "rebuilds its ring when the server set changes" $ do
      four <- clusterOf (scenarioServers "host4")
      three <- getServers =<< clusterOf (scenarioServers "host4_minus_cache3")
      servers <- newMVar =<< getServers four
      -- ElastiCache discovery replaces the servers in the MVar like this.
      let discovered = setServers four (Left servers)
          routes cluster = mapM (route cluster . C.pack . fst) (scenarioKeys "host4")
      routes discovered `shouldReturn` map (Just . snd) (scenarioKeys "host4")
      void (swapMVar servers three)
      routes discovered `shouldReturn` map (Just . snd) (scenarioKeys "host4_minus_cache3")
      -- The original cluster keeps its own servers and ring.
      routes four `shouldReturn` map (Just . snd) (scenarioKeys "host4")
      routes discovered `shouldReturn` map (Just . snd) (scenarioKeys "host4_minus_cache3")

    it "routes by the fixed servers that setServers gives it" $ do
      four <- clusterOf (scenarioServers "host4")
      three <- getServers =<< clusterOf (scenarioServers "host4_minus_cache3")
      let routes cluster = mapM (route cluster . C.pack . fst) (scenarioKeys "host4")
      routes (setServers four (Right three))
        `shouldReturn` map (Just . snd) (scenarioKeys "host4_minus_cache3")
      routes four `shouldReturn` map (Just . snd) (scenarioKeys "host4")

    it "rebuilds its ring when only a port changes" $ do
      -- Two servers on one host, then the second replaced by one on another
      -- port.
      let pair = [("localhost", 11211, 1), ("localhost", 11212, 1)]
          replaced = [("localhost", 11211, 1), ("localhost", 11213, 1)]
      original <- clusterOf pair
      servers <- newMVar =<< getServers original
      let discovered = setServers original (Left servers)
      mapM (route discovered) manyKeys `shouldReturn` map (serverFor pair) manyKeys
      void (swapMVar servers =<< getServers =<< clusterOf replaced)
      mapM (route discovered) manyKeys `shouldReturn` map (serverFor replaced) manyKeys

    it "routes by host when discovery returns new or reordered servers" $ do
      -- This checks the host and port of each server chosen. The next test
      -- checks that they are the Server values in the MVar.
      four <- clusterOf (scenarioServers "host4")
      -- New Server values for the same hosts...
      fresh <- getServers =<< clusterOf (scenarioServers "host4")
      -- ...and the same hosts listed the other way round.
      reordered <- getServers =<< clusterOf (reverse (scenarioServers "host4"))
      servers <- newMVar =<< getServers four
      let discovered = setServers four (Left servers)
          routes = mapM (route discovered . C.pack . fst) (scenarioKeys "host4")
          expected = map (Just . snd) (scenarioKeys "host4")
      routes `shouldReturn` expected
      void (swapMVar servers fresh)
      routes `shouldReturn` expected
      void (swapMVar servers reordered)
      routes `shouldReturn` expected

    it "routes to the servers in the MVar when new ones have the same hosts" $ do
      four <- clusterOf (scenarioServers "host4")
      servers <- newMVar =<< getServers four
      let discovered = setServers four (Left servers)
          routes = mapM (route discovered . C.pack . fst) (scenarioKeys "host4")
      routes `shouldReturn` map (Just . snd) (scenarioKeys "host4")
      -- The ring can be reused, but the router must check, and return, the
      -- new Server values: once the new cache3 is marked failed, its keys
      -- move.
      fresh <- clusterOf (scenarioServers "host4")
      void (swapMVar servers =<< getServers fresh)
      markFailed =<< serverNamed fresh "cache3.example.com:11211"
      routes `shouldReturn` map (Just . snd) (scenarioKeys "host4_minus_cache3")

    it "rebuilds its ring when a server is added at the end" $ do
      -- As when a refresh finds a new node listed after the others, and keeps
      -- the Server values of the nodes it knows.
      let four = scenarioServers "host4"
          three = take 3 four
      original <- clusterOf three
      known <- getServers original
      servers <- newMVar known
      let discovered = setServers original (Left servers)
      mapM (route discovered) manyKeys `shouldReturn` map (serverFor three) manyKeys
      added <- getServers =<< clusterOf (drop 3 four)
      void (swapMVar servers (known <> added))
      mapM (route discovered) manyKeys `shouldReturn` map (serverFor four) manyKeys

    it "spreads keys evenly over eight equal servers" $ do
      cluster <- clusterOf [(host, 11211, 1) | host <- equalHosts 8]
      routed <- mapM (route cluster) manyKeys
      let counts = map length (group (sort routed))
          share count = fromIntegral count / fromIntegral (length manyKeys) :: Double
      length counts `shouldBe` 8
      map share counts `shouldSatisfy` all (\s -> s >= 0.09 && s <= 0.16)

  -- 0.4 sorted the servers by sid when it made a cluster and when ElastiCache
  -- discovery found them. Neither sorts them now, and legacyServerForKey must
  -- still pick the server 0.4 did.
  describe "legacyServerForKey" $ do
    prop "routes keys as 0.4 did" $
      forAll legacyServers $ \servers -> ioProperty $ do
        cluster <- clusterOf [(host, port, 1) | ((host, port), _) <- servers]
        configured <- toList <$> getServers cluster
        sequence_ [markFailed server | (server, (_, True)) <- zip configured servers]
        let live = [server | (server, (_, False)) <- zip configured servers]
            -- Servers named twice are told apart by position.
            position server = findIndex ((== failed server) . failed) configured
            legacyKeys = take 1000 manyKeys
        routed <- mapM (legacyServerForKey cluster) legacyKeys
        return $ map (>>= position) routed
          === [router04 live key >>= position | key <- legacyKeys]

    it "sends every key to one of two servers" $ do
      cluster <- clusterOf [(host, 11211, 1) | host <- equalHosts 8]
      routed <- mapM (fmap (fmap serverLabel) . legacyServerForKey cluster) manyKeys
      length (nub routed) `shouldSatisfy` (<= 2)

    it "returns no server once every server is marked failed" $ do
      cluster <- clusterOf (scenarioServers "host4")
      mapM_ markFailed . toList =<< getServers cluster
      legacyServerForKey cluster "key" `shouldReturn` Nothing

-- | Look up a scenario's servers or expected routes by name.
scenarioServers :: String -> [(String, Int, Int)]
scenarioServers name = concat [servers | (n, servers, _) <- scenarios, n == name]

scenarioKeys :: String -> [(String, String)]
scenarioKeys name = concat [keys | (n, _, keys) <- scenarios, n == name]

-- | A ring of servers given as (host, port, weight), in that order.
ringOf :: [(String, Int, Int)] -> K.Ring
ringOf servers =
  K.ring [(K.serverName (C.pack host) (C.pack (show port)), weight) | (host, port, weight) <- servers]

-- | The host each key belongs to on a ring of these servers.
hostFor :: [(String, Int, Int)] -> Key -> Maybe String
hostFor servers = \key -> (hosts !!) <$> K.owner ring (K.keyHash key)
  where
    ring = ringOf servers
    hosts = [host | (host, _, _) <- servers]

-- | The server each key belongs to on a ring of these servers, as host:port.
serverFor :: [(String, Int, Int)] -> Key -> Maybe String
serverFor servers = \key -> (names !!) <$> K.owner ring (K.keyHash key)
  where
    ring = ringOf servers
    names = [host <> ":" <> show port | (host, port, _) <- servers]

-- | Hosts 10.0.1.1, 10.0.1.2, and so on.
equalHosts :: Int -> [String]
equalHosts n = ["10.0.1." <> show i | i <- [1 .. n]]

-- | A ring of @n@ hosts on port 11211, all with weight 1.
equalRing :: Int -> K.Ring
equalRing n = K.ring [(C.pack host, 1) | host <- equalHosts n]

-- | How many points each server owns, in server order.
pointCounts :: K.Ring -> [Int]
pointCounts = map length . group . sort . map snd . K.ringPoints

-- | Which of the given points are missing from the ring of a single server.
missingPoints :: C.ByteString -> C.ByteString -> [Word32] -> [Word32]
missingPoints host port = filter (`notElem` points)
  where
    points = map fst (K.ringPoints (K.ring [(K.serverName host port, 1)]))

manyKeys :: [Key]
manyKeys = [C.pack ("key:" <> show i) | i <- [1 .. 20000 :: Int]]

-- | 0.4's router, getServerForKeyDefault, with lists for vectors: of the live
-- servers, sorted by sid as 0.4 kept them, the first whose sid is below the
-- key's hash, or else the last.
router04 :: [Server] -> Key -> Maybe Server
router04 live k =
  let hashedKey = Hashable.hash k
      searchF s = sid s < hashedKey
      servers' = sort live
  in if null servers'
      then Nothing
      else Just $ fromMaybe (last servers') (find searchF servers')

-- | One to eight servers, each marked failed or not, from a few hosts and
-- ports, so that some lists name a server twice.
legacyServers :: Gen [((String, Int), Bool)]
legacyServers = do
  n <- choose (1, 8)
  vectorOf n ((,) <$> server <*> frequency [(3, pure False), (1, pure True)])
  where
    server = (,) <$> elements ["cache" <> show i <> ".example" | i <- [1 .. 10 :: Int]]
                 <*> elements [11211, 11212]

-- | A cluster of servers given as (host, port, weight); weights are ignored.
-- No connections are made until a request is sent.
clusterOf :: [(String, Int, Int)] -> IO Cluster
clusterOf servers =
  newCluster [ServerSpec host (show port) NoAuth | (host, port, _) <- servers]
    Client.def { optsDeadRetryDelay = 3600000 }

-- | The server the cluster's default router picks for a key, as host:port.
route :: Cluster -> Key -> IO (Maybe String)
route cluster key = fmap serverLabel <$> optsGetServerForKey Client.def cluster key

serverLabel :: Server -> String
serverLabel server = serverHost server <> ":" <> serverPort server

serverNamed :: Cluster -> String -> IO Server
serverNamed cluster name = do
  servers <- toList <$> getServers cluster
  case filter ((== name) . serverLabel) servers of
    [server] -> return server
    found -> fail ("expected one server " <> name <> ", found " <> show (length found))

-- | Mark a server failed now, as running out of retries does.
markFailed :: Server -> IO ()
markFailed server = writeIORef (failed server) =<< getPOSIXTime