Lock-Free Kuyruklarda Gerçek Maliyet
Lock-free bir kuyruğun mutex kullanmaması onu otomatik olarak daha hızlı yapmaz. CAS çekişmesi, cache-line paylaşımı, bellek sıralaması, producer/consumer topolojisi ve backpressure birlikte değerlendirilmelidir.
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ı cache line ü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 cache-coherence maliyetini aynı anda düşünmek gerekir.
Lock-free neyi garanti eder?
Lock-free, sistem seviyesinde ilerleme garantisidir. Thread'lerden biri uzun süre durdurulsa bile diğer thread'lerden en az birinin sonlu sayıda adım içinde ilerleyebilmesini hedefler. Bu tanım tek bir thread için gecikme üst sınırı vermez. Starvation 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 metadata veya daha pahalı atomik işlemlerdir.
Bu ayrım production tarafında önemlidir. "Deadlock yok" ile "tail latency 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:
- Güncel head veya tail değeri okunur.
- Yeni değer hesaplanır.
- CAS ile atomik güncelleme denenir.
- Başarısızsa başa dönülür.
Düşük çekişmede bu yaklaşım oldukça ucuz olabilir. Producer sayısı arttığında aynı atomik değişken farklı çekirdeklerin cache'leri arasında gidip gelir. Başarısız CAS artık yalnızca birkaç instruction değildir; cache coherence trafiği ve yeniden deneme döngüsü üretir.
Bu nedenle throughput arttıkça maliyet doğrusal davranmaz. Ortalama işlem süresi kabul edilebilir görünürken belirli thread'ler arka arkaya CAS kaybedebilir. Ölçülmesi gereken yalnız operation/s değil, retry 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ı cache line içindeyse, producer ve consumer birbirinden bağımsız alanlara yazarken bile cache line invalidation oluşabilir.
Bu, özellikle single-producer/single-consumer tasarımlarda gereksiz bir kayıptır. Alanları ayrı cache line'lara yerleştirmek veya padding kullanmak ölçülebilir fark yaratabilir. Ancak padding'i 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 instance'ı varsa cache line ayırmanın bellek maliyeti de hesaba katılmalıdır.
Memory ordering neden algoritmanın parçasıdır?
Atomik değişken kullanmak tek başına yeterli değildir. Producer'ın payload'u yazması ve indeks/sequence bilgisini yayınlaması arasında happens-before ilişkisi kurulmalıdır.
Her atomik işlemi sequentially consistent 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.
Bounded queue çoğu production 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 queue kapasitesinin sistem sözleşmesinin parçası olmasını daha güvenli buluyorum. Bounded yapı aşağıdaki kararları zorunlu hale getirir:
- Kuyruk dolduğunda producer bekleyecek mi?
- Kayıt düşürülecek mi?
- Eski kayıt mı yeni kayıt mı feda edilecek?
- Upstream'e backpressure nasıl aktarılacak?
- Timeout toplam istek zaman bütçesinden mi düşülecek?
Lock-free queue bu politikaların hiçbirini kendiliğinden çözmez.
SPSC, MPSC ve MPMC aynı problem değildir
Single-producer/single-consumer kuyruğu için gereksiz genel amaçlı MPMC algoritması kullanmak çoğu zaman fazladan atomik işlem demektir.
SPSC topolojisinde producer yalnız write index'i, consumer yalnız read index'i sahiplenebilir. MPSC'de producer'ların rezervasyon problemi ortaya çıkar. MPMC'de hem enqueue hem dequeue tarafında çoklu sahiplik vardır.
Dolayısıyla "en hızlı queue hangisi?" sorusu eksiktir. Doğru soru, gerçek thread topolojisi ve payload davranışı altında hangi kuyruğun daha düşük toplam maliyet ürettiğidir.
Allocation davranışı throughput kadar önemlidir
Node tabanlı kuyruklar her elemanda allocation yapıyorsa lock-free senkronizasyon kazancı allocator veya GC maliyetinde kaybolabilir. Sabit kapasiteli ring buffer bu açıdan avantajlıdır; veri düzeni daha yerel ve allocation davranışı deterministiktir.
Java tarafında nesne referanslı bir ring buffer GC basıncını tamamen kaldırmaz fakat node allocation'ını ortadan kaldırabilir. C/C++ tarafında ise ownership ve object lifetime açıkça çözülmelidir.
Özellikle büyük payload'u kuyruğa kopyalamak yerine sabit yaşam süresi tanımlanmış descriptor veya indeks taşımak veri hareketini azaltabilir.
Benchmark nasıl yanıltır?
Queue benchmark'larında sık gördüğüm hata, producer ve consumer'ı 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 latency
- saturated throughput
- P50/P95/P99/P99.9 gecikme
- CAS retry sayısı
- CPU tüketimi
- producer ve consumer sayısı
- payload boyutu
- queue occupancy dağılımı
- NUMA yerleşimi
- thread pinning etkisi
Bir tasarım en yüksek throughput değerini verirken CPU'yu sürekli busy-spin'de tutabilir. Başka bir tasarım biraz daha düşük throughput 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, failure semantics'i tanımlamak gerekir. Tüketici ölürse ne olacak? Producer sonsuza kadar üretmeye devam edecek mi? Queue 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 cache davranışı, allocation, memory ordering ve backpressure ile birlikte ele alındığında ortaya çıkar. Aksi halde "kilitsiz" kelimesi performans özelliği değil, yalnızca implementasyon ayrıntısı olarak kalır.
Kaynakça
