Migrasi Data Ledger Uber dari DynamoDB ke LedgerStore

• Platform pembayaran Uber memindahkan arsitektur campuran DynamoDB·TerraBlob·LedgerStore ke arsitektur yang berpusat pada LedgerStore, setelah data ledger yang terkumpul sejak 2017 tumbuh menjadi lebih dari 1 triliun entri dan berukuran beberapa PB
• Karena beban biaya DynamoDB, struktur yang sebelumnya hanya mempertahankan data 12 minggu terakhir memilih LedgerStore, sebuah penyimpanan bergaya ledger append-only, sebagai solusi jangka panjang
• Validasi dilakukan dengan menggabungkan validasi bayangan yang mereplikasi traffic produksi dan validasi offline yang membandingkan dump penuh, sehingga risiko pada data saat ini dan data dingin dapat diperiksa secara terpisah
• Backfill dapat menghasilkan beban lebih besar daripada traffic normal, sehingga dilakukan secara bertahap dengan batch kecil, idempotensi, pengendalian laju, penghentian darurat, dan pemisahan record bermasalah
• Peralihan di-roll out secara konservatif selama beberapa minggu, dan setelah fallback awal serta mempertahankan data DynamoDB selama satu bulan, proses diselesaikan tanpa downtime hingga backup akhir dan penghapusan tabel

---

Target migrasi dan struktur penyimpanan lama

• Platform pembayaran Uber Gulfstream menggunakan DynamoDB sebagai penyimpanan saat diluncurkan pada 2017
• Pada skala Uber, biaya DynamoDB membesar sehingga struktur penyimpanan terbagi menjadi tiga jalur
  • Data panas 12 minggu terakhir disimpan di DynamoDB
  • Data dingin yang lebih lama disimpan di TerraBlob, blob store internal Uber
  • Data sudah ditulis ke LedgerStore, dan LedgerStore menjadi target migrasi akhir
• Cakupan migrasi adalah data ledger seluruh bisnis Uber sejak 2017
  • Record immutable: 1,2PB dalam keadaan terkompresi
  • Indeks sekunder: 0,5PB dalam keadaan tidak terkompresi
• Setelah ditulis sekali, record ledger secara praktis tidak dapat diubah; jika perlu memperbaiki masalah, data indeks sekunder dapat dimodifikasi

Alasan memilih LedgerStore

• LedgerStore adalah database bergaya ledger append-only
• Desain yang disesuaikan untuk data pembayaran cocok dengan kebutuhan Gulfstream
  • Immutability yang dapat diverifikasi, yang memeriksa apakah record telah diubah melalui tanda tangan kriptografis
  • Penyimpanan bertingkat yang membagi data panas dan data dingin sesuai pemrosesan request dan biaya penyimpanan
  • Karakteristik latensi yang lebih baik untuk indeks sekunder dengan eventual consistency
• Mengurangi tiga penyimpanan menjadi satu menyederhanakan kode akses penyimpanan Gulfstream dan desain pembuatan indeks
• LedgerStore berjalan on-premises di dalam data center Uber, sehingga dapat memberikan latensi jaringan yang lebih cepat
• Migrasi ke LedgerStore juga memberikan efek besar dalam pengurangan biaya berulang

Stabilitas traffic saat ini yang dikonfirmasi melalui validasi bayangan

• Untuk menilai apakah backfill sudah benar, digunakan lima kriteria
  • Kelengkapan: semua record telah di-backfill
  • Akurasi: semua record benar
  • Beban: LedgerStore dapat menangani beban saat ini
  • Latensi: latensi P99 LedgerStore berada dalam batas yang dapat diterima
  • Latensi indeks: keterlambatan pembuatan indeks sekunder di background berada dalam batas yang dapat diterima
