PolarDB:WAL parallel replay

Istilah

• data block: Satuan penyimpanan data.

• WAL: Singkatan dari write-ahead logging.

• task node: Node dalam kerangka eksekusi paralel yang menerima dan mengeksekusi satu subtask.

• task tag: Pengenal yang mengkategorikan subtask. Subtask dengan tag yang sama memiliki ketergantungan urutan eksekusi.

• hold list: Daftar berantai yang digunakan setiap proses anak dalam kerangka eksekusi paralel untuk menjadwalkan dan mengeksekusi subtask replay.

Cara Kerja

• Ikhtisar

  Satu catatan WAL dapat memodifikasi beberapa data block.

  1. Misalkan log WAL ke-i memiliki LSN sebesar LSN<sub>i</sub>​ dan memodifikasi m blok data. Daftar blok data yang dimodifikasi oleh log WAL ke-i didefinisikan sebagai Block<sub>i</sub>​=[Block<sub>i,0</sub>​,Block<sub>i,1</sub>​,...,Block<sub>i,m</sub>​].

  2. Subtask replay minimum didefinisikan sebagai Task<sub>i,j​</sub>=LSN<sub>i​</sub>−>Block<sub>i,j</sub>​, yang merepresentasikan replay log WAL pada blok data Block<sub>i,j</sub>​ nomor i.

  3. Dengan demikian, satu log WAL yang memodifikasi m blok dapat direpresentasikan sebagai himpunan m subtask replay: TASK<sub>i,∗</sub>​=[Task<sub>i,0</sub>​,Task<sub>i,1</sub>​,...,Task<sub>i,m​</sub>].

  4. Oleh karena itu, beberapa log WAL dapat direpresentasikan sebagai rangkaian subtask replay: TASK<sub>∗,∗</sub>​=[Task<sub>0,∗</sub>​,Task<sub>1,∗</sub>​,...,Task<sub>N,∗</sub>​].

  Dalam himpunan subtask replay log Task<sub>∗,∗</sub>​, eksekusi setiap subtask tidak selalu bergantung pada hasil eksekusi subtask sebelumnya.

  Misalkan himpunan subtask replay adalah sebagai berikut: TASK<sub>∗,∗</sub>​=[Task<sub>0,∗</sub>​,Task<sub>1,∗​</sub>,Task<sub>2,∗</sub>​], dengan:

  • Task<sub>0,∗</sub>​=[Task<sub>0,0</sub>​,Task<sub>0,1</sub>​,Task<sub>0,2</sub>​]

  • Task<sub>1,∗</sub>​=[Task<sub>1,0</sub>​,Task<sub>1,1</sub>​]

  • Task<sub>2,∗</sub>​=[Task<sub>2,0</sub>​]

  Selain itu, Block_0,0 = Block_1,0, Block_0,1 = Block_1,1, dan Block_0,2 = Block_2,0.

  Dalam kasus ini, tiga set subtugas dapat dijalankan ulang secara paralel: [Tugas_0,0, Tugas_1,0], [Tugas_0,1, Tugas_1,1], dan [Tugas_0,2, Tugas_2,0].

  Secara ringkas, banyak urutan subtask dalam keseluruhan himpunan tugas replay WAL dapat dijalankan secara paralel tanpa memengaruhi konsistensi hasil akhir. Berdasarkan prinsip ini, PolarDB memperkenalkan kerangka eksekusi tugas paralel dan menerapkannya pada proses replay WAL.

