Typical systems and tips

• TinyUrl service / PasteBin

  • Short url length and characters space determine the urls to support

  • How to generate the key and map with the url

    • Method 1: real time generation, expensive to avoid duplicates

    • Method 2: pre generation, need to avoid using the same key

  • How to expire the expired urls with ttl

    • Proactively cleanup is expensive

    • Could check while accessing and remove it async, another job running to cleanup with a longer running frequency to reduce the impact

  • Cache is required to provide fast access

• Instagram photo sharing service

  • Storage sharding: Photo data sharding

  • Metadata sharding

  • NewsFeed pre-generation, rather than real-time quering

• Distributed key-value database

  • Data model

    • Sequencer is very important for resolve confliction, each row will have a unique sequenceId, could use last write win

  • Cluster/Replication group

    • 3 or 5 nodes in a cluster

    • Majority win, for strong consistency, only leader node serves write and read request. If we prefer availability over consistency, the follower nodes can serve read requests.

    • To resolve notes failure/partition, or split brains (two leaders), for the reads/writes, it could confirm the leadership with majority of the nodes.

  • Data-plane

    • Write-ahead log + B-Tree/LSM tree

  • Metadata Management Service

    • Leader selection with consensus algorithms

    • Manage the table/partition mapping with the key, the control-plane would load the mapping in memory, and the data should keep as up-to-date as possible

  • Workload management service

    • Sharding hot tables to more clusters/replication group. For queues, since there is not identify for each message, it can be just sharded to multiple clusters, don't need to track which message on wich cluster. But for key/value store, the key-range to cluster mapping is needed, and it need to be changed while sharding. During the sharding, there could be a period of time, the both cluster could serve read request, until the copy finished.

  • Control-plane

    • Authorization, authentication

    • Rate limit, circuit breaker

    • Metering, customer facing exception transform