redb

New features

• Add an experimental cursor API, behind the experimental_cursor feature flag:
  Table::lower_bound_mut() and Table::upper_bound_mut() return a CursorMut pointing at a gap
  between entries, modeled on the standard library's BTreeMap cursors. Inserting sorted data
  through its insert_before() method can be around 3x faster than calling insert() with the
  same data; insert_after() inserts through the gap in descending order at the same speed.
  ReadableTable::lower_bound() and ReadableTable::upper_bound() return a read-only Cursor.
  The feature is unstable and may change incompatibly, or be removed, in any release.
• Add ReadOnlyTable::get_owned(), ReadOnlyTable::range_owned(),
  ReadOnlyMultimapTable::get_owned(), and ReadOnlyMultimapTable::range_owned(), which
  return the new OwnedAccessGuard, OwnedRange, OwnedMultimapValue, and
  OwnedMultimapRange types. These keep the read transaction alive until they are dropped,
  including the guards yielded by the iterators, which may outlive the iterator that produced
  them.
• Add Table::entry() and the associated Entry, OccupiedEntry, and VacantEntry
  types, mirroring std::collections::BTreeMap::entry. Supports or_insert,
  or_insert_with, or_insert_with_key, and_modify, and the usual OccupiedEntry
  / VacantEntry accessors.
• Add ExtractIf::close() to explicitly finalize an extract iterator without removing unread
  entries.

Optimizations

• Improve write performance: Durability::None commits are about 2x faster, and writes that do not
  split a page are about 15% faster for single-key Durability::None commits and about 6% faster
  for batched writes.
• Improve write performance when tables of a single WriteTransaction are modified concurrently
  from multiple threads. Writes to separate tables previously serialized on internal locks and
  could be slower than writing from a single thread; they now scale with the number of threads.
  Up to about 4x faster.
• Optimize Table::pop_first() and Table::pop_last() to be about 2x faster.
• Optimize inserting in ascending key order. A table loaded in key order occupies about half as
  much space, and loads faster.
• Optimize Table::retain(), Table::retain_in(), Table::extract_if(), and
  Table::extract_from_if(). Benchmarks on large tables show a 30-100x speedup for retaining and
  an 18-65x speedup for extracting, depending on the fraction of entries affected. Iterating an
  extract iterator from both ends no longer degrades removal batching.
• Avoid unnecessary write amplification when removing a value that is not present from a multimap
  table. Such a removal is now a no-op.

Minor improvements

• Table::retain(), Table::retain_in(), Table::extract_if(), and Table::extract_from_if()
  now poison the write transaction if their predicate panics or an internal error prevents
  removals from being applied, causing WriteTransaction::commit() to return
  CommitError::TransactionPoisoned. After an extract iterator returns an error, later calls keep
  returning an error instead of continuing.
• Enable file space reclamation during non-durable transactions performed while a savepoint exists.
• Reuse pages freed by a durable write transaction in the next write transaction when no live read
  transaction or savepoint still needs them. Previously, pages were not reused for one additional
  transaction.
• compact() now returns CompactionError::PersistentSavepointExists or
  CompactionError::EphemeralSavepointExists instead of the misleading
  CompactionError::TransactionInProgress when a savepoint blocks compaction.
• StorageBackend::close() is now called when opening a database fails and when an I/O error occurs
  while dropping a Database, allowing backends to release their resources on both paths.

Bug fixes

• Return StorageError::Corrupted instead of panicking when opening or repairing a database with a
  corrupted persistent savepoint record or malformed freed-page record.
• Return StorageError::Corrupted instead of aborting the process when branch pages form a cycle or
  arbitrarily long chain, or when a corrupted page number could cause a multi-terabyte allocation.
• Fix WriteTransaction::stats() returning garbage statistics, or panicking when debug assertions
  are enabled, when called while a table is open and modified in the same transaction.
• Fix a deadlock when a Database was dropped while a WriteTransaction was live. A live
  WriteTransaction now keeps the database open: the transaction remains usable after the
  Database is dropped, and the database closes when the transaction commits, aborts, or is
  dropped.
• Fix a panic, including one raised while dropping a Database, after check_integrity() returned
  an error. Such a database now refuses to begin a write transaction or to re-run the check,
  returning StorageError::Corrupted, and is no longer recorded as cleanly shut down.
