Replikasi Mesin Keadaan

Replikasi mesin keadaan membuat layanan toleran terhadap kesalahan dengan menjalankan replika deterministik yang mengeksekusi perintah yang sama dalam urutan yang sama, sehingga replika yang bertahan menutupi kegagalan replika lainnya.

Definition

Replikasi mesin keadaan adalah teknik di mana suatu layanan dimodelkan sebagai mesin keadaan deterministik dan direplikasi di beberapa server yang semuanya menerapkan urutan perintah klien yang sama, memastikan bahwa replika yang tidak rusak tetap dalam keadaan identik dan dapat menggantikan replika yang gagal.

Scope

Topik ini mencakup model mesin keadaan suatu layanan, persyaratan bahwa replika harus deterministik, penggunaan siaran atau konsensus urutan total (atomik) untuk menyepakati urutan perintah, dan perbedaannya dengan replikasi primer-cadangan (pasif). Ini juga mencakup penanganan non-determinisme, rekonfigurasi replika, dan perluasan ke replika Bizantium.

Core questions

• Mengapa replika harus deterministik dan memproses perintah dalam urutan yang identik?
• Bagaimana urutan perintah yang disepakati dihasilkan dari konsensus atau siaran atomik?
• Bagaimana replikasi aktif (mesin keadaan) berbeda dari replikasi primer-cadangan pasif?

Key theories

Pendekatan mesin keadaan

Setiap layanan deterministik dapat dibuat toleran terhadap kesalahan dengan mereplikasinya dan memberi setiap replika aliran perintah terurut yang sama; asalkan kurang dari jumlah replika yang ditoleransi gagal, layanan tetap benar dan tersedia.

Pengurutan melalui konsensus

Urutan total yang diperlukan pada perintah adalah siaran atomik, yang setara dengan konsensus, sehingga mesin keadaan yang direplikasi biasanya dibangun di atas protokol konsensus seperti Paxos atau Raft.

Replikasi mesin keadaan Bizantium

Memperluas pendekatan untuk menoleransi kesalahan arbitrer memerlukan kesepakatan di antara lebih dari dua pertiga replika dan pemungutan suara hasil oleh klien, seperti yang direalisasikan dalam replikasi toleran kesalahan Bizantium praktis.

Clinical relevance

Replikasi mesin keadaan adalah cara standar untuk membangun layanan yang sangat tersedia dan konsisten; log yang direplikasi, layanan koordinasi, dan banyak basis data terdistribusi adalah mesin keadaan yang digerakkan oleh aliran perintah yang diurutkan secara konsensus.

History

Makalah jam logis Lamport menguraikan ide mesin keadaan yang direplikasi pada tahun 1978; tutorial Schneider tahun 1990 menjadikannya kerangka kerja kanonis untuk layanan toleran kesalahan; dan PBFT Castro dan Liskov tahun 1999 memperluasnya ke pengaturan Bizantium, sebuah jalur yang kemudian memengaruhi desain blockchain.

Debates

Replikasi aktif versus pasif

Replikasi aktif (mesin keadaan) mengeksekusi perintah di semua replika untuk failover cepat tetapi membuang pekerjaan dan memerlukan determinisme; replikasi primer-cadangan pasif hanya mengeksekusi di primer dan mengirimkan keadaan, menghemat pekerjaan tetapi menimbulkan penundaan failover dan satu titik eksekusi.

Key figures

• Fred Schneider
• Leslie Lamport
• Miguel Castro
• Barbara Liskov

Seminal works

• schneider1990
• lamport1998
• castro1999

Frequently asked questions

Mengapa layanan yang direplikasi harus deterministik?

Jika replika dapat membuat pilihan yang berbeda pada input yang sama—karena keacakan, waktu, atau penjadwalan thread—keadaan mereka akan menyimpang meskipun melihat perintah yang identik. Determinisme menjamin bahwa aliran perintah terurut yang sama menghasilkan keadaan yang sama di mana-mana.