3 releases

0.1.16-alpha.0 Apr 1, 2023
0.1.12-alpha.0 Jan 19, 2023
0.1.10-alpha.0 Jan 18, 2023

#10 in #data-block

Download history 139/week @ 2024-05-26 111/week @ 2024-06-02 76/week @ 2024-06-09 174/week @ 2024-06-16 127/week @ 2024-06-23 33/week @ 2024-06-30 104/week @ 2024-07-07 160/week @ 2024-07-14 132/week @ 2024-07-21 111/week @ 2024-07-28 113/week @ 2024-08-04 128/week @ 2024-08-11 97/week @ 2024-08-18 101/week @ 2024-08-25 100/week @ 2024-09-01 99/week @ 2024-09-08

430 downloads per month
Used in 66 crates (via bitcoin-leveldb)

MIT license

795KB
2K SLoC

bitcoinleveldb-duplex Rust Crate Description

duplex

The duplex module contains the implementation of a Two-Level Iterator. This is used to iterate over a sorted key-value map stored in LevelDB.

BlockFunction

The BlockFunction is a trait that defines the interface of a function that is used to compress a block of key-value pairs.

TwoLevelIterator

The TwoLevelIterator is a struct that provides an implementation of a two-level iterator over a sorted key-value map stored in LevelDB.

init_data_block

The init_data_block function is used to initialize a new data block.

key

The key method is used to return the current key of the iterator.

next

The next method is used to advance the iterator to the next key-value pair.

prev

The prev method is used to move the iterator to the previous key-value pair.

save_error

The save_error function is used to save an error message in the iterator's status.

seek

The seek method is used to move the iterator to the specified key.

seek_to_first

The seek_to_first method is used to move the iterator to the first key-value pair.

seek_to_last

The seek_to_last method is used to move the iterator to the last key-value pair.

set_data_iterator

The set_data_iterator method is used to set the data iterator.

skip_empty_data_blocks_backward

The skip_empty_data_blocks_backward method is used to skip empty data blocks while moving the iterator backward.

skip_empty_data_blocks_forward

The skip_empty_data_blocks_forward method is used to skip empty data blocks while moving the iterator forward.

status

The status method is used to return the current status of the iterator.

valid

The valid method is used to check whether the iterator is valid or not.

value

The value method is used to return the current value of the iterator.

Notice: This crate is part of a direct translation from C++ to Rust of the bitcoin core. As such, some of the function bodies may still be in the process of translation. It is important to note that this system will become testable once the translation process is complete.

14> what is a two level iterator in the context of leveldb?

In LevelDB, a two-level iterator is an iterator that uses two levels of iteration to allow for efficient traversal of key-value pairs in a database.

The first level of iteration is a block iterator, which iterates over blocks of key-value pairs stored in SST files (Sorted String Table files). The second level of iteration is a data block iterator, which iterates over the key-value pairs within a given block.

By using a two-level iterator, LevelDB can avoid the need to read an entire SST file into memory at once. Instead, it reads blocks of key-value pairs into memory as needed and iterates over them using the data block iterator.

The BlockFunction token in the bitcoinleveldb-duplex crate is a callback function used by the two-level iterator to load the next block of key-value pairs from the database. The init_data_block, skip_empty_data_blocks_backward, skip_empty_data_blocks_forward, set_data_iterator, and save_error tokens are all methods used by the two-level iterator to manipulate the data block iterator and navigate between blocks of key-value pairs. The status, valid, key, value, next, prev, seek, seek_to_first, and seek_to_last tokens are methods used to traverse the key-value pairs within a block.

15> thanks -- what are some things we should know when using one?

Here are some things to keep in mind when using a two-level iterator in LevelDB:

  1. Two-level iterators are useful when you need to iterate over a large amount of data that does not fit in memory. They allow you to keep the data on disk and read it as needed during iteration.

  2. Two-level iterators consist of a top-level iterator that iterates over keys in sorted order and a bottom-level iterator that iterates over values associated with each key.

  3. The top-level iterator is implemented using an internal LevelDB iterator, while the bottom-level iterators are implemented using block-based iterators.

  4. When creating a two-level iterator, you must specify a block size. This determines the maximum size of the data blocks that will be read from disk during iteration. A smaller block size will result in more I/O but may be necessary if you have limited memory.

  5. Two-level iterators are generally slower than in-memory iterators due to the I/O required to read data from disk. If you can fit your data in memory, you should use an in-memory iterator instead.

  6. Two-level iterators can be used to iterate over a subset of the data by specifying a range of keys to iterate over.

  7. When iterating over a large amount of data, it's important to keep track of your progress and handle errors gracefully. You may want to periodically report progress or use a progress bar to let the user know how much work has been done.

  8. If you need to modify the database while iterating over it, you should use a snapshot to ensure that the data being iterated over remains consistent.

  9. Two-level iterators are generally thread-safe, but you should still ensure that you are not modifying the iterator or the underlying database from multiple threads simultaneously.

  10. Finally, it's important to thoroughly test your code when using two-level iterators. Since they involve more I/O and have more potential failure points than in-memory iterators, you may encounter unexpected behavior or performance issues.

Dependencies

~90MB
~847K SLoC