rocksdb-query-0.7.0: src/Database/RocksDB/Query.hs
{-# LANGUAGE ImportQualifiedPost #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE MultiParamTypeClasses #-}
-- |
-- Module : Database.RocksDB.Query
-- Copyright : Haskoin Developers
-- License : MIT
-- Maintainer : jprupp@protonmail.ch
-- Stability : experimental
-- Portability : POSIX
--
-- Query functions to make interaction with RocksDB stores easier and safer.
--
-- = Purpose
--
-- RocksDB stores bytes. A program stores records: users, orders,
-- transactions. Between the two sits a lot of repetitive and error-prone code
-- that encodes keys, decodes values, and remembers which kind of value lives
-- under which kind of key. Getting that last part wrong is a silent bug: the
-- bytes decode into nonsense, or into the wrong record, long after they were
-- written.
--
-- This module removes that code and makes the mapping from key types to value
-- types something the compiler checks. It is deliberately small, and leaves
-- opening, tuning and closing the database to "Database.RocksDB".
--
-- = Design
--
-- * __Types describe the schema.__ A key type and the instance
-- @'KeyValue' Key Value@ together say what is stored where. Reading a key as
-- a type you did not declare for it does not compile.
--
-- * __Serialization is cereal.__ Its encodings of fixed-width unsigned
-- integers are big-endian, so numeric key parts sort numerically, which makes
-- range scans work. You keep full control over the bytes by writing the
-- 'Serialize' instance yourself when the order matters.
--
-- * __Prefix queries are the main way to read sets.__ RocksDB has no
-- secondary indices or queries, but it keeps keys sorted. A schema whose keys
-- start with what you look records up by turns "all orders of a customer"
-- into one seek and a short scan.
--
-- * __Corrupt data is a bug, not an outcome.__ Decoding failures call 'error'
-- rather than returning 'Maybe' or 'Either'. If data written by your own
-- program cannot be read back, the program is wrong, and carrying on would
-- only spread the damage.
--
-- Keys and values are Haskell types with 'Serialize' instances from the
-- @cereal@ package. They are encoded with 'encode' before being written and
-- decoded with 'decode' after being read. The empty classes 'Key' and
-- 'KeyValue' tie key types to value types, so that the type checker prevents
-- reading a value of the wrong type for a key:
--
-- @
-- data UserKey = UserKey Word32 deriving (Generic)
-- instance 'Serialize' UserKey
-- instance 'Key' UserKey
-- instance 'KeyValue' UserKey User
--
-- getUser :: DB -> Word32 -> IO (Maybe User)
-- getUser db = 'retrieve' db . UserKey
-- @
--
-- = Prefix queries
--
-- Because RocksDB keeps keys sorted by their bytes, all keys that start with
-- the same bytes are stored next to each other. The 'matching' family of
-- functions takes a short key whose encoding is a prefix of the encoding of
-- full keys, and returns every entry whose key starts with that prefix. See
-- 'matching' for an example.
--
-- = How a prefix is read
--
-- A prefix query reads the database in chunks: up to 256 entries, or a
-- megabyte of them, from one call into RocksDB. Moving an iterator is a
-- foreign call that may wait for the disk, and Haskell pays for each such
-- call, so one call per entry made long lists slow, and slower still when
-- many threads read at once. The list functions read whole chunks from the
-- start. The conduits start with 16 entries and grow, so that a consumer who
-- stops early has not made the database read much more than it took. The
-- functions that return the first match read one entry and no more.
--
-- = Decoding errors
--
-- If a stored key or value cannot be decoded, these functions call 'error'.
-- That indicates a bug, such as a mismatch between the 'Serialize' instance
-- used to write and to read, or two key types sharing a prefix.
--
-- = Column families
--
-- Functions ending in @CF@ act on a given column family. The others act on the
-- default column family.
module Database.RocksDB.Query
( -- * Schema
Key,
KeyValue,
-- * Reading and writing
retrieve,
retrieveCF,
insert,
insertCF,
remove,
removeCF,
-- * Batches
insertOp,
insertOpCF,
deleteOp,
deleteOpCF,
writeBatch,
-- * Prefix queries
matchingAsList,
matchingAsListCF,
matchingSkipAsList,
matchingSkipAsListCF,
firstMatching,
firstMatchingCF,
firstMatchingSkip,
firstMatchingSkipCF,
matching,
matchingSkip,
-- * Internal
retrieveCommon,
matchRecursiveList,
matchRecursive,
)
where
import Conduit
import Control.Monad
import Data.ByteString qualified as B
import Data.ByteString.Char8 qualified as C
import Data.Default (def)
import Data.Serialize as S
import Database.RocksDB as R
-- | Class for types that are database keys. It has no methods; an instance
-- marks a type as allowed to be used as a key in 'remove', 'deleteOp' and
-- related functions.
--
-- Deletion needs to know only that a type is a key, not what it maps to, which
-- is why it is a separate class.
class Key key
-- | Class for types that are corresponding database key and value. It has no
-- methods; an instance states that values of type @value@ are stored under keys
-- of type @key@. Functions that read or write values require it.
--
-- The class has no methods because its job is purely to be checked by the
-- compiler: it records a decision about your schema in a place where every read
-- and write must agree with it.
class KeyValue key value
-- | Read a value from the default column family, or 'Nothing' if not found.
-- Calls 'error' if the stored value cannot be decoded.
retrieve ::
(KeyValue key value, Serialize key, Serialize value) =>
DB ->
key ->
IO (Maybe value)
retrieve db = retrieveCommon db Nothing
-- | Like 'retrieve', but read from the given column family.
retrieveCF ::
(KeyValue key value, Serialize key, Serialize value) =>
DB ->
ColumnFamily ->
key ->
IO (Maybe value)
retrieveCF db cf = retrieveCommon db (Just cf)
-- | Read a value from the default column family, or from a column family if
-- one is given. Returns 'Nothing' if not found.
retrieveCommon ::
(KeyValue key value, Serialize key, Serialize value) =>
DB ->
Maybe ColumnFamily ->
key ->
IO (Maybe value)
retrieveCommon db mcf key =
f >>= \case
Nothing -> return Nothing
Just bytes ->
case decode bytes of
Left e -> error e
Right x -> return (Just x)
where
f = case mcf of
Just cf -> R.getCF db cf (encode key)
Nothing -> R.get db (encode key)
-- | The most entries that a prefix query reads from the database in one
-- call.
--
-- An iterator moves in a foreign call that may wait for the disk, and such a
-- call has a cost of its own in Haskell: the thread gives up its capability
-- and has to get one back. Reading one entry per call, a long list paid that
-- once for every entry. At 256 entries per call the cost is spread so thin
-- that a larger number gains nothing that the benchmark of
-- @rocksdb-haskell-jprupp@ can measure, while it would make a consumer that
-- stops early read more entries that it does not want.
chunkMost :: Int
chunkMost = 256
-- | The entries that a conduit reads in its first call. Each call after it
-- reads four times as many, up to 'chunkMost'.
--
-- A conduit does not know how much its consumer will take. Starting small
-- means that one who takes a few entries makes the database read 16 and not
-- 256; growing fast means that one who takes thousands is at full size
-- from the third call on.
chunkFirst :: Int
chunkFirst = 16
-- | The most bytes of keys and values that a prefix query reads in one call,
-- 1 MiB. One entry is always read, whatever its size.
--
-- It bounds the memory that a query holds beyond its result. A chunk is in
-- memory twice for a moment, as the bytes read and as the values decoded
-- from them, and 256 values can be of any size: without this limit, 256
-- values of a megabyte would be read at once to yield the first.
chunkBytesMost :: Int
chunkBytesMost = 1024 * 1024
-- | The chunk of so many entries, at most, whose keys start with the given
-- bytes.
chunkOf :: B.ByteString -> Int -> ChunkConfig
chunkOf prefix n =
def
{ chunkPrefix = prefix,
chunkEntries = n,
chunkBytes = chunkBytesMost
}
-- | Decode an entry read from the database. Calls 'error' if the key or the
-- value cannot be decoded, when the action runs and not when its result is
-- looked at.
decodeEntry ::
(Serialize key, Serialize value) =>
(B.ByteString, B.ByteString) ->
IO (key, value)
decodeEntry (key_bytes, value_bytes) = do
key <- either error return (decode key_bytes)
value <- either error return (decode value_bytes)
return (key, value)
-- | Internal function to collect, from the current position of the iterator,
-- every entry whose key starts with the encoding of the given key. Stops at the
-- first entry that does not match.
--
-- It reads 256 entries at a time, and keeps what it has read in an argument
-- of its loop, so that the stack does not grow with the list.
-- That matters for more than memory: the run-time system walks the stack of
-- a thread at every foreign call that may block, so a loop that left a frame
-- there for each entry got slower with every entry it read.
matchRecursiveList ::
(KeyValue key value, Serialize key, Serialize value) =>
key ->
Iterator ->
IO [(key, value)]
matchRecursiveList base it = go []
where
go acc = do
(entries, more) <- iterChunk it chunk
acc' <- foldM (\done entry -> (: done) <$> decodeEntry entry) acc entries
if more then go acc' else return (reverse acc')
chunk = chunkOf (encode base) chunkMost
-- | Internal function for recursively matching a key. Like
-- 'matchRecursiveList', but streams the entries through a conduit.
--
-- It reads a chunk, yields its entries one by one, and reads the next chunk
-- only when the consumer asks for more: nothing is read for a consumer that
-- has stopped. The chunks start at 16 entries and grow to 256. An entry is
-- decoded when it is its turn to be yielded, so an entry that cannot be
-- decoded is an error only for a consumer that gets as far as it.
matchRecursive ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
key ->
Iterator ->
ConduitT i (key, value) IO ()
matchRecursive base it = go chunkFirst
where
go n = do
(entries, more) <- liftIO (iterChunk it (chunkOf base_bytes n))
forM_ entries (liftIO . decodeEntry >=> yield)
when more $ go (min chunkMost (n * 4))
base_bytes = encode base
-- | Internal function to read the entry that the iterator is on, if its key
-- starts with the encoding of the given key.
--
-- It reads the one entry in place, with no call that moves the iterator: a
-- chunk would read on past the entry that is wanted.
matchFirst ::
(KeyValue key value, Serialize key, Serialize value) =>
key ->
Iterator ->
IO (Maybe (key, value))
matchFirst base it =
iterEntry it >>= \case
Just entry
| encode base `B.isPrefixOf` fst entry -> Just <$> decodeEntry entry
| otherwise -> return Nothing
Nothing -> do
-- no entry here: the end of the data, unless the iterator says that
-- it could not read
iterGetError it >>= mapM_ (ioError . userError . ("firstMatching: " <>) . C.unpack)
return Nothing
-- | Pass a short key to filter all the elements whose key prefix match it. Use
-- a sum type for keys that allows to create a version of the key that
-- serializes to a prefix of a full key.
--
-- > data MyKey = ShortKey String | FullKey String String deriving Show
-- > instance Serialize MyKey where
-- > put (ShortKey a) = put a
-- > put (FullKey a b) = put a >> put b
-- > get = FullKey <$> get <*> get
-- > instance KeyValue MyKey String
-- > main =
-- > withDB "test-db" def {createIfMissing = True} $ \db -> do
-- > insert db (FullKey "hello" "world") "despite all my rage"
-- > Just record <- withIter db $ \it ->
-- > runConduit $ matching it (ShortKey "hello") .| headC
-- > print (record :: (MyKey, String))
-- > -- (FullKey "hello" "world","despite all my rage")
--
-- In this example the @ShortKey@ is serialized to the prefix of the only
-- element in the database, which is then returned. Since the 'S.get' function of
-- the 'Serialize' instance for @MyKey@ only understands how to deserialize a
-- @FullKey@, then that is what is returned.
--
-- The iterator is moved to the first key at or after the prefix, and the
-- conduit yields entries until it finds a key that does not start with the
-- prefix. The iterator must stay open while the conduit runs. See
-- 'matchingAsList' and 'firstMatching' for versions that manage the iterator
-- themselves.
--
-- The conduit version exists for sets too large to hold in memory, and for
-- consumers that stop early. It reads the database in chunks, a little ahead
-- of its consumer: 16 entries at first, then four times as many with each
-- chunk, up to 256 entries or a megabyte. So a consumer that takes three
-- entries makes the database read 16, and one that takes thousands costs a
-- call into RocksDB for every 256 and not for each. Do not rely on where the
-- iterator is when the consumer stops: it is past the entries read ahead.
--
-- Throws an 'IOError' if RocksDB fails to read, where a short result would
-- otherwise look like the end of the data.
matching ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
Iterator ->
key ->
ConduitT i (key, value) IO ()
matching it base = do
liftIO (iterSeek it (encode base))
matchRecursive base it
-- | Like 'matching', but skip to the second key passed as argument, or after if
-- there is no entry for the second key.
--
-- This is useful for pagination: pass the last key seen in the previous page
-- (or the key just after it) as the second argument. The second key should
-- start with the same prefix as the first; if it sorts before the prefix, no
-- entries are returned.
--
-- Starting from a key instead of an offset is what makes deep pagination cheap:
-- the database seeks straight to the page instead of reading and discarding
-- every entry before it.
matchingSkip ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
Iterator ->
key ->
key ->
ConduitT i (key, value) IO ()
matchingSkip it base start = do
liftIO (iterSeek it (encode start))
matchRecursive base it
-- | Insert a record into the default column family, replacing any previous
-- value for the key.
insert ::
(KeyValue key value, Serialize key, Serialize value) =>
DB ->
key ->
value ->
IO ()
insert db key value = R.put db (encode key) (encode value)
-- | Like 'insert', but write to the given column family.
insertCF ::
(KeyValue key value, Serialize key, Serialize value) =>
DB ->
ColumnFamily ->
key ->
value ->
IO ()
insertCF db cf key value = R.putCF db cf (encode key) (encode value)
-- | Delete a record from the default column family. Deleting a key that does
-- not exist is not an error.
remove :: (Key key, Serialize key) => DB -> key -> IO ()
remove db key = delete db (encode key)
-- | Like 'remove', but delete from the given column family.
removeCF ::
(Key key, Serialize key) =>
DB -> ColumnFamily -> key -> IO ()
removeCF db cf key = deleteCF db cf (encode key)
-- | Get the 'BatchOp' to insert a record in the default column family. Use with
-- 'writeBatch' to apply several changes atomically.
insertOp ::
(KeyValue key value, Serialize key, Serialize value) =>
key ->
value ->
BatchOp
insertOp key value = R.Put (encode key) (encode value)
-- | Like 'insertOp', but for the given column family.
insertOpCF ::
(KeyValue key value, Serialize key, Serialize value) =>
ColumnFamily ->
key ->
value ->
BatchOp
insertOpCF cf key value = R.PutCF cf (encode key) (encode value)
-- | Get the 'BatchOp' to delete a record from the default column family. Use
-- with 'writeBatch' to apply several changes atomically.
deleteOp :: (Key key, Serialize key) => key -> BatchOp
deleteOp key = Del (encode key)
-- | Like 'deleteOp', but for the given column family.
deleteOpCF :: (Key key, Serialize key) => ColumnFamily -> key -> BatchOp
deleteOpCF cf key = DelCF cf (encode key)
-- | Write a batch to the database atomically. Synonym for 'write'.
--
-- @
-- 'writeBatch' db ['insertOp' k1 v1, 'deleteOp' k2]
-- @
writeBatch :: DB -> [BatchOp] -> IO ()
writeBatch = write
-- | Like 'matching' but return the first element only, or 'Nothing' if no key
-- starts with the prefix. Opens and closes its own iterator.
--
-- It reads that one entry and no further: a seek, and the entry under the
-- iterator. Use it, and not the head of a list or of a conduit, when one
-- entry is all that is wanted.
firstMatching ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
key ->
IO (Maybe (key, value))
firstMatching db base =
withIter db $ \it -> do
iterSeek it (encode base)
matchFirst base it
-- | Like 'firstMatching', but read from the given column family.
firstMatchingCF ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
ColumnFamily ->
key ->
IO (Maybe (key, value))
firstMatchingCF db cf base =
withIterCF db cf $ \it -> do
iterSeek it (encode base)
matchFirst base it
-- | Like 'matchingSkip', but return the first element only. Opens and closes
-- its own iterator.
firstMatchingSkip ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
key ->
key ->
IO (Maybe (key, value))
firstMatchingSkip db base start =
withIter db $ \it -> do
iterSeek it (encode start)
matchFirst base it
-- | Like 'firstMatchingSkip', but read from the given column family.
firstMatchingSkipCF ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
ColumnFamily ->
key ->
key ->
IO (Maybe (key, value))
firstMatchingSkipCF db cf base start =
withIterCF db cf $ \it -> do
iterSeek it (encode start)
matchFirst base it
-- | Like 'matching' but return a list. Opens and closes its own iterator. All
-- matching entries are loaded into memory, so use 'matching' for prefixes that
-- may match many entries.
--
-- The list is complete when the function returns: nothing of it is read
-- lazily, so the iterator can be closed. It is read in chunks of 256 entries
-- or a megabyte, and the time it takes grows in step with its length.
matchingAsList ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
key ->
IO [(key, value)]
matchingAsList db base =
withIter db $ \it -> do
iterSeek it (encode base)
matchRecursiveList base it
-- | Like 'matchingAsList', but read from the given column family.
matchingAsListCF ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
ColumnFamily ->
key ->
IO [(key, value)]
matchingAsListCF db cf base =
withIterCF db cf $ \it -> do
iterSeek it (encode base)
matchRecursiveList base it
-- | Like 'matchingSkip', but return a list. Opens and closes its own iterator.
matchingSkipAsList ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
key ->
key ->
IO [(key, value)]
matchingSkipAsList db base start =
withIter db $ \it -> do
iterSeek it (encode start)
matchRecursiveList base it
-- | Like 'matchingSkipAsList', but read from the given column family.
matchingSkipAsListCF ::
( KeyValue key value,
Serialize key,
Serialize value
) =>
DB ->
ColumnFamily ->
key ->
key ->
IO [(key, value)]
matchingSkipAsListCF db cf base start =
withIterCF db cf $ \it -> do
iterSeek it (encode start)
matchRecursiveList base it