System Design Examples

Question 1

If you are designing Bit.ly or a similar URL shortening service – what are the 2-3 primary requirements you should target?

Answer 1

Users should:
- Provide a URL and receive a shortened code that corresponds to the URL
- Aliases (optional)
- Expiration (optional)
- Provide a shortened code and be redirected to the original URL
- Unique (obviously)
- Short (as possible, depends on scale)

Question 2

For a Bit.ly-like system, what might be some common non-functional requirements?

Answer 2

• Low-latency (no difference from clicking a regular link)
• Highly available (required for links, they should work)
• Scalable (up to X)

Question 3

What core entities would exist in a Bit.ly system?

Answer 3

The first two can be combined from a data perspective:

• Original URLs
• Shortened URLs (URL codes)
• Users

Question 4

In fleshing out the APIs and interfaces for a Bit.ly like service what might be some common endpoints for your REST API?

Answer 4

// Request to create the new URL/short code
POST /urls/ : string (200)

// Get request to serve redirect of original URL
GET /urls/<code> (302, 301 optionally)</code>

Question 5

What’s the crux of the Bit.ly system design problem?

Answer 5

Key/short code generation

Question 6

What are two strong options for solving Bit.ly’s key generation problem?

Answer 6

• GOOD: Leveraging a hashing function fed through a Base62 encoding and relying on the database to enforce unique constraints (and try again when necessary)
• BETTER: Hashing/encoding a Base62 counter to ensure that unique values would be continually used

Question 7

How might you implement a counter-based, key generation approach for a service like Bit.ly?

Answer 7

There are a few options, you could use something like a distributed cache (e.g., Redis) to maintain it, or simply leverage a database to allocate a range of available identifiers to a server on startup that it would use (and request more when nearing capacity).

If you needed a distributed configuration model, you could also consider something more heavy-handed like Apache Zookeeper, etc.

Question 8

If you had to design a system like Dropbox – what might be the core requirements of handling a system like that?

Answer 8

Users can:
- Upload file to our system
- Download/view files from our system
- Permissions (optional)
- Sharing a file with another user?
- Sync files from local/server devices

Question 9

For a Dropbox-like system, what might be some important non-functional requirements?

Answer 9

• High availability (incredibly important that files are available, availability > consistency)
• Scalability (support for very large files, e.g., 50GB+)
• Low-latency (as possible for downloading, uploading, etc.)
• Secure (permissions, etc.)

Question 10

What core entities would be present in a Dropbox-style system?

Answer 10

The entities would probably be summed up as:

• File (Content), the actual file data (bytes)
• File (Metadata), additional data about the file
• User, the actor in the system, owner of files
• Permissions, to manage file accessibility

Question 11

In our Dropbox system design example, what types of REST-based endpoints would we have (initially)?

Answer 11

Obviously these would all contain additional payloads related to authentication/authorization via headers, session tokens, etc.

// Upload a file
POST /files/
{
file: byte[],
metadata: { … }
}

// Download a file
GET /files/<fileId> : bytes[] (more likely redirect)</fileId>

// Share a file
POST /files/<fileId>/share
{
users: string[]
}</fileId>

// Detect remote changes of a file
GET /files/<fileId>/changes</fileId>

Question 12

In a Dropbox-like system, how would you go about storing the files in terms of technology choices?

Answer 12

The files would need to be decoupled, that is, storing the actual bytes in some form of blob storage (e.g., GCS, S3, etc.) and the metadata could be stored within a database (non-relational is probably a fine choice)

Question 13

When uploading a file in our Dropbox style system – walk through a few alternate approaches and options?

Answer 13

• BAD: Attempt to upload the file and metadata to our system. Storing the file on our system would not scale and would place the responsibility of all of those files on us
• OKAY: Our servers could handle uploading the file data to our blob storage provider and write the metadata to our persistent data store (using the identifier from blob storage and storing it)
• BEST: Allow the user to upload directly to blob storage via requesting some type of presigned URL and rely on the upload event to notify our service the upload was complete, grab the related metadata and store it in our data store

Question 14

In the Dropbox upload process involving a presigned URL, how might this affect the flow during an upload?

Answer 14

The usual process of performing an upload would now provide the user with a presigned URL for them to upload the target file provided the metadata. The user could then upload the file directly (and efficiently to blob storage that the URL).

Once the upload was complete, we could leverage an event driven process (usually available from blob storage) to get a signal the file was complete and update the database. If signals weren’t available, we could leverage some type of queue or polling processing on the client to verify the file was uploaded.