• Harden against errors and panics raised part way through WriteTransaction::commit(): the
  database now refuses further write transactions until it is closed and reopened (which
  repairs it), instead of risking corruption from continued use after the failed commit.
• Fix a case where check_integrity() failed to repair the database when the table length was
  corrupted. Such a file previously passed the check and then panicked, including from
  Database::drop.
• Fix a potential deadlock when removing a value from a multimap table causes its value-set to
  shrink from a subtree back to inline storage, while another table of the same write transaction
  is used concurrently from a different thread.
• Fix crashes while growing or resizing the database file that could leave it permanently
  unopenable or reported as corrupted on subsequent opens, even though every committed transaction
  was intact and fully recoverable.
• Fix cases where the database file could grow instead of reusing freed space, and where
  compact() could grow the file or stop before fully shrinking it.
• Fix Table::get_mut() and Entry::and_modify() to enforce the maximum value size limit.
  Previously these paths could bypass the limit that Table::insert() and the entry() accessors
  enforce.
• Fix a panic in insert() when a single leaf page accumulated 65536 entries via in-place
  appends, e.g. by inserting a large value and then many small values in ascending key order
  within the same transaction.
• Fix check_integrity() incorrectly reporting a healthy database as corrupted (and panicking
  in debug builds) after a persistent savepoint was deleted or restored, or when an ephemeral
  Savepoint was dropped from another thread while the same write transaction was committing.
• Fix a leak of database space when an ephemeral Savepoint was created from one thread while the
  same write transaction was first accessing a table from another thread, and that savepoint was
  later restored. The leaked space was only reclaimed by a full repair.
• Fix a panic when opening a database file that was externally extended to an invalid size; such
  files are now rejected with StorageError::Corrupted.
• Fix a hang on Windows when opening a truncated or corrupt database file. Reads past the end of the
  file now return an error instead of looping forever.
• Fix check_integrity() so that it now returns DatabaseError::TransactionInProgress when an
  ephemeral Savepoint is still alive. Previously the check could invalidate the pages such a
  savepoint referenced while leaving it marked valid, so restoring it afterward could corrupt the
  database.
• Fix Database::check_integrity() silently discarding transactions committed with
  Durability::None that had not yet been made durable by a later commit; a passing check now
  preserves them (making them durable) instead of rolling them back.
• Fix a bug that could silently roll back or corrupt durably committed transactions if a crash
  occurred while recovering from an earlier crash. Triggering it required two crashes -- one
  interrupting a commit and another during the subsequent repair on the next open -- and it did
  not affect transactions committed with two-phase commit.
• Fix new composite types (Option, Vec, tuples, and arrays) of a user-defined type sharing a
  type identity with the same composite of a built-in type when the two happened to have the same
  name. A table using such a composite of a user type can no longer be silently opened under the
  built-in composite (and vice versa); the mismatch is now reported as TableError::TableTypeMismatch.
  Existing databases created by older versions remain readable. If an older database already used
  such a colliding composite name, its stored type identity remains ambiguous and may still open
  under either spelling.

This release contains a large number of bug fixes discovered by AI coding agents

• Fix a bug where MultimapValue::len() and is_empty() returned stale counts after
  consuming entries via next_back().
• Fix a bug where restore_savepoint() used in a non-Immediate durability transaction and when
  there are persistent savepoints newer than the one being restored, could fail
  with SavepointError::InvalidSavepoint, but the savepoint would actually be partially applied.
  The call now fails up front with SavepointError::ImmediateDurabilityRequired.
• Fix a bug in restore_savepoint() where modifications made earlier in the transaction might
  not be reverted.
• Fix a bug where renaming a table that was already modified in the same transaction could cause
  the database to become corrupted.
• Fix a bug where calling restore_savepoint() after modifying a table in the same
  transaction could cause the table to become corrupted in a future transaction.
• Fix a panic when delete_table() was called on a table that had been modified in the same
  transaction.
• Fix a panic in restore_savepoint() when passed a Savepoint from a different Database.
  SavepointError::InvalidSavepoint is now returned instead.
