Mencari pola penguncian terdistribusi

10

Saya perlu membuat mekanisme penguncian objek rekursif khusus \ pola untuk sistem terdistribusi dalam C #. Pada dasarnya, saya memiliki sistem multi-node. Setiap node memiliki izin menulis eksklusif di atas n -jumlah negara bagian. Keadaan yang sama juga tersedia dalam bentuk read-only pada setidaknya satu simpul lainnya. Beberapa penulisan / pembaruan harus bersifat atomis di semua node, sementara pembaruan lainnya pada akhirnya akan menjadi konsisten melalui proses replikasi latar belakang, antrian, dll ...

Untuk pembaruan atom saya sedang mencari pola atau sampel yang secara efisien memungkinkan saya untuk menandai objek sebagai terkunci untuk menulis yang kemudian dapat saya distribusikan, komit, kembalikan, dll ... Karena sistem memiliki tingkat konkurensi yang tinggi, saya Saya berasumsi saya harus dapat menumpuk kunci yang akan habis atau dibuka setelah kunci dilepaskan.

Potongan transaksi atau pesan bukan fokus dari pertanyaan ini, tetapi saya telah memberikan mereka untuk beberapa konteks tambahan. Dengan itu, jangan ragu untuk mengartikulasikan pesan apa yang menurut Anda akan diperlukan jika Anda mau.

Berikut ini adalah contoh samar dari apa yang saya bayangkan meskipun saya terbuka untuk ide-ide baru selain menerapkan seluruh produk baru

thing.AquireLock(LockLevel.Write);

//Do work

thing.ReleaseLock();

Saya sedang berpikir untuk menggunakan metode ekstensi, yang mungkin terlihat seperti ini

public static void AquireLock(this IThing instance, TupleLockLevel lockLevel)
{ 
    //TODO: Add aquisition wait, retry, recursion count, timeout support, etc...  
    //TODO: Disallow read lock requests if the 'thing' is already write locked
    //TODO: Throw exception when aquisition fails
    instance.Lock = lockLevel;
}

public static void ReleaseLock(this IThing instance)
{
    instance.Lock = TupleLockLevel.None;
}

Untuk memperjelas detail pasangan ...

  • Semua komunikasi adalah TCP / IP menggunakan protokol permintaan / respons biner
  • Tidak ada teknologi perantara seperti antrian atau database
  • Tidak ada simpul master pusat. Dalam hal ini, pengaturan penguncian ditentukan oleh penggagas penguncian dan mitra yang akan memenuhi permintaan dengan semacam batas waktu untuk mengatur perilakunya.

Ada yang punya saran?

JoeGeeky
sumber
Kunci umumnya merupakan fitur standar di sebagian besar sistem. Saya kira itu ada untuk C # juga. (Hasil pencarian Google: albahari.com/threading/part2.aspx ) Apakah Anda mencoba mencapai sesuatu di luar Mutex atau semafor dasar?
Dipan Mehta
2
@DipanMehta Maaf, saya seharusnya membahas ini dengan lebih jelas. The node yang saya sebutkan adalah mesin pada jaringan. Pemahaman saya tentang Mutex dan Semaphores adalah bahwa itu adalah kunci seluruh mesin ( mis. Lintas proses ) dan bukan kunci yang dapat meluas antar mesin pada jaringan.
JoeGeeky
@ Joeyeeky Pertanyaan Anda ada di topik di sini dan mungkin terlalu teoritis untuk Stack Overflow . Jika Anda ingin bertanya ulang di sana, Anda bisa, tetapi Anda ingin frasa yang lebih berfokus pada kode.
Adam Lear

Jawaban:

4

Terima kasih atas klarifikasi.

Dalam hal itu, apa yang saya rekomendasikan adalah menggunakan model terbitkan / berlangganan. Protokol penguncian terdistribusi Chubby Google (sebuah implementasi dari Paxos )

Saya tidak pernah menggunakan Paxos (atau Chubby), tetapi tampaknya ada implementasi open source di sini .

