Kilitsiz (Lock-Free) Kuyruklarda Gerçek Maliyet

Bir kuyruğun içinde mutex bulunmaması, o kuyruğun düşük gecikmeli olduğu anlamına gelmez. Uzun süreli ve yüksek trafikli sistemlerde bunun tersine çok kez rastlanır: algoritma kağıt üzerinde lock-free'dir, fakat aynı önbellek satırı üzerinde yarışan çekirdekler yüzünden P99 gecikmesi kilitli bir kuyruğun gerisine düşer.

Benim için lock-free yapıların değeri "kilidi kaldırmak" değil, bekleme davranışını daha öngörülebilir hale getirebildikleri noktalarda ortaya çıkar. Bunun için de veri yapısının ilerleme garantisiyle donanımın önbellek-coherence maliyetini aynı anda düşünmek gerekir.

Lock-free neyi garanti eder?

Lock-free, sistem seviyesinde ilerleme garantisidir. Iş parçacıklarından biri uzun süre durdurulsa bile diğer iş parçacıklarıden en az birinin sonlu sayıda adım içinde ilerleyebilmesini hedefler. Bu tanım tek bir iş parçacığı için gecikme üst sınırı vermez. Açlık mümkündür.

Wait-free daha güçlüdür; her katılımcı için sonlu adım garantisi ister. Bunun bedeli genellikle daha karmaşık veri yapıları, ek üstveri veya daha pahalı atomik işlemlerdir.

Bu ayrım üretim tarafında önemlidir. "Kilitlenme yok" ile "yüksek yüzdelik gecikme düşük" aynı iddia değildir.

CAS döngüsünün görünmeyen maliyeti

Çok sayıda lock-free kuyruk compare-and-swap etrafında kurulur. Basitleştirilmiş düşünce şudur:

1. Güncel head veya tail değeri okunur.
2. Yeni değer hesaplanır.
3. CAS ile atomik güncelleme denenir.
4. Başarısızsa başa dönülür.

Düşük çekişmede bu yaklaşım oldukça ucuz olabilir. Üretici sayısı arttığında aynı atomik değişken farklı çekirdeklerin önbellekleri arasında gidip gelir. Başarısız CAS artık yalnızca birkaç instruction değildir; önbellek tutarlılığı trafiği ve yeniden deneme döngüsü üretir.

Bu nedenle işlem hacmi arttıkça maliyet doğrusal davranmaz. Ortalama işlem süresi kabul edilebilir görünürken belirli iş parçacıkları arka arkaya CAS kaybedebilir. Ölçülmesi gereken yalnız işlem/s değil, yeniden deneme sayısı ve gecikme dağılımıdır.

False sharing lock-free kodu da vurur

Head ve tail mantıksal olarak farklı değişkenler olsa bile aynı önbellek satırı içindeyse, üretici ve tüketici birbirinden bağımsız alanlara yazarken bile önbellek satırı invalidation oluşabilir.

Bu, özellikle tek üreticili/tek tüketicili tasarımlarda gereksiz bir kayıptır. Alanları ayrı önbellek satırı'lara yerleştirmek veya dolgulama kullanmak ölçülebilir fark yaratabilir. Ancak dolgulamayı sabit 64 byte varsayımına bağlamak da taşınabilir değildir; hedef mimarinin destructive interference boyutu dikkate alınmalıdır.

Burada yapılacak optimizasyon nesne boyutunu büyütür. Binlerce kuyruk örneği varsa önbellek satırı ayırmanın bellek maliyeti de hesaba katılmalıdır.

Bellek sıralaması neden algoritmanın parçasıdır?

Atomik değişken kullanmak tek başına yeterli değildir. Üreticinin veri yükünü yazması ve indeks/sequence bilgisini yayınlaması arasında happens-before ilişkisi kurulmalıdır.

Her atomik işlemi ardışık tutarlı yapmak güvenli görünen kolay çözümdür fakat gereğinden ağır fence'lar üretebilir. Acquire/release semantiği doğru yerde kullanıldığında daha ucuz olabilir. Buna karşılık yanlış bir relaxed ordering x86 üzerinde yıllarca problemsiz görünen kodun ARM üzerinde bozulmasına yol açabilir.

Bu nedenle lock-free kodu yalnız hedef geliştirici makinesinde test etmek yanıltıcıdır. Algoritmanın bellek modeli kanıtı, instruction set'in tesadüfi ordering özelliklerinden bağımsız olmalıdır.

Sınırlı kuyruk çoğu üretim sistemi için daha anlamlıdır

Sınırsız kuyruk genellikle kolay görünür. Gerçekte tüketici üreticiden yavaşsa kuyruk problemi çözmez; yalnızca arızayı belleğe taşır.

