Futurelock: Risiko deadlock yang subtil di Rust asinkron

• Futurelock adalah fenomena deadlock yang terjadi ketika satu task mengelola beberapa Future sekaligus, lalu salah satunya membutuhkan resource milik Future lain tetapi tidak lagi di-poll
• Mudah terjadi saat konstruksi tokio::select! menggunakan Future yang direferensikan (&mut future) bersama branch yang mengandung await
• Masalah ini berasal dari gagalnya pemisahan tanggung jawab antara task dan Future, sehingga task yang sama menunggu dua Future tetapi hanya mem-poll salah satunya dan akhirnya berhenti total
• Bentuk serupa juga bisa muncul pada FuturesUnordered, bounded channel, Stream, dan lainnya
• Kunci desain asinkron yang aman adalah memisahkan Future ke task terpisah dengan tokio::spawn atau menghindari penggunaan await di dalam select

---

Konsep dan contoh Futurelock

• Futurelock terjadi ketika Future A yang memegang resource dibutuhkan oleh Future B, tetapi task yang menangani keduanya tidak lagi mem-poll A
• Pada kode contoh, tokio::select! menunggu &mut future1 dan sleep secara bersamaan; jika sleep selesai lebih dulu, future1 tetap berada dalam status menunggu lock
• Setelah itu future3 meminta lock yang sama, tetapi lock sudah dialokasikan ke future1 dan future1 tidak dipoll lagi, sehingga program berhenti selamanya

Interaksi tokio::select! dan Mutex

• tokio::sync::Mutex adalah lock yang fair, yaitu memberi lock sesuai urutan antrean
• Lock diberikan kepada future1, tetapi task sudah hanya mem-poll future3, sehingga future1 tidak pernah berjalan
• Mutex hanya bertugas membangunkan task penunggu berikutnya, dan tidak tahu Future mana yang benar-benar sedang dipoll

Penyebab umum Futurelock

• Struktur dependensi melingkar ketika task T menunggu Future F1, F1 bergantung pada F2, dan F2 kembali membutuhkan polling dari T
• Umumnya terjadi dalam situasi berikut
  • Menggunakan &mut future di tokio::select! lalu menjalankan await di branch lain
  • Pada FuturesOrdered atau FuturesUnordered, setelah sebagian Future selesai lalu melakukan pekerjaan asinkron lain
  • Perilaku serupa pada Future yang diimplementasikan secara manual

Kasus pada Stream dan struktur lain

• Pada FuturesOrdered atau FuturesUnordered, Futurelock bisa terjadi setelah sebuah Future diambil lalu sistem menunggu Future lain yang memakai resource terkait
• join_all tidak menimbulkan Futurelock karena terus mem-poll semua Future

Kasus nyata dan debugging

• Dalam kasus Omicron#9259, semua Future akses database terkena Futurelock sehingga request HTTP menunggu tanpa batas
• Pengiriman pada kanal mpsc terblokir, tetapi sisi penerima terlihat kosong sehingga penyebabnya sulit diidentifikasi
• Saat debugging, alat seperti tokio-console dapat membantu, tetapi dalam banyak kasus pelacakan akar masalah sangat sulit

Pedoman pencegahan Futurelock

• Saat satu task mem-poll beberapa Future, jangan sampai polling terhadap Future yang sudah dimulai dihentikan di tengah jalan
• Jika memungkinkan, spawn Future sebagai task baru agar berjalan mandiri
  • Jika JoinHandle diteruskan ke tokio::select!, risiko Futurelock hilang
• Hal yang perlu diperhatikan saat memakai tokio::select!
  • Jangan gunakan &mut future dan await secara bersamaan
  • Jika kedua kondisi itu ada sekaligus, risiko Futurelock menjadi tinggi
• Saat memakai Stream, gunakan JoinSet untuk menjalankan tiap Future di task terpisah
• Menambah kapasitas bounded channel bukan solusi mendasar
  • Sebagai gantinya, try_send() dapat dipakai untuk menghindari blocking

Pola penghindaran yang keliru

• Menaikkan kapasitas channel tanpa batas tidak realistis dan menimbulkan efek samping seperti latensi dan penggunaan memori yang lebih besar
• Mencoba menghilangkan dependensi antar-Future juga rapuh karena dependensi baru bisa muncul saat maintenance
• Satu-satunya cara yang benar-benar aman adalah memisahkan task dengan tokio::spawn

Perbaikan ke depan dan pertimbangan keamanan

• Ada kemungkinan menambahkan peringatan melalui lint Clippy saat tokio::select! memakai &mut future atau mengandung await
• Futurelock bisa disalahgunakan sebagai bentuk penolakan layanan (DoS), tetapi pada dasarnya ini adalah perilaku abnormal sehingga perlu dicegah

[GN⁺]

Komentar Hacker News

