failure-detector (empty) → 0

raw patch · 8 files changed

+190/−0 lines, 8 filesdep +QuickCheckdep +basedep +containerssetup-changed

Dependencies added: QuickCheck, base, containers, failure-detector, statistics, tasty, tasty-quickcheck, time

Files

ChangeLog.md +5/−0
LICENSE +30/−0
Setup.hs +2/−0
failure-detector.cabal +45/−0
src/Distributed/Failure/Class.hs +19/−0
src/Distributed/Failure/Phi.hs +50/−0
tests/Distributed/Failure/Test/Properties.hs +20/−0
tests/Test.hs +19/−0

+ ChangeLog.md view

@@ -0,0 +1,5 @@+# Revision history for failure-detector++## 0  -- YYYY-mm-dd++* First version. Released on an unsuspecting world.

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright (c) 2016, davean++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of davean nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ failure-detector.cabal view

@@ -0,0 +1,45 @@+name:                failure-detector+version:             0+synopsis:            Failure Detectors implimented in Haskell.+license:             BSD3+license-file:        LICENSE+author:              davean+maintainer:          davean@xkcd.com+copyright:           Copyright (C) 2016 davean+stability:           provisional+category:            Distributed Computing+build-type:          Simple+extra-source-files:  ChangeLog.md+cabal-version:       >=1.10+bug-reports:         oss@xkcd.com++source-repository head+  type: git+  location: http://code.xkrd.net/distributed-systems/failure-detector.git++library+  hs-source-dirs:      src+  default-language:    Haskell2010+  exposed-modules:+        Distributed.Failure.Class+      , Distributed.Failure.Phi+  build-depends:+        base >=4.8 && <4.10+      , time == 1.6.*+      , containers+      , statistics++test-suite tests+  type:                exitcode-stdio-1.0+  main-is:             Test.hs+  other-modules:       Distributed.Failure.Test.Properties+  hs-source-dirs:      tests+  default-language:    Haskell2010+  ghc-options:         -Wall+  build-depends:+        failure-detector+      , base+      , time+      , tasty+      , tasty-quickcheck+      , QuickCheck

+ src/Distributed/Failure/Class.hs view

@@ -0,0 +1,19 @@+module Distributed.Failure.Class where++import           Data.Time+++class FailureDetector d where+    {- | Add a liveness event to our set of evidence about the target.+     -   Specified as the amount of time that passed since the last evidence before it.+     -}+    observe :: d -> DiffTime -> d+    {- | If the failure detector suspects the target is faulty,+     -   given that the specified amount of time has passed since the last sample.+     -}+    suspected :: d -> DiffTime -> Bool++{-+class Accrual d where+    suspicion :: d -> DiffTime ->+-}

+ src/Distributed/Failure/Phi.hs view

@@ -0,0 +1,50 @@+{-# LANGUAGE FlexibleInstances #-}+module Distributed.Failure.Phi (+   Phi(..), phi+ ) where++import           Data.Foldable+import           Data.List.NonEmpty (NonEmpty)+import           Data.Sequence (Seq, (<|))+import qualified Data.Sequence as Seq+import           Data.Time+import           Distributed.Failure.Class+import           Statistics.Distribution+import           Statistics.Distribution.Normal++data Phi =+  Phi {+    _pThresh :: Double+  , _pWindow :: Int+  , _pLog :: Seq Double+  }+  deriving (Show, Eq, Ord)++{- | Start a phi-acrual failure detector, given a Φ, a window size, and the+ -   starting messurements.+ -}+phi :: Double -> Int -> NonEmpty DiffTime -> Phi+phi t w l = Phi t w (Seq.fromList . fmap realToFrac . toList $ l)++instance FailureDetector Phi where+  observe (Phi t w l) d = Phi t w (Seq.take w $ (realToFrac d) <| l)+  suspected (Phi t _ l) d =+      t <= negate (logBase 10 pLater)+    where+      s = realToFrac . length $ l+      m = sum l/s+      sd = sqrt $ (sum . fmap (\i -> (i - m)^(2::Int)) $ l)/(s-1)+      -- Our effective standard deviation, is the calculated sd as above when in range.+      -- Sadly, during startup, or when our message regularity is higher then our+      -- clock precision, our sd diverges. In these cases we just take the mean,+      -- or, when the mean is also divergent, one.+      -- This means that in edge cases we do not respect the requested phi fully.+      -- The values of phi are still related to each other in the same ways though.+      -- Addtionally we still satisfy the failure detector requirements in that+      -- we still will eventually suspect any process that fails to communicate,+      -- and that we will return to trusting a correct process.+      esd = if (sd > 0) && (sd < (1/0))+            then sd+            else if m>0 then m else 1+      dist = normalDistr m esd+      pLater = complCumulative dist (realToFrac d)

+ tests/Distributed/Failure/Test/Properties.hs view

@@ -0,0 +1,20 @@+module Distributed.Failure.Test.Properties where++import Test.QuickCheck++import Distributed.Failure.Class++{- | We test that we eventually will decide a remote process is dead,+     after its been alive but stops responding.++     As a proxy for infinity, we'll claim that we should have detected it as dead if we don't+     hear from it for a year.+-}+eventuallyDead :: FailureDetector d => d -> [(Positive Double)] -> Property+eventuallyDead d0 liveLog =+  all (\(Positive t) -> t < (60*60*24*7)) liveLog ==>+      let d1 = foldl observe d0 . map (fromRational . toRational . getPositive) $ liveLog+          wasLife = not .  suspected d1 $ 0+          endsDead = suspected d1 $ 60*60*24*7*52+      in wasLife && endsDead+

+ tests/Test.hs view

@@ -0,0 +1,19 @@+{-# LANGUAGE ScopedTypeVariables #-}+import Data.List.NonEmpty+import Test.Tasty+import Test.Tasty.QuickCheck as QC++import Distributed.Failure.Test.Properties+import Distributed.Failure.Phi++main :: IO ()+main = defaultMain tests++tests :: TestTree+tests =+  testGroup "Phi-Acrual"+  [ QC.testProperty "Eventually dead" $+     \(Positive t) (Positive w) (Positive (i::Double)) ->+         (t > 0.3) && (i < (60*60*24*7)) ==>+                     eventuallyDead . phi t w $ (fromRational . toRational $ i) :| []+  ]