Optimasi server tablebase Lichess

• Karena beban permintaan, Lichess kesulitan menyelesaikan pemeriksaan RAID berkala pada server tablebase Syzygy 7-piece, sehingga beralih dari metode memindai seluruh blok ke verifikasi integritas saat pembacaan
• Untuk memindahkan tablebase 17TiB tanpa downtime berjam-jam, mereka menyiapkan server baru dan memverifikasinya dengan memutar ulang log permintaan nyata pada lingkungan 32GiB RAM, 2×201GiB NVMe, dan 6×5.46TiB HDD
• Hasil pemutaran ulang 1 juta permintaan yang dicatat di produksi dengan 12 klien paralel menunjukkan bahwa latensi ekor yang dirasakan pengguna, bukan respons rata-rata, adalah bottleneck utama
• Dari sisi implementasi, pread(2) lebih unggul daripada mmap dalam penanganan error dan latensi ekor, sementara petunjuk akses acak seperti POSIX_FADV_RANDOM dan MADV_RANDOM umumnya justru berdampak negatif
• Pada SSD yang terbatas, mereka menempatkan prefix table dan memparalelkan probe di dalam permintaan untuk mengurangi akses disk lambat, lalu memeriksa apakah peningkatan benchmark juga tercermin pada waktu respons produksi

---

Beralih ke verifikasi saat pembacaan alih-alih pemeriksaan penuh RAID

• Server tablebase Syzygy 7-piece milik Lichess kesulitan menuntaskan pemeriksaan integritas RAID berkala saat permintaan tablebase sedang tinggi
• Konfigurasi baru menggunakan dm-integrity on LVM agar tidak perlu memeriksa seluruh blok data secara berkala, melainkan memverifikasi setiap kali blok dibaca
• Untuk memindahkan tablebase 17TiB tanpa downtime selama beberapa jam, mereka menyiapkan server baru secara terpisah
  • Sebelum cutover nyata, mereka bisa menjalankan benchmark terkontrol terhadap seluruh tablebase
  • Setelah itu, mereka beralih ke server baru dan memensiunkan server lama

Konfigurasi server baru

• RAM dipertahankan sama seperti sebelumnya, yaitu 32GiB
• Untuk penyimpanan, ditambahkan 2×201GiB NVMe yang tidak ada di server lama, dan sisa ruang dari disk 476GiB dicadangkan untuk OS serta workspace
• HDD bertambah dari 5 buah menjadi 6×5.46TiB HDD
• Sistem operasinya Debian bookworm, dengan kernel keluarga Linux 6.1.0-21-amd64
• Scheduler I/O default yang terpilih adalah none untuk NVMe dan mq-deadline untuk HDD

Konfigurasi dan pemantauan RAID 5

• RAID 5 cocok untuk server tablebase karena dapat pulih dari kegagalan satu disk dan menyebarkan pembacaan acak ke beberapa disk
• Konfigurasi awalnya sebagai berikut

lvcreate --type raid5 --raidintegrity y --raidintegrityblocksize 512 --name tables --size 21T vg-hdd

• Performa pengujian awal cukup baik, tetapi tanpa pemantauan, masalah bahwa sebagian disk tidak berpartisipasi pada tingkat yang sama bisa saja terlewat
• Jika --stripes dihilangkan, semua physical volume tidak otomatis digunakan sebagai default
• Pemantauan aktivitas baca per disk diperlukan untuk menemukan konfigurasi RAID yang salah

Bottleneck yang terlihat dari log permintaan nyata

• Dalam kondisi normal, server menerima 10–35 permintaan per detik
• Mereka merekam 1 juta permintaan di lingkungan produksi, lalu pada skenario terpilih 12 klien paralel mengirimkannya kembali secara berurutan
• Table dibuka dengan model lazy-open, dan cache aplikasi maupun OS terisi secara bertahap
  • 800 ribu waktu respons pertama dikeluarkan sebagai fase warm-up
  • Setelah itu, waktu respons dari 200 ribu permintaan dianalisis
• Waktu respons rata-rata sudah cukup cepat, tetapi latensi ekor yang tinggi menjadi fokus optimasi
• Grafik ECDF menunjukkan persentase permintaan yang lebih cepat daripada suatu waktu respons tertentu, dengan sumbu x dalam skala log
• Ke setiap waktu respons pada grafik ditambahkan 30ms untuk mencerminkan ping time 30ms dari klien
  • Ini dilakukan agar sumbu x berskala log tidak terlalu melebih-lebihkan perbedaan beberapa milidetik di area waktu rendah

