{-# OPTIONS_HADDOCK not-home #-}

module Database.LSMTree.Internal.Config (
    LevelNo (..)
    -- * Table configuration
  , TableConfig (..)
  , defaultTableConfig
  , RunLevelNo (..)
  , runParamsForLevel
    -- * Table configuration override
  , TableConfigOverride
  , applyOverride
  , configNoOverride
  , configOverrideDiskCachePolicy
    -- * Merge policy
  , MergePolicy (..)
    -- * Size ratio
  , SizeRatio (..)
  , sizeRatioInt
    -- * Write buffer allocation
  , WriteBufferAlloc (..)
    -- * Bloom filter allocation
  , BloomFilterAlloc (..)
  , defaultBloomFilterAlloc
  , bloomFilterAllocForLevel
    -- * Fence pointer index
  , FencePointerIndexType (..)
  , indexTypeForRun
    -- * Disk cache policy
  , DiskCachePolicy (..)
  , diskCachePolicyForLevel
    -- * Merge schedule
  , MergeSchedule (..)
  , defaultMergeSchedule
  ) where

import           Control.DeepSeq (NFData (..))
import           Data.Maybe (fromMaybe)
import           Data.Monoid (Last (..))
import           Data.Word (Word64)
import           Database.LSMTree.Internal.Entry (NumEntries (..))
import           Database.LSMTree.Internal.Index (IndexType)
import qualified Database.LSMTree.Internal.Index as Index
                     (IndexType (Compact, Ordinary))
import           Database.LSMTree.Internal.Run (RunDataCaching (..))
import           Database.LSMTree.Internal.RunAcc (RunBloomFilterAlloc (..))
import           Database.LSMTree.Internal.RunBuilder (RunParams (..))

newtype LevelNo = LevelNo Int
  deriving stock (Int -> LevelNo -> ShowS
[LevelNo] -> ShowS
LevelNo -> String
(Int -> LevelNo -> ShowS)
-> (LevelNo -> String) -> ([LevelNo] -> ShowS) -> Show LevelNo
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> LevelNo -> ShowS
showsPrec :: Int -> LevelNo -> ShowS
$cshow :: LevelNo -> String
show :: LevelNo -> String
$cshowList :: [LevelNo] -> ShowS
showList :: [LevelNo] -> ShowS
Show, LevelNo -> LevelNo -> Bool
(LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool) -> Eq LevelNo
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: LevelNo -> LevelNo -> Bool
== :: LevelNo -> LevelNo -> Bool
$c/= :: LevelNo -> LevelNo -> Bool
/= :: LevelNo -> LevelNo -> Bool
Eq, Eq LevelNo
Eq LevelNo =>
(LevelNo -> LevelNo -> Ordering)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> Bool)
-> (LevelNo -> LevelNo -> LevelNo)
-> (LevelNo -> LevelNo -> LevelNo)
-> Ord LevelNo
LevelNo -> LevelNo -> Bool
LevelNo -> LevelNo -> Ordering
LevelNo -> LevelNo -> LevelNo
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
$ccompare :: LevelNo -> LevelNo -> Ordering
compare :: LevelNo -> LevelNo -> Ordering
$c< :: LevelNo -> LevelNo -> Bool
< :: LevelNo -> LevelNo -> Bool
$c<= :: LevelNo -> LevelNo -> Bool
<= :: LevelNo -> LevelNo -> Bool
$c> :: LevelNo -> LevelNo -> Bool
> :: LevelNo -> LevelNo -> Bool
$c>= :: LevelNo -> LevelNo -> Bool
>= :: LevelNo -> LevelNo -> Bool
$cmax :: LevelNo -> LevelNo -> LevelNo
max :: LevelNo -> LevelNo -> LevelNo
$cmin :: LevelNo -> LevelNo -> LevelNo
min :: LevelNo -> LevelNo -> LevelNo
Ord)
  deriving newtype (Int -> LevelNo
LevelNo -> Int
LevelNo -> [LevelNo]
LevelNo -> LevelNo
LevelNo -> LevelNo -> [LevelNo]
LevelNo -> LevelNo -> LevelNo -> [LevelNo]
(LevelNo -> LevelNo)
-> (LevelNo -> LevelNo)
-> (Int -> LevelNo)
-> (LevelNo -> Int)
-> (LevelNo -> [LevelNo])
-> (LevelNo -> LevelNo -> [LevelNo])
-> (LevelNo -> LevelNo -> [LevelNo])
-> (LevelNo -> LevelNo -> LevelNo -> [LevelNo])
-> Enum LevelNo
forall a.
(a -> a)
-> (a -> a)
-> (Int -> a)
-> (a -> Int)
-> (a -> [a])
-> (a -> a -> [a])
-> (a -> a -> [a])
-> (a -> a -> a -> [a])
-> Enum a
$csucc :: LevelNo -> LevelNo
succ :: LevelNo -> LevelNo
$cpred :: LevelNo -> LevelNo
pred :: LevelNo -> LevelNo
$ctoEnum :: Int -> LevelNo
toEnum :: Int -> LevelNo
$cfromEnum :: LevelNo -> Int
fromEnum :: LevelNo -> Int
$cenumFrom :: LevelNo -> [LevelNo]
enumFrom :: LevelNo -> [LevelNo]
$cenumFromThen :: LevelNo -> LevelNo -> [LevelNo]
enumFromThen :: LevelNo -> LevelNo -> [LevelNo]
$cenumFromTo :: LevelNo -> LevelNo -> [LevelNo]
enumFromTo :: LevelNo -> LevelNo -> [LevelNo]
$cenumFromThenTo :: LevelNo -> LevelNo -> LevelNo -> [LevelNo]
enumFromThenTo :: LevelNo -> LevelNo -> LevelNo -> [LevelNo]
Enum, LevelNo -> ()
(LevelNo -> ()) -> NFData LevelNo
forall a. (a -> ()) -> NFData a
$crnf :: LevelNo -> ()
rnf :: LevelNo -> ()
NFData)