• Fix a bug where a transaction that created a persistent savepoint and was then
  aborted could cause the database file to grow excessively, until the Database was dropped.
• Fix a panic in check_integrity() when called while another transaction is still alive.
  DatabaseError::TransactionInProgress is now returned instead.
• Fix a bug where aborting a transaction that called restore_savepoint() with a savepoint
  when a newer savepoint existed could cause database space to be leaked.
• Fix a bug where aborting a transaction that called restore_savepoint() would leave more
  recent savepoints invalid.
• Improve performance when reading concurrently from multiple threads. Around 15% speedup on some benchmarks.
• Optimize cache usage, and general write performance. Around 1.5x speedup on some benchmarks.
• Optimize memory usage.
• Other performance optimizations.

• Implement Drop on AccessGuardMut and AccessGuardMutInPlace, which requires that these be dropped
  before the Table they borrow from.
  This fixes a critical bug where the accessor could outlive the Table, and be dropped after the
  transaction had already committed. This could cause data loss due to the data in the accessor
  being written out after the transaction had already completed.
• Remove Legacy type. To migrate off the Legacy type, use the Legacy type in the 3.x release
  and copy the data to a table with plain tuples, before upgrading to the 4.x release.

• Fix a data loss bug which can occur when the guard returned from Table::get_mut() is dropped
  after the transaction has been committed.
• Add a warning to Table::insert_reserve() indicating that it can cause data loss and recommending
  to upgrade to the 4.0.0 release.

• Reduce memory usage of open databases

• Fix panic which could occur when inserting into a table with fixed size keys when debug_assertions are enabled
• Add additional information to the stats returned by cache_stats()

• Implement std::error::Error for SetDurabilityError
• Fix compilation error on various non-tier-1 platforms, such as wasm32-unknown

• Fix performance issue where a transaction with a large number of writes would cause
  WriteTransaction::abort() and committing non-durable transactions to become slow

• Fix correctness issue with range(), extract_from_if(), and retain_in(). If a RangeBounds
  with start > end was passed as an argument and start and end keys were stored in different
  internal pages in the database (i.e. a sufficient condition is that more than 4KiB of key-value
  pairs were between the two keys) then these methods would perform as if the argument had been
  start..
• Fix performance regression, from redb 2.x, where Durability::None commits could become linearly
  slower during a series of transactions.

Removes support for file format v2.

Use Database::upgrade(), in redb 2.6, to migrate to the v3 file format.

General storage optimizations

The v3 file format has been further optimized to reduce the size of the database. Databases with only a few small keys will see the largest benefit, and the minimum size of a database file has decreased from ~2.5MiB to ~50KiB. To achieve the smallest file size call Database::compact() before dropping the Database.

Additionally, performance is ~15% better in bulk load benchmarks. This was achieved by implementing a custom hash function for various in-memory HashSets and HashMaps, and by optimizing the usage of buffers held in Arcs to reduce the number of atomic instructions executed.

Optimize storage of tuple types

Storage of variable width tuple types with arity greater than 1 is more efficient. The new format elides the length of any fixed width fields and uses varint encoding for the lengths of all variable width fields.

Note that this encoding is not compatible with the serialization of variable width tuples used in prior versions. To load tuple data created prior to version 3.0, wrap them in the Legacy type. For example, TableDefinition<u64, (&str, u32)> becomes TableDefinition<u64, Legacy<(&str, u32)>>. Fixed width tuples, such as (u32, u64) are backwards compatible.

Derive for Key and Value traits

Key and Value can be derived using the redb-derive crate. Note that it does not support schema migration. The recommended pattern to migrate schema is to create a new table, and then perform a migration from the old table to the new table.

Read-only multi-process support

Multiple processes may open the same database file for reading by using the new ReadOnlyDatabase type. On platforms which support file locks, this acquires a shared lock on the database file.

Enable garbage collection in Durability::None transactions

Non-durable transactions will now free pages when possible (pages allocated in a preceding non-durable transaction which are no longer referenced). This resolves an issue where a long sequence of non-durable transactions led to significant growth in the size of the database file. This change increases the RAM required for a sequence of non-durable transactions, such that RAM proportional to the net change in the database is now used. However, it will never use more than about 0.2% of the database file size.