• Validasi bayangan membandingkan respons berbasis penyimpanan lama dengan respons ketika LedgerStore digunakan sebagai sumber data
• Tujuannya adalah membuat kelengkapan dan akurasi backfill berdasarkan validasi bayangan setidaknya 99,99%, dengan batas atas 99,9999%
• Batas atas diperlukan karena dalam validasi data berskala besar, jika semua kasus mencurigakan diselidiki sampai tuntas, proyek bisa terhenti
  • Migrasi data historis dapat mencakup penulisan yang salah pada tahap pengembangan awal atau kerusakan data akibat skala
  • Meskipun S3 menjamin durabilitas 11 nines, pada skala 1 triliun record dapat diperkirakan ada 10 kerusakan
  • Pada indeks dengan eventual consistency, record yang akan muncul beberapa detik kemudian dapat terlihat hilang dalam validasi bayangan, menghasilkan false positive
  • Untuk memverifikasi 6 nines secara dapat dipercaya, diperlukan perbandingan 100 juta entri; pada 1.000 perbandingan per detik, pengumpulan data membutuhkan lebih dari satu hari
  • Untuk 7 nines, dalam kondisi yang sama perlu menunggu 12 hari
• Dengan mereplikasi traffic produksi ke LedgerStore, beban, latensi, latensi indeks, dan keandalan kode akses dapat diperiksa sekaligus
• Masalah latensi dan latensi indeks yang ditemukan selama migrasi mengarah pada beberapa perbaikan
  • Optimasi partition key untuk memperbaiki distribusi data indeks
  • Perbaikan masalah indeks yang memicu scan record alih-alih point lookup
• Validasi bayangan live berguna untuk data yang sedang diakses, tetapi sulit memberikan jaminan kuat untuk keseluruhan data historis yang hampir tidak pernah diakses

Validasi offline dan backfill inkremental

• Validasi offline membandingkan seluruh data LedgerStore dengan dump data DynamoDB
• Karena traffic live terutama mengakses data terbaru, masalah tersembunyi pada data dingin sulit ditemukan hanya dengan validasi bayangan
• Record yang memiliki isu data harus dilewati agar backfill dapat terus berjalan, dan kemungkinan bug pada pekerjaan backfill itu sendiri juga perlu dipertimbangkan
• Pekerjaan validasi terbesar menargetkan data 70TB terkompresi, diperkirakan 300TB tidak terkompresi, dan membandingkan 760 miliar record dalam satu pekerjaan
• Pekerjaan Apache Spark pada skala ini membutuhkan data shuffle, dan menggunakan Distributed Shuffle as a Service for Spark, Dynamic Resource Allocation, serta Speculative Execution
• Record hilang yang ditemukan melalui validasi offline digunakan sebagai input untuk backfill inkremental
• Dengan mengulang validasi dan backfill, dipastikan semua record telah ditulis

Masalah operasional yang dihadapi dalam backfill

• Backfill harus dimulai dari skala kecil lalu ditingkatkan secara bertahap hingga batas sistem
  • Jika dipaksa melewati batas tanpa kendali, situasinya sama seperti melakukan DDoS terhadap sistem sendiri
  • Bottleneck harus ditemukan dan diselesaikan, lalu skala diperbesar lagi
  • Setelah setiap peningkatan skala, diperlukan monitoring yang ketat
• Jika data bertahun-tahun di-backfill dalam beberapa bulan, beban yang muncul jauh lebih besar daripada traffic normal
  • Jika produksi memproses 1.000 entri per detik, backfill 100 miliar record pada 10.000 entri per detik membutuhkan 120 hari
  • Jika ada kemungkinan pekerjaan backfill menyebabkan gangguan saat berjalan, pekerjaan harus segera dihentikan
• Backfill tidak boleh berupa pekerjaan yang berjalan dari awal sampai akhir sekaligus, melainkan harus dibagi menjadi batch inkremental
  • Setiap batch harus cukup kecil agar dapat selesai dalam beberapa menit
  • Karena pekerjaan dapat berhenti di tengah batch, proses harus idempoten
  • Saat batch selesai, statistik seperti jumlah record yang dibaca dan jumlah record yang di-backfill ditulis ke file lalu diagregasi untuk memeriksa progres
• Backfill yang aman membutuhkan pengendalian laju yang dapat disesuaikan
  • Di Java/Scala, RateLimiter dari Guava dapat digunakan
  • Jika dapat berjalan lebih cepat saat traffic produksi rendah, RPS disesuaikan dengan memonitor kondisi sistem
  • Uber menyesuaikan RPS dengan metode additive increase/multiplicative decrease, tetapi tetap mempertahankan batas atas demi keamanan
