Yüksek performanslı bir ziyaretçi kayıt sistemi nasıl tasarlanır?
Talep noktaları
Her kullanıcının kendi kişisel alanı vardır. Diğer kullanıcılar ziyarete geldiğinde, bir ziyaretçi kaydı eklemeniz ve bunu en son ziyaretçiye güncellemeniz gerekir. İşte bir çukur, bu kullanıcının bir ziyaret kaydı varsa, kullanıcının son ziyaretini güncellemeniz gerekir zaman. Bu ihtiyacın teknoloji açısından herhangi bir özelliği var mı?
10 saniye düşünün, sonra aşağı bakın! ! ! Tasarım noktaları nelerdir?
- Kullanıcının ziyaretçi kayıtları önbelleğe alınmalıdır, aksi takdirde büyük eşzamanlılığa nasıl direnilir?
- En son ziyaretçi kayıtları çok hızlı değiştiği için hızlı bir şekilde yeni veri ekleyebilen ve eski verileri silebilen bir veri yapısı olmalıdır.
Bugün önbelleğe alma bölümünü bir kenara bırakalım. Yukarıdaki ikinci noktadan bahsedelim, bu da bugünün veri yapısının baş kahramanına götürür: Bağlantılı liste.
Bağlantılı liste
Bağlantılı Liste Ansiklopedisi: Bağlantılı liste, fiziksel bir depolama birimindeki bitişik olmayan, sıralı olmayan bir depolama yapısıdır.Veri öğelerinin mantıksal sıralaması, bağlantılı listedeki işaretçilerin bağlantı sırası ile elde edilir. Bağlantılı liste doğrusal bir yapıdır.
Sınıflandırma listesi
1. Tek bağlantılı liste : Bağlantılı listedeki öğeler, yalnızca bağlantılı listedeki sonraki öğeyi gösterebilir veya boştur ve öğeler birbirini gösteremez. Doğrusal bağlantılı bir listedir.
genel sınıf Düğüm < T >
{
// Mevcut düğümün veri elemanı
genel T Verileri {get; set;}
// Geçerli düğümün bir sonraki elemanı
genel Düğüm < T > NextNode {get; set;}
}
2. Çift bağlantılı liste: Her bağlantılı liste elemanının bir sonraki elemana bir gösterici ve önceki elemana bir gösterici vardır.Her düğümün iki işaretçisi vardır.
genel sınıf Düğüm < T >
{
// Geçerli düğümün önceki düğümü
genel Düğüm < T > Ön Düğüm {get; set;}
// Mevcut düğümün veri elemanı
genel T Verileri {get; set;}
// Geçerli düğümün bir sonraki elemanı
genel Düğüm < T > NextNode {get; set;}
}
3. Dairesel bağlantılı liste: Tek bağlantılı listeler ve çift bağlantılı listeler temelinde, döngüyü gerçekleştirmek için iki bağlantılı listenin son düğümünün birinci düğüme işaret edildiği anlamına gelir.
karakteristik
1. Eleman sayısı herhangi bir zamanda artırılabilir. Bağlantılı liste fiziksel depolama biriminde bitişik olmadığından, uzun süre kendine özgü avantajlarına sahiptir.Doğumum, gereksinimleri karşıladığı her yerde belleği tahsis edebilir.
2. Öğeler ekleyin:
Tek liste:
Bir N konumundan sonra yeni bir eleman eklerken, tek bağlantılı liste önce elemanın mevcut N konumundaki Sonraki göstericisini yeni elemana, ardından yeni elemanın Sonraki göstericisi N + 1 konumundaki elemana işaret eder. Elbette, ilk konuma yeni bir öğe eklerseniz, yalnızca yeni öğenin Sonraki işaretçisini bağlantılı listenin ilk öğesine yönlendirmeniz gerekir Benzer şekilde, tek bağlantılı listenin sonuna yeni bir öğe eklemek isterseniz, yalnızca tek bağlantılı listenin kuyruk öğesinin Sonraki işaretçisini ayarlamanız gerekir. Yeni öğeyi işaret edin. Dairesel tekil bağlantılı listeye gelince, ilk eleman ile son eleman arasında bir ayrım yoktur.
Çift bağlantılı liste:
N konumundan sonra yeni bir eleman eklemek, tekil bağlantılı bir listenin ilkesine benzer ve ilke, elemanın işaretçisini değiştirmektir. Ama burada bir fark var: Çift bağlantılı listenin ön ve arka elemanların (N konumu ve N + 1 konumu) ve yeni elemanın üç Düğümünün işaretçilerini değiştirmesi gerekiyor, bu yüzden biraz zahmetli.
3. Öğeleri silin:
Tek liste:
N konumundaki öğeyi silmek istediğinizde, yalnızca N-1 ila N + 1 konumundaki öğenin Sonraki işaretçisini göstermeniz gerekir.
Çift bağlantılı liste:
N konumundaki öğeyi silmek istediğinizde, N-1'deki öğenin Sonraki işaretçisini N + 1 öğesini gösterecek şekilde değiştirmeniz ve aynı zamanda N + 1'deki öğenin Ön işaretçisini N-1 öğesini gösterecek şekilde değiştirmeniz gerekir.
4. Öğeyi bulun:
Bağlı listenin öğeleri bellekte sürekli olmadığından, bir dizi gibi O (1) arama süresi karmaşıklığına sahip olamaz ve yalnızca bağlantılı listeyi ilk öğeden geçebilir, bu nedenle zaman karmaşıklığı O (n)
programlama
X toplam talebe dönmeniz için size 10 saniye verin. Bağlantılı listelerin tanıtılmasıyla, hangi bağlantılı listeyi seçmeliyiz? Burada önce düşüncelerim hakkında konuşacağım, herhangi bir hata varsa lütfen beni düzeltin:
1. Bir ziyaretçi kişisel alanın ana sayfasına girdiğinde, çoğu durumda, yalnızca ilk 100 veya 200 ziyaretçi kaydının önbelleğe alınması gerekir, bu da bu senaryoda sıcak veriler olduğu ve% 80 (veya daha yüksek) taleplerin karşılandığı anlamına gelir. Son 100 ziyaretçi verilerinde, çok az kişi kayıtlara uzun zaman önce bakacaktır. Bu yüzden, bellek alanı değerlendirmesine dayanarak, son 100 ziyaretçi verisini önbelleğe almaya karar verdim.
2. İlk 100 veriyi önbelleğe almak için bağlantılı bir liste kullandığımı varsayalım. Bunların arasında, birinci olmayan bir konumda A ziyaretçisinin bir kaydı var. Şu anda, A kullanıcı alanını tekrar ziyaret ediyor. A'nın kaydını ilk konuma taşımam gerekiyor. Bu işlem, A'yı silmekten geçti Veri, ilk konuma A verisi ekleyin. A'nın başlangıç konumu N ise, N konumunun verilerini sildiğimde, işaretçisini değiştirmek için N-1'in konum elemanını bulmalıyım.Eğer bu tek bağlı bir listeyse, çünkü mevcut konum N'nin elemanında N-1 konumunun elemanı hakkında bilgi yok, Tümünün bağlantılı listeyi yeniden taraması gerekir. Çift bağlantılı bir liste ise, N konumundaki öğe, öğeyi N-1 konumunda depolar, bu nedenle bağlantılı listeyi yeniden çaprazlamaya gerek yoktur.Bu aynı zamanda, tek bağlı listelerle karşılaştırıldığında çift bağlantılı listelerin avantajıdır, ancak bellek bir işaretçi bellek boyutu daha kaplar. , Ancak daha çok gerçek uygulama senaryolarında kullanılır. Bu yüzden çift bağlantılı listeyi seçiyorum. Silme işlemi ve ekleme işleminin zaman karmaşıklığı O (1) 'dir.
3. Aynı alana erişim, kaçınılmaz olarak kilitleme ve çoklu okuma problemine sahiptir. Bu yüzden çerçeveyi seçtiğimde, Actor modeline dayalı çerçeveyi tercih ettim. Aynı kullanıcı alanında kilitleme işleminden kaçının.
4. Actor modeline dayalı çerçeve nedeniyle, Redis gibi işlem dışı bir önbellek değil, işlem içi bir önbellek kullandım. Sonuçta, ağ aktarım hızı bellek işlemlerinden çok daha yavaş. Uygulama katmanındaki Actor hizmeti, doğal olarak dağıtımı destekler. Oyuncular hakkında fazla bir şey bilmiyorsan anneni kurtarabilirsin.
optimizasyon
1. Bunu okuduktan sonra bir şeylerin ters gittiğini mi hissediyorsunuz? Evet, bağlantılı liste öğelerinin aranmasıdır.Sadece üzerinden geçilebildiğinden, tüm bağlantılı liste arama öğelerinin zaman karmaşıklığı O (n) 'dur. Bunu optimize etmenin herhangi bir yolu var mı? Bu, daha sonra bahsedeceğimiz başka bir veri yapısıdır.
2. Alanın ziyaretçi kayıtları, boyut olarak zamanla ters sırada düzenlenir, bu nedenle işin tasarım türü ve DB zaman sütununun UTC zaman damgası uzun türü olması önerilir Sonuçta, uzun tür çoğu dilde tarih saat türünden çok daha küçük bellek kaplar.
3. Önbelleğin kullanılıp kullanılmadığına bakılmaksızın, kullanıcının erişim kayıtlarının DB tarafından saklanması gerekir.Çok sayıda istek olduğunda, veritabanına istek başına bir kez erişmek yerine, toplu işlerde DB'ye devam etmek için bir mekanizma kullanabiliriz.
4. Alan ziyaretçisi kayıtları için gerçek zamanlı gereksinimler çok yüksek olmadığında, önbelleği her 10 saniyede veya 5 saniyede bir güncelleyebiliriz, yani önbelleği toplu olarak güncelleyebiliriz, bu da tek bir kilit güncelleme önbelleğinden daha iyidir.
Kullanıcı erişim kayıtlarını aşırı derecede optimize edin
Ancak, kullanıcı erişim kayıtlarının önbelleğinde mevcut kullanıcının bir kaydı olup olmadığına nasıl karar verilir? Bağlantılı liste, iş senaryomuzdaki en önemli veri yapısı olsa da, mevcut soruna en iyi çözüm değil, bu yüzden bu sorunu çözmek için öğelere hızlıca erişebilen bir veri yapısına ihtiyacımız var? Bugün hash tabloları hakkında konuşacağımız şey bu.
Hash tablosu
Hash tablosu (Hash tablosu, hash table olarak da adlandırılır), anahtar değerine göre doğrudan erişilen bir veri yapısıdır. Başka bir deyişle, aramayı hızlandırmak için anahtar kod değerini tablodaki bir konuma eşleyerek kayda erişir. Bu eşleme işlevine bir karma işlevi adı verilir ve kayıtları depolayan dizi bir karma tablo olarak adlandırılır.
Karma tablo, aslında sık sık söylediğimiz Anahtar-Değer formuna yaklaşık olarak eşit olabilir. Karma tablosu, alt simgeye göre verilere rastgele erişimi desteklemek için dizinin özelliklerini kullanır, bu nedenle karma tablo aslında diziden gelişen dizinin bir uzantısıdır. Dizi yoksa hash tablosu olmadığı söylenebilir. Neden diziler kullanılıyor? Dizilerdeki öğelere aboneliklere göre erişmenin zaman karmaşıklığı O (1) olduğundan, anlamayan öğrenciler Cai Cainin dizilerle ilgili önceki makalesine bakabilirler.
Elemanlara dizinin alt simge durumuna göre erişmek istediğiniz için, Anahtarı bir alt simgeye nasıl dönüştüreceğinizi de düşünmelisiniz. Bu, daha sonra bahsedeceğimiz hash fonksiyonudur.
Özet fonksiyonu
Genel olarak, bir hash işlevi, bir Anahtarı bir dizi alt simge haline dönüştüren bir kara kutudur. Karma işlevi, karma tablosunda çok kritik bir rol oynar. Hash fonksiyonu, adından da anlaşılacağı gibi bir fonksiyondur. Bunu hash (key) olarak tanımlayabiliriz, burada key, elementin anahtar değerini temsil eder ve hash (key) değeri, hash fonksiyonu tarafından hesaplanan hash değerini temsil eder.
Bu hash işlevi için gereksinimler nelerdir?
- Karma işlevi tarafından hesaplanan değer, negatif olmayan bir tam sayı değeridir;
- Key1 = key2 ise, hash (key1) == hash (key2);
- Key1 key2 ise, hash (key1) hash (key2).
Basitçe yukarıdaki üç noktadan bahsedin, ilk nokta: hash değeri aslında dizinin alt simgesi olduğundan, negatif olmayan bir tamsayı olmalıdır ( > = 0), ikinci nokta: aynı anahtar için hesaplanan hash değeri aynı olmalıdır. Üçüncü noktaya odaklanmama izin verin, aslında üçüncü nokta sadece teorik ... Farklı anahtarlar ile elde edilen hash değerlerinin farklı olması gerektiğini düşünüyoruz ama aslında bunu başarmak zor. Bu formül doğruysa, sonsuz bir Anahtarın karma değerini hesaplıyorum, o zaman karma tablonun altındaki dizinin sonsuz olması gerektiğini kanıtlayabiliriz. Sektörde iyi bilinen MD5 ve SHA gibi karma algoritmalar bu tür çatışmaları tamamen önleyemez. Tabii ki, temeldeki dizi daha küçükse, bu çatışmanın olasılığı daha büyüktür.
Yani mükemmel bir hash fonksiyonu aslında mevcut değildir, var olsa bile, zaman maliyeti ve işçilik maliyeti hayal gücünün ötesinde olabilir.
Hash çarpışması
En iyi karma işlevi bile karma çatışmalardan kaçınamadığından, bu sorunu çözmek için başka yollar bulmalıyız.
1. Adresleme
Ya bir çatışma varsa? Yöntemlerden biri, dizideki boş alanı çakışan konumda aramaya başlamak, boş alanı bulmak ve onu yerleştirmektir. Sanki bir şey satın almak için bir mağazaya gidip tükendiğini fark ediyorsunuz, ne yapmalısınız? Bir şeyler satan bir sonraki tüccarı bulun. Hangi algılama yöntemi kullanılırsa kullanılsın, hash tablosunda çok fazla serbest pozisyon olmadığında, hash çarpışmaları olasılığı büyük ölçüde artacaktır. Karma tablonun çalışma verimliliğini olabildiğince sağlamak için, normal şartlar altında, karma tablosunda belirli bir yüzde serbest yuva olmasını sağlamaya çalışacağız. Boş kontenjan sayısını ifade etmek için yük faktörünü kullanıyoruz.
Karma tablosunun yükleme faktörü = tabloya doldurulan elemanların sayısı / karma tablonun uzunluğu
Yükleme faktörü ne kadar büyük olursa, o kadar az serbest konum ve daha fazla çakışma ve hash tablosunun performansı azalacaktır. Hash fonksiyonunun f = (anahtar% 1000) olduğunu varsayalım. Aşağıda gösterildiği gibi:
2. Zincir adres yöntemi (fermuar yöntemi)
Fermuar yöntemi, karma değer çatışmalarını çözmek için en sık kullanılan yöntemlerden biridir. Temel fikir, dizinin her öğesinin bağlantılı bir listeye işaret etmesidir ve karma değer çakıştığı zaman, bağlantılı listenin sonuna yeni bir öğe eklenir. Aynısı arama sırasında, karma değerine göre dizi konumunu belirledikten sonra ve ardından bağlantılı liste boyunca elemanı ararken de geçerlidir. Karma işlevinin tasarımı çok kötüyse ve aynı karma değeri çok büyükse, karma tablo öğelerinin aranması bağlantılı bir liste aramasına dönüşecek ve zaman karmaşıklığı O (n) olarak dejenere olacaktır.
3. Yeniden yıkama
Bu yöntem temelde karma değerini birden çok kez hesaplar, bu nedenle birden çok karma işlevi kaçınılmaz olarak gereklidir.Bir çakışma ortaya çıktığında, karma değeri artık çatışma oluşmayana kadar hesaplamak için başka bir karma işlevi kullanılır. "Toplanıyor", ancak hesaplama süresi arttı.
4. Ortak bir taşma alanı oluşturun
Bu tür bir şemaya gelince, ağa giriş nispeten küçüktür ve genel uygulama nispeten küçüktür. Şu şekilde anlaşılabilir: Çakışan hash değerlerine sahip elemanlar başka bir kaba yerleştirilir.Tabii ki, konteyner seçimi bir dizi, bağlantılı bir liste veya hatta bir kuyruk olabilir. Ancak ne olursa olsun, hash tablosunun avantajlarından emin olmak istiyorsanız, bu konteynerin seçimini dikkatlice düşünmelisiniz.
Arkasına yaz
1. Tekrar vurgulanması gerekiyor. Karma tablosunun alt katmanı, alt simgeye göre dizi erişiminin özelliklerine dayanır (zaman karmaşıklığı O (1)) ve genel karma tablosu, çok sayıda çakışmayı önlemek için bir yük faktörü tanımına sahiptir. Dizi genişletme özelliğine gelince: yeni dizi için yer açmanız ve öğeleri yeni diziye kopyalamanız gerekir. Depolanan veri miktarını veya depolanan yaklaşık veri miktarını bilirsek, hash tablosunu başlatırken, bir seferde yeterli alan ayırmayı deneyebiliriz. Sonraki dizi genişletmenin dezavantajlarından kaçının. Gerçekler, bellek sıkı olduğunda bu tek seferlik tahsis şemasının diğer şemalardan daha iyi olduğunu kanıtladı.
2. Hash tablosunun adresleme şemasında özel bir durum vardır: dizinin sonunu bulursam ve hala boş alan yoksa, ne yapmalıyım? Bu bana dairesel bağlantılı listeleri hatırlatıyor ve aynı şey dairesel bir dizide birleştirilebilen diziler için de geçerli. Sonunda boşluk yoksa, dizinin ilk konumunda aramaya devam edebilirsiniz.
3. Karma tablo elemanlarının silinmesi ile ilgili olarak, bundan bahsetmek gerektiğini düşünüyorum. İlk olarak, fermuar yöntemine dayalı hash tablosu Elemanlar bağlantılı listede olduğu için, bir elemanın silinmesinin zaman karmaşıklığı bağlantılı listeninkiyle aynıdır ve sonraki aramada herhangi bir sorun yoktur. Ancak adresleme modunun hash tablosu farklıdır Farz edelim ki N pozisyonundaki element silinmiş ve N pozisyonundan sonra aynı hash değerine sahip element aranamaz çünkü N pozisyonu zaten boştur. Karma tablosunun arama yöntemi, boş konumdan sonraki elemanın parçalanmış olduğunu belirler ... Bu, fermuar yöntemine dayalı karma tablonun daha yaygın olarak kullanılmasının nedenlerinden biridir.
4. Endüstriyel sınıf hash fonksiyonunda, gerekliliklerden biri, elemanların hash değerlerini olabildiğince eşit dağıtmaktır.Bu, yalnızca alanın tam kullanımı için değil, aynı zamanda çok sayıda hashCode'un aynı yere düşmesini önlemektir. Fermuar yönteminin en uç durumunda, bir elemanın aranmasının zaman karmaşıklığının, bağlantılı listedeki O (n) bir elemanın zaman karmaşıklığına dönüştüğünü ve bu da hash tablosunun maksimum karakteristiğinin kaybına yol açtığını hayal edin.
5. Fermuar yöntemi ile uygulanan bağlantılı listede, aslında çift bağlantılı bir liste kullanmayı tercih ediyorum, bu nedenle bir öğeyi silerken, çift bağlantılı listenin avantajları aynı anda devreye sokulabilir ve bu, öğelerin karma tablosundan O ( 1).
6. Karma tablosunda, öğenin konumu karma işlevi tarafından belirlendiğinden, bir karma tablosunu geçerken öğelerin sırası öğelerin eklendiği sıra değildir.Bu, belirli iş uygulamalarına dikkat etmemizi gerektirir.
Net Çekirdek c # kodu
Vurgulanması gereken birkaç nokta var:
1. Mevcut projede kullanılan dağıtılmış çerçeve, Actor modeline dayalı Orleans'tır, bu nedenle her kullanıcının erişim kaydı için çoklu okuma konusunda endişelenmeme gerek yok;
2. Hashtable'ı bir veri kabı olarak kullanmadım çünkü hashtable, sorunları paketleme ve paketten çıkarma konusunda çok eğilimli;
3. Çift bağlantılı liste, önceki elemanı ve sonraki elemanı bulmaya eşdeğer olan mevcut eleman bulunduğu için kullanılır.Geçerli elemanı silmenin zaman karmaşıklığı O (1) olabilir.
sınıf UserViewInfo { //Kullanıcı kimliği public int UserId {get; set;} // Erişim süresi, utc zaman damgası public int Zaman {get; set;} //Kullanıcı adı public string KullanıcıAdı {get; set;} } sınıf UserSpace { // Maksimum önbellek sayısı const int CacheLimit = 1000; // Burada kullanıcı alanı erişim kayıtlarını önbelleğe almak için çift bağlantılı bir liste kullanıyoruz Bağlantılı liste < UserViewInfo > cacheUserViewInfo = yeni LinkedList < UserViewInfo > (); // Burada, hızlı erişim sağlamak için erişim kayıtlarını depolamak için hash tablosunun bir varyantı olan Dictionary'yi kullanıyoruz.Aynı zamanda, hash çakışmalarını azaltmak için kapasiteyi önbellek sayısı sınırından daha büyük olacak şekilde ayarlayın Sözlük < int, UserViewInfo > dicUserView = yeni Sözlük < int, UserViewInfo > (1250); // Kullanıcının erişim kaydını ekle public void AddUserView (UserViewInfo uv) { // Önce önbellek listesinde olup olmadığını bulun ve hızlı arama gerçekleştirmek için hashtable'ı kullanın if (dicUserView. TryGetValue (uv.UserId, out UserViewInfo currentUserView)) { // Varsa, kullanıcı erişim kaydını önbelleğin mevcut konumundan kaldırın ve baş konumuna ekleyin cacheUserViewInfo.Remove (currentUserView); cacheUserViewInfo.AddFirst (currentUserView); } Başka { // Mevcut değilse, önbellek başlığına ekleyin ve karma tablosuna ekleyin cacheUserViewInfo.AddFirst (uv); dicUserView.Add (uv.UserId, uv); } // Önbelleğin sınırı aşıp aşmadığını her değerlendirdiğimizde if (cacheUserViewInfo.Count > CacheLimit) { // Son öğeyi önbellekten kaldırın ve hashtable'dan silin.Teorik olarak, sözlükteki ilk öğe ve son öğe için iki işaretçi olacaktır, bu nedenle bu iki öğeyi bulmanın zaman karmaşıklığı O (1) var lastItem = cacheUserViewInfo.Last.Value; dicUserView.Remove (lastItem.UserId); cacheUserViewInfo.RemoveLast (); } } }Yazar: Cai Cai, İnternet yüksek yolunun yönetilmesinde lider bir mühendis, İnternet teknolojisine meraklı. Şu anda bir İnternet eğitim şirketinde çalışıyor, uygulama sunucusundan sorumlu asıl kişi. 10 yıllık İnternet geliştirme tecrübesiyle, yüksek performans, yüksek eşzamanlılık ve dağıtılmış teknoloji alanındaki araştırmalara meraklıdır.Ana çalışma dilleri C # ve Golang'dır.
Sorumluluk Reddi: Bu makale yazar tarafından gönderilmiş olup, telif hakkı kendisine aittir, sorumlu Editör Guo Rui'dir.