• Kerangka eksekusi tugas paralel

  Kerangka ini membagi segmen memori bersama secara merata di antara proses konkuren. Setiap segmen hasil pembagian, yang dialokasikan ke satu proses, berfungsi sebagai antrian melingkar (circular queue). Anda dapat mengonfigurasi kedalaman setiap antrian melingkar melalui parameter.

  • Proses Dispatcher

    • Mengontrol penjadwalan konkuren dengan mendistribusikan tugas ke proses tertentu.

    • Menghapus tugas yang telah selesai dari antrian.

  • process pool

    Setiap proses dalam pool mengambil tugas dari antrian melingkar yang sesuai dan menentukan apakah akan mengeksekusinya berdasarkan status tugas tersebut.

  • Tugas

    Antrian melingkar berisi node tugas. Setiap node tugas dapat berada dalam salah satu dari lima status: Idle, Running, Hold, Finished, atau Removed.

    • Idle: Node tugas tidak memiliki tugas yang ditetapkan.

    • Running: Node tugas telah diberi tugas yang sedang menunggu eksekusi atau sedang dieksekusi.

    • Hold: Tugas bergantung pada tugas sebelumnya dan harus menunggu hingga tugas tersebut selesai.

    • Finished: Tugas telah diselesaikan oleh proses dalam process pool.

    • Removed: Ketika proses Dispatcher menemukan tugas dalam status Finished, hal ini menyiratkan bahwa semua tugas prasyaratnya juga telah selesai. Proses Dispatcher kemudian mengubah statusnya menjadi Removed, yang menandakan bahwa tugas tersebut beserta prasyaratnya telah dihapus dari struktur manajemen. Proses ini memastikan bahwa Dispatcher menangani tugas yang saling bergantung dalam urutan yang benar.

    Dalam proses transisi status pada mesin keadaan di atas, transisi yang ditandai garis hitam dilakukan oleh proses Dispatcher, sedangkan transisi yang ditandai garis oranye dilakukan oleh kelompok proses replay paralel.

  • Dispatcher process

    Proses Dispatcher menggunakan tiga struktur data utama: Task HashMap, Task Running Queue, dan Task Idle Nodes.

    • Task HashMap menyimpan pemetaan hash antara task tag dan daftar eksekusi tugas yang sesuai.

      • Setiap tugas diberi task tag tertentu. Jika dua tugas memiliki ketergantungan, keduanya berbagi task tag yang sama.

      • Saat mendistribusikan tugas, jika node tugas memiliki prasyarat, proses Dispatcher menandai statusnya sebagai Hold sehingga tugas tersebut menunggu hingga prasyaratnya dieksekusi.

    • Task Running Queue melacak semua tugas yang sedang dieksekusi.

    • Task Idle Nodes mencatat node tugas dari berbagai proses dalam process pool yang saat ini berada dalam status Idle.

    Proses Dispatcher menggunakan strategi penjadwalan berikut:

    • Jika tugas yang akan dieksekusi memiliki task tag yang sama dengan tugas lain yang sedang berjalan, tugas baru tersebut diprioritaskan untuk ditugaskan ke proses yang menjalankan tugas terakhir dalam daftar berantai task tag tersebut. Strategi ini bertujuan menjaga tugas yang saling bergantung tetap berada dalam proses yang sama guna mengurangi overhead sinkronisasi antar-proses.

    • Jika antrian proses yang diprioritaskan penuh atau tidak ada tugas dengan Task Tag yang sama sedang berjalan, proses dipilih secara berurutan dari process pool, dan node tugas dalam status Idle diambil dari proses tersebut untuk menjalankan tugas. Tujuannya adalah mendistribusikan tugas secara merata di antara berbagai proses.

    

  • process pool

    Eksekusi paralel ini menargetkan tugas dengan jenis yang sama yang memiliki struktur data node tugas yang identik. Saat process pool diinisialisasi, konfigurasikan SchedContext untuk menentukan pointer fungsi yang bertanggung jawab mengeksekusi tugas tertentu:

    • TaskStartup: Aksi inisialisasi yang diperlukan sebelum proses dapat mengeksekusi tugas.

    • TaskHandler: Fungsi yang bertanggung jawab mengeksekusi tugas tertentu berdasarkan node tugas yang diberikan.

    • TaskCleanup: Tindakan pembersihan yang diperlukan sebelum proses eksekusi berakhir.

    

    Proses dalam process pool mengambil node tugas dari antrian melingkar. Jika status saat ini dari node tugas adalah Hold, proses tersebut memasukkan node tugas ke ujung ekor hold list. Jika status node tugas adalah Running, proses tersebut memanggil TaskHandler untuk mengeksekusinya. Jika TaskHandler gagal mengeksekusi, proses tersebut menetapkan jumlah percobaan ulang default sebanyak 3 kali untuk node tugas tersebut dan memasukkannya ke kepala hold list.

    Proses tersebut pertama-tama mencari hold list dari kepala untuk mengambil Tugas yang dapat dieksekusi. Jika status Tugas tersebut adalah Running dan jumlah panggilan tunggunya adalah 0, proses tersebut mengeksekusi Tugas tersebut. Jika status Tugas tersebut adalah Running tetapi jumlah panggilan tunggunya lebih besar dari 0, proses tersebut mengurangi jumlah panggilan tunggu sebanyak 1.

• WAL parallel replay

  Data LogIndex mencatat pemetaan antara catatan WAL dan data block yang dimodifikasinya, serta mendukung pencarian berbasis LSN. Selama replay WAL berkelanjutan pada node standby, PolarDB memperkenalkan kerangka eksekusi tugas paralel dan menggunakan data LogIndex untuk memparalelkan tugas replay WAL, sehingga mempercepat sinkronisasi data pada node standby.

  Alur Kerja

  • Proses Startup mengurai catatan WAL dan membangun data LogIndex tetapi tidak mereplay catatan WAL tersebut.

  • Proses replay latar belakang LogIndex BGW berperan sebagai Dispatcher dalam kerangka eksekusi tugas paralel. Proses ini menggunakan LSN untuk mengambil data LogIndex, membuat subtask replay, lalu menugaskannya ke pool proses replay paralel.

  • Proses dalam process pool replay paralel mengeksekusi subtask replay, menerapkan satu catatan log ke satu data block.

  • Ketika proses backend secara aktif membaca data block, proses tersebut menggunakan page tag untuk mencari data LogIndex. Proses tersebut mengambil daftar berantai LSN yang memodifikasi data block tersebut dan mereplay seluruh rantai catatan log pada block tersebut.

  • Proses Dispatcher menggunakan LSN untuk mengambil data LogIndex, mengenumerasi PageTag dan LSN yang sesuai berdasarkan urutan penyisipan LogIndex, serta membangun pemetaan {LSN -> PageTag} guna membentuk node tugas yang sesuai.

  • Tag halaman digunakan sebagai task tag untuk node tugas tersebut.

  • Node tugas yang telah dienumerasi kemudian didistribusikan ke proses anak dalam process pool kerangka eksekusi paralel untuk direplay.

Aktifkan WAL parallel replay

polar_enable_parallel_replay_standby_mode = ON