47

In the movie theatre I go to they have ticket kiosks that allow you to select the seats you want; they also have a website that does the same (the website also has a countdown timer of like 30 secs in which you must choose a seat).

While I understand things such as database transactions and other techniques for handling multiple simultaneous users, I just can't get my head around how multiple people can be allowed to select a seat at the same time; is it as simple as the first one to press BUY gets the seats and the other person will get an error message, or am I missing something?

Mike Partridge
  • 6,587
  • 1
  • 25
  • 39
mbwasi
  • 581
  • 1
  • 4
  • 5
  • 11
    "is it as simple as the first one to press BUY gets the seats and the other person will get an error message". That. – yannis Nov 03 '11 at 09:38
  • 2
    Yeah probably, on a bussy day with like a dozen machines seems like that would be a pain though. – mbwasi Nov 03 '11 at 09:48
  • 2
    Perhaps, but keep in mind that users will be spending the majority of their time on other screens (entering payment details, waiting for tickets to print, etc.), so they won't all be picking seats at the same time, and not everyone has the same seat preferences, so even those who are picking at the same time will likely pick different seats. I wouldn't expect there to be all that many collisions. – Dave Sherohman Nov 03 '11 at 10:22
  • Learning the concept of race conditions might help. Here's an article that uses a database example: http://www.celticwolf.com/blog/2010/04/27/what-is-a-race-condition It shows a high level view of how transactional DB's may handle this. – Chris C Nov 03 '11 at 20:07
  • @Yannis Rizos: No, it's not. See the answers below. – Jim G. Nov 03 '11 at 20:08
  • 2
    @JimG. For every possible solution, if both customers press buy at the exact same time (to the millisecond) one will get served and the other will get some sort of error message. There are beautiful ways to minimize the chance of that happening (technical and conceptual, as explained in the answers) but in the extraordinary situation it does happen then one request will be served and the other will fail. As simple as that. – yannis Nov 03 '11 at 20:38
  • I had this happen to me just now trying to book a doctor's appointment. "We have an appointment at xx:xx. Your name? Oh wait, it's now taken. How about yy:yy?" – Hand-E-Food Nov 03 '11 at 22:36
  • @Yannis Rizos: That's great if your employer tolerates that type of behavior, but do you think that Fandango.com would tolerate that? ;) – Jim G. Nov 03 '11 at 22:52
  • 3
    @JimG. It's not a type of behavior. Concurrency works to a point, if both requests reach at the exact same microtime, one will fail. You can of course build a nice error message around that, as in Hand-E-Food's comment, but the fact remains: It's as simple as serving one request and failing the other. I'm not saying you shouldn't do everything to ensure that failing is as user friendly as it can be or that you shouldn't safeguard around it. – yannis Nov 03 '11 at 23:00

5 Answers5

34

The classic method to do this is to use a transactional database (so there's no clashes) and to do a tentative allocation of the seat to you that expires after some length of time (e.g., 10 minutes for kiosks) that gives you enough time to pay. If the (customer-visible) transaction falls through or times out, the seat allocation can be released back into the pool. (All state changes are processed via the transactional database, and one customer-visible transaction might require many database-level transactions.)

Airlines will use a similar system (though much more complex due to the need to handle multiple flight legs!) for booking seats online. I would imagine that the timeout would be considerably longer; airline tickets are usually booked further ahead than movie tickets, and are more expensive as well.

Donal Fellows
  • 6,347
  • 25
  • 35
  • Mind you, my local movie theater doesn't actually allocate seats normally. Instead, they over-provisioned the seats so that people can just turn up with minimal fuss. It's a different technique, but not one relevant to your question! – Donal Fellows Nov 03 '11 at 11:13
  • Similar to picking seats for sporting events. You get your N number of seats reserved for 3 minutes while you decide if you actually want them and complete the payment. – AndyMcKenna Nov 03 '11 at 12:24
  • Note that there are two different processes with, for instance, buying airline seats: first, you buy a ticket without a seat allocated. Second, when you get your boarding pass (or if you check in online) then you get a seat. The number of tickets are actually oversold because they know that, on average, a certain number don't show up for the flight. Seat allocation, however, seems to work by randomly assigning you a seat (first-come-first-serve) when you check in, and then allowing you to change the seat by picking an available one, then doing the transfer in a single transaction. – Scott Whitlock Nov 03 '11 at 12:56
  • @Scott: Depends. They're a lot more cautious with international flights where the consequences of being denied boarding will be much more dire. (I've never seen an international flight with standby ticket arrangements.) The process of committing a multi-hop multi-airline international flight must be horribly complicated, what with the fact that it's not just airlines but also governments that like to know exactly what's going on… – Donal Fellows Nov 03 '11 at 14:48
  • And the classic "dire consequence" of being denied boarding is where it causes someone's 48-hour transit visa to expire because their flight only happens twice a week. I've seen it take ages to sort those sorts of problems out (alas; I was queueing behind them at the same rebooking desk). – Donal Fellows Nov 03 '11 at 14:49
  • 2
    @DonalFellows could you explain the tentative allocation part a bit more? Do you mean reserving some seats for a user for some period of time? I am still trying to get a hang of challenges faced in this type of system. – Sandeepan Nath Jul 23 '16 at 06:24
  • 2
    @SandeepanNath Not properly in a comment, but the principle is trivial. The seat is put into a “tentatively allocated” state, and the timeout of that state is noted at the same time. If the booking is completed, the seat becomes fully allocated. If not and the timeout is reached, the seat is (eventually) moved back into the main pool. (Also, if the user _explicitly_ cancels then the seat is moved directly back into the pool. No need to wait.) – Donal Fellows Jan 18 '19 at 12:55
  • @DonalFellows What if the `tentative allocation` for the last seat happens for two people at the exact same time? It looks like instead of letting the DB rollback one of the transactions we have moved some locking mechanism to the application layer but I don't think it is full proof. Two tentative allocations at the exact same time from the application layer has as much chance of reaching the database as in the case if there were no tentative allocations at all and it was free game. The DB can obviously fail one of the transactions considering Isolation of ACID. How/Why is this better? – piepi Jan 06 '21 at 00:41