{-------------------------------------------------------------------------------
  Table configuration
-------------------------------------------------------------------------------}

-- | Table configuration parameters, including LSM tree tuning parameters.
--
-- Some config options are fixed (for now):
--
-- * Merge policy: Tiering
--
-- * Size ratio: 4
data TableConfig = TableConfig {
    TableConfig -> MergePolicy
confMergePolicy       :: !MergePolicy
    -- Size ratio between the capacities of adjacent levels.
  , TableConfig -> SizeRatio
confSizeRatio         :: !SizeRatio
    -- | Total number of bytes that the write buffer can use.
    --
    -- The maximum is 4GiB, which should be more than enough for realistic
    -- applications.
  , TableConfig -> WriteBufferAlloc
confWriteBufferAlloc  :: !WriteBufferAlloc
  , TableConfig -> BloomFilterAlloc
confBloomFilterAlloc  :: !BloomFilterAlloc
  , TableConfig -> FencePointerIndexType
confFencePointerIndex :: !FencePointerIndexType
    -- | The policy for caching key\/value data from disk in memory.
  , TableConfig -> DiskCachePolicy
confDiskCachePolicy   :: !DiskCachePolicy
  , TableConfig -> MergeSchedule
confMergeSchedule     :: !MergeSchedule
  }
  deriving stock (Int -> TableConfig -> ShowS
[TableConfig] -> ShowS
TableConfig -> String
(Int -> TableConfig -> ShowS)
-> (TableConfig -> String)
-> ([TableConfig] -> ShowS)
-> Show TableConfig
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> TableConfig -> ShowS
showsPrec :: Int -> TableConfig -> ShowS
$cshow :: TableConfig -> String
show :: TableConfig -> String
$cshowList :: [TableConfig] -> ShowS
showList :: [TableConfig] -> ShowS
Show, TableConfig -> TableConfig -> Bool
(TableConfig -> TableConfig -> Bool)
-> (TableConfig -> TableConfig -> Bool) -> Eq TableConfig
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: TableConfig -> TableConfig -> Bool
== :: TableConfig -> TableConfig -> Bool
$c/= :: TableConfig -> TableConfig -> Bool
/= :: TableConfig -> TableConfig -> Bool
Eq)

instance NFData TableConfig where
  rnf :: TableConfig -> ()
rnf (TableConfig MergePolicy
a SizeRatio
b WriteBufferAlloc
c BloomFilterAlloc
d FencePointerIndexType
e DiskCachePolicy
f MergeSchedule
g) =
      MergePolicy -> ()