Other changes

• Add ReadOnlyDatabase
• Add Builder::open_read_only()
• Add StorageBackend::close()
• Add Table::get_mut()
• Add chrono_v0_4 feature flag which enables serialization of the NaiveDate, NaiveTime, NaiveDatetime, DateTime<FixedOffset>, and FixedOffset types in the chrono crate
• Add uuid feature flag which enables serialization of the Uuid type in the uuid crate
• Change StorageBackend::read() to accept a &mut [u8] output argument instead of returning a Vec<u8>
• Change Table::insert_reserve() to take usize instead of u32 as the argument type
• Change TypeName::name() to be public
• Change ReadTransactionStillInUse to contain a Box
• Change set_durability() to return a Result
• Move Database::cache_stats() and Database::begin_read() to ReadableDatabase trait
• Rename AccessGuardMut to AccessGuardMutInPlace. Note that a new AccessGuardMut struct has been added; it serves a different purpose
• Remove Durability::Paranoid
• Fix a rare case where check_integrity() returned Ok(false) even though no repair was required, when called on a database that was not shutdown cleanly and was automatically repaired when opened
• Disallow access to the database from read transactions after the Database as been dropped. Access will now return DatabaseClosed

• Fix unbounded memory growth in the page cache under write workloads, when the cache never
  reached its configured size limit.

• Fix correctness issue with range(), extract_from_if(), and retain_in(). If a RangeBounds
  with start > end was passed as an argument and start and end keys were stored in different
  internal pages in the database (i.e. a sufficient condition is that more than 4KiB of key-value
  pairs were between the two keys) then these methods would perform as if the argument had been
  start..

• Forward compatibility improvement which makes the file format more flexible to support a potential future optimization

• Fix a forward compatibility issue which caused a crash when opening databases created with redb 3.x. Note that opening 3.x databases with redb 2.x is not generally supported and only works in certain situations.

Add support for the v3 file format.

This file format improves savepoints. Savepoints in the v3 format have constant, and small, overhead. Creating and restoring them is also much faster. The v3 file format also supports savepoints on large databases (v2 has a limit around 32TB). This release creates v2 databases by default. Use Builder::create_with_file_format_v3() and Database::upgrade(), respectively, to enable and migrate to v3.

The upcoming 3.0 release will only support the v3 file format.

• Add Builder::create_with_file_format_v3()
• Add Database::upgrade()

• Add rename_table() and rename_multimap_table()
• Add Key and Value implementations for the unary tuple type (i.e. (T,))
• Fix an issue which could cause a panic when concurrently performing read and write transactions, when debug_assertions were enabled
• Optimize retain() and retain_in() to use less space in the database file
• Improve handling of some internal errors to return LockPoisoned instead of panicking

• Add Database::cache_stats()
• Fix open() and create() to return InvalidData when they are called on a database file that is not a valid redb database
• Significantly speed up restore_savepoint(). The time is takes now scales with the change delta since the savepoint was captured, rather than the size of the database file
• DatabaseStats::fragmented_bytes() is now more accurate

• Add WriteTransaction::set_two_phase_commit()
• Add WriteTransaction::set_quick_repair() which enables a faster repair mechanism at the cost of slower transaction commits
• Durability::Paranoid is now deprecated. Use set_two_phase_commit(true) instead
• Fix various bugs when repairing the database after an unclean shutdown. These could result in panics, leaked space in the database file, or database corruption

• Implement TableHandle for ReadOnlyTable
• Fix bug in write cache, which caused pages to be evicted randomly. Pages are now evicted based on how recently they have been accessed

• Optimize first() and last() to be almost 2x faster
• Improve in-memory cache algorithm to resolve edge cases where certain pages could become uncacheable under cache pressure
• Fix bug in read cache where the read cache could become disabled. This was likely to occur in multithreaded workloads when the read cache was smaller than the database file. This bug lead to 5-10x performance degradations for some workloads

• Significant performance optimizations to compact()
• Fix some additional cases where compact() did not fully compact the database
• Fix a panic that could occur in commit() or abort() after an IO error. StorageError::PreviousIo is now returned
• Fix a potential panic that could occur when repairing the database after a crash

Major fixes:

