Ticket lottery design and shuffling algorithm

As a part of a technical challenge, I was asked to describe how to implement a digital lottery system for ticket purchasers. I have very little knowledge of system design, so I did a lot of research into potential technologies.

But before I dug into the specs, I wanted to consider the variables in play, though, admittedly, I’m unsure how best to handle all of them. Items of note: the number of prospective users (traffic), lottery window, number of tickets offered and are they all discounted, is a payment method required prior to entering the lottery, and most importantly — in my mind — how and where is the data stored, both for the ticket issuer and for the partnering theaters.

With the intention of keeping the digital lottery system quick, user-friendly, reliable, and secure, there are a number of ideal features. Asynchronous processing is important because of the high volume of requests being made for in-demand tickets. Without some sort of delay, one user might end up buying tickets someone has in their cart already. The idea of high-volume processing led me down the path of event streaming and how it works in conjunction with or apart from traditional database querying.

In a 2019 blog post on the IBM website, Alan Chatt, Offering Manager for IBM Event Streams & Kafka, said “A simple way to think about it is that event streaming enables companies to analyze data that pertains to an event and respond to that event in real time.” The “event” could be a button push, form submission, transaction, anything. You can see how this would be important with something like the digital lottery because the information regarding entries would need to be precise and constantly updating.

Event streaming is a way of making what would have previously been individual database changes into a log of all events. Using a checkout cart as an example, you might have in the past needed to make a change to the database every time you added or removed an item from the cart. Ultimately, though, the database will show the final decision. With event streaming, you would instead have a log of all cart events and not just the ultimate outcome. That log can be broken down later for more specific information and cataloging. An argument for this sort of storage is that immutable data is better for error handling, i.e. you have the whole log of events, rather than snippets.

The most popular service for event streaming is Apache Kafka. Kafka or a similar stream processing service could handle the queue of ticket requests. The user could make an API post request for the lottery entry. That submission would need to contain a promotional id specific to the show, date, and time, as well as a transaction id, ideally a universally unique identifier (UUID) specific to the user. The JSON response could be as simple as a boolean whether the ticket is a “win” or “loss” or an integer response, i.e. 0 for win, 1 for no win, 2 for lottery has closed. Regarding security, these requests should also contain unique session ids and I.P. address logs to limit the number of requests coming from one or a small number of users.

The above are considerations to make for the overall system, but as far as the method of choosing “winners” there are a variety of options. The discussion of sorting algorithms and how they could be be implemented is far too large of a discussion to have here. So instead of analyzing them all, I chose an algorithm I find interesting. It would not necessarily be the fastest method, but it would be fair. The Fisher-Yates Shuffle algorithm, which works like shuffling a deck of cards, would guarantee an unbiased permutation and reliable fairness given to all those who enter the drawing, as their position in the array of ticket holders would be shuffled and could therefore be selected at random.

Here is the algorithm demonstrated in JavaScript:

In this code, a loop is set to decrement currentIndex until it reaches the zero position. The variable randNum generates a new, random value between 0 and currentIndex with every pass of the loop. The temp variable first represents the random index position’s value. Then, you take the array at the random index and swap it for the value at the index position of the loop.

Next, the index position of the loop passing — currentIndex — is targeted and swapped for the temporary value.

Using this algorithm, the result is a unique array every time. You could pick a “winner” to receive a ticket by selecting the first user identified in the array (or at whatever index you want), then reshuffle and pick another user until you have gotten to the allotted number of tickets.