6

The 30 seconds you have seen are nowadays often more like 15 mins. I don't believe there is a database transaction active for that duration.

If I was to design such a system, this is how I would do it: Have the business objects Booking and Reservation. Bookings are essentially confirmed (i.e. paid) reservations. I would store them in the same DB table and distinguish by an attribute or two.

When fetching available seats, you would query both bookings and reservations.

When someone selects a seat, you create a new reservation, thus showing other customers the seat as taken. A second reservation for the same seat will be declined - the DB update or insert will fail. If the customer confirms/pays for the reservation, you transition it to a booking. In a periodic batch job you delete all reservations older than 15 mins (or whatever time you give your customers).

Hubert Grzeskowiak
  • 250
  • 4
  • 9
  • +1 I like the idea of having separate objects for temporary vs. final. – Christophe Dec 13 '20 at 22:58
  • This design helps in rolling back some payment already done. But how would it prevent two people from booking the same ticket? If two people do Booking at the exact same time for the last ticket, who gets the seat? – piepi Jan 19 '21 at 19:56
5

There are at least 2 business processes involved here.

  • Process one:

Show available seats.

  • Process two:

Book a selected seat.

Since these processes don't follow one another immoderately, and since 2 people may select the same seat the concurrency issue arises.

If your database design assigns the correct uniqueness constraint so that the combination of:

-TheaterID

-SeatID

-EventID

are unique, then the database will prevent duplicates.

The following scenario is also possible but will be taken care of by the above suggested implementation:

Assuming a grid view of available for a given theater and a given event can be displayed:

  1. User1 displays available seats (and gets seats 1 and 2)
  2. User2 displays available seats (and gets seats 1 and 2)
  3. User1 talks a bit with the customer on the phone
  4. User2 goes and books seat 2 for his customer
  5. User1 tries to book seat 2 for his customer (because it shows as available on his screen)
  6. The unique index prevents step 5 from commuting the data.

So all what you need to do may be nothing more correct database design and proper choice on constraints.

Other more complex approaches are possible if you want, using transaction queues. In this case, requests are written first to a queue then fires a process every n seconds but that is hardly necessary or practical in your case.

The really interesting part is what should the list grid for user 1 show?

NoChance
  • 12,412
  • 1
  • 22
  • 39
1

It goes with the database ACID property - Isolation. The database uses locks on the data to avoid concurrent modification of the data.

http://en.wikipedia.org/wiki/Isolation_%28database_systems%29

user841923
  • 251
  • 1
  • 2
  • 10
1

You can avoid the race condition if you delay allocating specific seats.

  1. Collect seating preferences from customer (number of seats, price, area of theatre, adjacent seats mandatory, etc...)
  2. Save the requested seating preferences in a queue
  3. One-by-one seating requests are pulled from queue, seats allocated according to preference and the booking completed if seats found.
  4. If booking completed, notify customers and mail tickets; otherwise, notify customer that no tickets matched preferences.
Ed James
  • 1,351
  • 1
  • 10
  • 14