Loading...
[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.]
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.]
Main data models are servers and VMs.
Server:
VM:
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.
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.
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.
[Mid-level deep dive topic]
Allocation Service requires the following information to make decisions:
(1) - (3) are provided by the configurations stored in Resource DB.
(4) (5) are provided by Monitoring Service, stored in Cache.
This is basically a bin-packing problem.
Efficient algorithms exist, e.g., First Fit, described in pseudo code below:
sort servers in terms of capacity
for vm in requested_VMs:
for server in servers:
if server has enough capacity to fulfill vm's configuration:
map vm to server
decrease server's capacities
Sorting would be tricky, as it would be sorted by multiple resources (CPU, memory, storage ...). It would make sense to sort based on a combination of these three resources.
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.
[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)
Pull (VMs/servers call Monitoring Service)
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.
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.