Simulating the Passport Seva Kendra using Clojure

A year ago, I went to the Passport Seva Kendra (PSK) in Mundhwa, Pune to get my passport renewed. At the time, the government had revamped this process and made it a simple, step-in/step-out painless affair. Unfortunately for me, I hit an edge-case in the system and took much longer than expected to complete. I was there for close to 4 hours. I used this time to observe the behavior of the PSK and think about ways to improve the applicant experience. I thought it was an interesting problem to solve and write about.

Recently, my wife booked an appointment at the PSK to renew her passport and this provided the spark I needed to write about it. So here we are, a year later, talking about the passport renewal process at the PSK.


The Problem Statement

Let me describe the process to you first.

  • The PSK has appointment slots every 15 minutes, and there are ~25 people in each slot.
  • Once you enter the PSK, there are 4 to 6 counters to verify your documents.
  • On verification, you are assigned a unique token number. We’ll talk about this in a bit.
  • Token numbers are displayed on an electronic display-board. The board indicates which counter the person should go to. You are to wait in the waiting area and look at the display. You will soon be scheduled against a counter, where a PSK employee will help you with that particular stage of the process.
  • There are 3 stages in the process. The first is ‘Biometrics’ (Stage A). At this counter, the PSK employee collects your fingerprints and takes your photo. Your online form is updated with this information. There are 36 counters serving this stage (A-1, A-2 … A-36).
  • The second stage is ‘Form Check’ (Stage B). At this point, the PSK employee checks the details in your form. If he finds any problems, he will redirect you to the Corrections counter. During my visit, counters A-34, A-35 and A-36 were reserved for corrections. After corrections, you have to come back to this stage. There are 12 counters (B-1, B-2 … B-12).
  • The final stage is ‘Form Re-Check’ (Stage C). At this point, the PSK employee double-checks the work of the previous counters and takes your form. If there are any corrections you have to go back to the corrections counters and start again. Once the form is checked, your reissue request has been processed. You are free to leave the PSK and go home. There are 10 counters (C-1, C-2 … C-10).
  • Coming back to the token numbers. These are of the form N-10, S-4 etc. The alphabet represents the applicant category. These categories are as follows:
  • Normal (represented by N): Most people fall into this category.
  • Senior (represented by S): For people older than 60
  • Tatkal (represented by T): For people who want speedy processing of their passport (and have paid extra for this benefit)
  • Requiring Police Clearance (represented by P): People who need clearance from the police (probably because they have criminal records, or work in sensitive departments in the government).
  • Categories other than ‘Normal’ have a higher priority when it comes to processing their applications. For the purposes of this post, I assume that P has the highest priority, followed by S, T and N.
The working of the Passport Seva Kendra, illustrated by Bhargava Chowdary (@renderkid)

In the rest of this post, we’ll build this system as described above, and see if we can fix the flaw in it. We will use Clojure to write the solution. Clojure’s concurrency primitives are fantastic, and helped me model this system in an elegant and readable way. As we go along, I’ll explain these primitives in brief. Eric Normand has written an excellent guide to understanding concurrency primitives in Clojure, and Rich Hickey has a great talk about this as well. I highly recommend both these resources to the interested reader. The focus of this post will be on using these tools to implement a non-trivial system.

So what is the problem with the system?

First, let’s get the flaw out of the way. The problem with this system is that the applicant has no idea when he’ll be scheduled with an agent. He must keep staring at the display board. For example, if you are N-30 and stage A took a particularly long time for you, others have moved past you to the next stage (B and beyond). The display board may read that N-41, N-42 etc are at counters B-1, B-2 etc. However, this does not mean that N-30 will show up next. The display board may go all the way to N-60 before N-30 shows up. As there is no certainty about when your number will show up, you have no option but to continuously stare at the board. This gets really irritating after a while.

Here are some ways to deal with this problem:

  1. Instead of using simple queues between the stages, use a priority queue. This means that even if N-30 took a long time on stage A, and the board had moved on to N-40s and above for stage B, as soon as N-30 is done with stage A he will be moved to the top of the queue for B. In this way, the applicant can look at the board and always tell whether he’ll be up next or not.
  2. Generate new token numbers between each stage. This will give the applicant a clear idea of the number of people ahead of him at any given point in time.
  3. Provide the person with a new display board, where he can enter his token and see where he is in the queue for his stage.

We will see these in action in our simulation program.


Representing all the information about the PSK

Everything describing the behavior of the PSK can be captured in code. For our simulation, the data looks like this:

A description of all the knobs of the PSK

We use a simple map - stages - to represent all the stages in the PSK, the number of counters per stage, the amount of time per stage and the next stage after this one. A person is either waiting (looking at the display board), or is at a counter, or is done with a stage (done triggers a move to the next stage). From the point of view of the person, he is either waiting or at a counter.


Letting people into the PSK, and generating token numbers for them.

The first thing we will build is the token generator, and we’ll use the most intuitive Clojure concurrency primitive for this: the atom.

