Koleksi serentak dalam 10 menit

^{Foto oleh Robert V. Ruggiero}

Topiknya bukan baru. Tetapi menanyakan pertanyaan, "Apa koleksi bersamaan dan kapan menggunakannya?" pada wawancara atau review kode, saya hampir selalu mendapatkan jawaban yang terdiri dari satu kalimat: "mereka benar-benar melindungi kita dari kondisi ras" (yang tidak mungkin bahkan dalam teori). Atau: "ini seperti koleksi biasa, tetapi semua yang ada di dalamnya terkunci", yang juga tidak sesuai dengan kenyataan.

Tujuan artikel ini adalah untuk melihat topik dalam 10 menit. Ini akan berguna untuk berkenalan singkat dengan beberapa kehalusan. Atau untuk menyegarkan ingatan Anda sebelum wawancara.

Pertama-tama, kita akan melihat isi System.Collections.Concurrent namespace. Kemudian kita membahas perbedaan utama antara koleksi konkuren dan klasik, perhatikan beberapa poin yang tidak jelas. Sebagai kesimpulan, kami membahas kemungkinan jebakan dan kapan jenis koleksi apa yang layak digunakan.

Apa yang ada di System.Collections.Concurrent

Intellisense memberi tahu Anda sedikit:



Mari kita bahas secara singkat tujuan setiap kelas.

ConcurrentDictionary : Kumpulan thread-aman, tujuan umum yang berlaku untuk berbagai skenario.

ConcurrentBag, ConcurrentStack, ConcurrentQueue : Koleksi Tujuan Khusus. “Spesialisasi” terdiri dari poin-poin berikut:

• Kurangnya API untuk mengakses elemen sewenang-wenang
• Stack and Queue (seperti yang kita semua tahu) memiliki urutan tertentu untuk menambahkan dan mengekstraksi elemen
• ConcurrentBag untuk setiap utas memiliki koleksi sendiri untuk menambahkan item. Saat mengambil, itu "mencuri" elemen dari aliran tetangga jika koleksi kosong untuk aliran saat ini

IProducerConsumerCollection - kontrak yang digunakan oleh kelas BlockingCollection (lihat di bawah). Diimplementasikan oleh koleksi ConcurrentStack , ConcurrentQueue, dan ConcurrentBag .

BlockingCollection - digunakan dalam skenario ketika beberapa utas mengisi koleksi, sementara yang lain mengekstrak elemen darinya. Contoh khas adalah antrian tugas yang diisi ulang. Jika koleksi kosong pada saat permintaan elemen berikutnya, maka pembaca masuk ke status menunggu elemen baru (polling). Dengan memanggil metode CompleteAdding () , kami dapat menunjukkan bahwa koleksi tidak akan diisi ulang, maka ketika membaca polling tidak akan dilakukan. Anda dapat memeriksa status koleksi menggunakan properti IsAddingCompleted ( true jika data tidak lagi ditambahkan) dan IsCompleted ( true jika data tidak lagi ditambahkan dan koleksi kosong).

Partitioner, OrderablePartitioner, EnumerablePartitionerOptions - konstruksi dasar untuk mengimplementasikan segmentasi koleksi . Digunakan oleh metode Parallel.ForEach untuk menentukan cara mendistribusikan item di seluruh thread pemrosesan.

Nanti di artikel, kita akan fokus pada koleksi: ConcurrentDictionary dan ConcurrentBag / Stack / Queue .

Perbedaan antara koleksi konkuren dan klasik

Perlindungan negara internal

Koleksi klasik dirancang dengan kinerja maksimal, jadi metode instan mereka tidak menjamin keamanan benang.

Sebagai contoh, lihat kode sumber untuk metode Dictionary.Add .
Kita dapat melihat baris berikut (kode disederhanakan agar mudah dibaca):

if (this._buckets == null) { int prime = HashHelpers.GetPrime(capacity); this._buckets = new int[prime]; this._entries = new Dictionary<TKey, TValue>.Entry[prime]; } 

Seperti yang dapat kita lihat, kondisi internal kamus tidak dilindungi. Saat menambahkan item dari beberapa utas, skenario berikut ini dimungkinkan:

1. Utas 1 disebut Tambah , eksekusi berhenti segera setelah memasuki kondisi if
2. Thread 2 disebut Tambah , menginisialisasi koleksi, menambahkan item
3. Stream 1 kembali bekerja, menginisialisasi ulang koleksi, sehingga menghancurkan data yang ditambahkan oleh stream 2.

