rocksdb-haskell-jprupp 2.6.4 → 2.7.0

raw patch · 8 files changed

+451/−5 lines, 8 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +19/−0
• README.md +76/−1
• rocksdb-haskell-jprupp.cabal +1/−1
• src/Database/RocksDB/Base.hs +4/−1
• src/Database/RocksDB/C.hs +25/−0
• src/Database/RocksDB/Internal.hs +5/−0
• src/Database/RocksDB/Iterator.hs +175/−2
• test/Spec.hs +146/−0

@@ -1,3 +1,22 @@+## 2.7.0++ * Bounded iterators. `withIterConfig` creates an iterator that RocksDB itself+   stops, as an `IterConfig` says: at a `lowerBound` or an `upperBound`, or at+   the end of the prefix that it was sent to, with `prefixSameAsStart`. Until+   now a scan of a range could only stop by reading the first key past it,+   and when the keys past it had been deleted, RocksDB stepped over the marker+   of every one to find that key. A scan of an empty range followed by 20,000+   deleted keys took 2,600 microseconds; with an upper bound it takes 2.5.+   `prefixUpperBound` gives the bound that ends a prefix, and+   `createIteratorConfig` manages such an iterator by hand.+ * `totalOrderSeek`, also in `IterConfig`, walks every key in order in a+   database that has a `prefixLength`, where a plain iterator only promises+   the keys of one prefix.+ * The `DB` record has a new field, `snapshot`, with the snapshot that its+   read options read from. Code that builds a `DB` by hand has to set it;+   code that gets one from `withDB`, `withDBCF` or `withSnapshot` needs no+   change. This is why the version is 2.7.0 and not 2.6.5.+ ## 2.6.4   * Iterators read rows about three times faster. `iterValid`, `iterKey` and

