多层级系统属性值获取的现有数据结构与算法方案问询

Great question! Let's break this down based on the two scenarios you mentioned, plus dive into the storage tradeoffs in document databases that you're curious about.

Since static data never (or almost never) changes, we can optimize purely for query performance without worrying about update consistency overhead. Here are proven solutions:

• Pre-merged Flat Structure: Pre-compute and store all inherited properties into a single flat key-value set for the lowest level (e.g., the user document). For example, if user doesn't have a theme property, pull it from role, then profile, then system, and save all these into the user document upfront. Queries become O(1) lookups with no traversal needed.
• Layered Hash Tables: Maintain separate hash tables for each level (user, role, profile, system). When querying, check the lowest level first; if the key isn't found, move up to the next level. This avoids data redundancy and is easy to implement, though it adds a tiny bit of query overhead compared to pre-merging.
• Trie-Based Hierarchical Index: Build a trie where each node represents a level, and leaf nodes store property values. Traversal starts at the lowest level and moves up until a value is found. This is efficient for hierarchical key patterns (e.g., user.role.profile.system.key).

Here, we need to balance fast queries with minimal update overhead (since changes happen rarely but need to be reflected correctly). Common approaches include:

• Lazy Update with Version Stamps: Attach a version number to each level's property set. When querying, fetch the latest version from each level (starting from the lowest) and use the first existing value. When a level's data changes, increment its version stamp. This ensures you always get the latest value without pre-merging, and updates are cheap.
• Event-Driven Hierarchical Sync: When a higher-level property (e.g., role) changes, trigger a background job to update all dependent lower-level entries (e.g., all users linked to that role) only if they don't have an override for that property. Since changes are infrequent, the one-time sync overhead is acceptable, and queries remain fast (no traversal needed).
• MVCC for Hierarchical Data: Use Multi-Version Concurrency Control where each level stores multiple versions of its property set. Queries resolve to the latest valid version for each level, and old versions are garbage collected after a grace period. This works well for systems where you need to maintain historical data alongside current values.

Let's compare the two storage strategies you asked about:

Separate Storage (Each Level as a Standalone Document) #

Pros #

• Granular Updates: Changing a role property only requires updating the role document, not every user that inherits from it. Perfect for infrequent changes that affect many entities.
• Data Reusability: Multiple users can reference the same role/profile document, eliminating redundant storage of shared static properties.
• Flexible Schema: Each level can have its own schema changes without impacting other levels.

Cons #

• Query Overhead: To resolve a property, you need to perform multiple document lookups (e.g., fetch user, then role, then profile if needed), which adds latency, especially with deep hierarchies.
• Consistency Risks: If a higher-level document is updated, there's a window where queries might get stale values from cached lower-level documents unless you implement cache invalidation.
• Complex Joins: Document databases aren't optimized for joins, so resolving hierarchical properties often requires application-level logic to fetch and merge data.

Combined Storage (All Levels Merged into a Single Document) #

Pros #

• Blazing-Fast Queries: All inherited properties are stored in one place, so queries are single-document lookups with no traversal or joins.
• Strong Consistency: No cross-document consistency issues—all properties in the document are always in sync.
• Simplified Caching: Cache the entire document, and you don't have to worry about invalidating multiple cached entries when changes happen.

Cons #

• Data Redundancy: Shared properties (e.g., a role used by 1000 users) are duplicated in every user document, increasing storage costs.
• Expensive Updates: If a shared property (like role.theme) changes, you need to update every user document that inherits it. Even infrequent changes can be costly if the scope is large.
• Bulky Documents: Merging all levels can lead to very large documents, which might slow down writes and take more memory to cache.

Which to Choose? #

• For static data: Combined storage is almost always better—redundancy is irrelevant since data doesn't change, and query performance is top priority.
• For infrequently changing data:
  • If changes affect small scopes (e.g., a single user's custom properties), combined storage works well.
  • If changes affect large scopes (e.g., a role property that applies to hundreds of users), separate storage with cache invalidation is the way to go.

内容的提问来源于stack exchange，提问作者Rui