Artinya, koleksi klasik tidak cocok untuk merekam dari berbagai aliran.

API toleran terhadap keadaan koleksi saat ini.

Seperti yang kita ketahui, kunci duplikat tidak dapat ditambahkan ke Kamus . Jika kita memanggil Tambah dua kali dengan kunci yang sama, panggilan kedua akan membuang ArgumentException .

Perlindungan ini berguna dalam skenario single-threaded. Tetapi dengan multithreading, kami tidak dapat memastikan keadaan koleksi saat ini. Secara alami, cek seperti berikut ini menyelamatkan kami hanya jika kami terus-menerus mengunci diri:

 if (!dictionary.ContainsKey(key)) { dictionary.Add(key, “Hello”); } 

API berbasis pengecualian adalah opsi yang buruk dan tidak akan memungkinkan perilaku yang stabil dan dapat diprediksi dalam skenario multi-utas. Alih-alih, Anda memerlukan API yang tidak membuat asumsi tentang keadaan koleksi saat ini, tidak memberikan pengecualian, dan menyerahkan keputusan tentang diterimanya status kepada penelepon.

Dalam koleksi bersamaan, API dibangun di atas pola TryXXX . Alih-alih biasa Tambahkan , Dapatkan dan Hapus, kami menggunakan metode TryAdd , TryGetValue dan TryRemove . Dan, jika metode ini menghasilkan false , maka kami memutuskan apakah ini situasi yang luar biasa atau tidak.

Perlu dicatat bahwa koleksi klasik sekarang juga memiliki metode yang toleran terhadap negara. Tetapi dalam koleksi klasik, API seperti itu adalah tambahan yang bagus, dan dalam koleksi bersamaan, itu adalah suatu keharusan.

API meminimalkan kondisi balapan

Pertimbangkan operasi pembaruan elemen paling sederhana:

 dictionary[key] += 1; 

Untuk semua kesederhanaannya, kode melakukan tiga tindakan: ia mendapat nilai dari koleksi, menambahkan 1, menulis nilai baru. Dalam eksekusi multi-utas, ada kemungkinan bahwa kode mengambil nilai, melakukan kenaikan, dan kemudian dengan aman menghapus nilai yang ditulis oleh utas lain saat kenaikan berjalan.

Untuk mengatasi masalah tersebut, API koleksi bersamaan berisi sejumlah metode pembantu. Misalnya, metode TryUpdate , yang mengambil tiga parameter: kunci, nilai baru, dan nilai saat ini yang diharapkan. Jika nilai dalam koleksi tidak sesuai dengan yang diharapkan, maka pembaruan tidak akan dilakukan dan metode akan kembali salah .

Pertimbangkan contoh lain. Secara harfiah setiap baris kode berikut (termasuk Console.WriteLine ) dapat menyebabkan masalah dengan eksekusi multi-utas:

 if (dictionary.ContainsKey(key)) { dictionary[key] += 1; } else { dictionary.Add(key, 1); } Console.WriteLine(dictionary[key]); 

Menambah atau memperbarui nilai, dan kemudian melakukan operasi dengan hasilnya, adalah tugas yang cukup umum. Oleh karena itu, kamus bersamaan memiliki metode AddOrUpdate , yang melakukan urutan tindakan dalam satu panggilan dan aman utas:

 var result = dictionary.AddOrUpdate(key, 1, (itemKey, itemValue) => itemValue + 1); Console.WriteLine(result); 

Ada satu hal yang perlu diketahui.

Penerapan metode AddOrUpdate memanggil metode TryUpdate yang dijelaskan di atas dan meneruskan nilai saat ini dari koleksi ke sana. Jika pembaruan gagal (utas tetangga telah mengubah nilainya), maka upaya tersebut diulangi dan delegasi pembaruan yang ditransmisikan dipanggil lagi dengan nilai saat ini yang diperbarui. Artinya, delegasi pembaruan dapat dipanggil beberapa kali , jadi tidak boleh mengandung efek samping.

Kunci algoritma gratis dan kunci granular

Microsoft melakukan pekerjaan besar pada kinerja koleksi bersamaan, dan tidak hanya membungkus semua operasi dengan kunci. Mempelajari sumbernya, Anda dapat melihat banyak contoh penggunaan kunci granular, penggunaan algoritma yang kompeten, bukan kunci, serta penggunaan instruksi khusus dan primitif sinkronisasi yang lebih "ringan" daripada Monitor .