@@ -92,6 +92,7 @@ | Column families| Open a database with several independent key spaces; add new ones on open     | | Snapshots      | Consistent point-in-time reads across many queries and iterators               | | Iterators      | Ordered scans, forwards and backwards, optionally pinned to a snapshot         |+| Bounds         | Iterators that stop at a key or at the end of a prefix, without reading past it | | Tuning         | Bloom filters, fixed-length prefix extractor, shared LRU block cache           | | Limits         | Memtable and WAL size limits, open file limit                                  | | Administration | Properties (memory use, statistics, SST files), approximate sizes, destroy, repair |@@ -184,7 +185,7 @@  ```yaml extra-deps:-  - rocksdb-haskell-jprupp-2.6.4+  - rocksdb-haskell-jprupp-2.7.0 ```  With `stack --nix`, add RocksDB to the Nix packages:@@ -398,6 +399,69 @@ `createIterator`, `createIteratorSnap` and `destroyIterator` manage iterators by hand. +### Bounded iterators++The scan above stops when it reads a key that does not start with `user:`.+RocksDB has to find that key first, and that can cost far more than the scan+itself. A deleted key is not gone: it leaves a marker that stays until+compaction drops it, and an iterator steps over every marker on its way to+the next key that is alive. If the keys after `user:` were a queue that has+been emptied, the scan reads the marker of every job that ever was in it.++`withIterConfig` creates an iterator that RocksDB stops at a bound, without+looking past it:++```haskell+-- every key that starts with "user:", and not one step further+withIterConfig db Nothing def {upperBound = prefixUpperBound "user:"} $ \it -> do+  iterSeek it "user:"+  let go acc =+        iterEntry it >>= \case+          Just kv -> iterNext it >> go (kv : acc)+          Nothing -> return (reverse acc)+  go []+```++The second argument is the column family, or `Nothing` for the default one.+The `IterConfig` has four fields, all off in `def`:++| Field               | Type               | What it does                                                    |+| ------------------- | ------------------ | --------------------------------------------------------------- |+| `upperBound`        | `Maybe ByteString` | The iterator stays below this key; the key itself is outside     |+| `lowerBound`        | `Maybe ByteString` | The iterator does not go below this key; the key itself is inside |+| `prefixSameAsStart` | `Bool`             | The iterator stays within the prefix of the key it was sent to   |+| `totalOrderSeek`    | `Bool`             | See every key in order, in a database that has a `prefixLength`  |++Which one to use:++- **`upperBound`**, with `prefixUpperBound`, when each range gets its own+  iterator. It needs nothing from the configuration of the database, and the+  range can be any.+- **`prefixSameAsStart`** when one iterator is sent to many ranges, seek+  after seek, which saves creating an iterator for each: the bound moves with+  every `iterSeek`. It needs a `prefixLength` in the `Config`, and each range+  has to be a whole prefix of that length. It also lets RocksDB use its+  prefix filters to skip the files that have nothing for the prefix.+- **`totalOrderSeek`** to walk a database that has a `prefixLength` from end+  to end. Without it, an iterator there only promises the keys that share+  the prefix of the key it was sent to.+- **`withIter`** when what follows the range is alive, or when there is no+  range. A bound costs a little when the iterator is created, and gains+  nothing there.++How much it matters, in this package's own test: one live key, then 20,000+keys that were written and deleted, then another live key. A scan from just+after the first one, which finds nothing, in microseconds:++| Iterator                         | Time  |+| -------------------------------- | ----- |+| `withIter`                       | 2,600 |+| `withIterConfig` with an `upperBound` | 2.5 |++`createIteratorConfig` manages such an iterator by hand. It returns the+iterator together with the action that destroys it, which also frees the+bounds: RocksDB keeps pointers to them for as long as the iterator lives.+ ### Properties and maintenance  ```haskell@@ -472,6 +536,7 @@ | Reading and writing      | `get`, `getCF`, `multiGet`, `multiGetCF`, `put`, `putCF`, `delete`, `deleteCF`, `write` | | Snapshots                | `withSnapshot`, `createSnapshot`, `releaseSnapshot`            | | Creating iterators       | `withIter`, `withIterCF`, `withIterSnap`, `withIterSnapCF`     |+| Bounded iterators        | `IterConfig`, `withIterConfig`, `createIteratorConfig`, `prefixUpperBound` | | Moving iterators         | `iterSeek`, `iterFirst`, `iterLast`, `iterNext`, `iterPrev`    | | Reading from iterators   | `iterKey`, `iterValue`, `iterEntry`, `iterValid`, `iterGetError` | | Administration           | `getProperty`, `getPropertyCF`, `approximateSize`, `destroy`, `repair` |@@ -489,6 +554,16 @@   `iterFirst` or `iterLast`. - An iterator that becomes invalid because of corruption looks like one that   reached the end. Check `iterGetError`.+- A scan that stops by looking at the key it has reached steps over every+  deleted key that follows its range. Where keys come and go, give the+  iterator a bound with `withIterConfig`.+- In a database with a `prefixLength`, an iterator that moves past the+  prefix it was sent to, or that starts with `iterFirst` or `iterLast`, may+  skip keys. Ask for `totalOrderSeek`, or stay within the prefix with+  `prefixSameAsStart`.+- Destroy an iterator from `createIteratorConfig` with the action that came+  with it, not with `destroyIterator`, which would leave its bounds and read+  options allocated. - Calls into RocksDB are `safe` foreign calls, so they do not block other   Haskell threads, but each one costs a little more than an `unsafe` call. - Releases before 2.6.2 built no Bloom filters on RocksDB 6.24 or later,

@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack  name:           rocksdb-haskell-jprupp-version:        2.6.4+version:        2.7.0 synopsis:       Haskell bindings for RocksDB description:    See README at <https://github.com/jprupp/rocksdb-haskell#readme> category:       Database, FFI

@@ -145,6 +145,7 @@             return DB { rocksDB = db_ptr                       , columnFamilies = []                       , readOpts = read_opts+                      , snapshot = Nothing                       , writeOpts = write_opts                       } @@ -204,6 +205,7 @@             return DB { rocksDB = db_ptr                       , columnFamilies = cfs                       , readOpts = read_opts+                      , snapshot = Nothing                       , writeOpts = write_opts                       }     destroy_db db = do@@ -243,6 +245,7 @@                     return DB { rocksDB = db_ptr                               , columnFamilies = cfs                               , readOpts = read_opts+                              , snapshot = Nothing                               , writeOpts = write_opts                               } @@ -269,7 +272,7 @@ createSnapshot db@DB{rocksDB = db_ptr} = do     snap_ptr <- c_rocksdb_create_snapshot db_ptr     read_opts <- createReadOpts (Just snap_ptr)-    return (db{readOpts = read_opts}, snap_ptr)+    return (db{readOpts = read_opts, snapshot = Just snap_ptr}, snap_ptr)  -- | Function to release an unmanaged snapshot. -- Also releases the read options associated with the snapshot DB.

