Risiko kunci utama UUID di SQLite

 (andersmurphy.com)
1 poin oleh GN⁺ 4 jam lalu | 1 komentar | Bagikan ke WhatsApp
  • Implementasi kunci utama di SQLite membuat urutan penyimpanan fisik berbeda antara tabel rowid biasa dan tabel WITHOUT ROWID, dan jika UUID4 acak digunakan sebagai clustered index, akan timbul penyeimbangan ulang B-tree serta biaya paging tambahan
  • Baseline integer rowid mencatat sekitar 1 juta insert per detik pada penyisipan per 1 juta baris, sedangkan UUID4 WITHOUT ROWID mencatat waktu insert 14–16 kali lebih lambat
  • Sifat UUID4 yang tidak berurutan membuat baris dimasukkan ke B-tree secara acak, dan hasil profiling menunjukkan lebih banyak waktu dipakai untuk penyeimbangan pohon serta operasi baca-tulis
  • UUID7 WITHOUT ROWID menggunakan UUID berurutan berdasarkan waktu untuk mengurangi masalah pengurutan pada UUID4, sehingga menunjukkan waktu insert yang lebih masuk akal, tetapi tetap lebih lambat daripada kunci integer 8-byte karena memakai kunci BLOB 16-byte
  • UUID4 WITH ROWID mendapatkan keuntungan dari rowid tersembunyi yang berurutan, tetapi write amplification akibat dua indeks dan biaya insert indeks acak tetap ada, sehingga performanya masih di bawah UUID7 WITHOUT ROWID

Apa itu clustered index?

  • Clustered index adalah indeks yang menentukan urutan penyimpanan fisik baris tabel
  • Karena baris secara fisik hanya bisa diurutkan dengan satu cara, setiap tabel hanya bisa memiliki satu clustered index
  • Clustered index adalah tabel itu sendiri, sedangkan non-clustered index hanya menyimpan kolom yang diindeks dan pointer ke lokasi data baris yang sebenarnya

Rowid

  • Semua tabel SQLite biasa memiliki kunci utama integer 64-bit implisit bernama rowid
  • Data tabel disimpan dalam struktur B-tree dengan satu entri untuk tiap baris, menggunakan nilai rowid sebagai kunci
  • rowid pada praktiknya adalah clustered index milik SQLite, dan urutan penyimpanan fisik baris mengikuti urutan rowid
Iklan

WITHOUT ROWID

  • SQLite mendukung tabel WITHOUT ROWID, dan tabel ini tidak memiliki rowid implisit
  • Pada tabel WITHOUT ROWID, kunci utama yang dideklarasikan berperan sebagai clustered index
  • Tabel SQLite rowid diimplementasikan sebagai B*-Tree yang menyimpan seluruh konten di leaf, sedangkan tabel WITHOUT ROWID memakai B-Tree biasa yang menyimpan konten di leaf dan node perantara

Baseline: kunci utama integer rowid

  • Baseline mengukur waktu insert per 1 juta baris pada tabel rowid biasa dengan struktur id INTEGER PRIMARY KEY, data BLOB
  • Total jumlah baris pada tabel hasil berkisar dari 10 juta hingga 100 juta baris, dengan waktu terukur antara 692ms sampai 838ms
  • Performa baseline kira-kira berada di level 1 juta insert per detik

UUID4 WITHOUT ROWID

  • Pengujian UUID4 dilakukan pada tabel WITHOUT ROWID dengan struktur id BLOB PRIMARY KEY, data BLOB, dengan nilai kunci utama random-uuid4-bytes
  • Waktu terukur pada tabel hasil adalah 2649ms untuk 10 juta baris dan 12586ms untuk 100 juta baris
  • Performa insert berada di kisaran 14–16 kali lebih lambat daripada baseline integer rowid