Apa koleksi bersamaan tidak memberikan

Dari contoh di atas, jelas bahwa koleksi konkuren tidak memberikan perlindungan lengkap terhadap kondisi ras dan kami harus merancang kode kami sesuai. Tapi itu belum semua, ada beberapa poin yang perlu diketahui.

Polimorfisme dengan koleksi klasik

Koleksi bersamaan, seperti yang klasik, mengimplementasikan antarmuka IDictionary , ICollection , dan IEnumerable . Tetapi bagian dari API dari antarmuka ini tidak dapat didefinisikan dengan aman menurut definisi. Misalnya, metode Tambahkan , yang kita bahas di atas.

Pengumpulan serentak menerapkan kontrak semacam itu tanpa pengaman benang. Dan untuk "menyembunyikan" API tidak aman, mereka menggunakan implementasi eksplisit dari antarmuka. Ini patut diingat ketika kita meneruskan koleksi bersamaan ke metode yang mengambil input, misalnya, ICollection.

Juga, koleksi bersamaan tidak mematuhi prinsip substitusi Liskov sehubungan dengan koleksi klasik.

Misalnya, konten koleksi klasik tidak dapat diubah selama iterasi , kode berikut akan melempar InvalidOperationException untuk kelas Daftar :

 foreach (var element in list) { list.Remove(element); } 

Jika kita berbicara tentang koleksi bersamaan, maka modifikasi pada saat pencacahan tidak mengarah pada pengecualian, sehingga kita dapat melakukan membaca dan menulis secara simultan dari aliran yang berbeda.

Selain itu, koleksi bersamaan secara berbeda menerapkan kemungkinan modifikasi selama enumerasi. ConcurrentDictionary hanya tidak melakukan pemeriksaan dan tidak menjamin hasil iterasi, dan ConcurrentStack / Antrian / Tas mengunci dan membuat salinan dari kondisi saat ini, yang iterate melalui.

Kemungkinan masalah kinerja

Kami sebutkan di atas bahwa ConcurrentBag dapat "mencuri" elemen dari utas tetangga. Ini dapat menyebabkan masalah kinerja jika Anda menulis dan membaca ke ConcurrentBag dari utas yang berbeda.

Juga, koleksi bersamaan memaksakan kunci lengkap ketika menanyakan keadaan seluruh koleksi ( Count , IsEmpty , GetEnumerator , ToArray , dll.) Dan karena itu secara signifikan lebih lambat daripada rekan-rekan klasik mereka.

Kesimpulan: menggunakan koleksi bersamaan hanya layak jika mereka benar-benar diperlukan, karena pilihan ini tidak "gratis".

Kapan koleksi jenis apa yang digunakan

• Skrip berulir tunggal: hanya koleksi klasik dengan kinerja terbaik.
• Rekam dari berbagai aliran: hanya koleksi bersamaan yang melindungi keadaan internal dan memiliki API yang sesuai untuk perekaman kompetitif.
• Membaca dari berbagai utas: tidak ada rekomendasi yang pasti. Koleksi bersamaan dapat menciptakan masalah kinerja dengan permintaan negara intensif untuk seluruh koleksi. Namun, untuk koleksi klasik, Microsoft tidak menjamin kinerja bahkan untuk operasi baca. Misalnya, implementasi internal koleksi mungkin memiliki properti malas yang dimulai saat membaca data dan, oleh karena itu, dimungkinkan untuk menghancurkan keadaan internal saat membaca dari beberapa utas. Pilihan rata-rata yang bagus adalah menggunakan koleksi tidak berubah .
• Dan membaca dan menulis dari berbagai utas: koleksi bersamaan yang unik, baik yang menerapkan perlindungan negara dan API yang aman.

Kesimpulan

Dalam artikel ini, kami secara singkat mempelajari koleksi bersamaan, kapan menggunakannya dan spesifikasinya apa. Tentu saja, artikel tersebut tidak menguras topik, dan dengan kerja serius dengan koleksi multithreaded, Anda harus menggali lebih dalam. Cara termudah untuk melakukan ini adalah dengan melihat kode sumber koleksi yang digunakan. Ini informatif dan sama sekali tidak rumit, kodenya sangat, sangat mudah dibaca.