forall a. NFData a => a -> ()
rnf MergePolicy
a () -> () -> ()
forall a b. a -> b -> b
`seq` SizeRatio -> ()
forall a. NFData a => a -> ()
rnf SizeRatio
b () -> () -> ()
forall a b. a -> b -> b
`seq` WriteBufferAlloc -> ()
forall a. NFData a => a -> ()
rnf WriteBufferAlloc
c () -> () -> ()
forall a b. a -> b -> b
`seq` BloomFilterAlloc -> ()
forall a. NFData a => a -> ()
rnf BloomFilterAlloc
d () -> () -> ()
forall a b. a -> b -> b
`seq` FencePointerIndexType -> ()
forall a. NFData a => a -> ()
rnf FencePointerIndexType
e () -> () -> ()
forall a b. a -> b -> b
`seq` DiskCachePolicy -> ()
forall a. NFData a => a -> ()
rnf DiskCachePolicy
f () -> () -> ()
forall a b. a -> b -> b
`seq` MergeSchedule -> ()
forall a. NFData a => a -> ()
rnf MergeSchedule
g

-- | A reasonable default 'TableConfig'.
--
-- This uses a write buffer with up to 20,000 elements and a generous amount of
-- memory for Bloom filters (FPR of 2%).
--
defaultTableConfig :: TableConfig
defaultTableConfig :: TableConfig
defaultTableConfig =
    TableConfig
      { confMergePolicy :: MergePolicy
confMergePolicy       = MergePolicy
MergePolicyLazyLevelling
      , confSizeRatio :: SizeRatio
confSizeRatio         = SizeRatio
Four
      , confWriteBufferAlloc :: WriteBufferAlloc
confWriteBufferAlloc  = NumEntries -> WriteBufferAlloc
AllocNumEntries (Int -> NumEntries
NumEntries Int
20_000)
      , confBloomFilterAlloc :: BloomFilterAlloc
confBloomFilterAlloc  = BloomFilterAlloc
defaultBloomFilterAlloc
      , confFencePointerIndex :: FencePointerIndexType
confFencePointerIndex = FencePointerIndexType
OrdinaryIndex
      , confDiskCachePolicy :: DiskCachePolicy
confDiskCachePolicy   = DiskCachePolicy
DiskCacheAll
      , confMergeSchedule :: MergeSchedule
confMergeSchedule     = MergeSchedule
defaultMergeSchedule
      }

data RunLevelNo = RegularLevel LevelNo | UnionLevel

runParamsForLevel :: TableConfig -> RunLevelNo -> RunParams
runParamsForLevel :: TableConfig -> RunLevelNo -> RunParams
runParamsForLevel conf :: TableConfig
conf@TableConfig {MergeSchedule
DiskCachePolicy
FencePointerIndexType
BloomFilterAlloc
WriteBufferAlloc
SizeRatio
MergePolicy
confMergePolicy :: TableConfig -> MergePolicy
confSizeRatio :: TableConfig -> SizeRatio
confWriteBufferAlloc :: TableConfig -> WriteBufferAlloc
confBloomFilterAlloc :: TableConfig -> BloomFilterAlloc
confFencePointerIndex :: TableConfig -> FencePointerIndexType
confDiskCachePolicy :: TableConfig -> DiskCachePolicy
confMergeSchedule :: TableConfig -> MergeSchedule
confMergePolicy :: MergePolicy
confSizeRatio :: SizeRatio
confWriteBufferAlloc :: WriteBufferAlloc
confBloomFilterAlloc :: BloomFilterAlloc
confFencePointerIndex :: FencePointerIndexType
confDiskCachePolicy :: DiskCachePolicy
confMergeSchedule :: MergeSchedule
..} RunLevelNo
levelNo =
    RunParams
      { runParamCaching :: RunDataCaching
runParamCaching = DiskCachePolicy -> RunLevelNo -> RunDataCaching
diskCachePolicyForLevel DiskCachePolicy
confDiskCachePolicy RunLevelNo
levelNo
      , runParamAlloc :: RunBloomFilterAlloc
runParamAlloc   = TableConfig -> RunLevelNo -> RunBloomFilterAlloc
bloomFilterAllocForLevel TableConfig
conf RunLevelNo
levelNo
      , runParamIndex :: IndexType
runParamIndex   = FencePointerIndexType -> IndexType
indexTypeForRun FencePointerIndexType
confFencePointerIndex
      }