pread(2) yang lebih menguntungkan daripada mmap

• Implementasi Syzygy tablebase, shakmaty-syzygy, menyediakan antarmuka yang memungkinkan cara membuka dan membaca file table diganti
• Ada dua kandidat utama
  • mmap: memetakan file table ke memori, lalu pembacaan disk terjadi secara transparan saat area memori tersebut diakses
  • pread(2): melakukan system call pada setiap pembacaan dan melaporkan error baca lewat nilai kembalian
• mmap tidak memerlukan system call tambahan setelah pemetaan, tetapi karena pembacaan terlihat seperti akses memori biasa, error harus ditangani lewat mekanisme out-of-band seperti signal
• Dalam implementasi server, penanganan error yang lebih tangguh saja sudah cukup untuk membenarkan penggunaan pread, dan benchmark juga menunjukkan bahwa pada skenario yang diperhatikan, pread berkinerja lebih baik
• Salah satu kemungkinan penyebabnya adalah bahwa akses ke satu blok data yang dipetakan ke memori bisa melewati batas halaman dan berujung pada dua pembacaan disk
• Bukan berarti pread harus langsung diterapkan pada engine catur
  • Pada pertandingan engine, penggunaan tablebase biasanya terjadi ketika semua table WDL bisa ditempatkan pada media penyimpanan yang cukup cepat
  • Dalam kasus itu, rentang waktu respons umumnya begitu kecil hingga tidak terlihat pada grafik tersebut, dan memory mapping yang mengurangi overhead system call lebih unggul

Efek negatif petunjuk akses acak

• posix_fadvise(fd, 0, 0, POSIX_FADV_RANDOM) dan petunjuk setara untuk memory map pada akhirnya justru sebagian besar berdampak negatif
• POSIX_FADV_RANDOM memberi tahu OS bahwa akses file bersifat acak dan kemungkinan besar read-ahead otomatis tidak berguna, sebagai petunjuk untuk mengurangi tekanan pada page cache
• Pola akses tablebase saat orang menganalisis endgame tampaknya tidak seacak yang diduga
• Pada engine catur, probe bisa lebih tersebar ke berbagai endgame yang mungkin, sehingga hasilnya bisa berbeda

Prefix table yang ditempatkan pada SSD terbatas

• Probe table pertama-tama mengodekan posisi menjadi indeks integer berdasarkan informasi pengodean pada header table
• Setelah itu, ia harus menemukan blok data terkompresi yang berisi hasil untuk indeks tersebut
• Syzygy menyediakan sparse block length list yang menunjuk ke dekat entri yang benar, lalu dilanjutkan dengan block length list untuk menemukan blok data terkait
• Ukuran section table adalah sebagai berikut

Table section	WDL	DTZ	Total
Headers and sparse block length lists	38GiB	9GiB	47GiB
Block length lists	274GiB	64GiB	339GiB
Compressed data blocks	8433GiB	8458GiB	16891GiB

• Ruang SSD juga bisa dipakai sebagai lapisan cache adaptif untuk menyimpan list entry dan data block yang hot
• Untuk tujuan mengurangi latensi ekor, dengan mempertimbangkan kasus terburuk, pendekatan yang cocok adalah menaruh sparse block length list dan block length list di SSD
• Tata letak ini dapat membatasi akses disk lambat menjadi maksimal 1 kali per probe table, terlepas dari apakah datanya hot atau cold
• Pada server tersebut, ruang SSD tidak cukup untuk melakukan mirroring RAID 1, dan karena ini merupakan optimasi selektif, redundansi dikorbankan dengan memakai RAID 0

Paralelisasi probe di dalam permintaan

• Permintaan tablebase yang umum dari engine catur adalah permintaan terhadap satu nilai WDL saja
• Pada antarmuka pengguna, sistem ingin menampilkan nilai DTZ untuk semua langkah
• Termasuk penyelesaian capture di dalam Syzygy, rata-rata satu permintaan menghasilkan 23 probe WDL dan 70 probe DTZ
• Implementasi awal sudah memparalelkan pemrosesan antar-permintaan, tetapi probe di dalam tiap permintaan masih dijalankan secara berurutan
• Paralelisme yang lebih halus memang menambah overhead pada area latensi rendah, tetapi secara signifikan mengurangi latensi ekor
• Meskipun disk secara fisik tidak benar-benar bisa menangani banyak pembacaan paralel, scheduler I/O menjadi lebih mungkin menjadwalkan pembacaan agar setiap permintaan selesai lebih cepat
• Cara ini membantu merencanakan urutan akses disk terkait dengan lebih baik untuk mengurangi waktu tunggu sampai head disk mencapai sektor permintaan berikutnya

