Spanner adalah database yang sangat konsisten, terdistribusi, dan skalabel, serta dibangun oleh engineer Google untuk mendukung beberapa aplikasi paling penting di Google. AI generatif mengambil ide inti dari database dan komunitas sistem terdistribusi, lalu mengembangkannya dengan cara baru. Spanner mengekspos layanan Spanner internal ini sebagai layanan yang tersedia untuk publik di Google Cloud Platform.
Karena Spanner harus menangani persyaratan waktu beroperasi dan skala yang sangat tinggi yang diberlakukan oleh aplikasi bisnis penting Google, kami membangun Spanner dari awal agar menjadi database yang didistribusikan secara luas. Layanan ini dapat mencakup beberapa mesin dan beberapa pusat data serta region. Kami memanfaatkan distribusi ini untuk menangani set data yang sangat besar dan beban kerja yang sangat besar, sambil tetap mempertahankan ketersediaan yang sangat tinggi. Kami juga berupaya agar Spanner dapat memberikan jaminan konsistensi ketat yang sama seperti yang diberikan oleh database tingkat perusahaan lainnya, karena kami ingin menciptakan pengalaman yang luar biasa bagi developer. Jauh lebih mudah untuk memikirkan dan menulis software untuk database yang mendukung konsistensi kuat daripada database yang hanya mendukung konsistensi tingkat baris, konsistensi tingkat entity, atau tidak memiliki jaminan konsistensi sama sekali.
Dalam dokumen ini, kami menjelaskan secara mendetail cara kerja operasi tulis dan baca di Spanner, serta cara Spanner memastikan konsistensi yang kuat.
Titik awal
Ada beberapa {i>dataset<i} yang terlalu besar untuk dimuat di satu mesin. Ada juga skenario saat set data berukuran kecil, tetapi beban kerjanya terlalu berat untuk ditangani oleh satu mesin. Ini berarti kita perlu menemukan cara untuk membagi data menjadi bagian-bagian terpisah yang dapat disimpan di beberapa komputer. Pendekatan kami adalah mempartisi tabel database menjadi beberapa rentang kunci yang berdekatan yang disebut bagian. Satu komputer dapat melayani beberapa bagian, dan terdapat layanan pencarian cepat untuk menentukan mesin yang melayani rentang kunci tertentu. Detail tentang cara data dibagi dan mesin tempat data berada transparan bagi pengguna Spanner. Hasilnya adalah sistem yang dapat memberikan latensi rendah untuk operasi baca dan tulis, bahkan pada beban kerja berat, dalam skala yang sangat besar.
Kita juga ingin memastikan bahwa data dapat diakses meskipun terjadi kegagalan. Untuk memastikannya, kita mereplikasi setiap pemisahan ke beberapa komputer di domain kegagalan yang berbeda. Replikasi yang konsisten ke berbagai salinan bagian dikelola oleh algoritma Paxos. Di Paxos, asalkan sebagian besar replika pemungutan suara untuk bagian tersebut habis, salah satu replika tersebut dapat dipilih sebagai leader untuk memproses penulisan dan memungkinkan replika lain menayangkan pembacaan.
Spanner menyediakan transaksi hanya baca dan transaksi
baca-tulis. Yang pertama adalah jenis transaksi pilihan untuk operasi
(termasuk pernyataan SELECT SQL) yang tidak mengubah data Anda. Transaksi hanya baca
masih memberikan konsistensi yang kuat dan beroperasi, secara default, pada
salinan data terbaru Anda. Namun, pod dapat berjalan tanpa perlu melakukan bentuk
penguncian secara internal, yang membuatnya lebih cepat dan lebih skalabel. Transaksi baca-tulis digunakan untuk transaksi yang menyisipkan, memperbarui, atau menghapus data; termasuk transaksi yang melakukan pembacaan yang diikuti dengan penulisan. Penggunaannya masih
sangat skalabel, tetapi transaksi baca-tulis menyebabkan penguncian dan harus
diatur oleh pemimpin Paxos. Perhatikan bahwa penguncian bersifat transparan untuk klien Spanner.
Banyak sistem database terdistribusi sebelumnya memilih untuk tidak memberikan jaminan konsistensi yang kuat karena komunikasi lintas-mesin yang mahal biasanya diperlukan. Spanner dapat menyediakan snapshot yang sangat konsisten di seluruh database menggunakan teknologi yang dikembangkan Google yang disebut TrueTime. Seperti Flux Capacitor pada mesin waktu
sekitar tahun 1985, TrueTime adalah yang memungkinkan Spanner. API ini memungkinkan mesin apa pun di pusat data Google mengetahui waktu global yang tepat dengan tingkat akurasi yang tinggi (yaitu, dalam beberapa milidetik). Hal ini memungkinkan berbagai
mesin Spanner untuk memikirkan urutan operasi transaksional (dan
membuat pengurutan tersebut cocok dengan yang telah diamati klien) tanpa adanya
komunikasi sama sekali. Google harus melengkapi pusat datanya dengan hardware khusus (jam atom) agar TrueTime dapat berfungsi. Presisi dan akurasi waktu yang dihasilkan jauh lebih tinggi daripada yang dapat dicapai oleh protokol lain (seperti NTP). Secara khusus, Spanner menetapkan stempel waktu ke semua operasi baca dan tulis. Transaksi pada stempel waktu T1 dijamin akan mencerminkan hasil semua penulisan yang terjadi sebelum T1. Jika ingin memenuhi pembacaan di T2, mesin harus memastikan bahwa tampilan datanya adalah yang terbaru setidaknya melalui T2. Karena
TrueTime, penentuan ini biasanya sangat murah. Protokol untuk
memastikan konsistensi data memang rumit, tetapi protokol ini dibahas lebih lanjut di
makalah Spanner asli dan
makalah ini tentang Spanner dan konsistensi.
Contoh praktis
Mari kita kerjakan beberapa contoh praktis untuk melihat cara kerjanya:
CREATE TABLE ExampleTable (
Id INT64 NOT NULL,
Value STRING(MAX),
) PRIMARY KEY(Id);
Dalam contoh ini, kita memiliki tabel dengan kunci utama bilangan bulat sederhana.
| Bagi | KeyRange |
|---|---|
| 0 | [-##,3) |
| 1 | [3.224) |
| 2 | [224.712) |
| 3 | [712.717) |
| 4 | [717.1265) |
| 5 | [1265.1724) |
| 6 | [1724.1997) |
| 7 | [1.997.2456) |
| 8 | [2456,sendiri) |
Dengan mempertimbangkan skema untuk ExampleTable di atas, ruang kunci utama dipartisi
menjadi beberapa bagian. Misalnya: Jika ada baris di ExampleTable yang berisi Id
3700, baris tersebut akan berada di Bagian 8. Seperti dijelaskan di atas, Bagian 8 sendiri direplikasi ke beberapa mesin.
Dalam contoh ini, pelanggan memiliki lima node, dan instance direplikasi di tiga zona. Sembilan bagian diberi nomor 0-8, dengan pemimpin Paxos untuk setiap bagian diberi warna gelap. Pemisahan juga memiliki replika di setiap zona (berarsir ringan). Distribusi pemisahan di antara node mungkin berbeda di setiap zona, dan pemimpin Paxos tidak semuanya berada di zona yang sama. Fleksibilitas ini membantu Spanner menjadi lebih andal terhadap jenis profil beban dan mode kegagalan tertentu.
Penulisan satu bagian
Misalkan klien ingin menyisipkan baris baru (7, "Seven") ke dalam
ExampleTable.
- Lapisan API mencari pemisahan yang memiliki rentang kunci yang berisi
7. File ini berada di Bagian 1. - Lapisan API mengirim permintaan tulis ke Pemimpin Bagian 1.
- Pemimpin memulai transaksi.
- Pemimpin mencoba mendapatkan kunci tulis pada baris
Id=7. Ini adalah operasi lokal. Jika transaksi baca-tulis serentak lainnya sedang membaca baris ini, maka transaksi lain tersebut memiliki kunci baca dan blok transaksi saat ini hingga dapat memperoleh kunci tulis.- Ada kemungkinan bahwa transaksi A menunggu kunci yang dipegang oleh transaksi B, dan transaksi B menunggu kunci yang dipegang oleh transaksi A. Karena tidak ada transaksi yang melepaskan kunci hingga mendapatkan semua kunci, hal ini dapat menyebabkan deadlock. Spanner menggunakan algoritma pencegahan deadlock "wound-wait" standar untuk memastikan bahwa transaksi berjalan. Secara khusus, transaksi "lebih muda" akan menunggu kunci yang dipegang oleh transaksi "lama", tetapi transaksi "lama" akan "memengaruhi" (membatalkan) transaksi yang lebih muda yang memegang kunci yang diminta oleh transaksi lama. Oleh karena itu, kita tidak pernah memiliki siklus deadlock pelayan kunci.
- Setelah kunci diperoleh, Pemimpin menetapkan stempel waktu ke transaksi
berdasarkan TrueTime.
- Stempel waktu ini dijamin lebih besar daripada transaksi yang di-commit sebelumnya yang menyentuh data. Inilah yang memastikan bahwa urutan transaksi (seperti yang dirasakan oleh klien) sesuai dengan urutan perubahan pada data.
- Pemimpin memberi tahu replika Bagian 1 tentang transaksi dan stempel waktunya. Setelah sebagian besar replika tersebut menyimpan mutasi transaksi dalam penyimpanan yang stabil (dalam sistem file terdistribusi), transaksi akan di-commit. Hal ini memastikan bahwa transaksi dapat dipulihkan, meskipun terjadi kegagalan di sebagian kecil komputer. (Replika belum menerapkan mutasi ke salinan datanya.)
Pemimpin menunggu hingga dapat dipastikan bahwa stempel waktu transaksi telah berlalu secara real time. Hal ini biasanya memerlukan waktu beberapa milidetik agar kita dapat menunggu ketidakpastian apa pun dalam stempel waktu TrueTime. Inilah yang memastikan konsistensi yang kuat—setelah klien mempelajari hasil transaksi, ada jaminan bahwa semua pembaca lain akan melihat efek transaksi tersebut. "Waktu tunggu commit" ini biasanya tumpang tindih dengan komunikasi replika pada langkah di atas, sehingga biaya latensi sebenarnya yang minimal. Detail selengkapnya dibahas dalam makalah ini.
Pemimpin membalas klien untuk mengatakan bahwa transaksi telah di-commit, yang secara opsional melaporkan stempel waktu commit transaksi.
Sejalan dengan balasan terhadap klien, mutasi transaksi diterapkan pada data.
- Pemimpin menerapkan mutasi ke salinan datanya, lalu melepas kunci transaksinya.
- Pemimpin juga memberi tahu replika Bagian 1 lainnya untuk menerapkan mutasi ke salinan datanya.
- Setiap transaksi baca-tulis atau hanya-baca yang harus melihat efek mutasi akan menunggu hingga mutasi diterapkan sebelum mencoba membaca data. Untuk transaksi baca-tulis, ini diterapkan karena transaksi harus mengambil kunci baca. Untuk transaksi hanya-baca, hal ini diterapkan dengan membandingkan stempel waktu baca dengan stempel waktu data yang terakhir diterapkan.
Semua ini terjadi biasanya dalam beberapa milidetik. Penulisan ini adalah jenis penulisan termurah yang dilakukan oleh Spanner, karena melibatkan satu bagian.
Penulisan multi-bagian
Jika beberapa pemisahan terlibat, lapisan koordinasi tambahan (menggunakan algoritma commit dua fase standar) diperlukan.
Misalnya, tabel berisi empat ribu baris:
| 1 | "one" |
| 2 | "two" |
| ... | ... |
| 4.000 | "empat ribu" |
Misalkan klien ingin membaca nilai untuk baris 1000 dan menulis nilai ke baris 2000, 3000, dan 4000 dalam transaksi. Tindakan ini akan dijalankan dalam transaksi baca-tulis sebagai berikut:
- Klien memulai transaksi baca-tulis, t.
- Klien mengeluarkan permintaan baca untuk baris 1000 ke Lapisan API dan menandainya sebagai bagian dari t.
- Lapisan API mencari pemisahan yang memiliki kunci
1000. Kartu ini ada di Bagian 4. Lapisan API mengirim permintaan baca ke Pemimpin Bagian 4 dan menandainya sebagai bagian dari t.
Leader of Split 4 mencoba mendapatkan kunci baca pada baris
Id=1000. Ini adalah operasi lokal. Jika transaksi serentak lainnya memiliki kunci tulis di baris ini, transaksi saat ini akan diblokir hingga dapat memperoleh kunci. Namun, kunci baca ini tidak mencegah transaksi lain mendapatkan kunci operasi baca.- Seperti dalam satu kasus terpisah, deadlock dicegah melalui "wound-wait".
Pemimpin mencari nilai untuk
Id1000("Seribu") dan menampilkan hasil baca ke klien.
Nanti...Klien mengeluarkan permintaan Commit untuk transaksi t. Permintaan commit ini berisi 3 mutasi: (
[2000, "Dos Mil"],[3000, "Tres Mil"], dan[4000, "Quatro Mil"]).- Semua bagian yang terlibat dalam transaksi menjadi peserta dalam transaksi. Dalam hal ini, Bagian 4 (yang menyalurkan pembacaan untuk kunci
1000), Bagian 7 (yang akan menangani mutasi untuk kunci2000), dan Bagian 8 (yang akan menangani mutasi untuk kunci3000dan kunci4000) adalah peserta.
- Semua bagian yang terlibat dalam transaksi menjadi peserta dalam transaksi. Dalam hal ini, Bagian 4 (yang menyalurkan pembacaan untuk kunci
Satu peserta menjadi koordinator. Dalam hal ini, mungkin pemimpin untuk Bagian 7 menjadi koordinatornya. Tugas koordinator adalah memastikan bahwa transaksi di-commit atau dibatalkan secara atomik di semua peserta. Artinya, tidak akan terjadi pada satu peserta dan pembatalan pada peserta lainnya.
- Pekerjaan yang dilakukan oleh peserta dan koordinator sebenarnya dilakukan oleh mesin pemimpin dari bagian tersebut.
Peserta mendapatkan kunci. (Ini adalah fase pertama dari commit dengan dua fase.)
- Bagian 7 memperoleh kunci tulis pada kunci
2000. - Bagian 8 memperoleh kunci tulis pada kunci
3000dan kunci4000. - Bagian 4 memverifikasi bahwa kunci masih memegang kunci baca pada kunci
1000(dengan kata lain, bahwa kunci tidak hilang karena terjadi error mesin atau algoritma wound-wait.) - Setiap peserta membagi kumpulan kunci-nya dengan mereplikasinya ke (setidaknya) sebagian besar replika terpisah. Hal ini memastikan bahwa kunci dapat tetap dipertahankan meskipun terjadi kegagalan server.
- Jika semua peserta berhasil memberi tahu koordinator bahwa kunci mereka disimpan, maka keseluruhan transaksi dapat dilakukan. Hal ini memastikan ada waktu ketika semua kunci yang diperlukan oleh transaksi disimpan, dan titik waktu ini akan menjadi titik waktu commit dalam transaksi, sehingga memastikan bahwa kita dapat dengan benar mengurutkan efek transaksi ini terhadap transaksi lain yang terjadi sebelum atau sesudahnya.
- Ada kemungkinan bahwa kunci tidak dapat diperoleh (misalnya, jika kita mengetahui mungkin ada deadlock melalui algoritma wound-wait). Jika ada peserta yang menyatakan bahwa ia tidak dapat meng-commit transaksi, seluruh transaksi akan dibatalkan.
- Bagian 7 memperoleh kunci tulis pada kunci
Jika semua peserta, dan koordinator, berhasil mendapatkan kunci, Koordinator (Bagian 7) memutuskan untuk meng-commit transaksi. Metode ini menetapkan stempel waktu ke transaksi berdasarkan TrueTime.
- Keputusan commit ini, serta mutasi untuk kunci
2000, direplikasi ke anggota Bagian 7. Setelah sebagian besar replika Bagian 7 merekam keputusan commit ke penyimpanan yang stabil, transaksi akan di-commit.
- Keputusan commit ini, serta mutasi untuk kunci
Koordinator mengomunikasikan hasil transaksi kepada semua Peserta. (Ini adalah fase kedua dari commit dengan dua fase.)
- Setiap pemimpin peserta mereplikasi keputusan commit ke replika pembagian peserta.
Jika transaksi dilakukan, Koordinator dan semua Peserta akan menerapkan mutasi pada data.
- Seperti dalam kasus pemisahan tunggal, pembaca data berikutnya di Koordinator atau Peserta harus menunggu hingga data diterapkan.
Pemimpin koordinator membalas klien untuk menyampaikan bahwa transaksi telah di-commit, secara opsional menampilkan stempel waktu commit transaksi
- Seperti dalam kasus terpisah tunggal, hasilnya dikomunikasikan kepada klien setelah menunggu commit, untuk memastikan konsistensi yang kuat.
Semua ini terjadi biasanya dalam beberapa milidetik, meskipun biasanya lebih sedikit dibandingkan dalam satu kasus pemisahan karena koordinasi lintas-bagian yang ekstra.
Pembacaan kuat (multi-bagian)
Misalkan klien ingin membaca semua baris dengan Id >= 0 dan Id < 700 sebagai bagian dari transaksi hanya baca.
- Lapisan API mencari bagian yang memiliki kunci apa pun dalam rentang
[0, 700). Baris ini dimiliki oleh Bagian 0, Bagian 1, dan Bagian 2. - Karena operasi baca ini kuat di beberapa mesin, Lapisan API memilih
stempel waktu pembacaan menggunakan TrueTime saat ini. Hal ini memastikan bahwa kedua operasi baca tersebut menampilkan data dari snapshot database yang sama.
- Jenis pembacaan lain, seperti pembacaan yang sudah tidak berlaku, juga memilih stempel waktu untuk dibaca (tetapi stempel waktu mungkin sudah berlalu).
- Lapisan API mengirim permintaan baca ke beberapa replika Bagian 0, beberapa replika Bagian 1, dan beberapa replika Bagian 2. Kode ini juga menyertakan stempel waktu baca yang telah dipilihnya pada langkah di atas.
Untuk pembacaan yang kuat, replika penayangan biasanya membuat RPC ke pemimpin untuk meminta stempel waktu transaksi terakhir yang perlu diterapkan dan pembacaan dapat dilanjutkan setelah transaksi tersebut diterapkan. Jika replika adalah pemimpin atau menentukan bahwa replika sudah cukup untuk menayangkan permintaan dari status internal dan TrueTime, replika akan langsung menayangkan pembacaan.
Hasil dari replika digabungkan dan ditampilkan ke klien (melalui lapisan API).
Perhatikan bahwa operasi baca tidak memperoleh kunci dalam transaksi hanya baca. Dan karena read berpotensi ditayangkan oleh replika terbaru dari bagian tertentu, throughput baca sistem mungkin sangat tinggi. Jika klien dapat menoleransi pembacaan yang setidaknya tidak berlaku selama sepuluh detik, throughput baca dapat menjadi lebih tinggi. Karena pemimpin biasanya memperbarui replika dengan stempel waktu aman terbaru setiap sepuluh detik, pembacaan pada stempel waktu yang tidak berlaku dapat menghindari RPC tambahan ke pemimpin.
Kesimpulan
Secara tradisional, desainer sistem database terdistribusi mendapati bahwa jaminan transaksional yang kuat itu mahal, karena semua komunikasi lintas mesin yang diperlukan. Dengan Spanner, kami telah berfokus pada pengurangan biaya transaksi agar bisa dilakukan dalam skala besar dan meskipun sudah didistribusikan. Alasan utama fitur ini berfungsi adalah TrueTime, yang mengurangi komunikasi lintas-mesin untuk berbagai jenis koordinasi. Selain itu, engineering dan penyesuaian performa yang cermat telah menghasilkan sistem dengan performa tinggi bahkan sekaligus memberikan jaminan yang kuat. Di Google, kami mendapati bahwa hal ini mempermudah pengembangan aplikasi di Spanner dibandingkan dengan sistem database lain dengan jaminan yang lebih lemah. Saat developer aplikasi tidak perlu khawatir tentang kondisi race atau inkonsistensi dalam data, mereka dapat berfokus pada hal yang benar-benar penting—mem-build dan mengirimkan aplikasi yang bagus.