Jika itu tidak berhasil, Anda bisa menerapkan versi Paxos Anda sendiri menggunakan, misalnya, salah satu tersangka yang biasa dalam hal perpustakaan perpesanan: perpustakaan antrian pesan nol , RabbitMQ , atau ActiveMQ .


Jawaban sebelumnya:

Sebagian besar saran pada SO ( [A] , [B] ) menggunakan antrian pesan untuk mencapai penguncian lintas mesin.

AcquireLockMetode Anda akan mendorong sesuatu yang mengidentifikasi objek kunci ke dalam antrian, memeriksa contoh kunci sebelumnya sebelum berhasil. ReleaseLockMetode Anda akan menghapus objek kunci dari antrian.

Pengguna SO atlantis menyarankan, dalam posting ini , posting Jeff Key untuk beberapa detail.

Peter K.
sumber
Terima kasih, tetapi solusi ini tidak cocok karena saya belum memiliki master sentral, database, atau antrian. Saya telah memperbarui pertanyaan dengan beberapa perincian tambahan untuk memperjelas beberapa perincian ini.
JoeGeeky
Saya tidak akan dapat menggunakan produk ini secara langsung karena sudah ada protokol yang terdefinisi dengan baik yang harus saya gunakan untuk semua komunikasi antar node, tetapi Chubby dan Paxos mungkin memiliki pola yang terdefinisi dengan baik yang dapat saya pelajari. Aku akan melihatnya.
JoeGeeky
@JoeGeeky Ya, tautan Paxos memiliki diagram urutan yang memungkinkan Anda menerapkannya menggunakan tautan komunikasi pilihan Anda.
Peter K.
Meskipun bukan jawaban langsung, membaca semua hal Chubby dan Paxos membantu saya menentukan solusi saya sendiri. Saya tidak menggunakan alat-alat itu, tetapi mampu mendefinisikan pola yang masuk akal berdasarkan beberapa konsep mereka. Terima kasih.
JoeGeeky
@ JoeGeeky: Senang mendengar itu adalah bantuan, setidaknya. Terima kasih untuk centangnya.
Peter K.
4

Menurut saya sepertinya Anda memiliki beberapa teknologi campuran di sini:

  • komunikasi (yang pada dasarnya Anda andalkan 100% andal ... yang bisa berakibat fatal)

  • mengunci / saling pengecualian

  • batas waktu (untuk tujuan apa)?

Kata peringatan: Timeout dalam sistem terdistribusi dapat penuh dengan bahaya dan kesulitan. Jika digunakan, mereka harus diatur dan digunakan dengan sangat hati-hati karena penggunaan timeout yang tidak membeda-bedakan tidak memperbaiki masalah, itu hanya akan mengalahkan malapetaka. (Jika Anda ingin melihat bagaimana timeout harus digunakan, baca dan pahami dokumentasi protokol komunikasi HDLC. Ini adalah contoh yang baik dari penggunaan yang cocok dan cerdas, dikombinasikan dengan sistem pengkodean bit yang pintar untuk memungkinkan deteksi hal-hal seperti jalur IDLE) .

Untuk beberapa waktu saya bekerja di sistem terdistribusi multi-prosesor yang terhubung menggunakan tautan komunikasi (bukan TCP, sesuatu yang lain). Salah satu hal yang saya pelajari adalah bahwa sebagai generalisasi kasar, ada beberapa tempat multi-pemrograman yang berbahaya untuk dikunjungi:

  • mengandalkan antrian biasanya berakhir dengan air mata (jika antrian mengisi, Anda dalam kesulitan. KECUALI Anda dapat menghitung ukuran antrian yang tidak akan pernah terisi, dalam hal ini Anda mungkin dapat menggunakan solusi no-antrian)

  • mengandalkan penguncian itu menyakitkan, coba dan pikirkan jika ada cara lain (jika Anda harus menggunakan penguncian, lihat literatur, penguncian terdistribusi multi-prosesor telah menjadi subjek banyak makalah acedemik selama 2-3 dekade terakhir)

Saya Anda harus melanjutkan menggunakan penguncian, kemudian:

Saya akan berasumsi bahwa Anda akan menggunakan batas waktu hanya sebagai alat pemulihan pilihan terakhir - yaitu untuk mendeteksi kegagalan sistem komunikasi yang mendasarinya. Saya selanjutnya akan berasumsi bahwa sistem komunikasi TCP / IP Anda adalah bandwidth tinggi dan dapat dianggap sebagai latensi rendah (idealnya nol, tetapi ini tidak pernah terjadi).

Apa yang saya sarankan adalah bahwa setiap node memiliki daftar konektivitas dari node lain yang dapat terhubung. (Node tidak akan peduli dari mana koneksi berasal.) Populasi dari tabel yang node dapat terhubung ke node dibiarkan sebagai hal yang terpisah untuk memilah, Anda belum mengatakan apakah itu akan diatur secara statis atau sebaliknya. Juga mudah diabaikan adalah hal-hal seperti alokasi nomor port IP di mana koneksi akan masuk ke sebuah simpul - mungkin ada alasan bagus untuk menerima permintaan hanya pada satu port, atau pada beberapa port. Ini perlu dipertimbangkan dengan cermat. Faktor-faktor akan mencakup antrian tersirat, pemesanan, penggunaan sumber daya, jenis dan kemampuan sistem operasi.

Setelah node tahu dengan siapa mereka terhubung, mereka dapat mengirim permintaan kunci ke simpul itu, dan harus menerima kembali dari balasan kunci dari simpul jarak jauh itu. Anda dapat mengemas kedua operasi tersebut menjadi pembungkus agar terlihat atom. Efek dari ini adalah bahwa node yang ingin memperoleh kunci akan membuat panggilan seperti:

if (get_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

/* Lock is now acquired - do work here */

if (release_lock(remote_node) == timeout) then
  {
    take some failure action - the comms network is down
  }

panggilan get_lock dan release_lock harus seperti (pada prinsipnya):

send_to_remote_node(lock_request)
get_from_remote_node_or_timeout(lock_reply, time)
if (result was timeout) then
  return timeout
else
  return ok

Anda harus sangat berhati-hati dengan sistem penguncian terdistribusi yang unit kerjanya dilakukan saat kunci dipegang kecil dan cepat karena Anda akan memiliki banyak node jarak jauh yang berpotensi menunggu untuk mendapatkan kunci. Ini secara efektif merupakan sistem multiprosesor / komunikasi stop-and-wait yang kuat tetapi tidak memiliki kinerja setinggi mungkin.

Saran adalah mengambil pendekatan yang sama sekali berbeda. Bisakah Anda menggunakan panggilan prosedur jarak jauh di mana setiap panggilan RPC membawa paket informasi yang dapat ditangani oleh penerima, dan yang menghilangkan kebutuhan untuk kunci?


Saat membaca kembali pertanyaannya, sepertinya Anda tidak benar-benar ingin peduli dengan sisi komunikasi berbagai hal, Anda hanya ingin menyelesaikan masalah penguncian Anda.

Karena itu, jawaban saya mungkin tampak agak di luar topik, namun saya yakin Anda tidak dapat menyelesaikan masalah penguncian Anda tanpa membuat bagian di bawahnya juga benar. Analogi: Membangun rumah di atas fondasi yang buruk menyebabkannya jatuh ... Akhirnya.

dengan cepat_now
sumber
1
Semantik timeout sebagian besar ada untuk berurusan dengan node yang hilang dari jaringan, atau untuk berurusan dengan tumpukan besar dalam mengunci tumpukan ... Ini akan membatasi waktu yang dihabiskan diblokir sambil menunggu untuk mendapatkan kunci dan akan memberikan mereka yang meminta kunci kesempatan. untuk memulai proses lain di tengah-tengah penundaan yang tidak terduga, kegagalan, dll ... Selain itu, ini akan mencegah sesuatu terkunci selamanya jika ada sesuatu yang gagal. Saya menghargai keprihatinan Anda walaupun pada titik ini, saya tidak melihat adanya alternatif karena pada akhirnya sesuatu akan gagal
JoeGeeky
Untuk berbicara dengan beberapa komentar Anda yang lain, saya tidak menggunakan antrian per se (dalam pengertian komunikasi async), meskipun saya berharap bahwa kunci ditumpuk dan dirilis berdasarkan menggunakan pola FIFO. Saya belum cukup mendamaikan bagaimana ini akan bekerja dalam hal pola permintaan / respons yang diperlukan selain dari ini perlu diblokir dalam beberapa cara dan menjadi bagian dari jabat tangan yang lebih besar. Saat ini, saya sedang bekerja melalui mekanisme penguncian bertumpuk dalam satu node dan kemudian bagaimana ia akan bekerja melalui skenario terdistribusi. Saya akan membaca lebih sedikit seperti yang Anda sarankan. Terima kasih
JoeGeeky
@JoeGeeky - FIFO adalah antrian. Waspadalah terhadap antrian. Pikirkan sisi itu dengan sangat hati-hati. Kedengarannya seperti Anda tidak akan hanya mendapatkan sesuatu "dari rak" tetapi harus memikirkan masalah dan solusi Anda dengan hati-hati.
cepat_now
Saya mengerti ... Saya mencoba untuk mengklarifikasi perbedaannya dengan menggunakan antrian FIFO yang digunakan dalam proses async ( mis. Satu proses enqueues dan kemudian dequeues lain ). Dalam hal ini, hal-hal perlu dikelola secara berurutan, tetapi proses memasuki antrian tidak akan pergi sampai (a) mereka mendapatkan kunci, (b) ditolak kunci, atau (c) mereka habis waktu dan meninggalkan garis. Lebih mirip antre di ATM. Ini berperilaku seperti pola FIFO dalam kasus sukses, tetapi proses bisa dibiarkan tidak teratur sebelum mencapai garis depan. Adapun off-the-shelf? Tidak, tapi ini bukan masalah baru
JoeGeeky
0

Pertanyaan Anda dapat dengan mudah diimplementasikan menggunakan cache terdistribusi seperti NCache. Yang Anda butuhkan adalah mekanisme Penguncian Pesimis di mana Anda bisa memperoleh kunci menggunakan objek. Kemudian lakukan tugas dan operasi Anda dan lepaskan kunci untuk digunakan aplikasi lain nanti.

Lihatlah kode berikut;

Di sini Anda akan mendapatkan kunci pada Kunci tertentu dan kemudian melakukan tugas (mulai dari satu operasi atau lebih) lalu akhirnya melepaskan kunci ketika Anda selesai.

// Instance of the object used to lock and unlock cache items in NCache
LockHandle lockHandle = new LockHandle();

// Specify time span of 10 sec for which the item remains locked
// NCache will auto release the lock after 10 seconds.
TimeSpan lockSpan = new TimeSpan(0, 0, 10); 

try
{
    // If item fetch is successful, lockHandle object will be populated
    // The lockHandle object will be used to unlock the cache item
    // acquireLock should be true if you want to acquire to the lock.
    // If item does not exists, account will be null
    BankAccount account = cache.Get(key, lockSpan, 
    ref lockHandle, acquireLock) as BankAccount;
    // Lock acquired otherwise it will throw LockingException exception

    if(account != null && account.IsActive)
    {
        // Withdraw money or Deposit
        account.Balance += withdrawAmount;
        // account.Balance -= depositAmount;

        // Insert the data in the cache and release the lock simultaneously 
        // LockHandle initially used to lock the item must be provided
        // releaseLock should be true to release the lock, otherwise false
        cache.Insert("Key", account, lockHandle, releaseLock); 
        //For your case you should use cache.Unlock("Key", lockHandle);
    }
    else
    {
        // Either does not exist or unable to cast
        // Explicitly release the lock in case of errors
        cache.Unlock("Key", lockHandle);
    } 
}
catch(LockingException lockException)
{
    // Lock couldn't be acquired
    // Wait and try again
}

Diambil dari tautan: http://blogs.alachisoft.com/ncache/distributed-locking/

Basit Anwer
sumber