package
0.0.0-20241212195640-2e19e05a42f5
Repository: https://github.com/addi-11/system-design.git
Documentation: pkg.go.dev

# README

Atomically incrementing integer ID

Implement an atomically incrementing counter-based unique ID generator.

  • Atomically increment counter and persist it on disk every time
  • Persist the counter every n iterations to the disk
  • Vary the n to understand how the throughput varies
  • Implement and test recovery by resuming from the safest value

Thought process for generating unique IDs in a distributed system:

  1. Using the Clock:

    • A timestamp-based ID could work but may lead to conflicts in distributed systems where multiple machines generate IDs simultaneously.
  2. Adding machine_id:

    • To make IDs unique across machines, combine machine_id with the timestamp: machine_id + time.
  3. Considering Multithreading:

    • With multiple threads on each machine, add thread_id for further uniqueness: machine_id + time + thread_id.
  4. Replacing thread_id with a Counter:

    • Using a counter instead of thread_id makes IDs sequentially unique within each machine and thread: machine_id + time + counter.
  5. Eliminating the Timestamp:

    • If each ID has a unique counter per machine, the timestamp becomes redundant, so we can simplify to machine_id + counter.

Summary

  1. Atomic Counter Increment: Each ID is created by combining machine_id with a globally shared, atomically incremented counter.
  2. Periodic Persistence: The counter's value is saved to disk every n iterations to safeguard progress without saving every time, which balances performance and reliability.
  3. Fault Recovery: On startup, the counter loads from the last saved value, ensuring continuity even after program restarts.
nTime Taken
1000408.5958ms
50002.1122575s
100003.8377447s
1000001m4.908891s