@@ -124,6 +124,10 @@     , c_rocksdb_readoptions_create     , c_rocksdb_readoptions_destroy     , c_rocksdb_readoptions_set_snapshot+    , c_rocksdb_readoptions_set_iterate_upper_bound+    , c_rocksdb_readoptions_set_iterate_lower_bound+    , c_rocksdb_readoptions_set_prefix_same_as_start+    , c_rocksdb_readoptions_set_total_order_seek     , c_rocksdb_writeoptions_create     , c_rocksdb_writeoptions_destroy     , c_rocksdb_free@@ -642,6 +646,27 @@ -- | Binding to @rocksdb_readoptions_set_snapshot@. foreign import ccall safe "rocksdb/c.h rocksdb_readoptions_set_snapshot"   c_rocksdb_readoptions_set_snapshot :: ReadOpts -> Snapshot -> IO ()++-- | Binding to @rocksdb_readoptions_set_iterate_upper_bound@.+--+-- RocksDB does not copy the key: the read options, and every iterator made+-- from them, keep the pointer. The memory has to stay as it is until the last+-- of those iterators is destroyed.+foreign import ccall safe "rocksdb/c.h rocksdb_readoptions_set_iterate_upper_bound"+  c_rocksdb_readoptions_set_iterate_upper_bound :: ReadOpts -> Key -> CSize -> IO ()++-- | Binding to @rocksdb_readoptions_set_iterate_lower_bound@. The key is not+-- copied; see 'c_rocksdb_readoptions_set_iterate_upper_bound'.+foreign import ccall safe "rocksdb/c.h rocksdb_readoptions_set_iterate_lower_bound"+  c_rocksdb_readoptions_set_iterate_lower_bound :: ReadOpts -> Key -> CSize -> IO ()++-- | Binding to @rocksdb_readoptions_set_prefix_same_as_start@.+foreign import ccall safe "rocksdb/c.h rocksdb_readoptions_set_prefix_same_as_start"+  c_rocksdb_readoptions_set_prefix_same_as_start :: ReadOpts -> CUChar -> IO ()++-- | Binding to @rocksdb_readoptions_set_total_order_seek@.+foreign import ccall safe "rocksdb/c.h rocksdb_readoptions_set_total_order_seek"+  c_rocksdb_readoptions_set_total_order_seek :: ReadOpts -> CUChar -> IO ()   --

@@ -58,6 +58,11 @@              , readOpts       :: !ReadOpts                -- ^ read options used by reads and iterators; set to read from                -- a snapshot by 'Database.RocksDB.withSnapshot'+             , snapshot       :: !(Maybe Snapshot)+               -- ^ the snapshot that 'readOpts' read from, if any. RocksDB+               -- cannot be asked what snapshot its read options hold, and+               -- 'Database.RocksDB.withIterConfig' has to make read options+               -- of its own that read from the same one.              , writeOpts      :: !WriteOpts                -- ^ write options used by all writes              }

