Strategy for concurrent group bookings?

Question

Consider a seat booking database. There is a list of n seats, and each one has an attribute is_booked. 0 means it isn't, 1 means it is. Any higher number and there is an overbooking.

What is the strategy for having multiple transactions (where each transaction will book a group of y seats concurrently) without allowing over bookings?

I would simply select all unbooked seats, select a randomly selected group of y of them, book them all, and check if that booking is correct (aka the number of is_booked is not over one, which would signify another transaction having booked the seat and committed), then commit. otherwise abort and try again.

This is run at isolation level Read Committed in Postgres.

Answer 1

Because you're not telling us much of what you need, I'll guess for everything, and we'll make it moderately complex to simplify some of the possible questions.

First thing about MVCC is that in a highly concurrent system you want to avoid table locking. As a general rule, you can't tell what does not exist without locking the table for the transaction. That leaves you one option: don't rely on INSERT.

I leave very little as an exercise for a real booking app here. We don't handle,

• Overbooking (as a feature)
• Or what to do if there are not x-remaining seats.
• Buildout to customer and transaction.

The key here is in the UPDATE. We lock only the rows for UPDATE before the transaction starts. We can do this because we've inserted all seat-tickets for sale in the table, event_venue_seats.

Create a basic schema

CREATE SCHEMA booking;
CREATE TABLE booking.venue (
  venueid    serial PRIMARY KEY,
  venue_name text   NOT NULL
  -- stuff
);
CREATE TABLE booking.seats (
  seatid        serial PRIMARY KEY,
  venueid       int    REFERENCES booking.venue,
  seatnum       int,
  special_notes text,
  UNIQUE (venueid, seatnum)
  --stuff
);
CREATE TABLE booking.event (
  eventid         serial     PRIMARY KEY,
  event_name      text,
  event_timestamp timestamp  NOT NULL
  --stuff
);
CREATE TABLE booking.event_venue_seats (
  eventid    int     REFERENCES booking.event,
  seatid     int     REFERENCES booking.seats,
  txnid      int,
  customerid int,
  PRIMARY KEY (eventid, seatid)
);

Test Data

INSERT INTO booking.venue (venue_name)
VALUES ('Madison Square Garden');

INSERT INTO booking.seats (venueid, seatnum)
SELECT venueid, s
FROM booking.venue
  CROSS JOIN generate_series(1,42) AS s;

INSERT INTO booking.event (event_name, event_timestamp)
VALUES ('Evan Birthday Bash', now());

-- INSERT all the possible seat permutations for the first event
INSERT INTO booking.event_venue_seats (eventid,seatid)
SELECT eventid, seatid
FROM booking.seats
INNER JOIN booking.venue
  USING (venueid)
INNER JOIN booking.event
  ON (eventid = 1);

And now for the Booking Transaction

Now we have the eventid hard coded to one, you should set this to whatever event you want, customerid and txnid essentially make the seat reserved and tell you who did it. The FOR UPDATE is key. Those rows are locked during the update.

UPDATE booking.event_venue_seats
SET customerid = 1,
  txnid = 1