Verifikasi di produksi dan data mentah

• Mereka memverifikasi lewat grafik waktu respons apakah optimasi pada skenario benchmark benar-benar membantu di produksi
• Data mentah tersedia secara publik di lila-tablebase-bench

[GN⁺]

Opini di Hacker News

• Lichess adalah layanan yang membuat orang berhenti sejenak dan mengaguminya seperti anggur yang bagus. Ini benar-benar luar biasa untuk komunitas catur, dan saya memakainya setiap hari sambil terus terkesan oleh fitur dan performanya.
  Terutama jika tahu bahwa ini adalah tim berukuran 1–2 orang dengan anggaran terbatas, itu makin menakjubkan.

  • Jangan lupa juga bahwa layanan ini gratis dan open source, tidak meminta uang, dan tidak akan melakukannya di masa depan. Banyak orang berdonasi, pengeluarannya juga dibuka, dan ada aplikasinya.
  • Saya berharap lebih banyak perangkat lunak open source untuk pengguna akhir yang seramah pengguna, dirancang sebaik, dan dipelihara sebaik Lichess.
  • Saya juga merasa begitu. Aplikasi mobile beta baru belakangan ini lebih rapi dan bahkan punya umpan balik haptic, keren.
  • Suatu hari saya ingin membuat sesuatu yang bernilai dan sekeren Lichess.

• Bagian yang menampilkan ECDF dengan tambahan 30 ms pada tiap waktu respons terasa menarik.
  Menambahkan konstanta bisa terlihat artifisial, tetapi sebenarnya itu cara melihat hasil dari sudut pandang klien dengan ping 30 ms, dan membuat sumbu x berskala log tidak melebih-lebihkan selisih beberapa ms di rentang rendah. Mungkin ini teknik standar, tetapi terlihat seperti trik yang cukup cerdas.

• Saya penasaran apakah penghematan biaya memang benar-benar diperlukan, atau ada alasan lain kenapa tidak cukup memasukkan SSD 20 TB ke satu mesin lalu selesai. SSD 4 TB juga sekitar 300 dolar, dan drive SFF HP atau Dell pun tidak jauh lebih mahal.
  Mungkin pengujian dan optimasinya sendiri memang menarik, dan dari sudut pandang produk, waktu yang terbatas mungkin akan dipakai untuk proyek lain.

  • Lichess adalah nirlaba dan punya banyak relawan, jadi kemungkinan keseimbangan antara biaya waktu dan hardware berbeda dari kebanyakan perusahaan komersial.
  • Lichess adalah organisasi nirlaba yang dijalankan hanya dengan donasi dan kerja sukarela. Pegawainya hanya satu orang yang mendirikan organisasi nirlaba itu, dan tampaknya ia mengambil jauh lebih sedikit daripada yang bisa ia peroleh di pekerjaan lain dibandingkan kemampuannya.
    Fakta bahwa organisasinya berbasis di Prancis juga layak disebut, meski saya tidak tahu bagaimana itu memengaruhi biaya.
  • Dengan pekerjaan ini, waktu respons maksimum diturunkan hingga skala satu digit. Jika proyeknya memakan 1 minggu, paling lama 2 minggu, dan waktu respons sebagian pengguna turun dari 15 detik menjadi 1,5 detik, itu jelas cukup bernilai.
    Untuk membenarkan investasi waktu yang lebih baik dari ini, mungkin harus ada proyek dengan pengalaman pengguna yang lebih buruk, atau kasus organisasi komersial yang mengakui ada peluang menghasilkan uang di tempat lain dan tidak terlalu peduli pada penderitaan pelanggan.
  • Insinyur yang menganggap ini sekadar “pengujian dan optimasi untuk bersenang-senang” sepertinya hampir tidak ada di industri selain IT.
    Ini lebih tampak seperti hasil gabungan antara hardware yang terlalu kuat dan murah, serta orang malas yang ingin berkata “cukup sampai di sini untuk hari ini”. Bukankah ada nasihat untuk punya kebanggaan terhadap pekerjaan sendiri?
  • Dari sudut pandang produk itu masuk akal, tetapi Lichess bukan perusahaan komersial yang punya produk, melainkan benar-benar dijalankan sebagai organisasi nirlaba, jadi untuk memahami keputusannya kita perlu mengubah sudut pandang.

