bihash总结

官方https://s3-docs.fd.io/vpp/22.10/developer/corearchitecture/bihash.html

原理分析https://blog.csdn.net/jqh9804/article/details/55100994?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-2-55100994-blog-109624119.pc_relevant_multi_platform_whitelistv3&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-2-55100994-blog-109624119.pc_relevant_multi_platform_whitelistv3&utm_relevant_index=4

Vpp uses bounded-index extensible hashing to solve a variety of exact-match (key, value) lookup problems. Benefits of the current implementation:

• Very high record count scaling, tested to 100,000,000 records.

• Lookup performance degrades gracefully as the number of records increases

• No reader locking required

• Template implementation, it’s easy to support arbitrary (key,value) types

以上介绍了bihash的优点

Initializing a bihash table

Call the init function as shown. As a rough guide, pick a number of buckets which is approximately number_of_expected_records/BIHASH_KVP_PER_PAGE from the relevant template instance header-file. See previous discussion.

The amount of memory selected should easily contain all of the records, with a generous allowance for hash collisions. Bihash memory is allocated separately from the main heap, and won’t cost anything except kernel PTE’s until touched, so it’s OK to be reasonably generous.

For example:

my_main_t *mm = &my_main;
clib_bihash_8_8_t *h;

h = &mm->hash_table;

clib_bihash_init_8_8 (h, "test", (u32) number_of_buckets,
                       (uword) memory_size);

bihash初始化时需要传入buckets大小和memory_size

buckets最优值：你预期存储的记录数除以BIHASH_KVP_PER_PAGE ，BIHASH_KVP_PER_PAGE 是bihash中一个page存储记录的个数，默认是4.假如存储50万记录

500000/4=125000

memory_size：最好就是能存储50万记录，存储解决hash冲突的数据结构，存储buckets，意思是给充足点。bihash  一个记录大小 kv 包含key值和value值。