@@ -40,6 +40,38 @@ -- Designing keys so that the records you read together sort together is the -- most important performance decision in a RocksDB schema. --+-- = Bounds+--+-- An 'Iterator' from 'withIter' has no end but that of the data. The scan+-- above stops when it /reads/ a key that does not start with @user:@, so+-- RocksDB has to produce that key first. Usually it is the next one and costs+-- nothing. It is not when the keys after the range have been deleted: a+-- deleted key stays in the database, as a marker, until compaction drops it,+-- and an iterator steps over every marker on its way to the next key that is+-- alive. A scan of an empty range that is followed by ten thousand deleted+-- keys reads ten thousand markers to return nothing.+--+-- 'withIterConfig' creates an iterator that RocksDB itself stops:+--+-- * at an 'upperBound' or a 'lowerBound', which are keys;+-- * at the end of the prefix that it was sent to, with 'prefixSameAsStart',+--   in a database or column family that has a 'prefixLength'.+--+-- Such an iterator becomes invalid at its bound without looking past it. A+-- bound also lets RocksDB leave out the table files that hold nothing inside+-- it.+--+-- @+-- -- the same scan, which ends where the keys of "user:" end+-- usersFrom db =+--     'withIterConfig' db Nothing def{'upperBound' = 'prefixUpperBound' "user:"} $ \\it -> do+--         'iterSeek' it "user:"+--         let go acc = 'iterEntry' it >>= \\case+--                 Just kv -> 'iterNext' it >> go (kv : acc)+--                 Nothing -> return (reverse acc)+--         go []+-- @+-- -- = Safety -- -- The C API crashes the process if an invalid iterator is moved, and the bytes@@ -53,9 +85,14 @@     withIterCF,     withIterSnap,     withIterSnapCF,+    -- * Bounded iteration+    IterConfig (..),+    withIterConfig,+    prefixUpperBound,     -- * Manual iterator management     createIterator,     createIteratorSnap,+    createIteratorConfig,     destroyIterator,     destroyReadOpts,     -- * Iterator operations@@ -72,11 +109,12 @@   ) where -import Control.Exception (bracket)-import Control.Monad (when)+import Control.Exception (bracket, mask_, onException)+import Control.Monad (forM, forM_, when) import Data.ByteString (ByteString) import Data.ByteString qualified as B import Data.ByteString.Unsafe qualified as BU+import Data.Default (Default (..)) import Database.RocksDB.C import Database.RocksDB.Internal import Foreign@@ -154,6 +192,141 @@         throwErrnoIfNull "create_iterator" $ case mcf of             Just cf -> c_rocksdb_create_iterator_cf rocks_db ro cf             Nothing -> c_rocksdb_create_iterator rocks_db ro++-- | Where an iterator stops, and what a seek promises. 'def' asks for+-- nothing, which gives the iterator that 'withIter' creates; override the+-- fields you need:+--+-- @+-- def { 'upperBound' = 'prefixUpperBound' "user:" }+-- @+--+-- The fields are the read options of RocksDB that concern iterators and that+-- change what a scan costs or returns. They are a record of their own, and+-- not arguments, so that more of them can be added without breaking callers.+--+-- Which one to use:+--+-- * 'upperBound' when each range gets an iterator of its own. It needs no+--   configuration of the database and works with keys of any shape.+-- * 'prefixSameAsStart' when one iterator is sent to many ranges, one seek+--   after another: the bound moves with each seek. It needs a 'prefixLength',+--   and the ranges have to be whole prefixes of that length.+-- * 'totalOrderSeek' when a database with a 'prefixLength' has to be walked+--   from end to end.+data IterConfig = IterConfig+    { lowerBound :: !(Maybe ByteString)+      -- ^ the smallest key that the iterator can be at. Going backwards, it+      -- becomes invalid instead of moving to a smaller key; a seek to a+      -- smaller key lands on the first key at or after the bound.+    , upperBound :: !(Maybe ByteString)+      -- ^ a key that the iterator stays below: the bound itself is outside.+      -- Going forwards, the iterator becomes invalid instead of reaching the+      -- bound or a larger key, and 'iterLast' goes to the last key below it.+      -- 'prefixUpperBound' gives the bound that ends a prefix.+    , prefixSameAsStart :: !Bool+      -- ^ stay within the prefix of the key that the iterator was last sent+      -- to with 'iterSeek': the iterator becomes invalid instead of moving+      -- to a key with another prefix. The prefix is the first+      -- 'Database.RocksDB.prefixLength' bytes of a key. It has no effect in+      -- a database or column family without a prefix length, nor together+      -- with 'totalOrderSeek', nor after 'iterFirst' or 'iterLast', which+      -- name no prefix.+    , totalOrderSeek :: !Bool+      -- ^ see every key in order, whatever its prefix, in a database or+      -- column family that has a 'Database.RocksDB.prefixLength'. There, a+      -- plain iterator is only sure to return the keys that share the prefix+      -- of the key it was sent to; what it does once it moves past them, or+      -- after 'iterFirst', is not defined. That is the price of the prefix+      -- filters, which let a seek skip the files that have nothing for a+      -- prefix. This option gives up the filters and gets the order back.+    }+    deriving (Eq, Show)++-- | No bounds, and seeks as RocksDB does them by default.+instance Default IterConfig where+    def =+        IterConfig+            { lowerBound = Nothing+            , upperBound = Nothing+            , prefixSameAsStart = False+            , totalOrderSeek = False+            }++-- | The smallest key that is greater than every key that starts with the+-- given prefix: the 'upperBound' of a scan of the prefix.+--+-- It is the prefix with its last byte raised by one, after dropping the bytes+-- @0xff@ at its end, which cannot be raised. An empty prefix, or one that is+-- all @0xff@, has no key above its keys, and gives 'Nothing': the scan needs+-- no bound, since it ends where the data ends.+--+-- >>> prefixUpperBound "user:"+-- Just "user;"+prefixUpperBound :: ByteString -> Maybe ByteString+prefixUpperBound prefix =+    case B.unsnoc (B.dropWhileEnd (== 0xff) prefix) of+        Nothing -> Nothing+        Just (start, byte) -> Just (B.snoc start (byte + 1))++-- | Create an 'Iterator' that stops where an t'IterConfig' says, over the+-- default column family or over a column family if one is given, and use it.+--+-- Like 'withIter', it reads from the snapshot of the t'DB' if it comes from+-- 'Database.RocksDB.withSnapshot', and otherwise sees the database as it was+-- when the iterator was created.+--+-- Use it instead of 'withIter' when the range to scan is known beforehand+-- and what follows it may hold many deleted keys, as in a queue or in any+-- index whose entries come and go: see the module header. For a range that+-- is followed by live keys there is little to gain. Creating the iterator+-- costs slightly more than with 'withIter', since it gets read options of+-- its own and the bounds are copied.+--+-- Iterator should not be used after computation ends.+withIterConfig :: DB -> Maybe ColumnFamily -> IterConfig -> (Iterator -> IO a) -> IO a+withIterConfig db mcf cfg f =+    bracket (createIteratorConfig db mcf cfg) snd (f . fst)++-- | Manually create an unmanaged iterator like that of 'withIterConfig'.+--+-- It returns the iterator and the action that destroys it. Run the action+-- once, when done with the iterator, and before the t'DB' is closed or its+-- snapshot released. Do not use 'destroyIterator' on this iterator: RocksDB+-- keeps pointers to the bounds for as long as the iterator lives, so they+-- are in memory that only that action frees, along with the read options.+--+-- For automatic resource management, prefer 'withIterConfig'.+createIteratorConfig :: DB -> Maybe ColumnFamily -> IterConfig -> IO (Iterator, IO ())+createIteratorConfig db mcf cfg = mask_ $ do+    ro <- c_rocksdb_readoptions_create+    lower <- bound ro c_rocksdb_readoptions_set_iterate_lower_bound (lowerBound cfg)+    upper <- bound ro c_rocksdb_readoptions_set_iterate_upper_bound (upperBound cfg)+    let release = do+            c_rocksdb_readoptions_destroy ro+            mapM_ free lower+            mapM_ free upper+    it <- flip onException release $ do+        forM_ (snapshot db) (c_rocksdb_readoptions_set_snapshot ro)+        when (prefixSameAsStart cfg) $ c_rocksdb_readoptions_set_prefix_same_as_start ro 1+        when (totalOrderSeek cfg) $ c_rocksdb_readoptions_set_total_order_seek ro 1+        createIteratorWithOpts db ro mcf+    return (it, c_rocksdb_iter_destroy it >> release)+  where+    -- A copy of the bound outside the Haskell heap, where it does not move+    -- and lives until it is freed. One byte is asked for at least, so that+    -- an empty bound has a pointer too.+    bound ::+        ReadOpts ->+        (ReadOpts -> CString -> CSize -> IO ()) ->+        Maybe ByteString ->+        IO (Maybe CString)+    bound ro set mkey = forM mkey $ \key -> do+        let len = B.length key+        ptr <- mallocBytes (max 1 len)+        BU.unsafeUseAsCString key $ \src -> copyBytes ptr src len+        set ro ptr (intToCSize len)+        return ptr  -- | Manually create unmanaged iterator, over the default column family or over -- a column family if one is given. It uses the 'readOpts' of the t'DB', so if