• Fix leak of database space that could occur when calling restore_savepoint()
• Fix leak of database space when calling delete_multimap_table()
• Fix database corruption which could occur when restoring a savepoint. This edge case is rare, and could only occur if the database was less than approximately 4TiB when the savepoint was created, and greater than 4TiB when the savepoint was restored
• Fix edge case where a transient I/O error that occurred during transaction commit, but then did not reoccur when the Database was dropped, could cause database corruption

Important: If your application has called restore_savepoint(), delete_multimap_table(), or you suspect it may have experienced a transient I/O error during transaction commit. It is recommended that you run check_integrity() after upgrading to this version. This will both detect corruption and clean up any leaked space.

Other changes and fixes:

• Optimize page freeing to reduce the size of the database file
• Fix several cases where check_integrity() would return Ok(false) instead of Ok(true)
• Fix some cases where compact() did not fully compact the database
• Make the metadata overhead returned by WriteTransaction::stats() more accurate
• Return StorageError::ValueTooLarge when a key-value pair exceeds a total of 3.75GiB. Previously, a panic would occur for key-value pairs that were approximately 4GiB.
• Downgrade several info! log messages to debug!
• Improve documentation

• Fix panic that occurred when calling compact() when a read transaction was in progress
• Fix ReadTransaction::close() to return Ok when it succeeds
• Performance optimizations

• Implement Key and Value for String
• Allow users to implement ReadableTableMetadata, ReadableTable, and ReadableMultimapTable

Major file format change

2.0.0 uses a new file format that optimizes len() to be constant time. This means that it is not backwards compatible with 1.x. To upgrade, consider using a pattern like that shown in the upgrade_v1_to_v2 test.

Other changes

• check_integrity() now returns a DatabaseError instead of a StorageError
• Table metadata methods have moved to a new ReadableTableMetadata trait
• Rename RedbKey to Key
• Rename RedbValue to Value
• Remove lifetimes from read-only tables
• Remove lifetime from WriteTransaction and ReadTransaction
• Remove drain() and drain_filter() from Table. Use retain, retain_in, extract_if or extract_from_if instead
• impl Clone for Range
• Add support for [T;N] as a Value or Key as appropriate for the type T
• Add len() and is_empty() to MultimapValue
• Add retain() and retain_in() to Table
• Add extract_if() and extract_from_if() to Table
• Add range() returning a Range with the 'static lifetime to read-only tables
• Add get() returning a range with the 'static lifetime to read-only tables
• Add close() method to ReadTransaction

• Fix correctness issue with range(), drain(), and drain_filter(). If a RangeBounds with start > end was passed as an argument and start and end keys were stored in different internal pages in the database (i.e. a sufficient condition is that more than 4KiB of key-value pairs were between the two keys) then these methods would perform as if the argument had been start..

• Fix check_integrity() so that it returns Ok(true) when no repairs were preformed. Previously, it returned Ok(false)

• Export TableStats type
• Export MutInPlaceValue which allows custom types to support insert_reserve()
• Add untyped table API which allows metadata, such as table stats, to be retrieved for at table without knowing its type at compile time
• Fix compilation on uncommon platforms (those other than Unix and Windows)

• Add Builder::set_repair_callback() which can be used to set a callback function that will be invoked if the database needs repair while opening it.
• Add support for custom storage backends. This is done by implementing the StorageBackend trait and using the Builder::create_with_backend function. This allows the database to be stored in a location other than the filesystem
• Implement RedbKey and RedbValue for char
• Implement RedbKey and RedbValue for bool
• Implement TableHandle for Table
• Implement MultimapTableHandle for MultimapTable
• Fix panic that could occur when inserting a large number of fixed width values into a table within a single transaction
• Fix panic when calling delete_table() on a table that is already open
• Improve performance for fixed width types
• Support additional platforms

