Strategi untuk pemesanan grup secara bersamaan?

8

Pertimbangkan basis data pemesanan kursi. Ada daftar n kursi, dan masing-masing memiliki atribut is_booked. 0 berarti tidak, 1 berarti tidak. Angka yang lebih tinggi dan ada overbooking.

Apa strategi untuk melakukan beberapa transaksi (di mana setiap transaksi akan memesan sekelompok kursi secara bersamaan) tanpa membolehkan pemesanan berlebihan?

Saya hanya akan memilih semua kursi tidak terdaftar, pilih grup yang dipilih secara acak, memesan semuanya, dan memeriksa apakah pemesanan itu benar (alias jumlah is_booked belum lebih dari satu, yang akan menandakan transaksi lain setelah memesan kursi dan berkomitmen), lalu berkomitmen. jika tidak batalkan dan coba lagi.

Ini dijalankan pada tingkat isolasi Baca Komit di Postgres.

Benjamin Scherer
sumber

Jawaban:

5

Karena Anda tidak memberi tahu kami apa yang Anda butuhkan, saya akan menebak semuanya, dan kami akan membuatnya cukup rumit untuk menyederhanakan beberapa pertanyaan yang mungkin.

Hal pertama tentang MVCC adalah bahwa dalam sistem yang sangat bersamaan Anda ingin menghindari penguncian tabel. Sebagai aturan umum, Anda tidak bisa mengatakan apa yang tidak ada tanpa mengunci tabel untuk transaksi. Itu membuat Anda satu pilihan: jangan mengandalkan INSERT.

Saya meninggalkan sedikit sebagai latihan untuk aplikasi pemesanan nyata di sini. Kami tidak menangani,

  • Overbooking (sebagai fitur)
  • Atau apa yang harus dilakukan jika tidak ada kursi x-tersisa.
  • Membangun ke pelanggan dan transaksi.

Kuncinya di sini adalah di UPDATE.Kami mengunci hanya baris untuk UPDATEsebelum transaksi dimulai. Kita dapat melakukan ini karena kita telah memasukkan semua tiket kursi untuk dijual di meja event_venue_seats,.

Buat skema dasar

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)
);

Data Uji

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);

Dan sekarang untuk Transaksi Pemesanan

Sekarang kami memiliki hard disk eventid ke salah satunya, Anda harus mengatur ini untuk acara apa pun yang Anda inginkan, customeriddan txnidpada dasarnya membuat kursi disediakan dan memberi tahu Anda siapa yang melakukannya. The FOR UPDATEadalah kunci. Baris-baris itu dikunci selama pembaruan.

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;

Pembaruan

Untuk pemesanan waktunya

Anda akan menggunakan reservasi berjangka waktu. Seperti ketika Anda membeli tiket konser, Anda memiliki menit M untuk mengkonfirmasi pemesanan, atau orang lain mendapatkan kesempatan - Neil McGuigan 19 menit yang lalu

Apa yang akan Anda lakukan di sini adalah mengatur booking.event_venue_seats.txnidsebagai

txnid int REFERENCES transactions ON DELETE SET NULL

Kedua, pengguna menyimpan seet, UPDATEmenempatkannya di txnid. Tabel transaksi Anda terlihat seperti ini.

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

Lalu dalam setiap menit Anda berlari

DELETE FROM transactions
WHERE txn_expire < now()

Anda dapat meminta pengguna untuk memperpanjang timer saat mendekati kedaluwarsa. Atau, biarkan saja menghapus txniddan turun membebaskan kursi.

Evan Carroll
sumber
Ini adalah pendekatan yang bagus dan cerdas: tabel transaksi Anda memainkan peran penguncian dari tabel pemesanan kedua saya ; dan memiliki penggunaan ekstra.
joanolo
Di bagian "transaksi pemesanan", di sub-kueri pemilihan dalam pernyataan pembaruan, mengapa Anda bergabung dengan kursi, tempat, dan acara karena Anda tidak menggunakan data apa pun yang belum disimpan di event_venue_seats?
Ynv
1

Saya pikir ini dapat dicapai dengan menggunakan meja ganda mewah dan beberapa kendala.

Mari kita mulai dengan beberapa struktur (tidak sepenuhnya dinormalisasi):