• Setelah membaca sekilas dokumennya, rasanya ini seperti laporan yang transparan dan sangat menyeluruh
  Terutama bagian catatan kaki yang menurut saya menarik
  Banyak orang ternyata tidak tahu soal masalah cancellation safety di Rust, dan cukup mengesankan bahwa masalah seperti ini kemungkinan menyebar di seluruh Omicron
  Ironis rasanya bahwa Rust dipilih untuk menghindari masalah keamanan memori di C, tetapi kali ini justru muncul bug cancellation yang sulit ditangkap saat runtime
  Sangat menjengkelkan bahwa properti dinamis yang tidak bisa dibantu compiler pada akhirnya harus dijamin sendiri oleh programmer

  • Saya jadi berpikir, apakah kita butuh lapisan abstraksi yang lebih tinggi untuk menghindari masalah seperti ini
    Tampaknya bahkan dalam model konkurensi Rust masih tetap ada kemungkinan deadlock
    Manajemen sumber daya gaya RAII terasa seperti seharusnya bisa mencegah masalah seperti ini, tetapi ternyata tidak, dan itu membingungkan
    Saya penasaran apakah ini hanya kebetulan implementasi, atau memang batasan struktural dari model Rust/Tokio

• Ini terlihat seperti variasi halus dari deadlock yang dijelaskan dalam tulisan withoutboats tentang FuturesUnordered
  Saat memakai konkurensi “intra-task”, kita harus berhati-hati agar tidak ada future yang mengalami starvation
  Pada dasarnya lebih aman untuk me-spawn task, lalu menangani timeout dengan tokio::select!, sambil mengelola semua future yang pending di dalamnya
  Saya benar-benar tidak merekomendasikan FuturesUnordered kecuali Anda sudah menguji semua edge case yang mungkin

• Ini terdengar mirip dengan masalah priority inversion
  Di OS, ketika thread prioritas rendah memegang lock dan thread prioritas tinggi menunggu, yang prioritas rendah akan mewarisi prioritas agar bisa berjalan
  Saya penasaran apakah konsep serupa bisa diterapkan di Tokio — misalnya, jika future yang tidak bisa dijalankan sedang memegang Mutex, future itu dipoll atas namanya
  Hanya saja, mendeteksi keadaan “tidak bisa dijalankan” tampaknya akan menimbulkan overhead yang cukup besar

  • Pendekatan seperti ini mungkin bisa diterapkan pada task di Tokio
    Tetapi tidak bisa diterapkan pada future di dalam task
    Ini karena desain dasar async Rust adalah “futures are inert” — future hanyalah struct biasa, dan runtime tidak tahu apa yang ada di dalamnya
    Runtime hanya mengetahui unit task, jadi status future internal sama sekali tidak dilacak

  • Async di Rust memakai model stackless coroutine, jadi tidak aman untuk melanjutkan eksekusi fungsi async yang sudah sedang berjalan secara sewenang-wenang
    Model stackless menyimpan state lokal pada stack bersama, sehingga hanya aman dieksekusi dalam urutan LIFO
    Karena itulah coloring diperlukan, dan ia tidak bisa melakukan yield secara bebas seperti stackful coroutine

  • Kodenya terasa terlalu rumit
    Terlihat jauh lebih bertele-tele dibanding jika ditulis dengan Erlang, Elixir, Go, bahkan C

  • Saya rasa ini mirip dengan deadlock dua lock yang mendasar
    Antrian tunggu Mutex di Tokio dan scheduling task saling terkait sehingga membentuk deadlock
    Kalau ini Mutex OS, mungkin bisa diselesaikan dengan membangunkan thread lain yang menunggu, tetapi di async Rust hal itu tampak sulit karena struktur state machine pada future
    Mungkin bisa diurai dengan memoll future-future di antrian tunggu secara berurutan, tetapi itu juga bisa menimbulkan efek samping yang tidak terduga

• Saya pernah mengalami menangani masalah seperti ini di ekosistem async Rust
  Jika referensi tidak boleh dipakai di select!, masalah seperti ini memang bisa dihindari, tetapi itu juga membuat pola menjalankan select! berulang kali tanpa kehilangan posisi di antrean menjadi tidak mungkin
  Bersama masalah cancellation, hal-hal seperti ini bisa menjadi jebakan tak terduga bahkan bagi pakar Rust
  Meski begitu, tetap jauh lebih sedikit hal mengejutkan dibanding kode berbasis callback

  • Betul, setelah tim kami menganalisis deadlock ini, kami juga membahas “bagaimana seharusnya ini bisa dicegah?”, tetapi akhirnya sampai pada kesimpulan bahwa ini bukan salah siapa pun
    Semua primitif Tokio bekerja sesuai tujuan, dan kodenya juga ditulis dengan benar, tetapi interaksi di antara semuanya menghasilkan deadlock yang tak terduga
    Melarang &mut future di select! memang bisa mencegahnya, tetapi itu juga akan melarang banyak kode yang sebenarnya valid
    Pada akhirnya kami sampai pada kesimpulan pahit bahwa ini adalah “bagian yang memang harus diwaspadai”
    Diskusi terkait juga berlanjut di komentar ini

  • Jika select! dibuat mengembalikan future yang tidak terpilih tanpa men-drop-nya, state bisa dipertahankan tanpa hilang
    Namun itu tidak praktis, dan bukan solusi mendasar
    Akar masalah yang sebenarnya, seperti dijelaskan di thread ini, adalah ketidaklengkapan penanganan cancellation