{-------------------------------------------------------------------------------
  Table configuration override
-------------------------------------------------------------------------------}

-- | Override configuration options in 'TableConfig' that can be changed dynamically.
--
-- Some parts of the 'TableConfig' are considered fixed after a table is
-- created. That is, these options should (i) should stay the same over the
-- lifetime of a table, and (ii) these options should not be changed when a
-- snapshot is created or loaded. Other options can be changed dynamically
-- without sacrificing correctness.
--
-- This type has 'Semigroup' and 'Monoid' instances for composing override
-- options.
data TableConfigOverride = TableConfigOverride {
      -- | Override for 'confDiskCachePolicy'
      TableConfigOverride -> Last DiskCachePolicy
confOverrideDiskCachePolicy  :: Last DiskCachePolicy
    }
    deriving stock Int -> TableConfigOverride -> ShowS
[TableConfigOverride] -> ShowS
TableConfigOverride -> String
(Int -> TableConfigOverride -> ShowS)
-> (TableConfigOverride -> String)
-> ([TableConfigOverride] -> ShowS)
-> Show TableConfigOverride
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> TableConfigOverride -> ShowS
showsPrec :: Int -> TableConfigOverride -> ShowS
$cshow :: TableConfigOverride -> String
show :: TableConfigOverride -> String
$cshowList :: [TableConfigOverride] -> ShowS
showList :: [TableConfigOverride] -> ShowS
Show

-- | Behaves like a point-wise 'Last' instance
instance Semigroup TableConfigOverride where
  TableConfigOverride
override1 <> :: TableConfigOverride -> TableConfigOverride -> TableConfigOverride
<> TableConfigOverride
override2 = TableConfigOverride {
        confOverrideDiskCachePolicy :: Last DiskCachePolicy
confOverrideDiskCachePolicy =
          TableConfigOverride -> Last DiskCachePolicy
confOverrideDiskCachePolicy TableConfigOverride
override1 Last DiskCachePolicy
-> Last DiskCachePolicy -> Last DiskCachePolicy
forall a. Semigroup a => a -> a -> a
<>
          TableConfigOverride -> Last DiskCachePolicy
confOverrideDiskCachePolicy TableConfigOverride
override2
      }

-- | Behaves like a point-wise 'Last' instance
instance Monoid TableConfigOverride where
  mempty :: TableConfigOverride
mempty = TableConfigOverride
configNoOverride

applyOverride :: TableConfigOverride -> TableConfig -> TableConfig
applyOverride :: TableConfigOverride -> TableConfig -> TableConfig
applyOverride TableConfigOverride{Last DiskCachePolicy
confOverrideDiskCachePolicy :: TableConfigOverride -> Last DiskCachePolicy
confOverrideDiskCachePolicy :: Last DiskCachePolicy
..} TableConfig
conf = TableConfig
conf {
      confDiskCachePolicy =
        fromMaybe (confDiskCachePolicy conf) (getLast confOverrideDiskCachePolicy)
    }

configNoOverride :: TableConfigOverride
configNoOverride :: TableConfigOverride
configNoOverride = TableConfigOverride {
      confOverrideDiskCachePolicy :: Last DiskCachePolicy
confOverrideDiskCachePolicy = Maybe DiskCachePolicy -> Last DiskCachePolicy
forall a. Maybe a -> Last a
Last Maybe DiskCachePolicy
forall a. Maybe a
Nothing
    }

configOverrideDiskCachePolicy :: DiskCachePolicy -> TableConfigOverride
configOverrideDiskCachePolicy :: DiskCachePolicy -> TableConfigOverride
configOverrideDiskCachePolicy DiskCachePolicy
pol = TableConfigOverride {
      confOverrideDiskCachePolicy :: Last DiskCachePolicy
confOverrideDiskCachePolicy = Maybe DiskCachePolicy -> Last DiskCachePolicy
forall a. Maybe a -> Last a
Last (DiskCachePolicy -> Maybe DiskCachePolicy
forall a. a -> Maybe a
Just DiskCachePolicy
pol)
    }

{-------------------------------------------------------------------------------
  Merge policy
-------------------------------------------------------------------------------}