• Jika dicurigai ada gangguan atau overload, backfill harus dapat dihentikan dengan cepat
  • Selama gangguan, backfill harus dihentikan sebagai langkah pencegahan dan untuk mengurangi noise
  • Bahkan setelah gangguan, proses pemulihan sistem dapat menimbulkan beban tambahan
  • Fitur penghentian darurat juga membantu debugging masalah terkait skala

File besar, toleransi kegagalan, dan logging

• Ukuran file dump data sebaiknya dipertahankan sekitar 1GB, dengan fleksibilitas sekitar 10x ke kedua arah
  • Jika file terlalu besar, bisa terkena batas MultiPart pada berbagai tool
  • Jika file terlalu kecil, jumlah file menjadi terlalu banyak sehingga hanya mengambil daftar file pun dapat memakan waktu besar
  • Saat menjalankan perintah shell, dapat terbentur batas ARGMAX
• Dalam proses transformasi data untuk backfill, masalah kualitas data atau record rusak pasti akan muncul
  • Karena record bermasalah tersebar secara acak, pekerjaan tidak bisa dihentikan setiap kali muncul
  • Pada saat yang sama, masalah tersebut bisa saja bug kode, sehingga tidak boleh diabaikan
  • Record bermasalah di-dump secara terpisah dan statistiknya dimonitor
  • Jika tingkat kegagalan tinggi, backfill dihentikan secara manual, masalah diperbaiki, lalu dilanjutkan
• Penulisan record dapat gagal karena RPC timeout
  • Retry dapat dilakukan, tetapi pada titik tertentu proses harus menyerah apa pun alasannya dan terus berjalan agar keseluruhan pekerjaan maju
• Meski ingin meninggalkan banyak log untuk debugging dan pemeriksaan progres, hal itu dapat memberi tekanan besar pada infrastruktur logging
  • Walaupun log dapat ditulis, jumlah yang harus disimpan bisa menjadi terlalu besar
  • Rate limiting diterapkan pada bagian yang menghasilkan banyak log
  • Jika error jarang terjadi, semua log error juga dapat disimpan

Rollout bertahap dan penghapusan fallback

• Peralihan ke LedgerStore menurunkan risiko melalui rollout konservatif selain analisis statistik validasi dan backfill
• Rollout dilakukan selama beberapa minggu, bersama persetujuan engineer on-call dari layanan pemanggil utama
• Pada awalnya, digunakan fallback yang mengambil data dari DynamoDB jika data tidak ditemukan di LedgerStore
• Setiap record yang ditandai hilang dalam log fallback diperiksa kembali apakah benar-benar tidak ada di LedgerStore
• Setelah fallback dihapus, data DynamoDB tetap dipertahankan selama satu bulan
• Setelah itu, penulisan ke DynamoDB dihentikan, backup akhir dibuat, lalu tabel dihapus
• Seluruh migrasi berlangsung selama 2 tahun dan selesai tanpa downtime atau gangguan selama maupun setelah migrasi

[GN⁺]

Opini Hacker News

• Penasaran apakah 1,7 petabyte data (1 triliun record terindeks) bisa dimasukkan ke satu server bare-metal yang sangat kuat dengan biaya di bawah beberapa ribu dolar per bulan, lalu dilayani dengan SQLite.
  Misalnya dengan cara seperti ini: https://use.expensify.com/blog/scaling-sqlite-to-4m-qps-on-a...

  • 1,7 petabyte dimasukkan ke SQLite? Rekomendasi SQLite sendiri begini: jika data tampaknya akan menjadi begitu besar sehingga tidak nyaman atau mustahil dimasukkan ke satu file disk, pilih solusi selain SQLite.
    SQLite mendukung database hingga maksimum 281 terabyte, dengan asumsi Anda bisa menemukan disk dan filesystem yang mendukung file 281 terabyte. Meski begitu, jika ukuran konten menunjukkan tanda-tanda akan tumbuh ke skala terabyte, mereka menyarankan mempertimbangkan database client/server tersentralisasi daripada SQLite.
  • SSD 30,7 TB harganya sekitar 5.500 dolar per unit, dan untuk mencapai 1,7 PB dibutuhkan 56 unit bahkan tanpa redundansi. Selain itu, ukuran DB maksimum SQLite adalah 140 TB.
    Rasanya sulit memasukkan kapasitas penyimpanan sebesar ini ke satu server, apalagi dengan biaya beberapa ribu dolar per bulan. SQLite juga tidak cocok untuk penggunaan ini.
  • Proposisi nilai cloud komersial bukanlah penghematan biaya, kecuali Anda mengkuantifikasi semua faktor tambahan/eksternal seperti risiko keamanan, pendinginan dan pemanasan, staf data center, serta siklus hidup hardware.
    Perusahaan dengan modal dan kapasitas organisasi yang cukup bisa membangun cloud sendiri dengan jauh lebih murah, tetapi sebagian besar perhitungannya ada pada mengalihdayakan faktor risiko.
  • Sebagus apa pun palu yang Anda punya, sebagian hal memang bukan paku sejak awal.
  • Tidak bisa. SQLite “hanya” bekerja hingga 281 TB [0] [1]
    [0] https://www.sqlite.org/releaselog/3_33_0.html
    [1] https://www.sqlite.org/limits.html (#12)