Clojure Concurrency Primitive — Atoms

Atoms are useful when reading / writing a single piece of data (potentially across multiple threads). This is the common case for shared resources and atoms are what I’ve used in most of the concurrency code I’ve written.

Generating a new token

Clojure provides something more powerful - the ref - when you want to deal with multiple pieces of data that change together. We’ll see it in action in the following sections.

If we choose some weights to represent the probability of an applicant belonging to a certain category, we can write some code to randomly generate applicants. The relevant code is here. We now have a way to assign increasing token numbers to each new person entering the PSK.

Clojure Concurrency Primitive — Futures

We’ll use another Clojure concurrency primitive — a future - to continuously move people into the PSK. A future object invokes the body provided to it in a different thread.

In this case, we are starting an endless loop in a new thread. This code creates some people (representing people entering the PSK), sleeps for a bit, then repeats. We’ll use our handy tool — an atom — to control when to stop the loop:

Send new people in every 15 mins

Queuing up people and simulating the work done at every stage

Now that people are coming into the PSK, we need a way to queue them up between stages. We also want to write a simulation for the work done at every counter. As described in the problem statement, the PSK is using simple FIFO queues between each stage. We will use the LinkedBlockingQueue data structure to represent these. This data structure is provided by the battle-tested java.util.concurrent package. Dropping down to Java when needed is a bonus Clojure superpower!

Linked Blocking Queues for every stage that needs one.

Work at the counter involves the following:

  1. Pick the next person in the queue.
  2. Call him to the counter by displaying his token number on the display.
  3. Process the person, do the work.
  4. Mark this stage as done. This will move him into the next queue.

We can represent this in code as follows:

Do the work at the given stage.

As we saw previously, we control the running of the code using the working-hours? atom. We’re seeing something new here - the send-off function used with Clojure Agents. Ignore this for the time being, we’ll come to an explanation of this after seeing refs and transactions.


Keeping track of people and the display board

The tough part of this project is to keep track of the changes to each person’s current state and the display board at every instant. These two views should always be consistent as multiple people are concurrently processed at different stages. Clojure makes this delightfully easy with refs and transactions.

Clojure Concurrency Primitive — Refs (and transactions)

Refs can be thought of as permanent pointers to mutable storage locations. The stored values can be safely changed — all together or none at all — using the functions alter, ref-set and commute within transactions. Clojure implements a Software Transactional Memory system and gives us A,C, and I of the famous ACID properties. (Since it’s in-mem there is no Durability). Using these transactions in code will be familiar to anyone with experience of using DB transactions.

In practice, updating values looks like this:

Refs: thinking about concurrent code just got easier.

Look Ma, no locks! This is much simpler, in my opinion, than thinking about which lock to take around which piece of data. Let’s also check out the store-state-change function in the code above. This is a small data-collection function I wrote to calculate statistics about how much time each person takes in each stage.

Record changes in stages / processing status of a stage.

Writing this function is simple: we know we want to modify an existing person, so we wrap it in a transaction. The calling code happens to already be in a transaction, but Clojure will deal with this correctly and collapse all the work into a single transaction. From our point of view, we know that anytime this function is called, it is going to safely and permanently modify the person and store the stage-change in it.


Processing people concurrently across all open counters

The final piece of the puzzle is concurrently processing people on all the available counters. This is straightforward to do against a thread-pool, but Clojure provides another tool we can use: the agent .

Clojure Concurrency Primitive — Agents

Agents are another way to access/change mutable state, but they do this in an asynchronous manner. The functions send and send-off apply actions (functions) to the value held by the agent. The return value of the action becomes the new value of the agent. However, these actions execute in a different thread asynchronously. Clojure also guarantees execution in the order of submission. The value of the agent is inspectable at all times.

In our case, this allows us to represent processing counters as agents. The state of the agent is simply an identifier for it. Under the hood, each agent is spawning a thread from a thread-pool and executing a function. This function pulls the next person from the queue supplied to it, processes him, and sends another action to the current agent. We saw this function already, but let me post it again for clarity:

send-off dispatches a new action to the current agent

We create Agents as follows:

Creating Clojure Agents to do the processing work of the PSK

Tying everything together — the main function

We tie all the pieces of the code together in our main function start-the-kendra!. The comments explain what each step is doing, for those of you unfamiliar with Clojure syntax.

The Kendra does a wonderful job during working hours.

We haven’t seen the move-people-through helper function used above yet. This is a simple future which regularly sweeps through all the people and moves a person done with one stage to the other.

Originally, I wrote the code such that each agent was aware of an input queue as well as an output queue. The agent understood that he had to pick the next person from the input queue and move that person to the output queue on completion. I refactored that out to show that it is simple to add functions around existing concurrent code which modify existing shared resources. The code for move-people-through looks like this:

Guide people to the next stage of processing.

Both mark-applicant-process-as-complete and move-applicant-to-next-stage are tiny transactional updates to the person:

Small, understandable, testable functions are a big win.