data MergePolicy =
    -- | Use tiering on intermediate levels, and levelling on the last level.
    -- This makes it easier for delete operations to disappear on the last
    -- level.
    MergePolicyLazyLevelling
    -- TODO: add other merge policies, like tiering and levelling.
  deriving stock (MergePolicy -> MergePolicy -> Bool
(MergePolicy -> MergePolicy -> Bool)
-> (MergePolicy -> MergePolicy -> Bool) -> Eq MergePolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: MergePolicy -> MergePolicy -> Bool
== :: MergePolicy -> MergePolicy -> Bool
$c/= :: MergePolicy -> MergePolicy -> Bool
/= :: MergePolicy -> MergePolicy -> Bool
Eq, Int -> MergePolicy -> ShowS
[MergePolicy] -> ShowS
MergePolicy -> String
(Int -> MergePolicy -> ShowS)
-> (MergePolicy -> String)
-> ([MergePolicy] -> ShowS)
-> Show MergePolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> MergePolicy -> ShowS
showsPrec :: Int -> MergePolicy -> ShowS
$cshow :: MergePolicy -> String
show :: MergePolicy -> String
$cshowList :: [MergePolicy] -> ShowS
showList :: [MergePolicy] -> ShowS
Show)

instance NFData MergePolicy where
  rnf :: MergePolicy -> ()
rnf MergePolicy
MergePolicyLazyLevelling = ()

{-------------------------------------------------------------------------------
  Size ratio
-------------------------------------------------------------------------------}

data SizeRatio = Four
  deriving stock (SizeRatio -> SizeRatio -> Bool
(SizeRatio -> SizeRatio -> Bool)
-> (SizeRatio -> SizeRatio -> Bool) -> Eq SizeRatio
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: SizeRatio -> SizeRatio -> Bool
== :: SizeRatio -> SizeRatio -> Bool
$c/= :: SizeRatio -> SizeRatio -> Bool
/= :: SizeRatio -> SizeRatio -> Bool
Eq, Int -> SizeRatio -> ShowS
[SizeRatio] -> ShowS
SizeRatio -> String
(Int -> SizeRatio -> ShowS)
-> (SizeRatio -> String)
-> ([SizeRatio] -> ShowS)
-> Show SizeRatio
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> SizeRatio -> ShowS
showsPrec :: Int -> SizeRatio -> ShowS
$cshow :: SizeRatio -> String
show :: SizeRatio -> String
$cshowList :: [SizeRatio] -> ShowS
showList :: [SizeRatio] -> ShowS
Show)

instance NFData SizeRatio where
  rnf :: SizeRatio -> ()
rnf SizeRatio
Four = ()

sizeRatioInt :: SizeRatio -> Int
sizeRatioInt :: SizeRatio -> Int
sizeRatioInt = \case SizeRatio
Four -> Int
4

{-------------------------------------------------------------------------------
  Write buffer allocation
-------------------------------------------------------------------------------}

-- | Allocation method for the write buffer.
data WriteBufferAlloc =
    -- | Total number of key\/value pairs that can be present in the write
    -- buffer before flushing the write buffer to disk.
    --
    -- NOTE: if the sizes of values vary greatly, this can lead to wonky runs on
    -- disk, and therefore unpredictable performance.
    AllocNumEntries !NumEntries
  deriving stock (Int -> WriteBufferAlloc -> ShowS
[WriteBufferAlloc] -> ShowS
WriteBufferAlloc -> String
(Int -> WriteBufferAlloc -> ShowS)
-> (WriteBufferAlloc -> String)
-> ([WriteBufferAlloc] -> ShowS)
-> Show WriteBufferAlloc
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> WriteBufferAlloc -> ShowS
showsPrec :: Int -> WriteBufferAlloc -> ShowS
$cshow :: WriteBufferAlloc -> String
show :: WriteBufferAlloc -> String
$cshowList :: [WriteBufferAlloc] -> ShowS
showList :: [WriteBufferAlloc] -> ShowS
Show, WriteBufferAlloc -> WriteBufferAlloc -> Bool
(WriteBufferAlloc -> WriteBufferAlloc -> Bool)
-> (WriteBufferAlloc -> WriteBufferAlloc -> Bool)
-> Eq WriteBufferAlloc
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
== :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
$c/= :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
/= :: WriteBufferAlloc -> WriteBufferAlloc -> Bool
Eq)

instance NFData WriteBufferAlloc where
  rnf :: WriteBufferAlloc -> ()
rnf (AllocNumEntries NumEntries
n) = NumEntries -> ()
forall a. NFData a => a -> ()
rnf NumEntries
n