• LedgerStore sepertinya bukan open source [1], dan untuk mencari informasi terkait, kita harus mengikuti tulisan blog Uber yang saling memberi backlink.
  Dari tulisan yang terbit pada 2021, yang tampaknya memuat informasi LedgerStore paling banyak adalah ini:
  https://www.uber.com/en-US/blog/dynamodb-to-docstore-migrati...
  [1]:https://github.com/uber

  • Benar. Tampaknya ini solusi internal.
    Secara umum, Uber tampaknya cukup condong ke pendekatan membangun sendiri. Mereka cenderung menyimpulkan bahwa solusi open source yang ada belum cukup, lalu membuat sendiri. Ini berbeda, misalnya, dari pendekatan Facebook yang meningkatkan MySQL dengan MyRocks/RocksDB dan mempertahankannya sebagai open source.

• Kalau membaca artikelnya, terlihat bahwa Uber sudah cukup cepat menggunakan DynamoDB dengan cara yang salah.
  Beberapa perjalanan pengguna inti tampaknya membutuhkan konsistensi kuat, dan transaksi lama membutuhkan data warehousing dalam jumlah besar.
  Aneh mereka tidak lebih dulu mengubah struktur DynamoDB dua tabel itu menjadi arsitektur seperti DynamoDB + Redshift. Itu pola yang cukup umum.

  • Bisa bagikan referensi tentang pola ini?
  • Saya tidak paham mengapa transaksi immutable selama 2 minggu harus dimasukkan ke Dynamo. Ada yang bisa memberi petunjuk?

• Sekitar 2015, ada masa ketika perusahaan teknologi keren seperti Netflix, Spotify, SoundCloud, dan Uber banyak membuat tool infrastruktur dan database.
  Sekarang engineer sering berbicara dalam istilah AWS/cloud.
  Rasanya menyegarkan melihat masih ada organisasi yang membuat tool seperti ini sendiri.

• Saya tidak tahu keekonomian proyek spesifik ini, tetapi DynamoDB memang sangat mahal.
  Dulu saya mengira orang lain semuanya memakai DynamoDB dengan salah, melakukan scan dan query alih-alih point lookup pada tabel yang sudah diprakomputasi.
  Namun bahkan jika dipakai seperti distributed hash table, Anda tetap membayar premium besar.

  • Saya tidak mengerti mengapa disebut mahal. Jika 100 WCU per tahun 120 dolar, dan 100 RCU per tahun 30 dolar, itu tidak terdengar mahal.
    Karena 1 RCU membaca hingga 4 KB, untuk membaca 100 MB dibutuhkan 100.000 RCU, yaitu 30.000 dolar per tahun atau 2.500 dolar per bulan. Kalau hitungan saya tidak salah, dari sisi harga saya rasa hampir tidak ada yang sebanding.

• Penasaran apakah mereka mempertimbangkan https://tigerbeetle.com

  • Pasti menarik. TigerBeetle ditulis dengan Zig.
    Dan Uber mungkin salah satu dari sedikit perusahaan besar yang punya kontrak dukungan dengan Zig Foundation.

