System requirements

Goals

Functional:

• Numeric IDs
• Chronologically sorted on time of creation (Timestamp based sorting)
• 64bit length
• Stateless: We don't need to store it for high throughput environments

Non-Functional:

• Scalability, we want our system be scalable
• Availability, we want our system to be highly available. Ideally we want no more than an hour of downtime per year
• Low Latency, ideally we would want latency as low as possible. Since, roundtrip for one datacenter is 150ns. I think it's fair to begin with latency target of 10ms
• Lowest possible collision

Non-Goals

• Authn/Authz
• Audit trails
• Analytics

Capacity estimation

• Total ids we could generate is 2^64 (since, 64 bit id) = approx 20 Quintillion ids we could generate
• Assuming we are generating: 100 Ids per seconds = 360K ids per hour = 360K * 24 =8.6 Million per day, 8.6 * 365 =3.1 Billion per year, for 10 years, we get 30 Billion UUIDs. So, we are sure we won't have collision in 10 years time.
• We will strive for SLA = 99.99% with equates to 50-60 minutes. We can use percentile such as 99P, 90P, 50P requests and track essential metrics such as Latency, Bandwidth, Throughput to derive this

API design

GET - /api/v1/new

Description: Gets a new 64 bit UUID

Inputs: None

Output: Number (length = 64)

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

High-level design

DNS: Geo based Routing to scale across datacenter

LoadBalancer: To route traffic to healthy nodes. Also, we use LoadBalancer to scale and de-scale nodes in a datacenter

Distributed UUID generator: Snowflake ID Approach

Request flows

Detailed component design

Algorithm:

Choice is twitter Snowflake:

We will use Twitter snowflake because this is very efficient essentially it store 1st bit for future purposes, 41 bits for timestamp in milliseconds since epoch (unix or custom), 5 bits for datacenter id, 5 bits for machine id, 2 bits sequence number (every id generated on a machine is incremented by 1 generated every millisecond). With our approach we don't need additional storage, neither we do have synchronisation issues

GEOROUTING:

We will use GEO Routing to cater datacenter level scaling. For instance client in us-west-1a will get routed to a load balancer that routes to machines in us-west-1a. This way we can route to the closest datacenter to the user.

Monitoring and Alerting

• LoadBalancer: Run heartbeat on all nodes and ensure we have 95% nodes in a datacenter up and running
• We publish metrics on new UID generated (to measure the throughput). we should have Latency metrics for both peak and non-peak hours
• We should alert on any 5XX errors and this would indicate issues on our system

Trade offs/Tech choices

Alternatives

• There are other approaches for instance, AUTO_INCREMENT with Database. However, scaling a DB is a challenge and even then, we need to ensure synchronisation when we have multiple database servers. Also, we have another responsibility to maintain database as part of our design

• We could use UUID. however, it would have generated 128 bits. which would consume more space and most likely impact latency and throughput Other issue is, ID's are non-numeric and id's won't be sorted with creation time.

Failure scenarios/bottlenecks

Our approach depends on Clock and we could expect clock skew. To address that, we will need NTP setup i.e. to ensure all machines have the time in-sync. I think we should config our machines using configuration management tools such as Ansible

With our approach we can add and remove nodes are we want. however, when a node is removed the calculations would change. So, if we want to have audit trail at later point. This many be an issue

Future improvements

I think we can look at the improvements in algorithm and given our specific needs we may need to tweak the UID length and how we configure our UID for example: Mastodon uses 48 bits and 32 bits for timestamp.