0
\$\begingroup\$

BUSINESS CASE

For users of my application I need to manage a granular list of grants. I'm using an aws dynamodb backend with lite Single Table Design (STD) strategies. A common syntax for STD keys and sort keys is:

'{type_1}#{type_1_instance_id}#{type_2}#{type_2_instance_id}#{type_3}#{type_3_instance_id}'

I'm creating primary keys (pk) based on my user_id and sort keys (sk) based on the resource grant. The sort keys look like this:

'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa#LEASE#d4406bf8-9694-49db-b5b5-fac71804aea2#UNIT#c186da4a-1192-465c-8a28-1522070c0e99'

These grants are heirarchical so anyone who access to:

'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa'

Also has access to:

'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa#LEASE#d4406bf8-9694-49db-b5b5-fac71804aea2'
'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa#LEASE#d4406bf8-9694-49db-b5b5-fac71804aea2#UNIT#c186da4a-1192-465c-8a28-1522070c0e99'

But someone with access to:

'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa#LEASE#d4406bf8-9694-49db-b5b5-fac71804aea2'

Only has access to:

'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa#LEASE#d4406bf8-9694-49db-b5b5-fac71804aea2'
'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa#LEASE#d4406bf8-9694-49db-b5b5-fac71804aea2#UNIT#c186da4a-1192-465c-8a28-1522070c0e99'

Not to:

'COMPANY#486aa43a-237f-4947-9d51-4e2a6638effa'

To reiterate it you can have levels of access at either a COMPANY, a LEASE, or a UNIT. COMPANY access gives you access to all related records. LEASE access gives access to all related UNIT records for that lease, but no COMPANY (parent relation) records.

The Problem

This setup works brilliantly for quickly asking the db for a grant and determining if the user has access. However, the downside is I need to make an algorithm to deconflict the grants, and keep the grant list as small as possible. Meaning any grant that exists for LEASE or UNIT where the grant already exists for COMPANY needs to be removed. Any grant that exists for UNIT where the grant for LEASE already exists needs to be removed.

Setup

using python

import uuid
n = 1000
ids = [uuid.uuid4() for i in range(n)]

grants = []
i = 0
while i + 6 <= n:
    grants += [
        f"COMPANY#{ids[i]}",
        f"COMPANY#{ids[i]}",
        f"COMPANY#{ids[i]}#LEASE#{ids[i+1]}",
        f"COMPANY#{ids[i]}#LEASE#{ids[i+1]}#UNIT#{ids[i+2]}",
        f"COMPANY#{ids[i]}#LEASE#{ids[i+3]}",
        f"COMPANY#{ids[i]}#LEASE#{ids[i+3]}#UNIT#{ids[i+4]}",
        f"COMPANY#{ids[i]}#LEASE#{ids[i+5]}#UNIT#{ids[i+6]}"
    ]
    i += 6

The Algorithm

def make_filter(comp_val):
    return lambda x: not (x.startswith(comp_val) and x != comp_val)

def split_sort_grants(grants):
    company = []
    lease = []
    unit = []
    for g in grants:
        x = len(g.split('#'))
        if x == 2:
            company.append(g)
        elif x == 4:
            lease.append(g)
        else:
            unit.append(g)
    return sorted(company), sorted(lease), sorted(unit)
    
def deconflict_grants(grants):
    # make sure of no duplicates. In production the db should gurantee this.
    # s = list(set(grants))
    
    # split and sort
    # O_1 = 2n
    companies, leases, units = split_sort_grants(grants)
    
    # create output grant list:
    len_company = len(companies)
    
    # remove lease grants that have existing company grants
    #O_2 = (n - len(company) - len(units))**(n - len(company))
    #O_3 = (n - len(company) - len(leases))**(n - len(company))
    while i < len_company:
        leases = list(filter(make_filter(companies[i]), leases))
        units = list(filter(make_filter(companies[i]), units))
        i += 1

    # remove unit grants that have existing lease grants
    # O = (n - (len(company) - len(leases) - x)**(n - (len(company) - len(units) - y)
    # where:
    #   x is the number of conflicted units removed in the step above
    #   y is the number of conflicted leases removed in the step above
    i = 0
    len_leases = len(leases)
    while i < len_leases:
        units = list(filter(make_filter(leases[i]), units))
        i += 1
    
    return companies + leases + units


result = deconflict_grants(grants)

# total O
# O = 2n + (n - len(company) - len(units))**(n - len(company)) + \
#        (n - len(company) - len(leases))**(n - len(company))  + \
#        (n - (len(company) - len(leases) - x)**(n - (len(company) - len(units) - y)
#
# This should appoxamate something like:
# O = 2n + (n - x)**2-y
# where:
#    x - represents some portion of conflicted leases
#    y - is len(units) / len(grants)

It seems like there should be some sort of bit masking solution here that results in an n*x somewhere, but I haven't fount it yet. Many thanks to anyone who can help me improve this.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This really seems like a job for the database and not the application. You should be able to query for this and use proper indices db-side. "Single table" or no, the grants being pasted together like that isn't helping. Can't they be separate columns? \$\endgroup\$
    – Reinderien
    Commented Jun 6 at 21:57
  • \$\begingroup\$ @Reinderien - they can be separate columns, but dynamodb (and other NOSQL) solutions don't make many server side queries available. There's no joining. An only filtering on the sk, or indices. Having an sk with format type#id#type#id is the norm for dynamodb \$\endgroup\$ Commented Jun 6 at 22:36

1 Answer 1

1
\$\begingroup\$

If your grants list is sorted, you can run through it, deleting those that has the previous node as a prefix. That would require a linear number of comparisons.

Of course sorting is O(n log n) string comparisons.

prev = "neverused"
result = []
for g in sorted(grants):
    if not g.startswith(prev):
        result.append(g)
        prev = g
\$\endgroup\$
1
  • \$\begingroup\$ This is a good thought. Potential for O(n log n + n). Off the bat, seems like it will beat my original idea of chopping the list into 3. Will test this out. \$\endgroup\$ Commented Jun 13 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.