Improve performance when rendering the prefix hierarchy

[jeremystretch]

NetBox version

v2.10.8

Feature type

Change to existing functionality

Proposed functionality

Employ MPTT for constructing the prefix hierarchy. This entails automatically assigning each prefix to its parent (if any) and recalculating the hierarchy. NetBox currently employs MPTT for several models (e.g. nesting regions) but adopting it for prefixes will require the automatic assignment and re-assignment of parents as prefixes are added and removed.

Use case

MPTT allows us to more efficiently model the prefix hierarchy, and obviates the need to make verbose SQL annotations to count parent and child prefixes. However, it further consideration is needed regarding the automatic assignment of parent prefixes.

Database changes

Extend ipam.Prefix to an MPTT-enabled model by adding the parent_id, tree_id, level, lft, and rght fields.

External dependencies

No response

[tyler-8]

What would be the performance impacts, good or bad, (in terms of response-time to load prefix pages) of doing this?

[jeremystretch]

@tyler-8 there would be some degree of performance impact at write time, but it should greatly reduce the amount of time required to render the prefixes list. This proposal is still just a rough idea: further testing is needed to determine its viability.

[tyler-8]

What implications are there for the REST API, if any? I presume new fields as stated in the OP, but if users have code around the existing fields, would their work be impacted?

[jeremystretch]

Status update: I ended up forgoing MPTT or any similar solution, and opted to simply cache the depth and child count of each prefix. It's not a super-elegant solution, but it works well and seems pretty robust. Load times for the full prefix hierarchy have been dramatically reduced. Plus, we can filter by depth and child count now!

I still want to do some more testing, especially around the migration, but I expect this to debut in v2.11.5.

[jeremystretch]

I did a quick benchmark of the #6087 branch against develop using the following parameters:

• 1,049,660 prefixes defined (1,092 of which are IPv6)
• Showing 100 per page
• Utilization column hidden
• DEBUG off

I made five requests for /ipam/prefixes/?per_page=100 and recorded the total load time reported by the browser. Times are below.

v2.11.4	#6087
21.92s	0.92s
21.52s	0.90s
21.65s	0.93s
21.51s	0.90s
21.58s	0.93s

Clearly, some pretty huge gains in performance.

It's worth reiterating that I've hidden the utilization column from the prefixes tables for these tests, since that imposes additional overhead. (All other default columns were retained.) Still, with the utilization column included (though no child IP addresses defined), load times averaged around five seconds with #6087 in place.

Migrating the roughly one million prefixes took about eight minutes on my development machine. A more realistic deployment with perhaps around 100 thousand prefixes should take less than a minute.

$ time ./manage.py migrate
Operations to perform:
  Apply all migrations: admin, auth, circuits, contenttypes, dcim, extras, ipam, secrets, sessions, taggit, tenancy, users, virtualization
Running migrations:
  Applying ipam.0047_prefix_depth_children... OK
  Applying ipam.0048_prefix_populate_depth_children...
Updating 1049660 prefixes...
 OK

real	8m9.779s
user	7m17.770s
sys	0m0.679s

Obviously this is far from a scientific test, though I believe it illustrates the enormity of the performance improvements gained with this work.

[sdktr]

Nice work @jeremystretch ! Will the children be available in the API response as well? Or the other way around: will the parent prefix reference be exposed in the API?

https://demo.netbox.dev/api/ipam/prefixes/?parent=123 ?

https://demo.netbox.dev/api/ipam/prefixes/456/?include_children=true ?

[jeremystretch]

@sdktr this doesn't enforce any explicit relationship between parent and child prefixes. This would actually be infeasible given that we (sometimes) allow duplicate prefixes to coexist.

We could extend the REST API serializers to annotate the depth and child count for each prefix with negligible performance impact, but that would be the extent of the changes (beyond the new filtering ability introduced).