System requirements

Functional:

• User can log in to this system. This results in the user getting an OAuth2 access token.
• User can present this access token to access a third party resource.
• OAuth2 covers identity federation and single sign-on
• Support Multi-factor authentication

Out of Scope:

• Identity lifecycle management
• Threat detection (see "Network Security Monitoring Tool" Editorial).

Non-Functional:

• Scalable
• Consistency
• Availability
• Response time below < 200ms

[Similarly to other systems, Identity Management is a big, vague topic. It is very important to clearly define the scope and get the interviewer's buy-in. Generally speaking, a good system design interview ends up with a deep conversation, instead of a shallow tour of many topics.]

Capacity estimation

• 100M DAU. 500M users in the system.
• Each user logs in twice a day on average
• 200M login / day
• 200 * 1000 * 1000 / (60 * 60 * 24) = 2300 logins / sec
• There would be multiple interactions per login (typing username, typing password, MFA, 3-legged OAuth2 message exchanges, etc.), so let's assume there would be 10 times more messages. 23K requests / sec

• Let's say each user takes up 10KB of data (username, email address, associated groups, associated apps, ...) on average.
• 500M * 10KB = 5000GB = 5TB
• To allow future growth and some buffer, let's assume data size would be 10TB

API design

• start_login_session(username) # this lets the server finds the user and initiate the login process. This returns user_id, session token.
• send_auth_token(user_id, session_token, auth_token) # auth token can be password or other types of MFA token, e.g. One Time Password, response to Passkey (WebAuthn) challenge. Upon successful login, this returns OAuth2 access token and refresh token to the user.

There would be APIs for implementing OAuth2 protocol, such as validating access tokens and refreshing tokens. This is out of scope of this problem.

Database design

Data Models and DB Choice

[Mid-level deep dive topic. It is almost a mandatory topic.]

For identity management, consistency is critical. For example, if admin deactivates or locks a user's account due to suspicious activities, you really want to make sure that the user cannot log in to the system, immediately. Eventual consistency (at some point in the future, that user would stop being able to log in) would not do.

User Data size is not huge at 10TB. It would also receive more read requests than write requests.

Therefore, we can use RDB for the user account storage.

User table:

• user_id
• username
• email address (may be the same with username)
• first / middle / last name
• phone number
• address
• organization_id
• created_at

AppUser table:

• user_id
• app_id
• created_at
• expires_at

App table:

• app_id
• app name
• required OAuth2 scopes

AppUser table joins User and App table. User and App have many-to-many relationship.

AuthFactor table:

• factor_id
• user_id
• factor_type # password, Passkey, OTP, etc.
• secret # password hash, public key, etc

AuthFactor table has a foreign key to User table. User and AuthFactor have one-to-many relationship.

Separation of Read and Write Stores

[Senior-level deep dive topic]

The main functionality of authentication can be implemented primarily with read access to the database: find user on User table, read password hash to validate the password user typed, etc. Since we are build a low response-time system with scalability in mind, it is important that this operation is optimized. By keeping accesses to User and AuthFactor tables primarily read-only, we can take advantage of caching and RDB's read replicas for performance and scalability.

But there are write operations in authentication. The system should record who logged in at what time, from which device, using which authentication method, and so on. This information is critical for threat detection and analytics.

These data will be write-heavy and larger than the user related tables. Write pattern will be primarily append-only. Therefore, a LSM based storage would be ideal to store it. The logs will also be timestamped. We can expect time-range queries (e.g., show all the users who logged in to this app between 8AM and 5PM). Therefore, Time-Sequence DB makes sense for Log Database.

High-level design

Client can be a browser or a rich client (e.g. on a mobile device).

Authentication Service takes all the requests. It uses data in User DB to authenticate users. It writes authentication logs to Log Database. It uses cache (e.g. Redis) to improve response time and scalability.

Request flows

Client sends requests to API Gateway.

API Gateway forwards the request to one of the Authentication Services. Because this service is stateless, we can use weighted round robin (round robin which prefers to send requests to less loaded servers with more capacity) to distribute requests.

Authentication Services looks up user in User DB using user_id. It then uses data in AuthFactor table to authenticate the user.

Detailed component design

Authentication Process

[Senior-level deep dive topic]

To support Multi Factor Authentication, we need multiple ways to authenticate a user: password (common but insecure), one time password, Passkey (on WebAuthn protocol), challenge-response (e.g. with smart card), and so on.

Let's look at how it works with password, as it is still the most common authentication method.

1. Client sends user name with start_login_session().
2. Authn Service finds the user in User DB. It returns user_id and session_id to the client. It caches the user data.
3. User types password on the client.
4. Client hashes the password and sends the hash via send_auth_token().
5. Authn Service reads the user's password hash from User DB. It compares it to the hash the client sent.
6. If they match, the user successfully logs in. Authn Service logs this in the Log Database.

One of the important points in this process is that the client does NOT send password to the server for security reasons. If an attacker is sniffing the network, they would be able to steal the hash, instead of the password. Stolen password is extremely dangerous because users tend to reuse the same password in many services. Password hash can be used in only this service, and it can be changed, for example by using a different salt in the hash function.

This process is also designed to handle other authentication methods. The client can send different auth token in Step (4). For example, it may send a signed nonce for Passkey authentication. It may send one time passcode (instead of password hash), and so on. This is how this system can support multi-factor authentication.

Trade offs/Tech choices

See discussion on "Separation of Read and Write Stores" above.

Failure scenarios/bottlenecks

Partitioning and Replication

User DB should be partitioned for scalability and response time. user_id is a good choice for partitioning. Users should usually consume similar amount of space and computation on average, because a human user should log in to the system only a few times a day. If some users log in a lot (e.g., thousands or millions of times a day), that would probably indicate a malicious intent or faulty software. Such activities should be blocked or retained via rate limiting.

As such, we do not anticipate large difference in activities between users. However, we should monitor activities regularly. If they show large differences, we should consider distributing load via consistent hashing.

User DB should also be replicated for fault tolerance and scalability. We can have multiple read replicas per primary node. Read replicas help in multiple ways:

• Durability - read replicas keep the same data with the primary.
• Fault tolerance - a read replica can take over the primary role when the primary goes down.
• Scalability - read accesses can be handled by read replicas, reducing the load on the primary.

Fault Tolerance

All components must be monitored for their health status, resource status, and latency.

Databases (RDB, Time Series DB) and Cache (e.g. Redis) all have built in fault tolerance functionalities such as replication and back up. We should take advantage of that.

Authn Service is stateless, so we can run multiple copies of it and distribute load among them.

There would be user errors, too, for example, abandoning login session, typing wrong passwords too many times, and so on. Appropriate timeouts and user lock-out policy should be implemented.

Future improvements

Privacy and Data Residency laws may impact where data have to reside. For example, GDPR (European privacy law) may require that, if the user resides in Europe, the data about this user must be stored in Europe.

In such case, we cannot solely rely on partitioning (e.g. using hash of user_id). We may consider a cell architecture. A cell is a unit which contains all the nodes (services, DBs, cache, ...) for a particular group of users. For example, in this example, we may create a cell in Europe that stores and handles all the users from Europe.