Performance in the Post Office

Today I was tasked with going out to the post office to pay the monthly bills. The post offices here are setup to accept payment. The branch that I went to has about 15 different windows that each offer some combination of services. The process is quite simple, find the windows that offer the service that you looking for, select a line and wait. And sometimes you wait.. and wait.. and wait.

How long do you have to wait? Well that depends on how long it takes to provide service for the people standing in front of you. And, it also depends upon the server actually staying put. If the clerk walks off or closes the window, you either wait or find another line. If a new window opens up you'll find people rushing to get to the front of the new line. What we are looking at here is effectively a round-robin queuing system with some semblance of load-balancing. After all people are not dumb processes and will jump queues if they think they see a better deal.

However what happens in systems where the entities being served are not people? In those cases your ability to gain service in this type of system is at the mercy of the system. Without some feedback and ability to react to change, some queues will grow while other may remain empty. Just as it takes much more time for people to clear the post office (on average) using this type of system, it also affects the ability of an application to provide timely service to it's clients.

The problem with this system runs deeper then its effects on the clients. It also hardens (ie. makes the system more fragile) the servers ability to be adaptive. To illustrate this point let us consider an alternative scheme.

An alternative scheme one can use is to setup a single queue to feed all of the servers. This eliminates the need to load-balance the system and it also means that management can add and remove servers from the system without disrupting the FIFO nature that we have all come to expect. As a client in a single queue multiple server system, I no longer care so much if one clerk disappears as the overall impact on me will be minimal. From the managers perspective he has to face far fewer glares from angry people when he decides to close a window. So by moving to this single queue multiple server system we have increased fairness and increased flexibility. Has all of this come for free? The answer to that question hit me hard while waiting in line to get a boarding pass to a United Airlines flight a while ago.

The first thing is that in a single queue multiple server system, all servers must be homogeneous. In other words, no matter what the client needs, all servers must be able to complete the task at hand. The second point is that by putting all clients in a single queue you have given everyone equal priority. Airlines recognized that their ticketing clerks essentially offered a homogenous service and turned from offering lines per destination to a single queue for all destinations.

Though a single queue can be desirable it can also have the undesired side-effect of leaving higher priority items wanting for service. For example, I missed my flight because I just missed getting through the queue in time to meet the deadline to get my boarding card. Airlines do provide priority queues but unfortunately priority is based on other critera that I didn't meet on UA :-). Also the clerks in the post office are all specialized to handle a small set of services which makes it difficult for them to implement a single queue system.

The implication of this mashup of post office, airport, bank, and all the other types of queues that we have in our everyday life is that they can give us lessons that we can use when we make design decisions in our role as developers. The biggest lession is that your choice of how you implement queues into your system can have some interesting down-stream effects that go beyond the client. Your choice can actually effect your ability to adapt a system to changing conditions. It also illustrates the point that round-robin is not load balancing, its load distribution. RR maybe good enough for your needs, however.....

tags: performance  java  queues