Systems Design Examples Short Url - herougo/SoftwareEngineerKnowledgeRepository GitHub Wiki

Reference Answer

Source:

• https://github.com/Jeevan-kumar-Raj/Grokking-System-Design/

Notes:

• Standalone Key Generation Service (KGS)
  • Generate random 6 letter strings and store them in a database (key DB)
  • When a short URL is needed, take one from the key DB
• keys are sharded to avoid concurrent access issues

Questions about this answer:

• Why do you need to code the URL? Isn't it the point that you go from shorted URL to actual URL?
• UUID replace KGS? What does that mean?

Personal Attempt 1 (Minimal)

Note: I read the answer before doing this.

Question

• can we reuse old (expired) keys?

Approach

• KGS
  • Naive approach: use an incrementing counter as the keys (short urls)
    • Problem: predictability and security
  • Idea: suppose you anticipate 68B keys. Now you can take these keys and shuffle them to get a seemingly random key at run-time.
    • Problem: How do you shuffle 68B keys?
      • Personal Idea 1 ("merge-shuffle"): recursively randomly assign the key a bucket to shuffle later. More concretely, do the following.

# f(n) = O(n) + b * f(n/b) -> O(nlog(n))
def merge_shuffle(keys, b):
    if len(keys) < b:
       return shuffle(keys)
    buckets = [[] for _ in range(b)]
    for key in keys:
        hash_modulo_b = hash(key + str(len(keys))) % b
        buckets[hash_modulo_b].append(key)
    result = []
    for i in range(b):
        buckets[i] = merge_shuffle(buckets[i], b)
        result.extend(buckets[i])
    return result