• Pertanyaan di FAQ tentang “bukankah future1 dibatalkan?” terasa menarik
  Cancellation punya dua tahap — menghentikan poll dan drop
  Dalam contoh ini, drop tertunda sehingga guard tetap dipegang dan menimbulkan efek samping
  Saya jadi bertanya-tanya apakah kedua tindakan itu bisa dijamin selalu terjadi bersamaan

• Saya ingin bertanya kepada perancang Rust — mengapa mereka memilih pola async alih-alih model actor
  Setelah memakai Erlang, model actor terasa jauh lebih bersih dan aman
  JS memang praktis terpaksa memakai async karena struktur bahasanya, tetapi Rust adalah bahasa baru, jadi saya penasaran mengapa memilih jalur itu

  • Desain async di Rust sangat dipengaruhi oleh kebutuhan dukungan lingkungan embedded
    Karena harus bisa berjalan tanpa malloc atau thread, model actor tidak memungkinkan
    Kita memang bisa menulis kode bergaya actor dengan Tokio, tetapi tidak terasa alami

  • Alasan lainnya adalah kinerja
    Model actor memiliki biaya penyalinan pesan yang besar, dan Rust sebagai bahasa sistem yang berorientasi performa mengejar zero-cost abstraction lewat async state machine
    Erlang dan Go adalah bahasa yang memilih trade-off yang berbeda

  • Karena Rust tidak ingin menoleransi overhead pada pemanggilan C FFI, model berbasis green thread dikesampingkan
    async/await dikompilasi menjadi state machine sehingga overhead-nya kecil
    Go pada masa awal juga tidak punya preemption dan pernah mengalami masalah starvation serupa, yang belakangan diselesaikan oleh scheduler
    Pada akhirnya setiap bahasa memang punya tujuan dan batasannya masing-masing

  • Saya juga terkejut Oxide mengadopsi async
    Di dunia embedded atau server HTTP itu terasa wajar, tetapi saya tidak menyangka perusahaan sistem seperti Oxide akan memakainya sedalam ini

• Bagian yang membuat saya bingung saat membaca dokumen itu adalah, mengapa yang dibangunkan justru thread utama, bukan future yang memegang lock
  Kalau lock-nya fair, seharusnya future1 yang dibangunkan, jadi saya heran mengapa runtime malah memilih thread lain

• Tulisannya benar-benar menarik
  Contoh kodenya juga jelas, dan meski menemukan bug seperti ini terdengar seperti mimpi buruk, ada kepuasan saat potongan puzzle akhirnya menyatu setelah ketemu

  • Perusahaan kami merekam semua rapat dan sesi debugging, dan tepat momen “puzzle-nya menyatu” itu terekam di video
    Sangat mengesankan melihat Eliza, Sean, John, dan Dave melakukan brainstorming bersama sampai menemukan penyebabnya
    Kami berencana merilis episode podcast yang membahas ini pada hari Senin
    Videonya bisa dilihat di RFD 537 dan tautan event ini

• Sulit dipahami bahwa Rust tidak membuat semua task aktif maju secara bersamaan; ini terasa seperti desain yang mudah melahirkan bug
  Rasanya akan lebih intuitif jika mengadopsi structured concurrency seperti Trio di Python
  Saya penasaran apakah Rust juga bisa mengadopsi model seperti itu

  • Structured concurrency di Rust sebenarnya memungkinkan, tetapi hanya pada level task
    Future hanyalah struct yang baru berjalan jika dipoll, jadi tidak ada konsep “future aktif”
    Semua masalah tampak bisa diselesaikan dengan me-spawn semuanya sebagai task, tetapi itu juga akan menghalangi beberapa pola yang berguna

  • Perbedaan antara task dan future itu penting
    Future tidak melakukan apa pun jika tidak dipoll
    Jika cancellation didefinisikan sebagai “keadaan tidak dipoll sampai akhirnya di-drop”, maka bisa muncul future yang berhenti sambil tetap memegang lock, seperti dalam masalah ini
    Dalam filosofi RAII Rust, kita biasanya berharap cleanup terjadi saat drop, tetapi ketika poll berhenti, bahkan itu pun belum tentu terjadi

• Belakangan saya merasa async di Rust mungkin dirilis terlalu terburu-buru

  • Saya juga merasa masih banyak yang perlu diperbaiki, tetapi menurut saya desain dasarnya sendiri merupakan fondasi yang sangat baik
    Pin dan sebagian sintaks mungkin masih bisa diperhalus, tetapi struktur dasarnya tidak perlu diubah
    Ini masih berada pada tahap “fondasi rumah yang belum selesai”, bukan hasil dari keputusan yang tergesa-gesa
    Hanya saja saya memang merasa masih dibutuhkan lapisan yang lebih rendah seperti coroutine yang digeneralisasi