/* 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 */
) ;

Pemesanan meja, alih-alih memiliki is_bookedkolom, sudah mendapat bookerkolom. Jika nol, kursi tidak dipesan, jika tidak ini adalah nama (id) dari pemesan.

Kami menambahkan beberapa contoh 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) ;

Kami membuat tabel kedua untuk pemesanan, dengan satu batasan:

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;

Tabel kedua ini akan berisi COPY dari tuple (session_id, seat_number, booker), dengan satu FOREIGN KEYkendala; yang tidak akan memungkinkan pemesanan asli DIPERBARUI oleh tugas lain. [Dengan asumsi bahwa tidak pernah ada dua tugas yang berurusan dengan pembukuan yang sama ; jika itu masalahnya, task_idkolom tertentu harus ditambahkan.]

Setiap kali kita perlu melakukan pemesanan, urutan langkah-langkah yang diikuti dalam fungsi berikut menunjukkan caranya:

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 ;

Untuk benar-benar melakukan pemesanan, program Anda harus mencoba menjalankan sesuatu seperti:

-- 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 ;

Ini bergantung pada dua fakta 1. FOREIGN KEYKendala tidak akan membiarkan data menjadi rusak . 2. Kami MEMPERBARUI tabel pemesanan, tetapi hanya MASUKKAN (dan tidak pernah MEMPERBARUI ) pada booking_with_bookers satu (tabel kedua).

Tidak perlu SERIALIZABLEtingkat isolasi, yang akan sangat menyederhanakan logika. Namun dalam praktiknya, deadlock diharapkan, dan program yang berinteraksi dengan database harus dirancang untuk menanganinya.

joanolo
sumber
Itu memang perlu SERIALIZABLEkarena jika dua book_sessions dieksekusi pada saat yang sama maka count(*)dari txn kedua dapat membaca tabel sebelum book_session pertama selesai dengan nya INSERT. Sebagai aturan umum, tidak aman untuk menguji tidak adanya wo / SERIALIZABLE.
Evan Carroll
@ EvanCarroll: Saya pikir kombinasi 2 tabel dan menggunakan CTE menghindari keharusan ini. Anda bermain dengan kenyataan bahwa kendala menawarkan jaminan bahwa, pada akhir transaksi Anda, semuanya konsisten atau Anda batalkan. Berperilaku dalam cara yang sangat mirip dengan serializable .
joanolo
1

Saya akan menggunakan CHECK batasan untuk mencegah overbooking dan menghindari penguncian baris secara eksplisit.

Tabel dapat didefinisikan seperti ini:

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)
);

Pemesanan sejumlah kursi dilakukan oleh satu orang 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.

Kode Anda harus memiliki logika coba lagi. Biasanya, coba jalankan ini UPDATE. Transaksi akan terdiri dari yang iniUPDATE . Jika tidak ada masalah, Anda dapat yakin bahwa seluruh kartu telah dipesan. Jika Anda mendapatkan pelanggaran PERIKSA kendala, Anda harus mencoba lagi.

Jadi, ini adalah pendekatan yang optimis.

  • Jangan mengunci apa pun secara eksplisit.
  • Cobalah untuk melakukan perubahan.
  • Coba lagi jika kendala dilanggar.
  • Anda tidak memerlukan pemeriksaan eksplisit setelah UPDATE, karena kendala (yaitu mesin DB) melakukannya untuk Anda.
Vladimir Baranov
sumber
1

Pendekatan 1s - PEMBARUAN Tunggal:

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

Pendekatan 2 - 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;

Pendekatan 3 - Tabel antrian:

Transaksi itu sendiri tidak memperbarui tabel kursi. Mereka semua MASUKKAN permintaan mereka ke dalam tabel antrian.
Sebuah proses yang terpisah mengambil semua permintaan dari tabel antrian dan menangani mereka, dengan mengalokasikan kursi untuk pemohon.

Keuntungan:
- Dengan menggunakan INSERT, penguncian / pertikaian dihilangkan
- Tidak ada pemesanan berlebih dipastikan dengan menggunakan satu proses untuk alokasi kursi

Kekurangan:
- Alokasi kursi tidak langsung

bentaly
sumber