Smaller, faster: NSD's refactored RDATA storage and compile time memory reduction options
On the 4th of December, NSD 4.14.0 was released with refactored RDATA storage, reducing the memory footprint of NSD. In this post we'll show the effect of this refactoring, what sort of zones benefit the most from it, and also show that the effect is further enlarged when combined with the compile time memory reducing options to configure: --enable-packed and --disable-radix-tree. As a bonus, the new NSD also reads and writes zones somewhat faster.
Addendum with the NSD 4.14.1 release
This blog post was initially meant to be released at the end of December just after the NSD 4.14.0 release, however just after the release, we received a report, saying that the new release was actually consuming more memory than before instead of less! At least in their setup.
The setup in question involved serving specific kind of zones, with a relatively small number of RRsets, but with a very large number of Resource Records (RRs) per set (thousands). NSD would "grow" those RRsets by adding each RR individually to it. This was done by allocating space to contain all the existing RRs in the set plus the additional one, and then de-allocating the space previously used for the set. The de-allocated space would be put in a recycle bin, to be reused with another request for that size. But since most sizes were only temporarily used to "grow" the RRset, those de-allocated spaces would remain in the recycle bin, never to be put to use.
This approach to zones with many-RRs-per-RRsets was already bad in NSD before 4.14.0, but 4.14.0 made it worse, because the data structure for the RRset and the RRs within the set are packed together, resulting in even more uniquely sized memory allocations (which are less likely to be re-used).
NSD release 4.14.1 has this issue resolved, by "growing" the RRsets by groups of RRs in batches instead of one-by-one. The memory reductions for these kind of zones are actually quite spectacular. The memory usage with the fix has been reported by the affected user to be almost one 6th, of what it used to be before the 4.14.0 release.
Refactored RDATA storage
When developing NSD we usually opt for speed over memory usage whenever we have the choice, but this time we saw a way to reduce memory usage without sacrificing speed by refactoring the way resource record (RR) data (RDATA) is stored.
Before version 4.14.0, RDATA was stored in NSD internally as a list of pointers to all the fields making up the RDATA. When writing responses, NSD would iterate over the fields to restore the original RDATA and to include it in the response. However, for most RR types, authoritative name servers don't have any usage for the values of those RDATA fields! So NSD was doing a lot of administration for the structure of RDATA, at the expense of memory usage and compute cycles, without it being necessary for serving responses. Only when writing out zone files, the fields need to be addresses individually, because they all have their own presentation format.
From version 4.14.0, NSD has a more lazy approach, and no longer stores each field individually for most RR types, but as an opaque binary blob of RDATA instead. This saves the space needed for the pointers to the fields, as well space that is lost by alignment of the allocated memory for the fields on the 64bit boundary, as well as the compute cycles needed to identify the RDATA fields.
Some zones benefit, some less so
The new way of storing RDATA works well "for most RR types", but better for some than for others. For example, domain name fields that may be compressed in responses are still stored by reference to a structural representation of the name, so NSD can do compression efficiently. Also, the relative return on memory usage will be largest with RR types that have many fields, like for example NSEC3 and RRSIG that both have 8 RDATA fields. Zones that benefit most from the new way of to store RDATA are zones with lots of these kind of RR types.
The .nl zone is such a zone. It has a relatively large zone (more than 6 million delegations) with a relatively large proportion of secure delegations (more than 62%) and it is signed with NSEC3 opt-in, so there is an NSEC3 record for every name. At NLnet Labs, we historically have a special relationship with SIDN (the registry for the .nl domain) and we have an agreement with them that we can use the .nl zone for research and improving our software.
Reduced memory requirements
Figure 1 (above) shows the effect of the new RDATA storage approach on the .nl zone. The first two columns show that NSD needs 14.9% less memory for the zone. The other columns show how much less memory is needed, when combined with the compile time memory reducing options to configure: --enable-packed and --disable-radix-tree, and in the last column those two options combined.
The --enable-packed option to configure reduces memory by dropping the requirement that all structure members need to be aligned on the (typical 4 byte) memory alignment boundary. It saves memory usage by leaving out the gaps between struct members. Not all CPU architectures support unaligned memory access and it can have a performance penalty on others. In reality, architectures for which it is not supported are rare and in practice we have only observed performance improvement with the --enable-packed option (maybe because related data is more likely to be together in the CPU cache). However, we must consider ALL supported architectures, and therefore the option is disabled by default.
The relative memory reduction of the new RDATA storage approach is larger when combined with the --enable-packed option to configure! The additional reduction from our new approach is then 16.2% on top of the 14.2% reduction that the --enable-packed option has on the .nl zone.
The disable-radix-tree option uses the red-black tree data structure (the default data structure in NSD version 3) for storing domain-names instead of the current default radix tree data structure. The red-black tree uses less memory, but at the expense of performance. However, for large zones this may still be the most practical. For example with the .com zone, for which the memory reduction is show in Figure 2. And although .com is not a good fit for the new RDATA storage approach (with relatively few secure delegations and NSEC3 opt-out), thanks to the new approach, combining all memory reducing options will bring the memory needed to serve .com from NSD conveniently well below the 64 Gigabyte mark!
| zone | reduction | packed | red-black | packed & red-black |
|---|---|---|---|---|
| lol | 18.3% | 33.4% | 41.4% | 51.0% |
| se | 17.7% | 28.1% | 31.8% | 39.5% |
| nl | 14.9% | 30.4% | 46.5% | 55.2% |
| net | 2.6% | 19.6% | 32.9% | 44.0% |
| org | 2.6% | 19.4% | 33.1% | 43.9% |
| com | 2.4% | 19.3% | 31.3% | 42.6% |
we have been evaluating memory reduction with the new RDATA storage approach of NSD 4.14.0 with 6 zones which all have their own specific properties:
- .com - large NSEC3 opt-out signed zone with 4.2% secure delegations
- .net and .org - larger NSEC3 opt-out signed zones similar to com with both ±5% secure delegations.
- .nl - larger NSEC3 opt-in signed zone with 62.2% delegations
- .se - somewhat larger NSEC signed zone with 61.3% delegations
- .lol - a small NSEC signed zone with 9.0% secure delegations
Table 1 shows the memory reduction for those zones with the new RDATA storage approach for those zones, without and with the other memory reducing options. .lol benefits most without any additional options. .nl benefits most with all options combined.
Faster zone loading and writing
While doing these measurements, we noticed that writing out and/or printing zones has become faster as well without options, and with the – enabled-packed option: ±18% faster for .nl, 6.7% faster for .net and .org, and 25% faster for .se and .lol.
Zone load times were already faster with just the --enable-packed option, and the new approach adds to that as well. Combined they reduce the load time with 21.7% for .lol, 19.6% for .se, 12.4% for .nl, 7.9% for .com and 3.9% and 4.7% for respectively .org and .net.
So all good news, but the best news for .nl, .se and .lol (and zones with similar properties) and less good (but still good) for .com, .net and .org.