I also added a book-keeping function when letting people into the PSK. This function removes completed applicants from the list of active applicants. This frees up PSK capacity. I also move this data to a different list, because it’s fun to go through it and look for interesting insights.

Book Keeping for the PSK.

Here we use the ref-set and alter functions to reset the value of active-applicants and modify the value of the done-applicants.


With me so far? Some thoughts

  • Clojure’s concurrency primitives make it simple for me to think about this problem. I wrote the code like I would write a high-level pseudo description of the problem, and it worked just fine. I think this simplification is a huge benefit when dealing with concurrent code.
  • The ability to write and test small bits of concurrent code is a big win. It was simple for me to modify the original code and devise experiments around it.
  • We haven’t really looked at what this looks like when it’s running! Let’s do that now!

Can we see the problem?

Let’s run this system! We’re setting up a small loop to display the board. We’re running much fewer counters than the actual PSK. This is in order to make the display board consumable.

A normal day at the Passport Seva Kendra

Things look good in this loop, the board looks predictable. The problem occurs when someone gets unlucky at one stage, and spends much more time there than the average person. Let’s repeat the run by marking someone as unlucky, and by increasing the number of counters processing earlier stages (which matches with reality)

Hello you unlucky person!

Here is what this looks like:

N-3 is not having a good day.

As you can see, there are a number of people ahead of N-3 by the time he’s done with stage 0. N-40s are being processed in stage 0 at this point in time. He has no idea where he is in the queue of people, and must keep staring at the display board at all times.

I will speak briefly about the three solutions that we initially proposed.

Solution 1: Use priority queues

Using priority queues between each stage solves the problem of the applicant not knowing when he is next. However, there are two points to think about:

  1. The priority queue solves the problem within a given category, but not across categories. You know that you are the next N- category person at counter B, but you don’t know when that will be because of all the S/T/P category people that will be served first.
  2. A potential drawback of this may be: if a certain set of applicants are always slow at each stage, then in this model they will bring down the average number of people who will be served by the PSK (since we will prioritize serving them over people who have moved ahead of them).

Making the change to use priority queues in our code is trivial. We go back to java.util.concurrent and swap out our LinkedBlockingQueue in favor of a PriorityBlockingQueue. Now all we have to do is provide a comparator function. The code for this is here We can also generate timing samples across people through repeated runs of the program. This will give us an idea of whether the average processing time is affected by using a Priority Queue or not.

Solution 2: New token numbers per stage

Using new token numbers solves the problem elegantly. This is probably not used because of the logistical difficulty of handing out new tokens to applicants again and again. In the real world, I’m sure that this process may cause confusion if not carefully designed. In our system, we already have a perfectly good way of getting the next token number — our atomic token generator. Implementing this solution is straight-forward and left as an exercise for the reader! (This blog post is already quite lengthy!)

Solution 3: “Where am I?” Estimated Wait Time

Another way the PSK can help the applicants is by providing a separate self-serve display. The applicant enters his token number and gets to see how many people are ahead of him for the given stage. Both LinkedBlockingQueue as well as PriorityBlockingQueue provide a toArray function which returns all the elements of the queue in order.

As we are tracking the time each person takes at each stage, we can also predict the estimated amount of time this person would have to wait. This could be an entire blog-post in itself (Look up Queueing Theory in case you are interested)

I leave this as an exercise for the reader :)


Final Thoughts

The complete code for this exercise can be found here. The comment block at the end of the gist explains how to run the program against a Clojure REPL. Note that this is not a trivial simulation of the PSK, I believe that the entire code can be actually used by them with a small set of changes. A list of things that we have not implemented:

  1. In the real world, we’d need to store each person’s information in a DB along the way. Since the in-mem structures are guaranteed to be consistent, this is something we can achieve by periodically reading information about all applicants and committing it to the DB (similar to how book-keeping-for-applicants works).
  2. We haven’t implemented the error and corrections flow. Failure to pass a stage can be represented as another state (say ::error). The process-applicant code will identify success/failure of the stage and set the appropriate state. move-people-through would need minor changes to deal with this. I leave this as an exercise for the reader.
  3. In the real world, we’d need to build inputs for a real PSK employee to inform us that processing is done. This is nothing but a loop inside process-applicant which checks the DB to see if the work is done.

I’d love to hear feedback about this post. Is there a better way to implement this? Tell me. Am I missing use-cases of the PSK and implementing a solution to a much simpler problem? Do tell! There may be drawbacks to solutions I’ve proposed that I cannot see, and there may be valid reasons the system is built the way it is. I’d love to understand the real-world problems that I’ve missed.

If you’re interested in working with Clojure, on problems like Estimated Wait Time, we’re hiring! Send us an email at jobs@helpshift.com.


A big thank you to the following people for reviewing initial drafts of this post: Kapil Reddy, Kiran Kulkarni, Mourjo Sen, Suvrat Apte, Dinesh Chhatani.

A big thank you to Bhargava Chowdary for creating the illustration of the Passport Seva Kendra.

References