[Design Discussion] Indexed User Attributes

[ThumulaPerera]

Related Feature Issue

#511

Problem Summary

Currently, all user attributes are stored as JSON in the ATTRIBUTES column. Identifying a user requires:

• Sequential scan of the USER table
• JSON parsing on every row
  This will lead to performance issues down the line when handling large number of users.

Proposed Approach

Implement global attribute indexing for a subset of user attributes, which are frequently used for user identification.

• Maintain a global (server-wide) list of attributes which would be indexed
• Create a separate table USER_INDEXED_ATTRIBUTES with 3 columns USER_ID, ATTRIBUTE_NAME and ATTRIBUTE_VALUE to store indexed attributes.
• Update USER and USER_INDEXED_ATTRIBUTES atomically during user create, update, delete operations.
• Handle user identification according to following cases.
  • All identifier attributes in the request are indexed -> Check only in the USER_INDEXED_ATTRIBUTES table (using JOINs when multiple identifier attributes are there).
  • Proper subset of identifier attributes in the request are indexed -> Check in USER and USER_INDEXED_ATTRIBUTES table using JOINs
  • None of the identifier attributes in the request are indexed -> Check only in USER table.

Technical Questions for Discussion

1. I have done a quick PoC and a local perf test and obtained following numbers for authentication (without getting an assertion). Given these numbers we need to decide whether this approach is worth pursuing.

   Single-Attribute Search

   Approach	Avg (ms)	95th	99th	Error %
   Non-indexed	44	94	557	0.00%
   Indexed	13	16	163	0.00%

   • On average, Indexed attribute improves performance by ~250%

   Two-Attribute Search

   Scenario	Avg (ms)	95th	99th	Error %
   Both non-indexed	45	98	648	0.02%
   One indexed (50% selectivity)	79	320	936	0.04%
   One indexed (10% selectivity)	46	80	738	0.04%
   One indexed (1% selectivity)	23	35	483	0.03%

   • On average, having an indexed attribute with 50% selectivity degrades performance by 75%
   • On average, having an indexed attribute with 10% selectivity gives similar performance to current implementation (which does not use any indexing)
   • On average, having an indexed attribute with 1% selectivity improves performance by ~100%

2. There are 2 possible ways to define the global list of indexed attributes. We need to decide which approach to follow.

   a) Make the list a server configuration (read from config.yaml)

   Pros

   • As the config is global, keeping this in the global server config makes sense.

   Cons

   • The list will need to be made immutable after the initial server startup. (We may be able to do some improvements to make them mutable when possible. But changing the config will still require a server restart)

   b) Define the indexed attributes during user schema creation

   Pros

   • Indexed attributes can be configured during runtime.

   Cons

   • We have to impose the restriction of defining an index by a schema.
     A schema can only define an attribute as indexed only if it's already an indexed attribute (defined previously by another schema) or if it's a new attribute which is not defined by any existing schema

3. Should we support indexing for attributes which are of a different type than string?*

Alternative Approaches

We initially considered defining indexed attributes independently for each user-schema. However, in order to benefit from indexes with that approach, we need to know the user type during authentication. Without knowing the user type, we cannot guarantee that USER_INDEXED_ATTRIBUTES table will return all matches and hence need to do a sequential search in USER table anyway.

Architecture and Components

User Store:

• Handles create update delete user operations to atomically modify data on both tables.
• Handles querying appropriate table/s based on identifier attributes in the request.

Security Considerations

1. Any indexing implementation should guarantee the correctness of the result.
2. Suppose 2 user schemas (user-type-a and user-type-b) have the same attribute name. But the selectivity of the attribute is very high in user-type-a and very low in user-type-b. Indexing that attribute to improve performance for user-type-a can degrade performance for user-type-b.

Implementation Complexity

Low (1-2 weeks)

Areas of Thunder that will be impacted

• User management
• Authentication

Questions for Community Input

No response

[senthalan]

b) Define the indexed attributes during user schema creation

Why we need to define it as a new attribute in the user schema? I remember we already have an unique attribute can't we reuse it? This way, we can detect the duplicate entry during user creation easily using this indexing and I assume User Identification during uses the unique attributes.

Do you see any concerns here ?

Should we support indexing for attributes which are of a different type than string?*

I assume the unique attribute is allowed for the strings and numbers. But in the store level, we can keep values as varchar in the USER_INDEXED_ATTRIBUTES table