Skip to content

Instantly share code, notes, and snippets.

@jathanism

jathanism/spike_dynamic_groups_of_groups.md Secret

Last active May 18, 2022 01:38
Show Gist options
  • Save jathanism/c58397e1d9d5760e8e4089e75c4a3576 to your computer and use it in GitHub Desktop.
Save jathanism/c58397e1d9d5760e8e4089e75c4a3576 to your computer and use it in GitHub Desktop.
Download ZIP
Nautobot Spike: Dynamic Groups of Groups
Raw
spike_dynamic_groups_of_groups.md

Nautobot Spike: Dynamic Groups of Groups

User Story

As ... Nelly - Network Engineer I want ... to be able to create multiple "rules" to a dynamic group. So that ... I can create a composable dynamic group combining different sub-queries that would either be combined or excluded in the resulting member lis. I know this is done when... - I can specify rule(s) that return their own list of group members - I can combine multiple rules that would return a combined list of members based on their membership in either sub-rule - I can combine multiple rules that would return a combined list of members based on their membership in both sub-rule - I can combine multiple rules that would return a filtered list of members based on their presence in one sub-rule but not another This spike will propose a design and identify work needed to complete this feature.

Notes

Filtering Design

  • Groups of groups will be filtered from left-to-right (or ltop-to-bottom depending on how your brain works), using set operations, where:
    • union = combine the results of two filters
    • intersection = return the shared results of two filters
    • difference = filter out the results of the right-hand (next) filter
  • A DynamicGroup can have a single filter or can have any number of child groups that are each DynamicGroup
  • When a group is added as a child to another group
    • Its own filter will be used as the base queryset for its children
    • Ordering (weight) and operation (union, intersection, or difference) must be declared
  • Child groups will be processed in order by weight, followed by name
    • Therefore child groups with the same weight will be processed in order by name
  • Filtering queries in passes iterating over all groups with set operations
    • Can’t filter/exclude after an intersection/union/diff
      • Union/intersection/difference methods are convenient because they take a QS as an argument vs. a filter/query expression (such as a Q object)
    • However, it becomes impossible to mix filter/exclude with union/intersection/difference. One or the other strategy must be used.
    • See:
    In [130]: qs = dg_site_a_active.process_group_filters()
    
    In [131]: qs.distinct()
    ...
    NotSupportedError: Calling QuerySet.distinct() after intersection() is not supported.
