Erken versiyonlarda Go, harita hash'lemesi sabit bir tohumla deterministik bir algoritma kullanıyordu. Bu, uygulamaların, saldırganların tümü aynı bölmeye çarpışan anahtarlar oluşturabileceği hash flooding saldırılarına karşı savunmasız hale gelmesine neden oldu ve arama performansını O(1)'den O(n)'ye düşürdü. Go ekibi, Go 1.12'de (ve sonraki sürümlerde daha da güçlendirildi) her harita için rastgele hash tohumları tanıttı ve saldırganların bucket yerleşimini tahmin etmesini sağlamak için çalışma zamanı hash rastgeleleştirmesi ile birleştirdi.
Kritik sorun, bir hash tablosu düşmanca bir girişle karşılaştığında ortaya çıkar. Önlem alınmadığı takdirde, güvensiz veriyi haritalara (örneğin, HTTP başlıkları veya JSON nesneleri) ayrıştıran web hizmetleri, çarpışan binlerce anahtar içeren tek bir kötü niyetli istekle durdurulabilir. Zorluk, hız ve bellek verimliliğinden ödün vermeden öngörülemezliği tanıtmaktı; bu özellikler Go haritalarını yüksek performanslı sistemler için uygun hale getirir.
Go çalışma zamanı, başlatma sırasında her harita örneği için bir rastgele tohum oluşturur, bunu runtime.fastrand kullanarak gerçekleştirir. Bu tohumla anahtarlanan bir hash fonksiyonu (genellikle modern CPU'larda AES donanım talimatları, diğerlerinde ise memhash ile geri dönüş) kullanılır. Örneğin, aşağıdaki satırı yazdığınızda:
m := make(map[string]int) m[untrustedInput] = 1
Çalışma zamanı, anahtarın baytlarını haritanın benzersiz hash0 alanıyla birleştiren tür spesifik bir hasher'i içten çağırır. Çarpışmaları yönetmek için Go, açık adresleme yerine taşma bölmeleriyle zincirleme kullanır ve büyüme aşamalarında girdileri kademeli olarak tahliye eder. Bu tasarım, düşmanca girdilerle bile, bölmeler arasındaki dağılımın uniform kalmasını sağlayarak ortalama durumda O(1) işlemlerini korur.
Yüksek trafikli bir API geçidi inşa ettiğinizi hayal edin; bu geçit, binlerce mikro hizmetten yapılandırma toplar. Her hizmet, bir JSON yükü aracılığıyla sağlık durumunu bildirir; bu yük dinamik etiketler içerir ve bir map[string]string içerisinde saklanır. Bir saldırgan, uç noktanızı keşfeder ve her etiket anahtarının aynı hash değerini üretmek üzere tasarlandığı hatalı bir yük gönderir; bu, hizmetinizin istekleri işlerken saniyelerce tek bir bölmeyi dolaşmasına neden olur ve zaman aşımı zincirine yol açar.
Sistemi güçlendirmek için birden fazla çözüm düşünüldü.
Bir yaklaşım, harita yerine dengeli bir ikili arama ağacı olan kırmızı-siyah ağaç uygulamasını kullanmaktı. Bu, girdiden bağımsız olarak O(log n) en kötü durum aramasını garanti ederdi ve hizmet reddi vektörünü ortadan kaldırırdı. Ancak bu, önemli bir karmaşıklık getirecek, dış kütüphanelerin ithalini veya ağır makine yazımı gerektirecek ve her meşru isteği, yerel harita ile karşılaştırıldığında daha yavaş erişim süreleri ve yüksek bellek aşımıyla cezalandıracaktı.
Düşünülen bir diğer çözüm, şüpheli kalıplar içeren istekleri reddetmek veya toplam anahtar sayısını yüz gibi küçük bir sayı ile sınırlamaktı. Bu, bir saldırının mutlak etkisini azaltırken, temel algoritmik karmaşıklık zayıflığını gidermemekte; saldırgan, daha az sayıda, oldukça optimize edilmiş çarpışan anahtarlarla maksimum zararı verebilir ve birçok etiket gerektiren meşru kullanım durumları yanlışlıkla reddedilebilir.
Seçilen çözüm, Go'nun yerleşik harita güçlendirmesine güvenmek ve ara katman hız sınırlama eklemek oldu. Modern Go sürümleri her harita örneği için otomatik olarak hash tohumunu rastgele hale getirdiğinden, saldırgan hangi anahtarların çarpışacağını tahmin edemez ve bu da hash flooding saldırısını etkisiz hale getirir. Bunu kötü niyetli yüklerle performans testleri yaparak ve tutarlı alt milisaniye ayrıştırma süreleri gözlemleyerek doğruladık. Sonuç, temel veri yapısını değiştirmeden veya API ergonomisinden ödün vermeden O(1) performans özelliklerini sürdüren dayanıklı bir geçit oldu.
Neden Go, anahtarlar için SHA-256 gibi kriptografik hash fonksiyonları kullanmıyor ve dağılımı garanti altına almıyor?
Kriptografik hash'ler mükemmel çığ etkisi özellikleri sağlasa da, yıkıcı hesaplama yükü ile birlikte gelir. Go haritaları, günlük işlemler için hız önceliklidir ve kriptografik hashing, belirli bir kenar durumu saldırısına karşı savunma yapmak için tüm kullanım durumları için performansı on kat kötüleştirecektir. Bunun yerine, Go, dağılım için yeterli rastgelelik sağlarken sistem programlaması için gereken verimliliği koruyan hızlı, kriptografik olmayan hash algoritmalarını kullanır (mevcut olduğu yerlerde AES-NI talimatlarıyla optimize edilmiştir).
Harita büyümesi (iki katına çıkma), mevcut hash tohumlarının geçerliliğini nasıl korur ve girişlerin doğru bir şekilde yeniden dağıtılmasını nasıl sağlar?
Bir harita büyüdüğünde (genellikle yük faktörü 6.5 bölmeyi aştığında), çalışma zamanı iki katı boyutunda yeni bir dizi tahsis eder. Kademeli tahliye sırasında, çalışma zamanı her girişi orijinal rastgele tohumla ancak yeni bucket maskesi (daha yüksek bitler) ile yeniden hash'ler. Hash'i belirli bir tohum için deterministik olduğu için, ancak bölme sayısı değiştiği için, girişler doğal olarak farklı bölmelere dağılır. Adaylar genellikle tohumun haritanın ömrü boyunca sabit kaldığını atlar; yalnızca bucket indeksini seçmek için kullanılan bitmask değişir ve bu, yeniden hash yapma işlemine yalnızca büyüme sırasında, her aramada değil, gerçekleşmesine neden olur.
Haritalar için kullanılan hash fonksiyonu ile diğer amaçlar için runtime.memhash tarafından kullanılan hash fonksiyonu arasındaki fark nedir ve bu ayrım neden önemlidir?
Her ikisi de benzer algoritmalar kullanmasına rağmen, harita hash'lemesi per-harita rastgele tohumunu ve tür spesifik alg işlevlerini (bunun üzerinden runtime.typeAlg) içerir ve değişen anahtar türlerini (dizeler, tam sayılar, yapılar) yönetir. Buna karşılık, runtime.memhash, tür farkındalığı olmaksızın ham bellek baytlarını hash'lemek için genel amaçlı bir yardımcı araçtır. Bu ayrım önemlidir çünkü harita hash'lemesi Go'nun eşitlik semantiğine saygı göstermelidir; örneğin, farklı yapı alanlarının hash'e doğru bir şekilde katkıda bulunmasını sağlamak; oysa memhash, yalnızca bayt dizileri içindir. Bu ayrımın anlaşılması, Go'nun hem tür güvenliği hem de performans için nasıl optimize olduğunu vurgular.