Implementasi Antrian dengan Custom Consistent Absolute Ordering

Question

Saya perlu membuat skema untuk antrian. Elemen dalam antrian ini akan diproses dalam urutan berdasarkan kolom. Bagaimanapun, ini tidak selalu pada date_addedkolom eg .

Pengguna harus dapat dengan bebas memesan ulang item dalam antrian, sehingga mengatur posisi khusus - sebut saja bidang itu position. Oleh karena itu, item antrian yang memiliki posisi >=ke posisi baru yang saya tetapkan untuk item tertentu perlu dipesan ulang pada setiap pembaruan.

Saya benar-benar ingin menghindari penggunaan skrip sisi server untuk secara manual melalui setiap elemen yang sekarang sudah ketinggalan zaman dan memperbarui posisinya.

Adakah cara untuk melakukan ini secara otomatis, dan dengan penggunaan sumber daya yang relatif rendah? Saya yakin orang-orang telah menerapkan antrian seperti itu di MySQL sebelumnya, tetapi tampaknya tidak ada jawaban yang relevan di mana pun, meskipun tugasnya terdengar sepele. Ada ide?

Saya tahu saya seharusnya tidak bergantung pada urutan penyimpanan catatan. Tapi saya mungkin mempertimbangkan untuk menggunakan ALTER TABLE ORDER BY. Seberapa buruk ini sebenarnya? Dan seberapa bermanfaatkah itu dalam mencapai tujuan saya?

Ada beberapa PK, kemungkinan kenaikan otomatis, atau mungkin date_addeddengan lebih presisi. Versi tersebut adalah InnoDB, MySQL> = 5.6.

Posisi antrian dapat diubah beberapa kali. Ini harus bekerja tanpa kegagalan. UI dengan HTML dan JS itu sepele: Pada setiap perubahan hierarki langsung dalam penampung, Anda cukup membaca urutan elemen dengan atribut tertentu. Ini juga sangat umum. Mungkin ada ratusan item dalam daftar.

Yang saya maksud dengan "elemen usang" adalah yang tidak lagi memiliki positionbidang yang disetel dengan benar, dan perlu "diindeks ulang". Secara alami, sesuatu di MySQL akan mengatasinya.

Untuk selesai, saya membutuhkan itu untuk diambil juga, jadi mereka tetap di tabel, dan ditandai sebagai selesai dengan bidang boolean . Ada tabel lain yang menangani transisi status yang lebih rumit, karena ini bukan bagian dari yang membuat antrean.

Answer 1

(Saya akan bersaing dengan diri saya sendiri. Ini Jawaban untuk item "besar".)

Memperbarui baris 1K tidak terlalu cepat, karena baris disimpan jika terjadi rollback. Menambah / mengurangi nomor urut (kolom seq) untuk suatu rentang baris, lalu mengubah satu urutan dalam satu baris yang dipindahkan. Itu 3 PEMBARUAN - satu lambat, satu cepat.

UI perlu menyediakan beberapa cara bagi pengguna untuk menentukan item mana yang akan dipindahkan dari beberapa urutan ke urutan baru.

Kolom di tabel akan berisi nomor urut. seqefektif UNIQUE, tetapi mengatakan demikian mungkin akan memperlambatnya.

Misalkan UI memberi tahu db bahwa "Seq = 222 perlu pindah ke setelah seq = 567. (Setelah" 0 "untuk menyisipkan di depan.)

BEGIN;   -- need atomicity
-- Move item out of the way (assuming "0" is not otherwise used):
UPDATE t SET seq = 0 WHERE seq = 222;
-- Shift the items that need to move:
UPDATE t SET seq = seq - 1   -- "-" or "+" depending
    WHERE seq BETWEEN 222+1 AND 567;
-- move the item in question:
UPDATE t SET seq = 567 WHERE seq = 0;
COMMIT;

Pindah ke arah lain membutuhkan beberapa perubahan.

Answer 2

Jadi, inilah jawaban saya yang keluar dari diskusi yang sangat produktif dengan @RickJames. Terima kasih banyak!