{-------------------------------------------------------------------------------
  Bloom filter allocation
-------------------------------------------------------------------------------}

-- | Allocation method for bloom filters.
--
-- NOTE: a __physical__ database entry is a key\/operation pair that exists in a
-- file, i.e., a run. Multiple physical entries that have the same key
-- constitute a __logical__ database entry.
data BloomFilterAlloc =
    -- | Allocate a fixed number of bits per physical entry in each bloom
    -- filter.
    AllocFixed
      !Word64 -- ^ Bits per physical entry.
  | -- | Allocate as many bits as required per physical entry to get the requested
    -- false-positive rate. Do this for each bloom filter.
    AllocRequestFPR
      !Double -- ^ Requested FPR.
  deriving stock (Int -> BloomFilterAlloc -> ShowS
[BloomFilterAlloc] -> ShowS
BloomFilterAlloc -> String
(Int -> BloomFilterAlloc -> ShowS)
-> (BloomFilterAlloc -> String)
-> ([BloomFilterAlloc] -> ShowS)
-> Show BloomFilterAlloc
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> BloomFilterAlloc -> ShowS
showsPrec :: Int -> BloomFilterAlloc -> ShowS
$cshow :: BloomFilterAlloc -> String
show :: BloomFilterAlloc -> String
$cshowList :: [BloomFilterAlloc] -> ShowS
showList :: [BloomFilterAlloc] -> ShowS
Show, BloomFilterAlloc -> BloomFilterAlloc -> Bool
(BloomFilterAlloc -> BloomFilterAlloc -> Bool)
-> (BloomFilterAlloc -> BloomFilterAlloc -> Bool)
-> Eq BloomFilterAlloc
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
== :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
$c/= :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
/= :: BloomFilterAlloc -> BloomFilterAlloc -> Bool
Eq)

instance NFData BloomFilterAlloc where
  rnf :: BloomFilterAlloc -> ()
rnf (AllocFixed Word64
n)        = Word64 -> ()
forall a. NFData a => a -> ()
rnf Word64
n
  rnf (AllocRequestFPR Double
fpr) = Double -> ()
forall a. NFData a => a -> ()
rnf Double
fpr

defaultBloomFilterAlloc :: BloomFilterAlloc
defaultBloomFilterAlloc :: BloomFilterAlloc
defaultBloomFilterAlloc = Word64 -> BloomFilterAlloc
AllocFixed Word64
10

bloomFilterAllocForLevel :: TableConfig -> RunLevelNo -> RunBloomFilterAlloc
bloomFilterAllocForLevel :: TableConfig -> RunLevelNo -> RunBloomFilterAlloc
bloomFilterAllocForLevel TableConfig
conf RunLevelNo
_levelNo =
    case TableConfig -> BloomFilterAlloc
confBloomFilterAlloc TableConfig
conf of
      AllocFixed Word64
n        -> Word64 -> RunBloomFilterAlloc
RunAllocFixed Word64
n
      AllocRequestFPR Double
fpr -> Double -> RunBloomFilterAlloc
RunAllocRequestFPR Double
fpr

{-------------------------------------------------------------------------------
  Fence pointer index
-------------------------------------------------------------------------------}

-- | Configure the type of fence pointer index.
data FencePointerIndexType =
    -- | Use a compact fence pointer index.
    --
    -- Compact indexes are designed to work with keys that are large (for
    -- example, 32 bytes long) cryptographic hashes.
    --
    -- When using a compact index, it is vital that the
    -- 'Database.LSMTree.Internal.Serialise.Class.serialiseKey' function
    -- satisfies the following law:
    --
    -- [Minimal size] @'Database.LSMTree.Internal.RawBytes.size'
    -- ('Database.LSMTree.Internal.Serialise.Class.serialiseKey' x) >= 8@
    --
    -- Use 'Database.LSMTree.Internal.Serialise.Class.serialiseKeyMinimalSize'
    -- to test this law.
    CompactIndex
    -- | Use an ordinary fence pointer index
    --
    -- Ordinary indexes do not have any constraints on keys other than that
    -- their serialised forms may not be 64 KiB or more in size.
  | OrdinaryIndex
  deriving stock (FencePointerIndexType -> FencePointerIndexType -> Bool
(FencePointerIndexType -> FencePointerIndexType -> Bool)
-> (FencePointerIndexType -> FencePointerIndexType -> Bool)
-> Eq FencePointerIndexType
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: FencePointerIndexType -> FencePointerIndexType -> Bool
== :: FencePointerIndexType -> FencePointerIndexType -> Bool
$c/= :: FencePointerIndexType -> FencePointerIndexType -> Bool
/= :: FencePointerIndexType -> FencePointerIndexType -> Bool
Eq, Int -> FencePointerIndexType -> ShowS
[FencePointerIndexType] -> ShowS
FencePointerIndexType -> String
(Int -> FencePointerIndexType -> ShowS)
-> (FencePointerIndexType -> String)
-> ([FencePointerIndexType] -> ShowS)
-> Show FencePointerIndexType
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> FencePointerIndexType -> ShowS
showsPrec :: Int -> FencePointerIndexType -> ShowS
$cshow :: FencePointerIndexType -> String
show :: FencePointerIndexType -> String
$cshowList :: [FencePointerIndexType] -> ShowS
showList :: [FencePointerIndexType] -> ShowS
Show)