• Implement RedbKey for Option<T>
• Implement RedbValue for Vec<T>
• Implement Debug for tables
• Add ReadableTable::first() and last() which retrieve the first and last key-value pairs, respectively`
• Reduce lock contention for mixed read-write workloads
• Documentation improvements

• Add Builder::create_file() which does the same thing as create() but takes a File instead of a path
• Add stats() to tables which provides informational statistics on the table's storage
• Fix WriteTransaction::stats() to correctly count the storage used by multi-map tables
• Fix panics that could occur when operating on savepoints concurrently from multiple threads on the same WriteTransaction
• Implement Send for WriteTransaction
• Change MSRV to 1.66
• Performance optimizations

• Fix panic when calling compact() on certain databases
• Fix panic when calling compact() when an ephemeral Savepoint existed
• Improve performance of compact()
• Relax lifetime requirements on arguments to insert()

• Fix a rare panic when recovering a database file after a crash
• Minor performance improvement to write heavy workloads

• Fix serious data corruption issue when calling drain() or drain_filter() on a Table that had uncommitted data

• Fix panic when re-opening databases of certain, small, sizes

• Fix panic when recovering some databases after a forceful shutdown
• Fix panic when recovering databases with multimaps that have fixed width values after a forceful shutdown

• Fix panic that could occur after an IO error when reopening a database
• Fix panic that could occur after an IO error when opening a table
• Improve error message when opening a table twice to include a more meaningful line number
• Performance improvements

Announcement

redb has reached its first stable release! The file format is now gauranteed to be backward compatible, and the API is stable. I've run pretty extensive fuzz testing, but please report any bugs you encounter.

The following features are complete:

• MVCC with a single WriteTransaction and multiple ReadTransactions
• Zero-copy reads
• ACID semantics, including non-durable transactions which only sacrifice Durability
• Savepoints which allow the state of the database to be captured and restored later

Changes from 0.22.0:

• Stabilize file format
• Improve performance of restore_savepoint()

• Fix panic while repairing a database file after crash
• Fix rare panic in restore_savepoint()

• Improve cache heuristic. This asymptotically improves performance on large databases. Benchmarks show 30% to 5x+
• Fix rare crash that could occur under certain conditions when inserting values > 2GiB
• Fix crash when growing database beyond 4TiB
• Fix panic when repairing a database containing a multimap table with fixed width values
• Performance optimizations
• File format simplifications

• Export TransactionError and CommitError. These were unintentionally private
• Implement std::error::Error for all error enums

• Remove Clone bound from range argument type on drain() and drain_filter()
• File format changes to improve future extensibility

• Improve errors to be more granular. Error has been split into multiple different enums, which can all be implicitly converted back to Error for convenience
• Rename savepoint() to ephemeral_savepoint()
• Add support for persistent savepoints. These persist across database restarts and must be explicitly released
• Optimize restore_savepoint() to be ~30x faster
• Add experimental support for WASI. This requires nightly
• Implement RedbKey for ()
• Fix some rare crash and data corruption bugs

• Enforce a limit of 3GiB on keys & values
• Fix database corruption bug that could occur if a Durability::None commit was made, followed by a durable commit and the durable commit crashed or encountered an I/O error during commit()
• Fix panic when re-openning a database file, when the process that last had it open had crashed
• Fix several bugs where an I/O error during commit() could cause a panic instead of returning an Err
• Change length argument to insert_reserve() to u32
• Change Table::len() to return u64
• Change width of most fields in DatabaseStats to u64
• Remove K type parameter from AccessGuardMut
• Add Database::compact() which compacts the database file
• Performance optimizations

• Combine Builder::set_read_cache_size() and Builder::set_write_cache_size() into a single, Builder::set_cache_size() setting
• Relax lifetime constraints on read methods on tables
• Optimizations to Savepoint

• Add Database::check_integrity() to explicitly run repair process (it is still always run if needed on db open)
• Change list_tables() to return a TableHandle
• Change delete_table() to take a TableHandle
• Make insert_reserve() API signature type safe
• Change all iterators to return Result and propagate I/O errors
• Replace WriteStrategy with Durability::Paranoid
• Remove Builder::set_initial_size()
• Enable db file shrinking on Windows
• Performance optimizations

• Remove Builder::create_mmapped() and Builder::open_mmapped(). The mmap backend has been removed because it was infeasible to prove that it was sound. This makes the redb API entirely safe, and the remaining File based backed is within a factor of ~2x on all workloads that I've benchmarked
• Make Table implement Send. It is now possible to insert into multiple Tables concurrently
• Expose AccessGuardMut, Drain and DrainFilter in the public API
• Rename RangeIter to Range
• RenameMultimapRangeIter to MultimapRange
• Rename MultimapValueIter to MultimapValue
• Performance optimizations

• Fix a major data corruption issue that was introduced in version 0.12.0. It caused databases greater than ~4GB to become irrecoverably corrupted due to an integer overflow in PageNumber::address_range that was introduced by commit b2c44a824d1ba69f526a1a75c56ae8484bae7248
• Add drain_filter() to Table
• Make key and value type bounds more clear for tables

• Fix open() on platforms with OS page size != 4KiB
• Relax lifetime requirements on argument to range() and drain()

• Add pop_first() and pop_last() to Table
• Add drain() to Table
• Add support for Option<T> as a value type
• Add support for user defined key and value types. Users must implement RedbKey and/or RedbValue
• Change get(), insert(), remove()...etc to take arguments of type impl Borrow<SelfType>
• Return Error::UpgradeRequired when opening a file with an outdated file format
• Improve support for 32bit platforms
• Performance optimizations

• Remove [u8] and str type support. Use &[u8] and &str instead.
• Change get(), range() and several other methods to return AccessGuard.
• Rename AccessGuard::to_value() to value()
• Add a non-mmap based backend which is now the default. This makes Database::create() and Database::open() safe, but has worse performance in some cases. The mmap backend is available via create_mmapped()/open_mmapped(). There is no difference in the file format, so applications can switch from one backend to the other.
• Better handling of fsync failures

• Remove maximum database size argument from create(). Databases are now unbounded in size
• Reduce address space usage on Windows
• Remove set_dynamic_growth()
• Add set_initial_size() to Builder
• Optimize cleanup of deleted pages. This resolves a performance issue where openning a Database or performing a small transaction, could be slow if the last committed transaction deleted a large number of pages
• Remove set_page_size(). 4kB pages are always used now
• Add iter() method to Table and MultimapTable
• Fix various lifetime issues with type that had a lifetime, such as &str and (&[u8], u64)

• Add support for dynamic file growth on Windows
• Add support for tuple types as keys and values
• Remove Builder::set_region_size
• Save lifetime from Savepoint
• Fix crash when using create() to open an existing database created with WriteStrategy::TwoPhase
• Fix rare crash when writing a mix of small and very large values into the same table
• Performance optimizations

• Performance improvements for database files that are too large to fit in RAM
• Fix deadlock in concurrent calls to savepoint() and restore_savepoint()
• Fix crash if restore_savepoint() failed
• Move savepoint() and restore_savepoint() methods to WriteTransaction
• Implement Iterator for the types returned from range() and remove_all()

• Add support for Windows
• Add Database::set_write_strategy which allows the WriteStrategy of the database to be changed after creation
• Make Database::begin_write block, instead of panic'ing, if there is another write already in progress
• Add Database::savepoint and Database::restore_savepoint which can be used to snapshot and rollback the database
• Rename DatabaseBuilder to Builder
• Performance optimizations for large databases

• Fix crash when Database::open() was called on a database that had been created with WriteStrategy::TwoPhase
• Change default region size on 32bit platforms to 4GiB

• Return Err instead of panic'ing when opening a database file with an incompatible file format version
• Many optimizations to the file format, and progress toward stabilizing it
• Fix race between read & write transactions, which could cause reads to return corrupted data
• Better document the different WriteStrategys
• Fix panic when recovering a database that was uncleanly shutdown, which had been created with WriteStrategy::Checksum (which is the default)
• Fix panic when using insert_reserve() in certain cases

• Optimize MultimapTable storage format to use O(k * log(n_k) + v * log(n_v / n_k)) space instead of O(k * log(n_k + n_v) + v * log(n_k + n_v)) space, where k is the size of the stored keys, v is the size of the stored values, n_k is the number of stored keys, n_v is the number of stored values
• Fix compilation errors for 32bit x86 targets
• Add support for the unit type, (), as a value
• Return an error when attempting to open the same database file for writing in multiple locations, concurrently
• More robust handling of fsync failures
• Change MultimapTable::range to return an iterator of key-value-collection pairs, instead of key-value pairs
• Automatically abort WriteTransaction on drop