[GH-ISSUE #2984] Refactor recursor to eliminate recursive calls #1104

New issue

Open

opened 2026-03-16 01:36:57 +03:00 by kerem · 0 comments

kerem commented

2026-03-16 01:36:57 +03:00

Owner

Originally created by @divergentdave on GitHub (May 9, 2025).
Original GitHub issue: https://github.com/hickory-dns/hickory-dns/issues/2984

Refactoring the recursor to replace recursion on the native stack with iterative algorithms and custom data structures would be desirable because it could reduce complexity and open the door for further improvements.

RFC 9156 recommends a resolver algorithm that amortizes how many labels from the QNAME are added to each successive iterative query, based on the number of labels in the QNAME and configured limits on iterative queries per recursive query. This is not practical to implement via recursive calls. We currently add one label per recursive call and iterative query, which is simple but overly resource intensive.

Handling of concurrent requests in the recursor is limited. Currently we use FuturesUnordered in one place when looking up name server addresses, and wait for all such lookups to complete before proceeding. (the parallel_conn_loop() in the resolver crate is also used to race queries to multiple name servers in a pool) If we moved away from recursive calls to drive iterative resolution, it would be possible to interleave requests to the first name servers we get IPs for concurrently with slower resolutions of other name server IP addresses for the same zone, for example.

Originally created by @divergentdave on GitHub (May 9, 2025). Original GitHub issue: https://github.com/hickory-dns/hickory-dns/issues/2984 Refactoring the recursor to replace recursion on the native stack with iterative algorithms and custom data structures would be desirable because it could reduce complexity and open the door for further improvements. RFC 9156 recommends a resolver algorithm that amortizes how many labels from the QNAME are added to each successive iterative query, based on the number of labels in the QNAME and configured limits on iterative queries per recursive query. This is not practical to implement via recursive calls. We currently add one label per recursive call and iterative query, which is simple but overly resource intensive. Handling of concurrent requests in the recursor is limited. Currently we use `FuturesUnordered` in one place when looking up name server addresses, and wait for all such lookups to complete before proceeding. (the `parallel_conn_loop()` in the resolver crate is also used to race queries to multiple name servers in a pool) If we moved away from recursive calls to drive iterative resolution, it would be possible to interleave requests to the first name servers we get IPs for concurrently with slower resolutions of other name server IP addresses for the same zone, for example.