instance NFData FencePointerIndexType where
  rnf :: FencePointerIndexType -> ()
rnf FencePointerIndexType
CompactIndex  = ()
  rnf FencePointerIndexType
OrdinaryIndex = ()

indexTypeForRun :: FencePointerIndexType -> IndexType
indexTypeForRun :: FencePointerIndexType -> IndexType
indexTypeForRun FencePointerIndexType
CompactIndex  = IndexType
Index.Compact
indexTypeForRun FencePointerIndexType
OrdinaryIndex = IndexType
Index.Ordinary

{-------------------------------------------------------------------------------
  Disk cache policy
-------------------------------------------------------------------------------}

-- | The policy for caching data from disk in memory (using the OS page cache).
--
-- Caching data in memory can improve performance if the access pattern has
-- good access locality or if the overall data size fits within memory. On the
-- other hand, caching is determental to performance and wastes memory if the
-- access pattern has poor spatial or temporal locality.
--
-- This implementation is designed to have good performance using a cacheless
-- policy, where main memory is used only to cache Bloom filters and indexes,
-- but none of the key\/value data itself. Nevertheless, some use cases will be
-- faster if some or all of the key\/value data is also cached in memory. This
-- implementation does not do any custom caching of key\/value data, relying
-- simply on the OS page cache. Thus caching is done in units of 4kb disk pages
-- (as opposed to individual key\/value pairs for example).
--
data DiskCachePolicy =

       -- | Use the OS page cache to cache any\/all key\/value data in the
       -- table.
       --
       -- Use this policy if the expected access pattern for the table
       -- has a good spatial or temporal locality.
       DiskCacheAll

       -- | Use the OS page cache to cache data in all LSMT levels at or below
       -- a given level number. For example, use 1 to cache the first level.
       -- (The write buffer is considered to be level 0.)
       --
       -- Use this policy if the expected access pattern for the table
       -- has good temporal locality for recently inserted keys.
     | DiskCacheLevelsAtOrBelow !Int

       --TODO: Add a policy based on size in bytes rather than internal details
       -- like levels. An easy use policy would be to say: "cache the first 10
       -- Mb" and have everything worked out from that.

       -- | Do not cache any key\/value data in any level (except the write
       -- buffer).
       --
       -- Use this policy if expected access pattern for the table has poor
       -- spatial or temporal locality, such as uniform random access.
     | DiskCacheNone
  deriving stock (Int -> DiskCachePolicy -> ShowS
[DiskCachePolicy] -> ShowS
DiskCachePolicy -> String
(Int -> DiskCachePolicy -> ShowS)
-> (DiskCachePolicy -> String)
-> ([DiskCachePolicy] -> ShowS)
-> Show DiskCachePolicy
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> DiskCachePolicy -> ShowS
showsPrec :: Int -> DiskCachePolicy -> ShowS
$cshow :: DiskCachePolicy -> String
show :: DiskCachePolicy -> String
$cshowList :: [DiskCachePolicy] -> ShowS
showList :: [DiskCachePolicy] -> ShowS
Show, DiskCachePolicy -> DiskCachePolicy -> Bool
(DiskCachePolicy -> DiskCachePolicy -> Bool)
-> (DiskCachePolicy -> DiskCachePolicy -> Bool)
-> Eq DiskCachePolicy
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: DiskCachePolicy -> DiskCachePolicy -> Bool
== :: DiskCachePolicy -> DiskCachePolicy -> Bool
$c/= :: DiskCachePolicy -> DiskCachePolicy -> Bool
/= :: DiskCachePolicy -> DiskCachePolicy -> Bool
Eq)