• Selamat untuk orang-orang yang terlibat dalam pekerjaan ini. Namun biaya menjalankan tim ini saja tampaknya cukup besar dan mungkin tidak jauh berbeda dari penghematan 6 juta dolar, ditambah beban maintenance.
  Sistem pembayaran juga tampaknya kecil kemungkinan menjadi taruhan jangka panjang; menarik mengapa tim-tim mengambil proyek seperti ini. Apakah ini semacam sunk cost karena tim engineering yang sudah dimiliki?

  • Di satu ujung spektrum ada orang-orang yang mengklaim bisa membuat software seperti ini dalam satu akhir pekan. Di ujung lain ada yang mengklaim butuh gaji 600 ribu dolar dan 9 rekan lagi untuk bisa menyelesaikan hal seperti ini.
    Di antara keduanya ada banyak ruang untuk estimasi biaya yang lebih realistis.
  • Estimasi itu mencurigakan sangat mirip dengan hanya menghitung biaya penyimpanan data DynamoDB.
    Jika data dan indeksnya 1,7 PB, berdasarkan harga daftar storage DynamoDB biayanya sekitar 5,1 juta dolar per tahun.
  • Jika 5 juta dolar per tahun dipakai untuk mengembangkan dan memelihara sistem DB yang sepenuhnya kustom pada skala itu, kira-kira bisa mempekerjakan 25 engineer senior dan masih menyisakan 1 juta dolar untuk biaya peralatan.
    Tampaknya cukup realistis untuk memiliki sistem khusus yang disesuaikan dengan baik untuk bagian inti bisnis.
  • Sepertinya tepat untuk menganggap mereka jauh lebih tahu tentang biaya mereka sendiri, sementara Anda hampir tidak tahu apa-apa. Tidak banyak nilainya merendahkan anggota tim dengan cara seperti ini.
  • Kalau membaca artikelnya, sistem ini adalah lapisan di atas DynamoDB, lalu diperbarui agar memakai produk internal Docstore, dan dalam prosesnya mereka perlu menambahkan satu fitur ke Docstore.
    Ini bukan pekerjaan sebesar yang orang-orang katakan. Selain itu, karena record-nya immutable, banyak hal menjadi jauh lebih mudah.

• Penasaran apakah ini contoh pengecualian lain ketika, setelah mencapai skala tertentu, membangun sendiri menjadi lebih menguntungkan. Skala yang harus ditangani Uber cukup mengejutkan.
  Dari artikel aslinya saja, tidak jelas berapa total biaya kepemilikan layanan yang baru direfaktor ini. Bukankah sekarang mereka harus mengelola database sendiri dan storage di belakangnya? Apakah ada yang saya lewatkan?

  • Saya pernah bekerja di perusahaan yang pada tahap prototipe memakai Redis, lalu menulis database sendiri untuk meningkatkan performa dan resiliensi.
    Perusahaan itu bukan menjual produk untuk end user, melainkan menjadikan distributed filesystem sebagai produknya.
    Menurut saya, sebagian besar perusahaan tidak punya keahlian untuk membangun sistem seperti database, dan meskipun secara biaya pengembangan tampak masuk akal, dalam praktiknya mereka takut melakukan hal seperti itu.

• Menurut saya ini contoh yang sangat baik tentang seberapa mahal data store berbasis cloud proprietary bisa menjadi, dan bahwa berpindah darinya ke sesuatu yang lain secara realistis memungkinkan.

• Dengan asumsi orang bertindak logis, rasanya hari perhitungan bagi penyedia layanan cloud akan datang.
  Saya pernah melakukan pekerjaan kontrak di sebuah perusahaan kecil; mereka memakai GCP Bigtable untuk menjalankan laporan dari data yang berasal dari DB MySQL berukuran 375 MB, dan biayanya lebih dari 11.000 dolar per bulan.
  Mereka mempekerjakan data scientist yang baru lulus untuk membuat laporan, dan ia melakukan hal yang sangat tidak efisien pada dataset yang sangat kecil. Mereka meminta saya memperbaikinya besok juga dengan bayaran receh, jadi saya menolak.

  • Saya setuju dengan poin besarnya, tetapi menurut saya contoh ini bukan contoh yang bagus.
    Itu hanya sistem yang dirancang buruk. Jika mereka menjalankan hal yang sama dengan database on-premise yang diprovision secara berlebihan, masalah yang sama juga akan muncul.