FROM (
  SELECT eventid, seatid
  FROM booking.event_venue_seats
  JOIN booking.seats
    USING (seatid)
  INNER JOIN booking.venue
    USING (venueid)
  INNER JOIN booking.event
    USING (eventid)
  WHERE txnid IS NULL
    AND customerid IS NULL
    -- for which event
    AND eventid = 1
  OFFSET 0 ROWS
  -- how many seats do you want? (they're all locked)
  FETCH NEXT 7 ROWS ONLY
  FOR UPDATE
) AS t
WHERE
  event_venue_seats.seatid = t.seatid
  AND event_venue_seats.eventid = t.eventid;

Updates

For timed reservations

You would use a timed reservation. Like when you buy tickets for a concert, you have M minutes to confirm the booking, or someone else gets the chance – Neil McGuigan 19 mins ago

What you would do here is set the booking.event_venue_seats.txnid as

txnid int REFERENCES transactions ON DELETE SET NULL

The second the user reserves the seet, the UPDATE puts in the txnid. Your transaction table looks something like this.

CREATE TABLE transactions (
  txnid       serial PRIMARY KEY,
  txn_start   timestamp DEFAULT now(),
  txn_expire  timestamp DEFAULT now() + '5 minutes'
);

Then in every minute you run

DELETE FROM transactions
WHERE txn_expire < now()

You can prompt the user to extend the timer when nearing expiration. Or, just let it delete the txnid and cascade down freeing up the seats.

Answer 2

1s approach - Single UPDATE:

UPDATE seats
SET is_booked = is_booked + 1
WHERE seat_id IN
(SELECT seat_id FROM seats WHERE is_booked = 0 LIMIT y);

2nd approach - LOOP (plpgsql):

v_counter:= 0;
WHILE v_counter < y LOOP
  SELECT seat_id INTO STRICT v_seat_id FROM seats WHERE is_booked = 0 LIMIT 1;
  UPDATE seats SET is_booked = 1 WHERE seat_id = v_seat_id AND is_booked = 0;
  GET DIAGNOSTICS v_rowcount = ROW_COUNT;
  IF v_rowcount > 0 THEN v_counter:= v_counter + 1; END IF;
END LOOP;

3rd approach - Queue table:

The transactions themselves don't update the seats table. They all INSERT their requests into a queue table.
A separate process takes all requests from the queue table and handles them, by allocating seats to requesters.

Advantages:
- By using INSERT, locking/contention is eliminated
- No overbooking is ensured by using a single process for seat allocation

Disadvantages:
- Seat allocation is not immediate

Answer 3

I think this can be accomplished by the use of a little fancy double table and some constraints.

Let's start by some (not fully normalized) structure:

/* Everything goes to one schema... */
CREATE SCHEMA bookings ;
SET search_path = bookings ;

/* A table for theatre sessions (or events, or ...) */
CREATE TABLE sessions
(
    session_id integer /* serial */ PRIMARY KEY,
    session_theater TEXT NOT NULL,   /* Should be normalized */
    session_timestamp TIMESTAMP WITH TIME ZONE NOT NULL,
    performance_name TEXT,           /* Should be normalized */
    UNIQUE (session_theater, session_timestamp) /* Alternate natural key */
) ;

/* And one for bookings */
CREATE TABLE bookings
(
    session_id INTEGER NOT NULL REFERENCES sessions (session_id),
    seat_number INTEGER NOT NULL /* REFERENCES ... */,
    booker TEXT NULL,
    PRIMARY KEY (session_id, seat_number),
    UNIQUE (session_id, seat_number, booker) /* Needed redundance */
) ;

The table bookings, instead of having an is_booked column, has got a booker column. If it is null, the seat is not booked, otherwise this is the name (id) of the booker.

We add some example data...

-- Sample data
INSERT INTO sessions 
    (session_id, session_theater, session_timestamp, performance_name)
VALUES 
    (1, 'Her Majesty''s Theatre', 
        '2017-01-06 19:30 Europe/London', 'The Phantom of the Opera'),
    (2, 'Her Majesty''s Theatre', 
        '2017-01-07 14:30 Europe/London', 'The Phantom of the Opera'),
    (3, 'Her Majesty''s Theatre', 
        '2017-01-07 19:30 Europe/London', 'The Phantom of the Opera') ;

-- ALl sessions have 100 free seats 
INSERT INTO bookings (session_id, seat_number)
SELECT
    session_id, seat_number
FROM
    generate_series(1, 3)   AS x(session_id),
    generate_series(1, 100) AS y(seat_number) ;

We create a second table for bookings, with one restriction:

CREATE TABLE bookings_with_bookers
(
    session_id INTEGER NOT NULL,
    seat_number INTEGER NOT NULL,
    booker TEXT NOT NULL,
    PRIMARY KEY (session_id, seat_number)
) ;

-- Restraint bookings_with_bookers: they must match bookings
ALTER TABLE bookings_with_bookers
  ADD FOREIGN KEY (session_id, seat_number, booker) 
  REFERENCES bookings.bookings (session_id, seat_number, booker) MATCH FULL
   ON UPDATE RESTRICT ON DELETE RESTRICT
   DEFERRABLE INITIALLY DEFERRED;

This second table will contain a COPY of the (session_id, seat_number, booker) tuples, with one FOREIGN KEY constraint; that will not allow the original bookings to be UPDATED by another task. [Assuming that there are never two tasks dealing with the same booker; if that were the case, a certain task_id column should be added.]

Whenever we need to do a booking, the sequence of steps followed within the following function shows the way:

CREATE or REPLACE FUNCTION book_session 
    (IN _booker text, IN _session_id integer, IN _number_of_seats integer) 
RETURNS integer  /* number of seats really booked */ AS
$BODY$

DECLARE
    number_really_booked INTEGER ;
BEGIN
    -- Choose a random sample of seats, assign them to the booker.

    -- Take a list of free seats
    WITH free_seats AS
    (
    SELECT
        b.seat_number
    FROM
        bookings.bookings b
    WHERE
        b.session_id = _session_id
        AND b.booker IS NULL
    ORDER BY
        random()     /* In practice, you'd never do it */
    LIMIT
        _number_of_seats
    FOR UPDATE       /* We want to update those rows, and book them */
    )

    -- Update the 'bookings' table to have our _booker set in.
    , update_bookings AS 
    (
    UPDATE
        bookings.bookings b
    SET
        booker = _booker
    FROM
        free_seats
    WHERE
        b.session_id  = _session_id AND 
        b.seat_number = free_seats.seat_number
    RETURNING
        b.session_id, b.seat_number, b.booker
    )

    -- Insert all this information in our second table, 
    -- that acts as a 'lock'
    , insert_into_bookings_with_bookers AS
    (
    INSERT INTO
        bookings.bookings_with_bookers (session_id, seat_number, booker)
    SELECT
        update_bookings.session_id, 
        update_bookings.seat_number, 
        update_bookings.booker
    FROM
        update_bookings
    RETURNING
        bookings.bookings_with_bookers.seat_number
    )

    -- Count real number of seats booked, and return it
    SELECT 
        count(seat_number) 
    INTO
        number_really_booked
    FROM
        insert_into_bookings_with_bookers ;

    RETURN number_really_booked ;
END ;
$BODY$
LANGUAGE plpgsql VOLATILE NOT LEAKPROOF STRICT
COST 10000 ;

To really make a booking, your program should try to execute something like:

-- Whenever we wich to book 37 seats for session 2...
BEGIN TRANSACTION  ;
SELECT
    book_session('Andrew the Theater-goer', 2, 37) ;

/* Three things can happen:
    - The select returns the wished number of seats  
         => COMMIT 
           This can cause an EXCEPTION, and a need for (implicit)
           ROLLBACK which should be handled and the process 
           retried a number of times
           if no exception => the process is finished, you have your booking
    - The select returns less than the wished number of seats
         => ROLLBACK and RETRY
           we don't have enough seats, or some rows changed during function
           execution
    - (There can be a deadlock condition... that should be handled)
*/
COMMIT /* or ROLLBACK */ TRANSACTION ;

This relies on two facts 1. The FOREIGN KEY constraint won't allow the data to be broken. 2. We UPDATE the bookings table, but only INSERT (and never UPDATE) on the bookings_with_bookers one (the second table).

It doesn't need SERIALIZABLE isolation level, which would greatly simplify the logic. In practice, however, deadlocks are to be expected, and the program interacting with the database should be designed to handle them.

Answer 4

I would use a CHECK constraint to prevent overbooking and avoid explicit locking of rows.

The table could be defined like this:

CREATE TABLE seats
(
    id serial PRIMARY KEY,
    is_booked int NOT NULL,
    extra_info text NOT NULL,
    CONSTRAINT check_overbooking CHECK (is_booked >= 0 AND is_booked <= 1)
);

The booking of a batch of seats is done by a single UPDATE:

UPDATE seats
SET is_booked = is_booked + 1
WHERE 
    id IN
    (
        SELECT s2.id
        FROM seats AS s2
        WHERE
            s2.is_booked = 0
        ORDER BY random() -- or id, or some other order to choose seats
        LIMIT <number of seats to book>
    )
;
-- in practice use RETURNING to get back a list of booked seats,
-- or prepare the list of seat ids which you'll try to book
-- in a separate step before this UPDATE, not on the fly like here.

Your code should have a retry logic. Normally, simply try to run this UPDATE. Transaction would consist of this one UPDATE. If there were no problems, you can be sure that the whole batch was booked. If you get a CHECK constraint violation, you should retry.

So, this is an optimistic approach.

• Don't lock anything explicitly.
• Try to make the change.
• Retry if constraint is violated.
• You don't need any explicit checks after the UPDATE, because constraint (i.e. the DB engine) does it for you.