Please enable JavaScript.

Coggle requires JavaScript to display documents.

Sharding - Coggle Diagram

- - - - Automatically
      - Manually by admin
    - - Upon DB setup some DBs allow for config of initial set of shards on an empty DB (pre-splitting). You need to have idea of the distrib.
      - As vol & W throughput ^ we split the existing shard into 2 or more smaller shards.
      - If ^ amounts of data are deleted may end up merging adj. shards
      - In DBs that auto. manage it
        
        shard split is triggered by shard reaching a predefined size (e.g. 10GB)
        
        If W throughput persistently exceeds a predefined threshold
      - Splitting a shard is expensive
        
        Req all its data to be RW into new files
        
        Shard that needs splitting is already under ^ load -> risk of OL
  - - - A good one uniformly distr. skewed data
      - Even if strings are similar hashes may be totally diff
      - No need to be cryptographically strong (MD5 or Murmur3 are good)
      - Careful with built-in ones in prog langs may hash same key diff in diff processes
    - - Hash modulo number of nodes
        
        Very ineff rebalancing
        
        If N changes almost all keys will be moved to a diff node
        
        Easy to compute
      - Fixed number of shards
        
        Simple and widely used solution
        
        Create many more shards than there are nodes
        (e.g. 1000 shards for 10 nodes)
        
        Choose N that is divisible by many factors
        
        Assign several shards to each node
        
        Can account for hardware imbalance - powerful nodes get ^ shards
        
        The system keeps track of which shard is on which node
        
        If a node is added/removed system can reassign some of the shards
        
        Entire shards are moved, much cheaper than splitting shards
        
        N of shards doesn't change, nor does the assig. of keys to shards
        
        Process takes some time for large amounts of data to move over network
        
        Good when you idea of how many shards
        you need when initially creating the DB
        
        Diff when the total dataset size is highly variable
        
        Shard size
        
        Just right → good performance
        
        Too small → too much overhead
        
        Too large → rebalancing expensive
      - Sharding by hash range
        
        For unpredictable n of shards better
        
        N of shards can easily adapt to the workload
        
        Key range sharding has risk of hotspots when ^ Ws to nearby keys
        
        Combine key-range sharding with a hash function
        
        Each shard contains a range of hash values not of keys
        
        Downside range queries are ineff as keys in the range are scattered
        
        Fix by key consisting of more than 1 col - can still perform eff range queries over the second and later cols
      - Consistent hashing
        
        Roughly equal n of keys on each shard
        
        Min. amount of keys are moved upon rebalancing
  - - - Good for write-heavy systems
      - But reads become more complicated
  - - - Slower
      - More control
      - Preemptive rebalancing before expected surge in traffic
    - - Less operational work for normal maintenance
      - Autoscale to adapt to changes in workload
      - Unpredictable (+ the expensive rebalancing is an issue)
      - If + automatic failure detection can falsely determine overloaded nodes are dead and cause cascading failure
    - - Autom. gen. a shard assignment
      - Admin has to approve
  - - - Sharding much less efficient
      - Bottleneck can become 1 or several busy nodes
      - Hot shard/spot
      - Key with ^^ load - hot key
  - - - Takes as input the partition key of a record
        
        Key/first part of key for KV store or а col in rel model
    - - Must support rebalancing to relieve hot spots
- - - - Some DB systems support ops that touch mult. shards at once
    - - Take advantage of NUMa architecture
      - One process per core
- - - - Client hits any node (e.g. round-robin)
      - Node serves if it owns shard
      - Or forwards to correct node and relays response
    - - All client requests go to routing layer first
      - Routing layer picks correct node and forwards
      - Acts as shard-aware load balancer only
    - - Clients know shard→node mapping
      - Clients connect directly to the right node
      - No intermediary in the path
  - - - Who decides which shard lives on which node?
      - Single coordinator is simplest, but must be fault-tolerant.
    - - Routing component (node / routing tier / client) must track shard→node changes
      - Needs a way to discover updated mappings
      - Must keep routing info in sync with current assignments
    - - When a shard moves, new node starts handling it.
      - Old node may still receive in-flight requests.
      - Need a strategy: forward, reject, or carefully drain to avoid inconsistency or errors.
- - - - Multi-user login per tenant
      - Each tenant has own separate dataset
      - Sharding implements it
        
        Each tenant has a separate shard
        
        Multiple small tenants grouped into a larger shard
      - Location
        
        Physically separate DBs
        
        Separately manageable portions of a larger logical DB
  - - - One tenant performs expensive ops
      - Doesn't affect others
      - Better capacity planning per shard
    - - Data separated per tenant
      - Access-control bugs less likely to cross tenants
    - - Group services + storage into cells
      - Each cell serves a set of tenants
      - Fault isolation: failures stay within cell
      - Cells can operate largely independently
    - - GDPR/CCPA: per-user data access/deletion
      - Per-person/per-tenant shard → simple export/delete
    - - Region-aware database assigns shard to region
      - Easier compliance with local data laws
    - - Migrate schema tenant by tenant
      - Lower blast radius for migration bugs
      - Safer experimentation and staged rollout
    - - Separate backups per tenant/shard
      - Restore one tenant without touching others
      - Useful for accidental deletions / overwrites
  - - - Requires intra-tenant sharding
      - Introduces complexity
    - - 1 shard per tenant → too much overhead
      - Group multiple tenants into shared shard
      - Tenant movement between shards as they grow
    - - Connecting data across tenants is harder
      - Requires joins across multiple shards
- - - - Secondary index
      - Join records
    - - For consistency use distributed transactions
      - Much slower than single-node ones and may become bottleneck
- - - - Index spans data from all shards.
      - Index itself is sharded, using the indexed value (term) as partition key.
      - Also called term-partitioned index.
      - Terms partitioned by range (e.g., colors a–r → shard 0, s–z → shard 1).
      - Or partitioned by hash(term).
      - Different sharding scheme from primary-key index.
      - Writing one record may touch multiple index shards (one per term/value).
      - Harder to keep index in sync with base data.
      - Often needs distributed transactions or accepts eventual consistency for index updates.
      - Good when read throughput >> write throughput and postings lists aren’t huge.
    - - Each shard maintains its own secondary indexes.
      - Index covers only records stored in that shard.
      - Shard doesn’t care about other shards’ data.
      - On add/update/delete, only the shard holding that record updates its local index.
      - If partition key is known → query that shard’s local index.
      - If not, query every shard, then merge results (tail-latency amplification)
      - Query throughput doesn’t scale well if every shard must process each index query.