- #440 Introduce Cosmos SDK iterator type directly into IAVL. Improves the iterator performance by 40%.
- #432 Fix race condition related to Cosmos SDK and nodeDB usage.
- Various performance improvements. Credits: Orijtech.
- Updating dependencies
- #396 Add "prefix" arg to iaviewer.
- #355
Get
iniavlServer
no longer returns an error if the requested key does not exist.GetResponse
now contains aNotFound
boolean to indicate that a key does not exist, and the returned index will be that of the next occupied key.
- #355 Add support for
GetByIndex
toiavlServer
and RPC interface.
Special thanks to external contributors on this release: @odeke-em
- #352 Reuse buffer to improve performance of
GetMembershipProof()
andGetNonMembershipProof()
.
Special thanks to external contributors on this release: @odeke-em
-
#347 Fix another integer overflow in
decodeBytes()
that can cause panics for certain inputs. TheValueOp
andAbsenceOp
proof decoders are vulnerable to this via malicious inputs since 0.15.0. -
#349 Fix spurious blank lines in
PathToLeaf.String()
.
Special thanks to external contributors on this release: @odeke-em
- #340 Fix integer overflow in
decodeBytes()
that can cause panics on 64-bit systems and out-of-memory issues on 32-bit systems. TheValueOp
andAbsenceOp
proof decoders are vulnerable to this via malicious inputs. The bug was introduced in 0.15.0.
The IAVL project has moved from https://github.com/tendermint/iavl to
https://github.com/cosmos/iavl. This changes the module import path, which is now
github.com/cosmos/iavl
.
Users upgrading from 0.13 should read important upgrade information in the 0.14.0 release below.
-
#285 The module path has changed from
github.com/tendermint/iavl
togithub.com/cosmos/iavl
. -
#304 Empty trees now return hashes rather than
nil
from e.g.Hash()
,WorkingHash()
, andSaveVersion()
, for conformance with RFC-6962. -
#317
LoadVersion()
andLazyLoadVersion()
now error if called with a positive version number on an empty tree.
-
#296 Add
iavlserver
, a gRPC/REST API server. -
#276 Introduced
ImmutableTree.GetMembershipProof()
andGetNonMembershipProof()
to return ics23 ExistenceProof and NonExistenceProof respectively. -
#265 Encoding of tree nodes and proofs is now done using the Go stdlib and Protobuf instead of Amino. The binary encoding is identical.
- #309 Allow
SaveVersion()
for old, empty versions as long as the new version is identical.
Special thanks to external contributors on this release: @klim0v
- #324 Fix
DeleteVersions
not properly removing orphans, and addDeleteVersionsRange
to delete a range.
- #318 Fix constant overflow when compiling for 32bit machines.
-
#299 Added
Options.InitialVersion
to specify the initial version for new IAVL trees. -
#312 Added
MutableTree.SetInitialVersion()
to set the initial version after tree initialization.
- #288 Fix panics when generating proofs for keys that are all
0xFF
.
Important information: the pruning functionality introduced with IAVL 0.13.0 via the options
KeepEvery
and KeepRecent
has problems with data corruption, performance, and memory usage. For
these reasons, this functionality has now been removed. All 0.13 users are urged to upgrade, and to
not change their pruning settings while on 0.13.
Make sure to follow these instructions when upgrading, to avoid data corruption:
-
If using
KeepEvery: 1
(the default) then upgrading to 0.14 is safe. -
Otherwise, upgrade after saving a multiple of
KeepEvery
- for example, withKeepEvery: 1000
stop 0.13 after saving e.g. version7000
to disk. A later version must never have been saved to the tree. Upgrading to 0.14 is then safe. -
Otherwise, consider using the
Repair013Orphans()
function to repair faulty data in databases last written to by 0.13. This must be done before opening the database with IAVL 0.14, and a database backup should be taken first. Upgrading to 0.14 is then safe. -
Otherwise, after upgrading to 0.14, do not delete the last version saved to disk by 0.13 - this contains incorrect data that may cause data corruption when deleted, making the database unusable. For example, with
KeepEvery: 1000
then stopping 0.13 at version7364
(saving7000
to disk) and upgrading to 0.14 means version7000
must never be deleted.It may be possible to delete it if the exact same sequence of changes have been written to the newer versions as before the upgrade, and all versions between
7000
and7364
are deleted first, but thorough testing and backups are recommended if attempting this.
Users wishing to prune historical versions can do so via MutableTree.DeleteVersion()
.
- #274 Remove pruning options
KeepEvery
andKeepRecent
(see warning above) and therecentDB
parameter toNewMutableTreeWithOpts()
.
-
#282 Add
Repair013Orphans()
to repair faulty orphans in a database last written to by IAVL 0.13.x -
#271 Add
MutableTree.DeleteVersions()
for deleting multiple versions. -
#235 Reduce
ImmutableTree.Export()
buffer size from 64 to 32 nodes.
-
#281 Remove unnecessary Protobuf dependencies.
-
#275 Fix data corruption with
LoadVersionForOverwriting
.
- [import] #230 Set correct version when committing an empty import.
- [#213] Added
ImmutableTree.Export()
andMutableTree.Import()
to export tree contents at a specific version and import it to recreate an identical tree.
- [dep] #220 Update tm-db to 0.5.0, which includes a new B-tree based MemDB used by IAVL for non-persisted versions.
- [nodedb] #219 Fix a concurrent database access issue when deleting orphans.
Special thanks to external contributors on this release: @rickyyangz, @mattkanwisher
- [pruning] #158 NodeDB constructor must provide
keepRecent
andkeepEvery
fields to define PruningStrategy. All Save functionality must specify whether they should flushToDisk as well usingflushToDisk
boolean argument. All Delete functionality must specify whether object should be deleted from memory only using thememOnly
boolean argument. - [dep] #194 Update tm-db to 0.4.0 this includes interface breaking to return errors.
- [orphans] #177 Collect all orphans after remove (@rickyyangz)
- #46 Removed all instances of cmn (tendermint/tendermint/libs/common)
Special thanks to external contributors on this release: @ethanfrey
IMPROVEMENTS
- Implement LazyLoadVersion (@alexanderbez) LazyLoadVersion attempts to lazy load only the specified target version without loading previous roots/versions. - see goDoc
- Move to go.mod (@Liamsi)
iaviewer
command to visualize IAVL database from leveldb (@ethanfrey)
IMPROVEMENTS
- Use Tendermint v0.30.2 and close batch after write (related pull request in Tendermint: tendermint/tendermint#3397)
IMPROVEMENTS
- Use Tendermint v0.30
BREAKING CHANGES
- Uses new Tendermint ReverseIterator API. See tendermint/tendermint#2913
IMPROVEMENTS
- Uses GoAmino v0.14
BREAKING CHANGES
- Changed internal database key format to store int64 key components in a full 8-byte fixed width (#107)
- Removed some architecture dependent methods (e.g., use
Get
instead ofGet64
etc) (#96)
IMPROVEMENTS
- Database key format avoids use of fmt.Sprintf fmt.Sscanf leading to ~10% speedup in benchmark BenchmarkTreeLoadAndDelete (#107, thanks to @silasdavis)
BREAKING CHANGES
- refactored API for clean separation of mutable and immutable tree (#92, #88);
with possibility to:
- load read-only snapshots at previous versions on demand
- load mutable trees at the most recently saved tree
BUG FIXES
- remove memory leaks (#92)
IMPROVEMENTS
- Change tendermint dep to ^v0.22.0 (#91)
BREAKING CHANGES
- getRangeProof and Get[Versioned][Range]WithProof return nil proof/error if tree is empty.
IMPROVEMENTS
- some minor changes: mainly lints, updated parts of documentation, unexported some helpers (#80)
IMPROVEMENTS
- RangeProof.ComputeRootHash() to compute root rather than provide as in Verify(hash)
- RangeProof.Verify*() first require .Verify(root), which memoizes
BREAKING CHANGES
- RangeProof.VerifyItem doesn't require an index.
- Only return values in range when getting proof.
- Return keys as well.
BUG FIXES
- traversal bugs in traverseRange.
- Swap
tmlibs
fortendermint/libs
- Remove
sha256truncated
in favour oftendermint/crypto/tmhash
- same hash function but technically a breaking change to the API, though unlikely to effect anyone.
NOTE this means IAVL is now dependent on Tendermint Core for the libs (since it
makes heavy use of the db
package). Ideally, that dependency would be
abstracted away, and/or this repo will be merged into the Cosmos-SDK, which is
currently is primary consumer. Once it achieves greater stability, we could
consider breaking it out into it's own repo again.
July 1st, 2018
BUG FIXES
- fix bug in iterator going outside its range
BREAKING CHANGES
- Nodes are encoded using proto3/amino style integers and byte slices (ie. varints and varint prefixed byte slices)
- Unified RangeProof
- Proofs are encoded using Amino
- Hash function changed from RIPEMD160 to the first 20 bytes of SHA256 output
BREAKING CHANGES
- LoadVersion and Load return the loaded version number
- NOTE: this behaviour was lost previously and we failed to document in changelog, but now it's back :)
IMPROVEMENT
- Remove spurious print statement from LoadVersion
BREAKING CHANGES
- NewTree order of arguments swapped
- int -> int64, uint64 -> int64
- NewNode takes a version
- Node serialization format changed so version is written right after size
- SaveVersion takes no args (auto increments)
- tree.Get -> tree.Get64
- nodeDB.SaveBranch does not take a callback
- orphaningTree.SaveVersion -> SaveAs
- proofInnerNode includes Version
- ReadKeyXxxProof consolidated into ReadKeyProof
- KeyAbsentProof doesn't include Version
- KeyRangeProof.Version -> Versions
FEATURES
- Implement chunking algorithm to serialize entire tree
First versioned release! (Originally accidentally released as v0.2.0)