• Ada beberapa pilihan yang dipertanyakan dalam optimasi ini. Alasan optimasinya adalah aktivitas I/O terlalu tinggi sehingga pemeriksaan RAID tidak bisa selesai.
  Dari tulisannya saja tidak jelas apakah pemeriksaan RAID atas data 17 TiB itu pernah benar-benar selesai. Sebagai gantinya, mereka mematikan pemeriksaan RAID berkala dan mengubahnya agar pemeriksaan kesalahan dilakukan per halaman saat data dibaca, tetapi kedua cara itu tidak sama dan untuk data penting seharusnya keduanya dipakai.
  Jika kerusakan baru ditemukan saat data hendak dibaca, kerusakan data lama bisa terus tersisa, dan mungkin melewati masa retensi backup sehingga sumber aslinya tidak bisa dipulihkan. Di sini juga ada keputusan beralih ke RAID 0; walau itu pilihan tercepat, berarti mereka cukup besar menaruh kepercayaan bahwa konfigurasi NVMe tersebut akan tahan terhadap beban seperti itu.
  Semoga backup-nya baik. Solusi yang bagus adalah menyalakan server sementara, memulihkan backup, menjalankan pemeriksaan seluruh data, lalu jika berhasil, sekaligus memverifikasi prosedur backup/pemulihan dan integritas file. Meski begitu, tetap perlu menyediakan kelonggaran agar pemeriksaan RAID di server utama bisa selesai, dan sebaiknya tidak memakai RAID 0 demi performa.

  • Benar bahwa kedua cara itu tidak sama, tetapi untuk use case ini sudah cukup. Sebab jika kerusakan data ditemukan, filenya bisa dibuang lalu diunduh ulang atau dibuat ulang.
    Ini adalah dataset yang tersedia bebas, hanya saja ukurannya agak besar. https://en.wikipedia.org/wiki/Endgame_tablebase menjelaskannya dengan lebih baik. Jadi mereka juga tidak melakukan backup.

• Ada juga lishogi, tetapi skalanya masih kecil sehingga belum sampai membutuhkan optimasi seperti ini.
  Di antara varian catur, shogi paling menarik, sedangkan xiangqi tidak sampai seperti itu.

• Saya jadi bertanya-tanya apakah lichess berarti lich perempuan. Seperti baron/baroness.

  • Gelar bangsawan bukan perbandingan yang bagus. Itu karena ia termasuk contoh langka yang memang punya akar kata khusus laki-laki, sementara sebagian besar kata akarnya netral dan meski ada bentuk maskulin atau feminin, tetap butuh afiks.
    Secara ketat, lich laki-laki adalah “werlich”, lich perempuan adalah “wiflich”, dan bentuk jamaknya mendapat “-en”. Namun bagi undead, gender umumnya tidak relevan, jadi bentuk netral jauh lebih banyak dipakai.
    “lichess” adalah kombinasi aneh yang mencampur akar bahasa Jerman dan Prancis, sehingga secara alami tidak bisa dibedakan dari kata-kata bahasa Inggris lain.
  • Artinya Libre chess, yaitu catur yang bebas dan open source.

• Ini bukan perbandingan yang adil, tetapi saya benar-benar kagum pada kualitas engineering tim Lichess. Pesaing utamanya membanggakan migrasi ke GCP tetapi mengalami gangguan berulang seiring naiknya popularitas, dan saya kira jumlah orangnya sekitar 100 kali lebih banyak.
  Kelemahan Lichess adalah aplikasi mobile-nya, tetapi v2 yang dibuat ulang dengan Flutter, meski masih beta, sudah cukup bagus.
  Dan perlu diingat juga bahwa Thibault mengambil kompensasi untuk dirinya sendiri kurang dari 60 ribu dolar per tahun.

  • Menurut saya tidak perlu merasa bersalah untuk menaikkan gaji. Jika dinaikkan menjadi 200 ribu dolar per tahun agar hidupnya lebih nyaman, dalam jangka panjang itu pasti baik juga untuk proyek.
  • Lichess adalah layanan yang bagus bagi pemain catur kasual seperti saya untuk cepat bermain satu ronde dengan orang lain. Hampir tidak pernah perlu menunggu.
    Namun saya penasaran bagaimana cara mengucapkan Lichess. Apakah Lie chess, Le chess, atau League chess?
  • Lichess tampak seperti contoh bagus tentang seberapa efisien Wikipedia seharusnya bisa berjalan, baik dari sisi kode maupun organisasi.
  • Sepertinya Anda cukup melebih-lebihkan jumlah developer di Chess.com.