Design Question for a simple technical interview

This was an interview question given to me 2 years back:

The idea was to design a solution for a simple problem within couple of hours and also give some insight into its scalability aspects. Many companies are these days throwing up these design problems to aspiring technocrats in order to see if you can come out with "out of the box" solution. Basically in today's world innovation sell.

Attached below is the transcript of the interview solution:

Queue Management System (QMS) Problem

Goal:

a) The queue management system should be able to server multiple applications.

b) All the applications must register itself with the queue management system before using the queue management system

c) Queue in the queue management system should be able to store generic data.

Challenges:

• Management of internal memory subsystem inside this queue management system
• Multiple applications access queue management system (so these applications should get different queues and the dedicated queues to one application should be protected from the other application in order to avoid data corruption)
• Boot time initialization (QMS can be implemented in the form of driver inside OS kernel) or it can exist in user space and just a wrapper over OS to provide abstraction and provide dynamic support to the applications
• QMS will have dedicated memory region for queues management and this memory is not infinite (so QMS needs to support applications flexibly and efficiently)
• Queues should store generic data
• Fairness in the queueing order to support first come first serve basis (One application shouldn’t be starved in order to benefit the other application unless there is a concept of priority based service by QMS to the applications)
• Advanced QMS should have knowledge of past history of the jobs (read applications + memory requirement by them in order to allocate memory in advance to such jobs in advance at the time of registration). History information is maintained and the statistical data processing can be done in order to efficiently manage new requests.
• Better QoS (Quality of service) to the application
• OS independent and portable i.e. no OS system calls (A wrapper is written over OS so that it can be ported to some other GPOS or RTOS for future enhancements).

Limitations:

Assumptions/Comments:

1. QMS provides first level abstraction with the underlying OS calls by declaring its own memory pool internally and allocation/deallocation of the queue data structure is handled internally by QMS.
2. QMS can be implemented inside OS kernel or outside in the user world. When inside OS kernel, it can be implemented as a driver or a loadable module inside kernel. So, the BOOTINIT facility as discussed on the following pages is dependent on the implementation of the QMS.
3. Though at some places, whatever I am talking about looks like linux oriented but I have tried to keep everything as much OS independent as possible.

Design Overview

The design overview for a QMS is depicted below in the form of a pictorial diagram.

Functional Blocks:

BOOTINIT: This module is in-charge of the initialization of the QMS internal memory pool and the initialization of the external and internal context associated with it. This module is basically necessary to bootstrap the QMS.

RMC: The role of RMC is dual purpose.

It’s a registration module for all the applications. Applications must init itself with the QMS and QMS responds back with a sid (service identifier) which the applications must use in order to be served by the QMS. Actually AC checks it later on while serving.

This is for authentication + also keeping the number of

• clients to a value below threshold limit. The threshold limit is governed by the initial memory allocation for QMS (given by MMU of the OS). So, QMS based on its calculations and also the average memory required by earlier application clients (of similar nature) knows how many clients it can serve now. QMS rejects application requests if the threshold limit is crossed or can be violated by this new application request.
• Callback facility is provided for the applications whose request can’t be processed the first time or who need to wait for the additional requests due to unavailability of enough memory inside QMS. All the clients register their callback functions at the time of the registration and these clients can be waked up in round-robin fashion by the RMC as and when the memory is freed for some other application. So, this can avoid busy wait for an application with QMS and also this ensures a proper mechanism to ensure some fairness in the system.

AC: Authenticity checker basically checks for the incoming requests sid (service identifier). There is a range or service identifier which is known to QMS and which is governed randomly by rand() inside RMC (unlike nonces or seq nos. in TCP) so that even if some malicious agent decrypts one sid for one application, it is not possible for that agent to guess the next sid. So, sid is unique for one application request and AC checks this before processing the request. Once the request is valid, it passes this onto ASPE.

ASPE: The role of ASPE is as mentioned below

• This is the core part of the QMS. Once a request is found legitimate by AC, ASPE works over it. It calls on the internal memory subsystem (IMS) services to look for whether this request can be processed. If there is not enough memory inside QMS, then error id is returned to the application. If there is enough memory, then IMS in collaboration with DTA module allocates a queue for this request.
• Once a valid queue is allocated for this application, ASPE asks the QS to see if this application request can be serviced now. If yes and there are no pending requests from other users, then ASPE service this request. Actually this step should be before the 1^st step of ASPE but it is debatable.

IMS: The role of IMS is to manage memory pool allocated to the QMS. It also needs to provide memory (read queue) protection for queues being used by different applications. It also needs to verify that the threshold limit (as discussed earlier) is not violated. Besides, it needs to work with DTA in order to provide generic data type service to the application. To avoid endian-ness issues in certain processor architectures, we can keep the queue elements as word aligned but it depends on the implementation. It’s a minor suggestion.

DTA: As QMS is required to provide data abstraction to the application e.g. application can use queue of int, char, map etc. The role of DTA is to provide abstraction to the application. Internally it would return the queue pointer (pqueueid) allocated by IMS as of void type to the application and it would be the role of the application to cast it into the requisite data type in order to be used properly by the application.

Exported Functional APIs

Following is the list of APIs to be used by the application while using QMS services. QMS initializes and exports these APIs at the time of BOOTINIT or the QMS initialization time. I am not defining list of error ids here due to time constraints but we can keep error ids as enum.

1) void Qms_init(void);

This API would initialize QMS and would do the job of BOOTINIT as described earlier.

2) void Qms_register_app(void *datatype, void *apptype, int *sid);

This API is used by the application to register itself with the QMS and in turn QMS responds back with a sid. For now since the API is not returning errors (time constraint), if sid is NULL, this means that the request has failed. Or we can return SUCCESS/FAILURE (bool type).

3) void Qms_aspe_service_req(int sid, void *datatype, qsize_t queuesize);

qsize_t can be similar to size_t structure in linux and the sid should be a valid one for ASPE to process this request.

Internal Functional APIs of the QMS

Naming convention: systemname_callerroutine_calledroutine_requesttype();

· int qms_rmc_ac_gsid(void);

o This function generates a random sid which is unbreakable by external moles or malicious agents.

· void qms_aspe_qs(int apprequest);

o Apprequest is internally generated from sid and is required by QS (qms scheduler to see if this request can be processed at this time).

· Void qms_aspe_ims(void *datatype, qsize_t size);

o ASPE asks IMS whether this request can be processed or not by looking into the memory requirements. IMS upon checking itself whether this is a valid request or not (remember threshold limit…J) can allow DTA to take over and allocates a generic data type queue.

· Void qms_ims_dta(void *datatype);

o This is for generic data type abstraction purposes (as it was one of the goal).

· void qms_aspe_auccheck(int sid);

o This checks whether this is a valid sid from the application or a fake one.