Performant Eval on CAC config

[pratikmishra356]

Problem Statement : Improve CAC eval latency , currently it is linearly dependent on the number of contexts , goal is to come up with a representation of storing cac config file , so that latency for eval can be fast

Representation of contexts (Assumption is that context will have only and and == operators)

Current toml representation

[context."$clientIs == 'cId1' && $platform == 'android' && $scope == 'release'"]
[context."$clientIs == 'cId1' && $platform == 'ios' && $scope == 'cug'"]
[context."$clientIs == 'cId1' && $scope== 'release'"]
[context."$platform == 'web'"]

Tree Structure representation

        clientId
         /     \    \
      cid1     cid2   NA
        |         |       \
     platform   platform  platform
      /   \      /   \       \
 android  ios  android  ios     web
    |       |     |       |      \
   scope   scope   scope   scope   override_val
    |        |      |       |
release:   cug   release:  cug
overrides_val overrides_val

Eval Approach : We can think of dimension with the highest weightage as root node (in this case its clientId), we will then traverse in tree according to the object value provided for eval, we will have to traverse along two branches one with the given value and other along NA branch ( NA means context which does not have that dimension in condition). In each dimension object , key will the context's value like cId1, android and then again nested json structure . Each path to the override_val (or leaf node ) will represent a context

Problem: In this approach issue is that for a particular cac_config file , we should have knowledge of its dimensions and their weightage, as during tree traversal we should know in which order we have to patch the overrides,
then for each config version we should have versioning of dimension details also,

Solution: solution to the above problem is that instead of storing override_val , we could store the context_id itself and get all the contexts_ids which matches , then order them based on context's weightage and then patch

[pratikmishra356]

Toml representation

[context."$clientId == 'cId1' && $platform == 'ios' && $scope == 'release'"] -> context_id1
[context."$clientId == 'cId1' && $platform == 'android'"] -> context_id2
[context."$clientId == 'cId2' && $platform == 'ios' && $scope== 'release'"] -> context_id3
[context."$clientId == 'cId2' && $platform == 'android' && $scope== 'cug'"] -> context_id4
[$platform == 'ios'] -> context_id5

Second Type of Context Representation

clientId ->
       cId1 -> [context_id1, context_id2]
       cid2 -> [context_id3, context_id4]
       ....
platform -> 
        android -> [ context_id2, context_id4]
        ios ->  [ context_id1, context_id3, context_id5]
scope -> 
       release -> [ context_id1, context_id3]
       cug -> [ context_id4 ]

Eval Approach -> Based on the given object value for eval , for each dimension value given we will find the list of context_ids,
we will then merge the context_ids list and filter the unique Ids, next apply eval on those filtered contexts with the given object value and then patch the overrides of context's which satisfies

Problem -> Issue in this approach is that for such dimensions whose value is of enum , like lets say platform which has value ios, android, web, so it is possible that number of contexts containing platform can be large and we have to run eval on large number of context's list

[Datron]

@pratikmishra356 rather than a tree, a graph representation seems more efficient? For example:

        clientId
         /     \    \
      cid1     cid2   NA
        |         |       \
     platform   platform  platform
      /   \      /   \       \
 android  ios  android  ios     web
    |       |     |       |      \
   scope   scope   scope   scope   override_val
    |        |      |       |
release:   cug   release:  cug
overrides_val overrides_val

Given this structure, we have mixed the dimensions and their values in traversal, it would be better to make it something like this:

[Datron]

While traversing each rectangle node we apply any overrides attached to it