Transactions are great. They keep your data together atomically, so you’re not in for any nasty surprises. But even a novice knows better than to leave transactions open, waiting for user interaction. If you do, lock waits and probably deadlocks will pile up in no time.
So how do you book a flight without blocking all the other users or losing your seat to somebody else while you make up your mind?
The answer is that you try to find a way to handle the transactions yourself. And because a typical booking system for an airline or a train business has to manage a large amount of simultaneous connections and a huge number of bookings, you’ll also have to try to keep each individual statement as fast as possible.
Suppose we have an overly simplified example airline with a bunch of flights, each with a number of seats in three cabin classes. To complicate things further, each cabin class offers two different price levels.
Here’s the table where we collect all the bookings.
CREATE TABLE dbo.seats ( flight int NOT NULL, seat int NOT NULL, bookingClass tinyint NOT NULL, price numeric(8, 2) NOT NULL, [state] tinyint NOT NULL, passenger int NULL, lockedDate datetime NULL, PRIMARY KEY CLUSTERED (flight, seat) );
Let’s add some sample data to the table. I’m going to go with 3000 flights with 250 seats each. Booking class 1 (“business”) has 20 seats, class 2 (“premium economy”) has 30, and finally there are 200 economy seats.
WITH n (i) AS (SELECT 1 AS i UNION ALL SELECT i+1 FROM n WHERE i<10000) INSERT INTO dbo.seats (flight, seat, bookingClass, price, [state]) SELECT f.i AS flight, s.i AS seat, p.bookingClass, p.i AS price, 0 AS [state] FROM n AS s INNER JOIN n AS f ON f.i<3000 AND s.i<250 CROSS APPLY ( SELECT (CASE WHEN s.i<20 THEN 1 WHEN s.i<50 THEN 2 ELSE 3 END) AS bookingClass, (CASE WHEN s.i<10 THEN 1000 WHEN s.i<20 THEN 900 WHEN s.i<35 THEN 600 WHEN s.i<50 THEN 500 WHEN s.i<200 THEN 100 ELSE 80 END) AS i) AS p OPTION (MAXRECURSION 0);
You will have noticed the state column. The state column in this solution is used to define where in the booking process a given booking (a row in the table) is. State 0 means that the seat is available, state 1 is a preliminary booking, which means that somebody is looking at this seat and trying to make up their mind. Finally, state 2 means that the purchase is complete and the seat has been allocated.
If you were to compare this to traditional database transactions, you could say that state 0 is an “unstarted” transaction. State 1 is a current, open transaction and state 2 is committed. If a transaction is rolled back, the row naturally goes back to state 0.
The state column solves the SQL transaction problem for us – by marking a row as “in progress”, other processes will know not to touch that seat until we’ve made up our mind. If you were to book a seat in a SQL transaction, on the other hand, that table record would be blocking other processes until you’ve completed and committed the transaction (i.e. entered names, credit card details, your frequent flyer number, etc).
To speed things up a bit, I’m going to add two additional indexes to the table. You’ll see later on in the code what they do.
CREATE INDEX IX_seats_available ON dbo.seats (flight, bookingClass, price) INCLUDE (seat) WHERE [state]=0; CREATE UNIQUE INDEX IX_seats_timeout ON dbo.seats (lockedDate, flight, seat) WHERE [state]=1;
Creating preliminary bookings
In a high-load scenario, we want to keep the footprint of each operation to a bare minimum. Even when you run a single statement, without a SQL transaction, this operation will still aquire locks to complete its operation. Your job is to keep those locks to a minimum, because they can keep other processes waiting.
Keeping execution time to minimum means optimizing all the indexes, eliminating JOINs and sorts, among other costly operations.
The probably toughest challenge in this solution is the process of finding the cheapest seat for a given flight and booking class, and reserving it. The index “IX_seats_available” is specifically tailored for this purpose. It only includes available seats (WHERE state=0), and it’s ordered by flight, bookingClass and price (ascending, i.e. lowest price first). This means you can perform an index seek.
We can use this index to perform an UPDATE on a single row that matches our criteria. Here’s the stored procedure:
CREATE PROCEDURE dbo.seatPreliminary @flight int, @bookingClass tinyint, @passenger int, --- OUTPUT variables are returned to the caller: @seat int=NULL OUTPUT, @price numeric(8, 2)=NULL OUTPUT AS SET NOCOUNT ON; --- This table variable is designed to capture the OUTPUT of --- the UPDATE statement, so we can return the relevant --- data to the user. DECLARE @row TABLE ( seat int NOT NULL, price numeric(8, 2) NOT NULL ); --- Update the state on a single seat: UPDATE s SET s.[state]=1, s.passenger=@passenger, s.lockedDate=GETDATE() --- ... and OUTPUT the price and seat number: OUTPUT inserted.seat, inserted.price INTO @row (seat, price) FROM (SELECT TOP (1) seat, price, [state], lockedDate, passenger FROM dbo.seats --- ... using the index we've custom-built for this purpose: WITH (INDEX=IX_seats_available, ROWLOCK) WHERE flight=@flight AND bookingClass=@bookingClass AND [state]=0 ORDER BY price ) AS s WHERE s.flight=@flight AND s.bookingClass=@bookingClass AND s.[state]=0 --- Return preliminary seat and price to caller: SELECT @seat=seat, @price=price FROM @row;
You could use just UPDATE TOP (1) on the table with the same index hint, instead of the subquery construct, but the order of UPDATE TOP() isn’t guaranteed according to the product documentation. The code above is just as efficient, but maybe a tad less pretty to look at, but I can live with that.
Committing or cancelling a booking
Once we’ve created a preliminary booking, we don’t need to keep a lock on the row (or even a connection to the database). When the user has decided to complete or cancel his purchase, we’ll just go back and update the state column again.
For this, we’re using two stored procedures. One to “commit”:
CREATE PROCEDURE dbo.seatDefinitive @flight int, @seat int, @passenger int AS SET NOCOUNT ON; --- Finalize the reservation: UPDATE dbo.seats SET [state]=2, lockedDate=NULL --- ... but only if it's still yours to take and --- in the "preliminary" state. WHERE flight=@flight AND seat=@seat AND [state]=1 AND passenger=@passenger; --- If the rowcount is zero, that means that the preliminary --- booking wasn't there anymore: IF (@@ROWCOUNT=0) THROW 50000, 'Seat not available or timed out', 1;
and one to “roll back”:
CREATE PROCEDURE dbo.seatCancel @flight int, @seat int, @passenger int AS SET NOCOUNT ON; --- Cancel the reservation: UPDATE dbo.seats SET [state]=0, lockedDate=NULL, passenger=NULL WHERE flight=@flight AND seat=@seat AND --- ... but only if it's still yours to cancel: [state]=1 AND passenger=@passenger;
Whenever you’re storing states in a relational database like this, it’s just a matter of time before you get orphaned bookings in the table. If, for instance, your web server shuts down unexpectedly, any preliminary transactions you have won’t be either committed nor cancelled. For this, you’re going to need some type of clean-up job that runs periodically.
CREATE PROCEDURE dbo.seatCleanup @timeout_s int=300 --- Timeout, in seconds. AS SET NOCOUNT ON; --- Auto-cleanup untouched preliminary bookings that have timed out. UPDATE dbo.seats SET [state]=0, lockedDate=NULL WHERE [state]=1 AND lockedDate<DATEADD(ss, 0-@timeout_s, GETDATE());
This procedure makes use of the “IX_seats_timeout” index, so it should generate a really effective execution plan. It can be run using SQL Server Agent or another scheduling process of your choice.
The whole booking chain
Here’s the whole booking process, from start to finish: User looks for an available seat in premium economy:
DECLARE @seat int, @price numeric(8, 2); EXECUTE dbo.seatPreliminary @flight=104, @bookingClass=2, @passenger=57, @seat=@seat OUTPUT, @price=@price OUTPUT;
The procedure returns @seat=35, @price=500.00.
To book this seat, the following command is issued:
EXECUTE dbo.seatDefinitive @flight=104, @seat=35, @passenger=57;
Or, to cancel the booking:
EXECUTE dbo.seatCancel @flight=104, @seat=35, @passenger=57;
Testing on my desktop machine, performance for each of these procedure calls was pretty good, with execution times in the range of 1-5 ms. In theory, you should probably be able to run a hundred or so concurrent users with this solution. In the real world, of course, the data is going to be a bit more complex, and there are going to be a lot more rows in the table, but there will of course also be considerably more server hardware to go around.
Let me know if there’s anything missing or unclear. See you next week!