Advantages:

  • For most lookups, only one memory access required per lookup.
  • The database is smaller by 8 bytes per key after compaction as we don’t store sequence number and value type in the key.

Limitations:

  • Because the file format is hashing based, range scan is very slow
  • Key and value lengths are fixed
  • Does not support Snapshots
  • File must be mmaped
  • The last SST file in the database may have a utilization of only 50% in worst case.

We have plans to reduce some of the limitations in future.

Examples:

or

  1. options.table_factory.reset(NewCuckooTableFactory(
  3.     100 /* max_search_depth */,

The Cuckoo SST file comprises of:

  • Hash table containing key value pairs. Empty buckets are filled using a special key outside the key range in the table.
  • Property Block containing Table properties
  • Metadata and footer.

We filled the db with 100M records in 8 files with key length of 8 bytes and value length of 4 bytes. We chose the default Cuckoo hash parameter: hash_table_ratio=0.9, max_search_depth=100, cuckoo_block_size=5.

Command to create and compact DB:

  1. ./db_bench --disable_seek_compaction=1 --statistics=1 --histogram=1 --cache_size=1048576 --bloom_bits=10 --cache_numshardbits=4 --open_files=500000 --verify_checksum=1 --write_buffer_size=1073741824 --max_write_buffer_number=2 --level0_slowdown_writes_trigger=16 --level0_stop_writes_trigger=24 --delete_obsolete_files_period_micros=300000000 --max_grandparent_overlap_factor=10 --stats_per_interval=1 --stats_interval=10000000 --compression_type=none --compression_ratio=1 --memtablerep=vector --sync=0 --disable_data_sync=1 --key_size=8 --value_size=4 --num_levels=7 --threads=1 --mmap_read=1 --mmap_write=0 --max_bytes_for_level_base=4294967296 --target_file_size_base=201327616 --level0_file_num_compaction_trigger=10 --max_background_compactions=20 --use_existing_db=0 --disable_wal=1  --db=/mnt/tmp/cuckoo/2M100 --use_cuckoo_table=1 --use_uint64_comparator --benchmarks=filluniquerandom,compact --cuckoo_hash_ratio=0.9 --num=100000000

Random Read:

  1. multireadrandom :       0.278 micros/op 3601345 ops/sec; (1080449950 of 1080449950 found)

Note that the MultiGet experiment contains an implementation of MultiGet() in readonly mode which is not yet checked in. The performance is likely to improve further as we submit more optimizations that we have identified.