Profil

  • Diffgraph ternormalisasi membandingkan snapshot profiling INTEGER dan UUID4, lalu menampilkan perbedaannya dalam struktur flamegraph
  • Tampilan ternormalisasi menyesuaikan total jumlah sampel dari dua profil agar sama, sehingga perbedaan relatif bisa dilihat dalam persentase
  • Frame biru menunjukkan bahwa waktu fungsi tersebut berkurang pada profil kedua, yaitu UUID4, dibanding INTEGER; frame merah menunjukkan waktunya meningkat pada UUID4
  • Intensitas warna menunjukkan perubahan relatif pada jumlah sampel frame itu sendiri, yaitu perubahan self time delta
  • Pada diffgraph terlihat lebih banyak waktu dipakai untuk penyeimbangan pohon serta operasi baca-tulis
  • Karena UUID4 tidak berurutan, kunci diurutkan secara acak dan SQLite harus terus-menerus menyeimbangkan ulang B-tree
Iklan

UUID7 WITHOUT ROWID

  • UUID7 adalah UUID berurutan berdasarkan waktu, sehingga dapat menghilangkan masalah pengurutan pada UUID4
  • Pengujian UUID7 juga dijalankan pada tabel WITHOUT ROWID dengan struktur id BLOB PRIMARY KEY, data BLOB
  • Waktu terukur pada tabel hasil adalah 1372ms untuk 10 juta baris dan 1258ms untuk 100 juta baris
  • UUID7 WITHOUT ROWID kembali ke angka yang lebih masuk akal dibanding UUID4 WITHOUT ROWID, tetapi tetap lebih lambat daripada baseline
  • Kunci utama UUID bertipe BLOB berukuran 16-byte, sedangkan kunci utama integer berukuran 8-byte

UUID4 WITH ROWID

  • Pengujian UUID4 WITH ROWID menggunakan tabel id BLOB PRIMARY KEY, data BLOB tanpa WITHOUT ROWID
  • Dalam konfigurasi ini, rowid tersembunyi menjadi clustered index, dan keunggulan rowid adalah sifatnya yang berurutan
  • Kekurangannya adalah tabel memiliki dua indeks, sehingga menimbulkan write amplification
  • Waktu terukur pada tabel hasil adalah 2003ms untuk 10 juta baris dan 7119ms untuk 100 juta baris
  • UUID4 WITH ROWID tidak sebaik UUID7 WITHOUT ROWID, karena meskipun bukan clustered index, indeks tetap harus terus dibangun lewat insert acak

Kesimpulan

  • Di SQLite, kunci utama UUID adalah pilihan yang performa insert-nya bisa sangat berbeda tergantung clustered index dan keterurutan kuncinya
  • Masalah UUID acak tidak terbatas pada SQLite saja, tetapi juga berlaku pada database lain yang menggunakan clustered index
  • Seluruh kode benchmark tersedia di repositori GitHub

Bacaan terkait