- IMO using the set operations is more desirable as it is cleaner but CAN NOT be further filtered.
    - If filtering the resultant QuerySet is a requirement, we could wrap it in something like `[django-delayed-union](https://github.com/roverdotcom/django-delayed-union)` but this library would require contribution to do what we want
    - Or we’ll have to rethink the entire strategy and make creative use of `filter/exclude` (See: https://github.com/jathanism/nsot/blob/release-v2.0.0/nsot/models/resource.py#L108-L119 for an example of how we might do that)
    - There is an existing project that appears to actually deeply merge correctly called `[deepmerge](https://pypi.org/project/deepmerge/)`
    In [36]: import deepmerge
    
    In [37]: filter_params = {}
    
    In [38]: for grp in dg.groups.all():
        ...:    deepmerge.always_merger.merge(filter_params, grp.filter)
        ...:
    
    In [39]: filter_params
    Out[39]: {'status': ['active'], 'site': ['ams01', 'ang01']}
    
    In [40]: fsq = dg_site_a_active.filterset_class(filter_params, Device.objects.all())
    
    In [41]: fsq.qs.count()
    Out[41]: 17

DynamicGroup changes

  • A new m2m for DynamicGroup.groups will need to be created with an intermediate model
    • DynamicGroup filter logic will need to specify set operation logic and order/weight
    • See DynamicGroupMembership design for adding extra fields on this relationship
  • Filter validation will need to enumerate all filters in all nested groups
    • But each group can validate itself at save time, so an already-saved group is implied to be valid
    • dg.groups.all()
  • Filter form generation will need to aggregate all fields reduced down
    • This has not been addressed in prototyping
    • Not quite sure how to reduce down multiple nested dictionaries for passing to a filterset instance at this time other than perhaps a dictionary merge (See: nautobot.utilities.utils.deepmerge, except that in basic testing this DID NOT work as it clobbers existing values)
  • The UI edit form will need to implement a formset factory for the DynamicGroup objects similar to CustomField + CustomFieldChoice in the UI
    • The DynamicGroupEditView.post() method will need to be overloaded similary to CustomFieldEditView.post()
  • Groups must default to including all members so that a baseline group with child groups will always start with itself as the “left-hand-most” (top-most) filter used.
    • In other words the base DynamicGroup.filter is always used to filter the initial queryset used for any further filtering of that group
    • So in many cases if a group has child groups, it will be common to see a group with an empty filter ({})
  • All objects from all member groups shall be flattened as DynamicGroup.members
    • Since the base queryset provided by DynamicGroup.get_queryset() will be filtered by the parent group’s DynamicGroup.filter value, there will need to be another way to get the aggregate filterset OR the base filterset
      • Perhaps get_base_queryset() should return self.content_type.model_class().objects.all() unfiltered
      • And get_queryset() will be changed to return either a filterset filtered by self.filter or the processed filter from all child groups
    • , but maybe not
    • Might also be worth introducing some “tree” style terminology here (seeing as some delineation between “base” and “child” members might also be necessary) aka
      • parent (my parent group)
      • children (my child groups)
      • descendants (all children of my child groups)
      • siblings (same parent group)
      • ancestors (all parents of my parent groups)
      • is_leaf (has no child groups)

DynamicGroupMembership design

Intermediate model for constraining relationship between DeviceGroup ← m2m → DeviceGroup

  • Should include group, parent_group, operator , and weight to designate union/intersection/difference) relationship and order in which groups are processed
    • Operator and Weight SHOULD be required fields so that a value for them is required at creation time so as to prevent creating set operations that make no sense or just don’t work properly
  • There should be an enum for the operator choices (e.g. DynamicGroupOperatorChoices) as choices for the operator field
  • Uniqueness should be for group/parent_group as we’d only want a unique group per parent_group
  • For m2m-pre-validation, signal handler must be connected to m2m_changed and the pre_add event.
    • This is to block creation of DynamicGroupMembership objects if validation fails.
    • Needs to validate that DG and child content_type must match
  • There MUST NOT be API/UI to expose direct management of this object
    • Management of add/remove filters from groups should be done thru DynamicGroup UI
    • Care will need to be taken to assert that operator and weight are used to achieve desirable filter groups
    • Perhaps some kind of live “here’s what your filter returns” functionality in the UI could be useful?
  • In any case, documentation of this feature explaining set operations, criticality of ordering of filtering with groups, and how to test will be incredibly important

Reversibility

  • Not quite yet possible without evaluating the filtersets
  • The problem is in aggregating nested generation of filtersets
    • Each individual filterset may be easily reversible by enumerating the filters, generating predicates, and providing the values saved on the filter for that group
    • Perhaps using the same set operations that we already know about based on the group membership relationships, we may be able to and/or/not the Q objects together in a similar fashion.
  • For example if we make proper use of lookup expressions on fields such as a field for which it is a multi-choice filter it should be in not exact:
    In [118]: dg2.filter
    Out[19]: {'site': ['ams01']}
    
    In [119]: fs1.filters['site'].lookup_expr = "in"
    
    In [120]: fs1.filters['site'].get_filter_predicate("dg2.filter['site']")
    Out[120]: {'site__slug__in': ['ams01']}
    
    In [124]: Q(**fs1.filters['site'].get_filter_predicate(dg2.filter['site']))
    Out[124]: <Q: (AND: ('site__slug__in', ['ams01']))>
    
    In [125]: Device.objects.filter(Q(**fs1.filters['site'].get_filter_predicate(dg2.fil
         ...: ter['site']))).count()
    Out[125]: 11

Schema/Performance

  • Identify all places where field sets are used for lookup
  • Perform EXPLAIN ANALYZE SELECT queries on those lookups
  • Use https://explain.depesz.com to analyze the queries and identify any places where obvious “index together” indexes should be added to the models

Data Migrations

  • n/a - Since this a new feature and no changes were made to DynamicGroup.filter

Backwards Compatibility

  • n/a - New features

Prototyping

Control

Control is just a Q object used to filter a queryset.

  • where site in (``"``ams01``"``, "``ang01``"``) and status=``"``active``"
  • 389 total devices
    In [29]: query = (Q(site__slug="ams01") | Q(site__slug="ang01")) & Q(status__slug="active")
    
    In [30]: Device.objects.filter(query).count()
    Out[30]: 17
    
    In [35]: Device.objects.count()
    Out[35]: 389

