CODEWITHSUNDEEP
algorithmdata-structurestreeb-tree
BlitzKrieg
BlitzKrieg

Reputation: 781

hierarchical multi-part key value store

I'm trying to design a configs/settings management system which I'm thinking of storing in a key value store.

I have a multi-part key - OrganizationId + TenantId + UserId + ApplicationId whereas value is a serialized config/settings object. The multiple parts of the key are hierarchical - i.e userid belongs to a tenantid which belongs to a organization id

The business requirement is such that I have to return the user-level (user id) config/settings object if it exists or else return tenant level (tenant id) or else return organization level (org id) object. The organization level object will always exist.

I plan to store the org level object with key as -(OrgId - a, TenantId - 0, UserId - 0, AppId - 0) Similarly, tenant level object will be stored as - (OrgId - a, TenantId - b, UserId - 0, AppId - 0) and so on...

When I get a query to return a certain config/setting object I get - OrgId(a), TenantId(b), UserId(c), and AppId(d) as the input. My job is query the key-value store to return the object at appropriate level

I can achieve this by making 4 calls in the worst case to the key value store -

  1. a, b, c, d
  2. a, b, c, 0
  3. a, b, 0, 0
  4. a, 0, 0, 0

Is there any way in which I can achieve this in a single call ? Any additional data structures that I can maintain to achieve this ? Any algorithms I can use to solve this issue ?

Thanks in advance !!

Upvotes: 0

Views: 214

Answers (1)

mcdowella
mcdowella

Reputation: 19601

Here are your two example settings

(a,0,0,0) => 1
(a,b,0,0) => 2

Now suppose I go through all possible combinations in lexicographical order and see what I get

(a,0,0,0) => 1
(a,0,0,a) => 1
....
(a,b,0,0) => 2
(a,b,0,a) => 2
...
(a,c,0,0) => 1

and I store only the points at which things change

(a,0,0,0) => 1
(a,b,0,0) => 2
(a,c,0,0) => 1

I haven't expanded the original data by more than a factor of two, and I can work out the setting for any position by using a single query that returns the largest position <= the query position.

Upvotes: 1

Related Questions