@@ -36,6 +36,7 @@ import Data.Map.Strict qualified as Map import Data.Maybe import Database.RocksDB+import GHC.Clock (getMonotonicTime) import System.IO.Temp import Test.Hspec import Test.Hspec.QuickCheck (modifyMaxSuccess, prop)@@ -47,6 +48,7 @@ main = hspec $ do   around (withTunedDB ["one", "two", "tree"]) tunedSpec   around withPlainDB plainSpec+  boundSpec   openingSpec   tuningSpec   modifyMaxSuccess (const 50) modelSpec@@ -135,6 +137,14 @@   iterGetError itr `shouldReturn` Nothing   return entries +-- | The time that so many runs of an action take, in seconds.+timed :: Int -> IO a -> IO Double+timed n action = do+  t0 <- getMonotonicTime+  replicateM_ n action+  t1 <- getMonotonicTime+  return (t1 - t0)+ -- | Whether a property value is a number greater than zero. positive :: Maybe ByteString -> Bool positive = maybe False (maybe False ((> 0) . fst) . C.readInt)@@ -155,6 +165,22 @@ -- Examples against a tuned database ------------------------------------------------------------------------------- +boundSpec :: Spec+boundSpec = describe "The bound that ends a prefix" $ do+  it "gives the bound that ends a prefix" $ do+    prefixUpperBound "user:" `shouldBe` Just "user;"+    prefixUpperBound "a\xff\xff" `shouldBe` Just "b"+    prefixUpperBound "\xff\xff" `shouldBe` Nothing+    prefixUpperBound "" `shouldBe` Nothing+  prop "bounds exactly the keys with the prefix" $ \(ws, vs) ->+    let prefix = BS.pack ws+        rest = BS.pack vs+        inside b k = (prefix `BS.isPrefixOf` k) == (k >= prefix && k < b)+     in case prefixUpperBound prefix of+          Nothing -> BS.all (== 0xff) prefix+          -- a key that has the prefix, and one that most likely has not+          Just b -> inside b (prefix <> rest) && inside b rest+ tunedSpec :: SpecWith DB tunedSpec = do   describe "Database" $ do@@ -210,6 +236,39 @@         iterEntry itr `shouldReturn` Just ("bbb1", "vbbb1")         iterNext itr         iterEntry itr `shouldReturn` Just ("bbb2", "vbbb2")+  describe "Iterators and prefixes" $ do+    -- the prefix of this database is three bytes+    let keys = ["aaa1", "aaa2", "bbb1", "bbb2", "ccc1"] :: [ByteString]+        fill db = forM_ keys $ \k -> put db k k+        from k itr = iterSeek itr k >> map fst <$> scan iterNext itr+    it "stays within the prefix it was sent to" $ \db -> do+      fill db+      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do+        from "bbb" itr `shouldReturn` ["bbb1", "bbb2"]+        iterGetError itr `shouldReturn` Nothing+        -- the same iterator, sent elsewhere, has its bound there+        from "aaa2" itr `shouldReturn` ["aaa2"]+        from "ccc" itr `shouldReturn` ["ccc1"]+        from "abc" itr `shouldReturn` []+    it "stays within the prefix when the data is in table files" $ \db -> do+      fill db+      -- enough writes to flush the keys out of memory, where the prefix+      -- filters are+      forM_ [0 .. 20000] $ \i -> put db ("zzz" <> key i) (BS.replicate 1000 0)+      withIterConfig db Nothing def {prefixSameAsStart = True} $ \itr -> do+        from "bbb" itr `shouldReturn` ["bbb1", "bbb2"]+        from "abc" itr `shouldReturn` []+    it "walks every prefix in order when asked for the total order" $ \db -> do+      fill db+      withIterConfig db Nothing def {totalOrderSeek = True} $ \itr -> do+        map fst <$> forwards itr `shouldReturn` keys+        map fst <$> backwards itr `shouldReturn` reverse keys+        from "abc" itr `shouldReturn` ["bbb1", "bbb2", "ccc1"]+    it "takes an upper bound across prefixes with the total order" $ \db -> do+      fill db+      let cfg = def {totalOrderSeek = True, upperBound = Just "bbb2"}+      withIterConfig db Nothing cfg (from "aaa2") `shouldReturn` ["aaa2", "bbb1"]+   describe "Properties" $ do     it "reports memory use, per database and per column family" $ \db -> do       one <- firstFamily db@@ -366,6 +425,93 @@       put db "a" "1"       bracket (createIterator db Nothing) destroyIterator forwards         `shouldReturn` [("a", "1")]+  describe "Bounded iterators" $ do+    let keys = ["a1", "a2", "b1", "b2", "c1", "c2"] :: [ByteString]+        fill db = forM_ keys $ \k -> put db k k+        from k itr = iterSeek itr k >> map fst <$> scan iterNext itr+    it "stops below an upper bound, which is outside" $ \db -> do+      fill db+      withIterConfig db Nothing def {upperBound = Just "b2"} $ \itr -> do+        from "a2" itr `shouldReturn` ["a2", "b1"]+        iterGetError itr `shouldReturn` Nothing+        map fst <$> backwards itr `shouldReturn` ["b1", "a2", "a1"]+        from "b2" itr `shouldReturn` []+    it "stops at a lower bound, which is inside" $ \db -> do+      fill db+      withIterConfig db Nothing def {lowerBound = Just "b1"} $ \itr -> do+        map fst <$> backwards itr `shouldReturn` ["c2", "c1", "b2", "b1"]+        map fst <$> forwards itr `shouldReturn` ["b1", "b2", "c1", "c2"]+        from "a1" itr `shouldReturn` ["b1", "b2", "c1", "c2"]+    it "keeps between two bounds" $ \db -> do+      fill db+      let cfg = def {lowerBound = Just "a2", upperBound = Just "c1"}+      withIterConfig db Nothing cfg $ \itr -> do+        map fst <$> forwards itr `shouldReturn` ["a2", "b1", "b2"]+        map fst <$> backwards itr `shouldReturn` ["b2", "b1", "a2"]+    it "scans a prefix with the bound that ends it" $ \db -> do+      fill db+      withIterConfig db Nothing def {upperBound = prefixUpperBound "b"} $ \itr ->+        from "b" itr `shouldReturn` ["b1", "b2"]+    it "returns nothing below an empty upper bound" $ \db -> do+      fill db+      withIterConfig db Nothing def {upperBound = Just ""} $ \itr ->+        forwards itr `shouldReturn` []+    it "is an ordinary iterator without bounds" $ \db -> do+      fill db+      withIterConfig db Nothing def $ \itr ->+        map fst <$> forwards itr `shouldReturn` keys+    it "keeps bounds with bytes that C takes for the end of a string" $ \db -> do+      let ks = ["k\0a", "k\0b", "k\0c"]+      forM_ ks $ \k -> put db k k+      withIterConfig db Nothing def {upperBound = Just "k\0c"} $ \itr ->+        map fst <$> forwards itr `shouldReturn` ["k\0a", "k\0b"]+    it "stays within its column family" $ \db -> do+      cf <- firstFamily db+      fill db+      putCF db cf "b3" "other"+      withIterConfig db (Just cf) def {upperBound = Just "c"} $ \itr ->+        forwards itr `shouldReturn` [("b3", "other")]+    it "reads from the snapshot of its database" $ \db -> do+      fill db+      withSnapshot db $ \snap -> do+        put db "b15" "late"+        delete db "b2"+        let cfg = def {upperBound = prefixUpperBound "b"}+        withIterConfig snap Nothing cfg (from "b") `shouldReturn` ["b1", "b2"]+        withIterConfig db Nothing cfg (from "b") `shouldReturn` ["b1", "b15"]+    it "can be created and destroyed by hand" $ \db -> do+      fill db+      (itr, destroyIt) <- createIteratorConfig db Nothing def {upperBound = Just "b"}+      from "a" itr `shouldReturn` ["a1", "a2"]+      destroyIt+    it "does not keep its bounds in memory that Haskell moves" $ \db -> do+      forM_ [0 .. 999] $ \i -> put db (key i) "v"+      -- the bound is built at run time, used by many iterators, and the+      -- heap is churned between seeks+      forM_ [1 .. 50 :: Int] $ \n ->+        withIterConfig db Nothing def {upperBound = Just (key (n * 10))} $ \itr -> do+          let junk = sum (map BS.length [key j | j <- [1 .. 20000]])+          junk `shouldBe` 160000+          iterSeek itr (key 0)+          length <$> scan iterNext itr `shouldReturn` n * 10+    it "does not step over deleted keys past its upper bound" $ \db -> do+      -- keys of "b" that are all deleted, between two keys that live: an+      -- unbounded scan of "a" reads every marker to find "c"+      let dead = [C.pack (printf "b%06d" i) | i <- [1 .. 20000 :: Int]]+      put db "a1" "v"+      put db "c1" "v"+      write db (map (\k -> Put k "v") dead)+      write db (map Del dead)+      let bounded = withIterConfig db Nothing def {upperBound = prefixUpperBound "a"} (from "a2")+          unbounded = withIter db $ \itr -> iterSeek itr "a2" >> iterKey itr+      bounded `shouldReturn` []+      unbounded `shouldReturn` Just "c1"+      slow <- timed 20 unbounded+      fast <- timed 20 bounded+      -- measured at 2,600 microseconds against 2.5; ten times leaves room+      -- for a busy machine+      (fast * 10 < slow) `shouldBe` True+   describe "Snapshots" $ do     it "hides later writes and deletes from every kind of read" $ \db -> do       other <- firstFamily db