]> git.ipfire.org Git - thirdparty/bind9.git/commit
dns/rbt.c: Implement incremental hash table resizing
authorOndřej Surý <ondrej@sury.org>
Thu, 7 Oct 2021 16:41:02 +0000 (18:41 +0200)
committerOndřej Surý <ondrej@sury.org>
Tue, 12 Oct 2021 13:01:53 +0000 (15:01 +0200)
commit8c819ec3667e2cc60bb4943f814ffcc3abf559d2
tree95875d6a8bef5c64cdc5ada635762b1680c4c15d
parent0590d71977d303730e3c981074f4ce3c42f3cbe7
dns/rbt.c: Implement incremental hash table resizing

Originally, the hash table used in RBT database would be resized when it
reached certain number of elements (defined by overcommit).  This was
causing resolution brownouts for busy resolvers, because the rehashing
could take several seconds to complete.  This was mitigated by
pre-allocating the hash table in the RBT database used for caching to be
large-enough as determined by max-cache-size.  The downside of this
solution was that the pre-allocated hash table could take a significant
chunk of the memory even when the resolver cache would be otherwise
empty because the default value for max-cache-size is 90% of available
memory.

Implement incremental resizing[1] to perform the rehashing gradually:

 1. During the resize, allocate the new hash table, but keep the old
    table unchanged.
 2. In each lookup or delete operation, check both tables.
 3. Perform insertion operations only in the new table.
 4. At each insertion also move r elements from the old table to the new
    table.
 5. When all elements are removed from the old table, deallocate it.

To ensure that the old table is completely copied over before the new
table itself needs to be enlarged, it is necessary to increase the
size of the table by a factor of at least (r + 1)/r during resizing.

In our implementation r is equal to 1.

The downside of this approach is that the old table and the new table
could stay in memory for longer when there are no new insertions into
the hash table for prolonged periods of time as the incremental
rehashing happens only during the insertions.

The upside of this approach is that it's no longer necessary to
pre-allocate large hash table, because the RBT hash table rehashing
doesn't cause resolution brownouts anymore and thus we can use the
memory as needed.

1. https://en.m.wikipedia.org/wiki/Hash_table#Dynamic_resizing
bin/tests/system/dyndb/driver/db.c
lib/dns/cache.c
lib/dns/db.c
lib/dns/dnsrps.c
lib/dns/include/dns/db.h
lib/dns/include/dns/rbt.h
lib/dns/rbt.c
lib/dns/rbtdb.c
lib/dns/sdb.c
lib/dns/sdlz.c