Jadi, buat tabel antrian seperti ini. Harap dicatat bahwa ini mendukung banyak antrian sekaligus, dan beberapa fitur lainnya. Juga, posisi sebenarnya dapat ditambahkan secara opsional sebagai tabel lain, yang bisa lebih baik jika Anda menyukai modularitas (saya tahu saya).

CREATE TABLE `queue_jobs` (
    `id` int unsigned PRIMARY KEY AUTO_INCREMENT,
    `queue_name` varchar(255),
    `added_on` datetime DEFAULT CURRENT_TIMESTAMP,
    `processed_on` datetime,
    `data` text,
    `position` int unsigned
);

Setiap kali saya menyisipkan catatan, saya hanya menetapkan padanya posisi dengan positionnilai terbesar saat ini +1.

INSERT INTO `queue_jobs` (
  `id`,
  `queue_name`,
  `added_on`,
  `processed_on`,
  `data`,
  `position`)
VALUES (
  NULL,
  'people',
  NULL,
  NULL,
  'Richard',
  ( -- This is the subquery that is responsible for getting the next available position
    SELECT MAX(`position`)
    FROM `queue_jobs` `qj`
    WHERE `queue_name` = 'people'
    LIMIT 1)
  + 1);

Setiap kali saya memindahkan data, saya melakukannya dalam 2 langkah:

1. Geser semua pekerjaan, yang posisinya> = posisi target pekerjaan yang ingin saya pindahkan, sebesar 1.
2. Ubah posisi pekerjaan yang ingin saya pindahkan ke posisi yang diinginkan, karena posisi tersebut sekarang dijamin bebas.

BEGIN;
-- 6: Move queue item up
UPDATE `queue_jobs` SET `position` = `position` + 1
WHERE `position` >= 2; -- 2 is the new position we want out item to be at
-- 7: Assign new position to target item
UPDATE `queue_jobs` SET `position` = 2
WHERE `id` = 3;
COMMIT;

Catatan: ini tidak dapat dilakukan jika positionlapangan adalah unik, karena posisi pekerjaan bergeser mungkin bertentangan dengan saat ini posisi pekerjaan saya ingin pindah.

Ini berfungsi untuk memindahkan pekerjaan ke dua arah. Ini memungkinkan lebih dari 4 miliar penyisipan atau pergerakan sebelum nilainya mulai meluap. Dalam hal ini, sesuatu seperti BIGINT UNSIGNEDharus digunakan yang memungkinkan hingga 18 triliun. Selain itu, nilai posisi dari solusi ini tidak akan terlalu padat. Kepadatan dapat ditingkatkan dengan mungkin menugaskan kembali posisi sesekali dalam jadwal, dengan menggunakan variabel, yaitu sesuatu seperti ini .

Answer 3

Untuk sekumpulan item "kecil", berikut adalah desain untuk UI dan pengurutannya. Ini berpusat di sekitar komalist id.

UI akan mencantumkan semua item. Katakanlah praktis untuk menampilkan item secara horizontal seperti teks yang dibungkus. Item dapat direpresentasikan sebagai nama, nomor tugas, gambar mini, apa pun.

Sekarang miliki beberapa JavaScript untuk memungkinkan pengguna menarik & melepaskan satu item ke dalam ruang di antara dua item lainnya (atau mematikan salah satu ujungnya). JS akan segera:

1. Atur ulang larik internalnya
2. Tampilkan kembali daftarnya
3. Buat commalist if id dalam satu string
4. Gunakan AJAX untuk mengirim komalist itu ke server.

Server MySQL:

1. simpan string tunggal itu di suatu tempat.
2. Gunakan string itu untuk menyediakan pemesanan: ORDER BY FIND_IN_SET(item, commalist)

Peringatan : Jika dua pengguna membuat perubahan pada daftar pada "waktu yang sama", perubahan satu orang akan hilang.

Jika set terlalu besar untuk solusi itu, saya akan menggaruk kepala saya lagi. Tapi berhati-hatilah, aku akan botak.