1 komentar

 
GN⁺ 4 jam lalu
Komentar Lobste.rs

  • Bagus. Akan menarik juga melihat angka saat pada tabel rowid, kunci integer bukan meningkat monoton melainkan acak
    Poin penting yang terlewat dari tulisan itu adalah indeks dasar tabel rowid adalah pohon B+, sedangkan tabel without rowid adalah pohon B
    Karena itu, secara umum jika ukuran rata-rata record melewati ambang tertentu, yang belakangan tidak ideal. Sebab node internal indeks menyimpan seluruh record, dan kalau tidak salah manual SQLite menyarankan 1/20 ukuran halaman sebagai aturan praktis

  • Sudah bersusah payah mengukur performa UUID, tapi kunci alami tidak dipertimbangkan
    Baik integer, UUID, maupun bentuk lain, kunci pengganti menambah kompleksitas, tidak menambah informasi, dan menyembunyikan kesalahan normalisasi
    Penulis menyebut “mencegah duplikasi” sebagai alasan memakai UUID, tapi itu bukan alasan. Setiap baris di setiap tabel pada setiap basis data setidaknya harus memiliki satu kunci, yaitu kumpulan kolom yang secara unik mengidentifikasi baris itu
    Basis data yang tidak punya kunci seperti itu menyimpan informasi duplikat dan rentan terhadap inkonsistensi logis. Basis data yang sudah punya kunci seperti itu tidak membutuhkan kunci pengganti. Jika kunci alami sudah ada dan ditegakkan, klaim “perlu demi performa” berarti ada biaya tambahan dan kompleksitas yang tidak perlu, jadi perlu dibuktikan

    • Mungkin saya kurang imajinasi, tapi saat menangani data yang datang dari dunia nyata, menurut saya biasanya sulit menemukan kunci alami yang benar-benar nyata
      Nilai yang tampak unik sering kali tidak seunik yang diharapkan, atau nilai yang diperkirakan tidak berubah ternyata pada akhirnya harus diubah
      Sebaliknya, dengan memakai kunci pengganti saya bisa mendefinisikan identitas di dalam sistem saya sendiri tanpa bergantung pada bagaimana orang lain mendefinisikan keteridentifikasian, atau biasanya gagal mendefinisikannya dengan baik
      Ada pengecualian. Jika saya mendefinisikan seluruh modelnya, dan datanya tidak datang dari apa yang disebut dunia nyata, maka kunci alami lebih masuk akal. Tetapi saat merancang skema yang menampung data dunia nyata yang mungkin tidak pernah sepenuhnya ternormalisasi, kunci pengganti sering berguna
    • Kunci pengganti integer yang meningkat monoton punya kegunaan praktis yang langsung terasa
      Baris apa pun bisa direferensikan sebagai integer sehingga akses menjadi jauh lebih sederhana, dan mudah diingat manusia maupun dipakai dalam kueri
      Jika meningkat monoton, itu sendiri juga membawa informasi. Memang informasi yang redundan, tapi tetap fakta
      Kecepatan pencarian juga optimal. Ini nyaris kondisi terbaik untuk diindeks dengan pohon B, bitmap, dan sebagainya
      Menurut saya orang terutama memakai UUID karena kebingungan. Biasanya logikanya untuk menyamarkan kunci dan membuatnya tidak bisa ditebak, tapi saya sudah menyerah memahami mengapa tujuan itu harus dipaksakan sampai ke kunci primer, bukannya memakai pengenal terpisah untuk tujuan tersebut
    • Frasa “mencegah duplikasi” tidak muncul di tulisan blog itu. Sebenarnya tulisannya sama sekali tidak menjelaskan mengapa UUID dipakai

  • UUID versi 7 punya timestamp 48-bit di bagian depan, jadi tidak terdistribusi acak seperti ini. Karena itu paging berlebihan dan penyeimbangan ulang juga akan berkurang

    • Benar. Yang dibahas di tulisan itu memang UUID7

  • Apakah orang benar-benar memakai UUID sebagai kunci primer? Kalau memang butuh UUID, saya penasaran apa keuntungan melakukan itu alih-alih menjadikannya kunci sekunder

    • Karena skalabilitas. Jika Anda ingin menghasilkan ID unik secara terdistribusi dengan kecepatan tinggi di banyak komputer dan berbagai pusat data di seluruh dunia, misalnya seperti unggahan S3, Anda tidak ingin mengunci integer tunggal yang terus bertambah. Penguncian lambat untuk disinkronkan secara global
      GUID dan UUID secara struktural menyelesaikan masalah ini
      v1 dan v6 mengodekan ID mesin dan timestamp, sehingga mirip integer auto-increment dengan namespace per mesin
      Kebingungan muncul karena banyak orang menganggap UUID itu acak. Itu hanya berlaku untuk v4, dan memilih v4 sayangnya memang ada biayanya
      Sering kali ada kebutuhan akan tingkat determinisme tertentu seperti v3, v5, v7 untuk membantu merapikan data atau demi jaminan performa dan benturan
    • Meski UUID acak atau nilai acak berdistribusi seragam ditempatkan sebagai kunci sekunder, penyisipan tetap melambat. Walaupun bukan clustered index, pada pohon B indeks itu tetap terjadi penyisipan acak