System requirements

Functional:

The system will primarily work on VMs, which are hosted by the servers. It is more common a user requests VMs instead of whole servers, as the latter would be expensive.
User can request VMs by specifying the number of VMs, and the criteria using feature flags (e.g., OS, CPU / memory / storage type and size).
Requests may succeed fully (all VMs reserved), succeed partially (some, but not all, VMs reserved), or fail completely (no VMs reserved).
User can release VMs that were allocated earlier.

[Generally speaking, you would like to keep the requirements scope small. You only have 35 - 50 min in an interview. If you have a lot of requirements, you'd risk running out of time. We could add many requirements here - capacity planning, serverless computation nodes, dynamic scaling, etc., but we will start with a small set of requirements. Easier to expand later than shrink.]

Non-Functional:

Consistency. We need to avoid double-booking servers, or under-booking servers.
Scalability. Imagining this system is AWS / Azure / GCP, it would need to scale massively.
Availability is important, as users worldwide would like to request servers on 24x7 basis.
Response time can be relaxed. Taking 1 - 10 seconds to fulfill a request would be acceptable.

Capacity estimation

The system has 1M servers
On average, 5 VMs are hosted on one server.
1K max feature flags per server
On average, a user requests 5 VMs per request.
On average, 1 request comes per second. The request can be either to request, or release servers.

API design

request_VMs(user_id, number, criteria)

-> This returns an array JSON objects describing the VMs reserved. Each object contains VM_ID, security group and region it belongs to, and configuration information like CPU, memory, storage.

release_VMs(user_id, [VM_IDs])

-> This release (or un-reserve) the VMs.

criteria is a JSON object. Note that not all criteria should match exactly. For example, when a user requests storage size to be 1TB, they may be fine to receive storage more than 1TB, provided the cost is not too high.

The JSON criteria object must be able to accommodate this flexibility. An example follows.

{

num_CPU: {equals_or_more_than: 4},

type_CPU: {prefer: "Intel XYZ"},

memory_size: {equals: '1GB'},

storage_type: {equals: 'SSD'},

storage_size: {equals_or_more_than: '1TB'}

}

[We are putting more effort in the API for this solution than usual. It is because the criteria would be an important aspect later in deep dives.]

Database design

Main data models are servers and VMs.

Server:

server_id
OS
CPU
... up to 1000 feature flags

VM:

vm_id
server_id # foreign key
OS
CPU
... up to 1000 feature flags

VM table has a foreign key to Server table. VM to Server is many-to-1 relationship.

Given we need to store up to 1,000 feature flags, Let's assume each needs 8KB.

8KB * (1M servers + 5*1M VMs) = 68 GB

Given the storage size requirement is modest, and we need strong consistency, RDB (e.g. MySQL, Postgres) is a good choice.

High-level design

Allocation Service handles request_VMs() and release_VMs() APIs.

It stores the mapping information (which server is hosting which VMs) on Resource Database. It also caches the mapping in Cache (e.g. Redis Cache) for faster access.

When client wants to access the VMs directly (e.g. by connecting to it via SSH), Forwarding Service maps the VM ID to an appropriate server and VM IP address, and forwards the request to the VM.

All servers and VMs send periodic heartbeats to Monitoring Service. The heartbeat includes resource related information, such as CPU, memory, and storage capacity. Monitoring Service stores this information in the database and cache.

flowchart TD
    C[client] --> API[API Gateway]
    API --> All[Allocation Service]
    All --> DB[Resource DB]
    All --> Cache[Cache]
    Svr[Servers in Server Pool]
    API --> Svr
    API --> Fwd[Forwarding Service]
    Fwd --> Cache
    Fwd --> DB
    Fwd --> Svr
    Svr --status--> MQ[Message Queue]
    Mon[Monitoring Service] --> MQ
    Mon --> DB
    Mon --> Cache

Request flows

Calls to request_VMs() and release_VMs() APIs are first received by API Gateway.

API GW picks an appropriate Allocation Service node.

Allocation Service reads the VMs and server status from Resource DB. It then chooses the right server to host requested VMs

It also uses Cache to access frequently accessed data with low latency.

Detailed component design

[Senior-level deep dive topic. It can be powerful if we can discuss a solution at an algorithm level, like we are doing here. However, it is also important to not get stuck in the details of algorithms (e.g. trying to implement them perfectly during interview), because it would take a lot of time. Have a high level understanding of the core idea, and be ready to discuss it.]

Allocation Service

Allocation Service requires the following information to make decisions:

Servers configuration
VMs configuration
Which VMs are hosted by which server, and which resource are allocated (% of CPU, memory and storage size, network bandwidth)
Real time information of how much resource VMs are using.
Real time information of how much resource servers have.

(1) - (3) are provided by the configurations stored in Resource DB.

(4) (5) are provided by Monitoring Service, stored in Cache.

Given VM requirements, we need to find the best server to host this VM. In case it is possible to host it, we need to either reject the request, or add a new server to the server pool.

This is basically a bin-packing problem, which tries to minimize the number of bins (in our case servers).

This is similar to Knapsack problem, but it's different. Knapsack problem tries to maximize the value of items carried (in our problems, equivalent to VMs). At this point, we are trying to fit all VMs, instead of selecting highest valued VMs. Therefore, bin-packing is the better suited problem.

We can use a variation of Best Fit algorithm. It can be implemented efficiently by using a balanced binary tree to store server capacities.

It is a little tricky that we need to account for multiple resources (CPU, memory, storage ...). We can define the resource level as a tuple containing these three resources. And then, evaluate how well a tuple fits to a server with an Euclidian distance.

In addition to the algorithm, we should add a couple of wrinkles:

a. If our monitoring show some VMs are not using all the allocated capacities, we could over-book some servers, with an expectation that VMs would use only some (say 80%, 50% ...) of the reserved capacities.

b. If a server becomes overwhelmed because VMs are using resources to the full reserved capacities, we might rebalance by moving some VMs to another server with more capacity.

Trade offs/Tech choices

Monitoring Service

[Mid-level deep dive topic]

Monitoring Service receives status information from VMs and servers, and stores the information in Resource DB and Cache.

An interesting topic would be whether the Monitoring Service should pull the information from VMs and servers, or the VMs and servers should push the information to Monitoring Service.

Push (Monitoring Service calls VMs/servers)

Pro: Monitoring Service can ask for the information when it is ready for that information. It wouldn't be overwhelmed.
Con: Implementation gets complicated. It needs to keep complete list of VMs and servers. When VMs / servers do not respond in a timely fashion, it needs to retry and make a decision on if they are responding slowly or have crashed.

Pull (VMs/servers call Monitoring Service)

Pro: Simplifies Monitoring Service implementation.
Con: Monitoring Service may get overwhelmed if many VMs/servers send the information at the same time.

We lean toward Pull model for simplicity.

To address the issue of Monitoring Service being overwhelmed, we can introduce a Message Queue to buffer the messages from VMs/servers.

Failure scenarios/bottlenecks

All services we implement - Allocation Service, Monitoring Service, and Forwarding Service - are designed to be stateless.

We will be running multiple instances of each service for fault tolerance. If some nodes experience difficulty (e.g., crash, slowness, needs to be taken out of rotation or restarted), the other nodes can take the requests. Since it is a stateless service, it should be easy to implement load balancing, e.g., partitioned by VM ID.

We can use built-in partitioning mechanisms of Resource DB, Cache, and Message Queue for fault tolerance and scalability. VM ID would be a good partitioning key for these services because each VM would require similar amount of data to run, e.g., configuration and monitored resource level.

Future improvements

Capacity planning - Use historical reservation data and monitored data to figure out how many servers we need to provision in the server pool.
Serverless computation nodes - instead of providing VMs, we can provide environments to run customer provided code.
Dynamic scaling - Instead of users requesting certain capacities of VMs, change VMs capacities according the resources they are consuming.

Design a Resource Allocation Service

Try this problem yourself