instance NFData DiskCachePolicy where
  rnf :: DiskCachePolicy -> ()
rnf DiskCachePolicy
DiskCacheAll                 = ()
  rnf (DiskCacheLevelsAtOrBelow Int
l) = Int -> ()
forall a. NFData a => a -> ()
rnf Int
l
  rnf DiskCachePolicy
DiskCacheNone                = ()

-- | Interpret the 'DiskCachePolicy' for a level: should we cache data in runs
-- at this level.
--
diskCachePolicyForLevel :: DiskCachePolicy -> RunLevelNo -> RunDataCaching
diskCachePolicyForLevel :: DiskCachePolicy -> RunLevelNo -> RunDataCaching
diskCachePolicyForLevel DiskCachePolicy
policy RunLevelNo
levelNo =
  case DiskCachePolicy
policy of
    DiskCachePolicy
DiskCacheAll  -> RunDataCaching
CacheRunData
    DiskCachePolicy
DiskCacheNone -> RunDataCaching
NoCacheRunData
    DiskCacheLevelsAtOrBelow Int
n ->
      case RunLevelNo
levelNo of
        RegularLevel LevelNo
l | LevelNo
l LevelNo -> LevelNo -> Bool
forall a. Ord a => a -> a -> Bool
<= Int -> LevelNo
LevelNo Int
n -> RunDataCaching
CacheRunData
                       | Bool
otherwise      -> RunDataCaching
NoCacheRunData
        RunLevelNo
UnionLevel                      -> RunDataCaching
NoCacheRunData

{-------------------------------------------------------------------------------
  Merge schedule
-------------------------------------------------------------------------------}

-- | A configuration option that determines how merges are stepped to
-- completion. This does not affect the amount of work that is done by merges,
-- only how the work is spread out over time.
data MergeSchedule =
    -- | Complete merges immediately when started.
    --
    -- The 'OneShot' option will make the merging algorithm perform /big/ batches
    -- of work in one go, so intermittent slow-downs can be expected. For use
    -- cases where unresponsiveness is unacceptable, e.g. in real-time systems,
    -- use 'Incremental' instead.
    OneShot
    -- | Schedule merges for incremental construction, and step the merge when
    -- updates are performed on a table.
    --
    -- The 'Incremental' option spreads out merging work over time. More
    -- specifically, updates to a table can cause a /small/ batch of merge work
    -- to be performed. The scheduling of these batches is designed such that
    -- merges are fully completed in time for when new merges are started on the
    -- same level.
  | Incremental
  deriving stock (MergeSchedule -> MergeSchedule -> Bool
(MergeSchedule -> MergeSchedule -> Bool)
-> (MergeSchedule -> MergeSchedule -> Bool) -> Eq MergeSchedule
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: MergeSchedule -> MergeSchedule -> Bool
== :: MergeSchedule -> MergeSchedule -> Bool
$c/= :: MergeSchedule -> MergeSchedule -> Bool
/= :: MergeSchedule -> MergeSchedule -> Bool
Eq, Int -> MergeSchedule -> ShowS
[MergeSchedule] -> ShowS
MergeSchedule -> String
(Int -> MergeSchedule -> ShowS)
-> (MergeSchedule -> String)
-> ([MergeSchedule] -> ShowS)
-> Show MergeSchedule
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> MergeSchedule -> ShowS
showsPrec :: Int -> MergeSchedule -> ShowS
$cshow :: MergeSchedule -> String
show :: MergeSchedule -> String
$cshowList :: [MergeSchedule] -> ShowS
showList :: [MergeSchedule] -> ShowS
Show)

instance NFData MergeSchedule where
  rnf :: MergeSchedule -> ()
rnf MergeSchedule
OneShot     = ()
  rnf MergeSchedule
Incremental = ()

-- | The default 'MergeSchedule'.
--
-- >>> defaultMergeSchedule
-- Incremental
defaultMergeSchedule :: MergeSchedule
defaultMergeSchedule :: MergeSchedule
defaultMergeSchedule = MergeSchedule
Incremental