Ben uzun süre çalışan servislerde kuyruk kapasitesinin sistem sözleşmesinin parçası olmasını daha güvenli buluyorum. Sınırlı yapı aşağıdaki kararları zorunlu hale getirir:

• Kuyruk dolduğunda üretici bekleyecek mi?
• Kayıt düşürülecek mi?
• Eski kayıt mı yeni kayıt mı feda edilecek?
• Ana kaynak'e geri basınç nasıl aktarılacak?
• Zaman aşımı toplam istek zaman bütçesinden mi düşülecek?

Lock-free kuyruk bu politikaların hiçbirini kendiliğinden çözmez.

SPSC, MPSC ve MPMC aynı problem değildir

Tek üreticili/tek tüketicili kuyruğu için gereksiz genel amaçlı MPMC algoritması kullanmak çoğu zaman fazladan atomik işlem demektir.

SPSC topolojisinde üretici yalnız write index'i, tüketici yalnız read index'i sahiplenebilir. MPSC'de üreticilerın rezervasyon problemi ortaya çıkar. MPMC'de hem enqueue hem dequeue tarafında çoklu sahiplik vardır.

Dolayısıyla "en hızlı kuyruk hangisi?" sorusu eksiktir. Doğru soru, gerçek iş parçacığı topolojisi ve veri yükü davranışı altında hangi kuyruğun daha düşük toplam maliyet ürettiğidir.

Bellek ayırma davranışı işlem hacmi kadar önemlidir

Node tabanlı kuyruklar her elemanda bellek ayırma yapıyorsa lock-free senkronizasyon kazancı bellek ayırıcı veya GC maliyetinde kaybolabilir. Sabit kapasiteli ring buffer bu açıdan avantajlıdır; veri düzeni daha yerel ve bellek ayırma davranışı deterministiktir.

Java tarafında nesne referanslı bir ring buffer GC basıncını tamamen kaldırmaz fakat node bellek ayırmayı ortadan kaldırabilir. C/C++ tarafında ise ownership ve object lifetime açıkça çözülmelidir.

Özellikle büyük veri yükünü kuyruğa kopyalamak yerine sabit yaşam süresi tanımlanmış descriptor veya indeks taşımak veri hareketini azaltabilir.

Başarım ölçümü nasıl yanıltır?

Kuyruk başarım ölçümlerinde sık gördüğüm hata, üretici ve tüketiciyi gerçek iş yapmadan yalnız enqueue/dequeue döngüsüne sokmaktır. Bu test veri yapısının teorik tavanını ölçer; uygulamanın davranışını değil.

Daha anlamlı ölçümde şunlar ayrılmalıdır:

• uncontended gecikme
• saturated işlem hacmi
• P50/P95/P99/P99.9 gecikme
• CAS yeniden deneme sayısı
• CPU tüketimi
• üretici ve tüketici sayısı
• veri yükü boyutu
• kuyruk occupancy dağılımı
• NUMA yerleşimi
• iş parçacığı sabitleme etkisi

Bir tasarım en yüksek işlem hacmi değerini verirken CPU'yu sürekli etkin bekleme'de tutabilir. Başka bir tasarım biraz daha düşük işlem hacmi ile çok daha iyi enerji tüketimi ve operasyonel kararlılık sağlayabilir.

Lock-free bir amaç değil araçtır

Kritik sistemlerde veri yapısını seçerken önce ilerleme garantisini değil, hata semantiği'i tanımlamak gerekir. Tüketici ölürse ne olacak? Üretici sonsuza kadar üretmeye devam edecek mi? Kuyruk dolarsa veri kaybı kabul edilebilir mi? Yeniden başlatmada kuyruktaki kayıtların kalıcılığı gerekiyor mu?

Bu sorular cevapsızsa mutex'i kaldırmak mimari problemi çözmez.

Lock-free algoritmaların gerçek değeri, doğru topolojide önbellek davranışı, bellek ayırma, bellek sıralaması ve geri basınç ile birlikte ele alındığında ortaya çıkar. Aksi halde "kilitsiz" kelimesi performans özelliği değil, yalnızca gerçekleştirim ayrıntısı olarak kalır.

Kaynakça

• Cameron Desrochers. moodycamel/concurrentqueue. https://github.com/cameron314/concurrentqueue

• Cameron Desrochers. “A Fast General Purpose Lock-Free Queue for C++.” 2014. https://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++

• Maged M. Michael; Michael L. Scott. “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.” Proceedings of PODC '96, 1996, ss. 267-275. DOI: 10.1145/248052.248106.

• Maurice Herlihy. “Wait-Free Synchronization.” ACM Transactions on Programming Languages and Systems, 13(1), 1991, ss. 124-149. DOI: 10.1145/114005.102808.