Basic Groups

Basic groups are just a single group with a filter designed with no child groups.

devices-ang01

  • where site=``"``ang01``"
    In [19]: dg_ang01
    Out[19]: <DynamicGroup: devices-ang01>
    
    In [20]: dg_ang01.filter
    Out[20]: {'site': ['ang01']}
    
    In [32]: dg_ang01.process_group_filters().count()
    Processing group devices-ang01...
    Out[32]: 7

devices-ams01

  • where site=``"``ams01``"
    In [21]: dg_ams01
    Out[21]: <DynamicGroup: devices-ams01>
    
    In [22]: dg_ams01.filter
    Out[22]: {'site': ['ams01']}
    
    In [33]: dg_ams01.process_group_filters().count()
    Processing group devices-ams01...
    Out[33]: 11

devices-active Only one device has status=``"``planned``"

  • where status=``"``active``"
    In [27]: dg_active
    Out[27]: <DynamicGroup: devices-active>
    
    In [28]: dg_active.filter
    Out[28]: {'status': ['active']}
    
    In [34]: dg_active.process_group_filters().count()
    Processing group devices-active...
    Out[34]: 388

Single Group with flat group members

This is a flat group that includes three groups, one each for devices by site and one for status, associated by weight to be processed in order.

Doesn’t take advantage of any potential parenthetical grouping

devices-group

    In [43]: dg
    Out[43]: <DynamicGroup: devices-group>
    
    In [44]: dg.dynamic_group_memberships.all()
    Out[44]: <RestrictedQuerySet [<DynamicGroupMembership: devices-ams01: intersection (10)>, <DynamicGroupMembership: devices-ang01: union (20)>, <DynamicGroupMembership: devices-active: intersection (30)>]>
    
    In [45]: dg.process_group_filters().count()
    Processing group devices-group...
    Processing group devices-ams01...
    devices-ams01 -> {'site': ['ams01']} -> intersection
    Processing group devices-ang01...
    devices-ang01 -> {'site': ['ang01']} -> union
    Processing group devices-active...
    devices-active -> {'status': ['active']} -> intersection
    Out[45]: 17

Group with nested child groups

devices-site-a This group nests three flat groups each w/ their own basic filter. Observe that since it’s only filtering by site and not status, there are 18 (not 17).

  • group=devices-ams01, operator=intersection, weight=10
  • group=devices-ang01, operator=union, weight=20
  • group=devices-active, operator=intersection, weight=30
    In [48]: dg_site_a
    Out[48]: <DynamicGroup: devices-site-a>
    
    In [49]: dg_site_a.dynamic_group_memberships.all()
    Out[49]: <RestrictedQuerySet [<DynamicGroupMembership: devices-ang01: intersection (10)>, <DynamicGroupMembership: devices-ams01: union (20)>]>
    
    In [50]: dg_site_a.process_group_filters().count()
    Processing group devices-site-a...
    Processing group devices-ang01...
    devices-ang01 -> {'site': ['ang01']} -> intersection
    Processing group devices-ams01...
    devices-ams01 -> {'site': ['ams01']} -> union
    Out[50]: 18

devices-site-a-active This group nests devices-site-a and devices-active in order

  • First the groups in devices-site-a are processed together using intersection with the base group
  • Second the single filter from devices-active is processed using intersection
    In [95]: dg_site_a_active
    Out[95]: <DynamicGroup: devices-site-a-active>
    
    In [96]: dg_site_a_active.dynamic_group_memberships.all()
    Out[96]: <RestrictedQuerySet [<DynamicGroupMembership: devices-site-a: intersection (10)>, <DynamicGroupMembership: devices-active: intersection (20)>]>
    
    In [98]: dg_site_a_active.process_group_filters().count()
    Processing group devices-site-a-active...
    Processing group devices-site-a...
    Processing group devices-ang01...
    devices-ang01 -> {'site': ['ang01']} -> intersection
    Processing group devices-ams01...
    devices-ams01 -> {'site': ['ams01']} -> union
    devices-site-a -> {} -> intersection
    Processing group devices-active...
    devices-active -> {'status': ['active']} -> intersection
    Out[98]: 17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment