2.1 N kez parçalama ve yavaşlatma nasıl yapılır?

Bunun gibi tam olarak N kez parçalayabilir ve yavaşlatabilirsiniz:

  • docs00...docs15 isteklerini paralel olarak değil sırayla gönderin.
  • Basit sorgularda, key ile değil , WHERE bir şey=234 ile bir seçim yapın.

Bu durumda, serileştirilmiş kısım (seri), modern veritabanlarında% 1 ve% 5 değil, yaklaşık% 20'yi alır. Veritabanına son derece verimli bir ikili protokol kullanarak erişirseniz veya onu dinamik bir kitaplık olarak bir Python betiğine bağlarsanız, serileştirilmiş parçanın %50'sini de elde edebilirsiniz.

Basit bir talebin işlem süresinin geri kalanı, talebin ayrıştırılması, planın hazırlanması vb. paralelleştirilemez işlemler tarafından işgal edilecektir. Yani kaydı okumamak yavaşlar.

Verileri 16 tabloya böler ve örneğin PHP programlama dilinde alışılageldiği gibi sırayla çalıştırırsak (asenkron işlemleri başlatmada pek iyi değildir), o zaman 16 kat yavaşlama elde ederiz. Ve belki daha da fazlası, çünkü ağ gidiş-dönüşleri de eklenecek.

Aniden, parçalama sırasında programlama dili seçimi önemlidir.

Programlama dili seçimini unutmayın, çünkü sorguları veritabanına (veya arama sunucusuna) sırayla gönderirseniz, hızlanma nereden gelir? Aksine bir yavaşlama olacaktır.

2.2 Yarı otomatik hakkında

Yer yer, bilgi teknolojisinin karmaşıklığı chtonik korkuya ilham veriyor. Örneğin, MySQL'in kutudan çıktığı haliyle belirli sürümlere parçalama uygulaması kesinlikle yoktu, ancak savaşta kullanılan veritabanlarının boyutları uygunsuz değerlere ulaştı.

Bireysel DBA'lar karşısında acı çeken insanlık, yıllarca eziyet gördü ve hiçbir şeye dayanmayan birkaç kötü parçalama çözümü yazdı. Bundan sonra, ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...) adı verilen az çok düzgün bir parçalama çözümü yazılır. Bu, bu lekenin iyi bilinen bir örneğidir.

Bir bütün olarak ProxySQL, elbette, yönlendirme ve daha fazlası için açık kaynak için tam teşekküllü bir kurumsal sınıf çözümdür. Ancak çözülmesi gereken görevlerden biri, kendi başına insani bir şekilde parçalayamayan bir veritabanı için parçalamadır. Görüyorsunuz, “shards = 16” anahtarı yok, ya uygulamadaki her isteği yeniden yazmanız gerekiyor ve bunların birçoğu var ya da uygulama ile veritabanı arasına şöyle görünen bir ara katman koyuyorsunuz: “Hmm ... Belgelerden * SEÇİN? Evet, 16 küçük SELECT * FROM server1.document1, SELECT * FROM server2.document2 - bu sunucuya böyle bir kullanıcı adı / şifre ile, buna diğerine bölünmelidir. Biri cevap vermediyse, o zaman ... ", vb. Tam olarak bu, ara lekeler ile yapılabilir. Tüm veritabanlarından biraz daha azdırlar. PostgreSQL için, anladığım kadarıyla,

Her bir özel yamayı yapılandırmak, tek bir rapora sığmayacak ayrı dev bir konudur, bu nedenle yalnızca temel kavramları tartışacağız. En iyisi biraz vızıltı teorisi hakkında konuşalım.

2.3 Mutlak mükemmel otomasyon?

Bu harf F()' de sharding durumunda yüksek olma teorisinin tamamı , temel prensip kabaca her zaman aynıdır: shard_id = F(object).

Sharding - tüm bunlar neyle ilgili? 2 milyar kaydımız var (veya 64). Onları birkaç parçaya bölmek istiyoruz. Beklenmedik bir soru ortaya çıkıyor - nasıl? 2 milyar (veya 64) kaydımı hangi ilkeye göre kullanabileceğim 16 sunucuya dağıtmalıyım?

İçimizdeki gizli matematikçi, sonunda her belge için (nesne, çizgi vb.) onu hangi parçaya koyacağımızı belirleyecek sihirli bir işlev olduğunu önermelidir.

Matematiğin derinliklerine inildiğinde, bu işlev her zaman yalnızca nesnenin kendisine (satırın kendisine) değil, aynı zamanda toplam kırık sayısı gibi harici ayarlara da bağlıdır. Her nesne için onu nereye koyacağını söylemesi gereken bir işlev, sistemdeki sunuculardan daha fazla bir değer döndüremez. Ve işlevler biraz farklıdır:

Java webinar 
shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

Ancak ayrıca, bu bireysel işlevlerin vahşi doğasına girmeyeceğiz, sadece F () 'nin sihirli işlevlerinin ne olduğu hakkında konuşacağız.

2.4 F() nedir?

Pek çok farklı ve pek çok farklı uygulama mekanizması bulabilirler. Örnek özet:

  • F = rand() % nums_shards
  • F = bazı hash(object.id) % num_shards
  • F = nesne.tarihi % num_shards
  • F = object.user_id % num_shards
  • ...
  • F = shard_table [ bazı hash() |… nesne.tarihi |… ]

İlginç bir gerçek - tüm verileri doğal olarak rastgele dağıtabilirsiniz - bir sonraki kaydı rastgele bir sunucuya, rastgele bir çekirdeğe, rastgele bir tabloya atarız. Bunda pek mutluluk olmayacak ama işe yarayacak.

Tekrar üretilebilir veya hatta tutarlı bir hash işleviyle parçalamak veya bazı özniteliklere göre parçalamak için biraz daha akıllı yöntemler vardır. Her yöntemi inceleyelim.

F = rand()

Etrafa saçılmak çok doğru bir yöntem değil. Bir sorun: 2 milyar kaydımızı rastgele bin sunucuya dağıttık ve kaydın nerede olduğunu bilmiyoruz. user_1'i çıkarmamız gerekiyor, ancak nerede olduğunu bilmiyoruz. Bin sunucuya gidiyoruz ve her şeyi sıralıyoruz - bir şekilde bu verimsiz.

F = birazhash()

Kullanıcıları yetişkin bir şekilde dağıtalım: user_id'den yeniden üretilebilir karma işlevini hesaplayın, bölümün geri kalanını sunucu sayısına göre alın ve hemen istenen sunucuyla iletişime geçin.

Bunu neden yapıyoruz? Ve sonra, bir yüksek yükümüz var ve başka hiçbir şey tek bir sunucuya sığmıyor. Eğer uysaydı, hayat çok basit olurdu.

Harika, durum çoktan düzeldi, bir kayıt almak için önceden bilinen bir sunucuya gidiyoruz. Ancak, bir dizi anahtarımız varsa, o zaman tüm bu aralıkta, anahtarların tüm değerlerini gözden geçirmemiz ve sınırda, aralıktaki anahtarlarımız kadar çok parçaya gitmemiz gerekir. her sunucu. Durum elbette düzeldi, ancak tüm talepler için değil. Bazı sorgular etkilendi.

Doğal parçalama (F = object.date % num_shards)

Bazen, yani genellikle trafiğin %95'i ve yükün %95'i, bir tür doğal paylaşıma sahip isteklerdir. Örneğin, koşullu sosyal-analitik sorguların %95'i yalnızca son 1 gün, 3 gün, 7 güne ait verileri etkiler ve geri kalan %5'lik kısım son birkaç yılı ifade eder. Ancak isteklerin %95'i doğal olarak tarihe göre parçalanır, sistem kullanıcılarının ilgisi son birkaç güne odaklanır.

Bu durumda, verileri tarihe göre, örneğin bir güne bölebilir ve bir gün için bir rapor talebinin yanıtını veya bu günden bu parçaya bir nesneyi takip edebilir ve gidebilirsiniz.

Hayat gelişiyor - artık sadece belirli bir nesnenin yerini değil, aynı zamanda menzili de biliyoruz. Bizden bir tarih aralığı değil, bir dizi başka sütun istenirse, o zaman elbette tüm parçaları gözden geçirmemiz gerekecek. Ancak oyunun kurallarına göre bu tür isteklerin sadece %5'ine sahibiz.

Görünüşe göre her şeye ideal bir çözüm bulduk, ancak iki sorun var:

  • Bu çözüm, isteklerin %95'inin yalnızca geçen haftayı içerdiği belirli bir durum için uyarlanmıştır.
  • İsteklerin %95'i geçen haftaya dokunduğu için hepsi bu geçen hafta hizmet veren tek bir parçaya düşecek. Bu parça eriyecek, diğerleri ise bu süre zarfında boşta kalacak. Aynı zamanda onları atamazsınız, arşiv verilerinin de saklanması gerekir.

Bunun kötü bir parçalama şeması olduğunu söylememek - sıcak verileri kestik, yine de en sıcak parçayla bir şeyler yapılması gerekiyor.

Sorun, maskaralıklar, atlamalar ve lapalarla çözülür, yani yanan gün için kopya sayısında bir artış, ardından bu gün geçmişe dönüştüğünde ve arşive gittiğinde kopya sayısında kademeli bir azalma. “Sihirli bir hash fonksiyonu ile verileri yanlış bir şekilde kümeye yaymanız yeterli” diye ideal bir çözüm yoktur.

2.5 Ödenecek bedel

Resmi olarak, artık "her şeyi" bildiğimizi biliyoruz. Doğru, bir dev baş ağrısı ve iki küçük baş ağrısı bilmiyoruz.

1. Basit ağrı: Kötü bir şekilde bulaşmış

Bu, savaşta neredeyse hiç olmayan, ancak aniden ortaya çıkan bir ders kitabından bir örnektir.

  • Tarihli bir örnek olarak, yalnızca tarihsiz!
  • Kasıtsız düzensiz (algılanabilir) dağılım.

Parçalama mekanizmasını seçtiler ve/veya veriler değişti ve tabii ki Proje Yöneticisi gereksinimleri iletmedi (kodda hatamız yok, Proje Yöneticisi her zaman gereksinimleri bildirmiyor) ve dağıtım canavarca düzensiz hale geldi. Yani kriteri kaçırdılar.

Yakalamak için parçaların boyutuna bakmanız gerekir. Kırıklarımızdan biri aşırı ısındığında veya diğerlerinden 100 kat daha büyük hale geldiğinde sorunu mutlaka göreceğiz. Anahtarı veya parçalama işlevini değiştirerek basitçe düzeltebilirsiniz.

Bu basit bir sorun, dürüst olmak gerekirse, hayatta en az yüz kişiden birinin bununla karşılaşacağını düşünmüyorum ama birdenbire en azından birine yardımcı olacaktır.

2. "Yenilmez" acı: toplama, birleştirme

Bir tablodaki bir milyar kaydı başka bir tablodaki bir milyar kayda bağlayan seçimler nasıl yapılır?

  • Nasıl "hızlı" hesaplanır... Randcol aaa VE bbb ARASINDA NEREDE?
  • "Akıllıca" nasıl yapılır... users_32shards posts_1024 shards'a KATILIN?

Kısa cevap: mümkün değil, acı çek!

İlk tablodaki bin sunucuya daha hızlı çalışsınlar diye milyarlarca kayıt dağıttıysanız ve ikinci tabloda da aynısını yaptıysanız, o zaman doğal olarak bin ila bin sunucunun birbiriyle çiftler halinde konuşması gerekir. Bir milyon bağlantı iyi çalışmayacak. Veritabanına (arama, depolama, belge deposu veya dağıtılmış dosya sistemi) parçalamaya pek uymayan istekler yaparsak, bu istekler çılgınca yavaşlar.

Önemli bir nokta, bazı isteklerin her zaman başarısız bir şekilde lekelenmesi ve yavaşlamasıdır . Yüzdelerini en aza indirmeye çalışmak önemlidir. Sonuç olarak, milyar x milyar kayıtla devasa birleştirmeler yapmaya gerek yoktur. Dev bir paylaşımlı masada göreli olarak katıldığınız küçük bir tabloyu tüm düğümlere çoğaltmak mümkünse, bunu yapmalısınız. Birleştirmeler aslında bir şekilde yerelse, örneğin, kullanıcıyı ve gönderilerini yan yana yerleştirmek, bunları aynı şekilde parçalamak ve tüm birleştirmeleri aynı makine içinde yapmak mümkündür - tam da bunu yapmanız gerekir .

Bu, üç günlük ayrı bir ders dersidir, bu yüzden hadi son cehennem acısına ve bununla başa çıkmak için farklı algoritmalara geçelim.

2.6. Karmaşık/Uzun Ağrı: Yeniden Sertleştirme

Hazır olun: Hayatınızda ilk kez verilerinizi parçaladıysanız, ortalama olarak beş kez daha parçalayacaksınız.

Ne kadar küme yapılandırırsanız yapılandırın, yine de yeniden donanıma ihtiyacınız vardır.

Çok akıllı ve şanslıysanız, en az bir kez aşırı paylaşım yapın. Ama emin olduktan sonra, çünkü kullanıcı için 10 birimin yeterli olduğunu düşündüğünüz anda, birisi tam o anda 30 birim için bir istek yazar ve 100 birim bilinmeyen kaynak için bir istekte bulunmayı planlar. Parçalar asla yeterli değildir. İlk parçalama şemasıyla, her durumda, özleyeceksiniz - her zaman eklenecek sunucu sayısını artırmanız veya başka bir şey yapmanız gerekecek - genel olarak, verileri bir şekilde yeniden paketlemeniz.

İkinin güzel güçlerine sahipsek iyi olur: 16 sunucu parçacığı vardı, şimdi 32. 17 olsaydı daha eğlenceliydi, 23 - iki küçük asal sayı. Veritabanları bunu nasıl yapıyor, belki de içinde bir tür sihir var?

Doğru cevap: hayır, içlerinde sihir yok, içlerinde cehennem var.

Ardından, "elle" ne yapılabileceğini ele alacağız, belki "otomatik bir makine olarak" anlayacağız.

Alında # 1. Her Şeyin Yerini Değiştirin

Tüm nesneler için, NewF(nesne), yeni bir parçaya geçiş olarak değerlendiriyoruz.

NewF()=OldF() eşleşme şansı düşüktür.

Neredeyse her şeyi ele alalım.

Ah.

Umarım 2 milyar plağın tamamını eski parçalardan yenilerine aktarmak gibi bir cehennem yoktur. Naif yaklaşım anlaşılabilir: 17 makine vardı, kümeye 6 makine eklendi, 2 milyar kayıt tasnif edildi, 17 makineden 23 makineye kaydırıldı. Her 10 yılda bir, muhtemelen bunu bile yapabilirsiniz. Ama genel olarak kötü bir hamle.

Alında #2. Yarının yerini değiştir

Bir sonraki saf gelişme - hadi böyle aptalca bir planı terk edelim - 17 arabanın 23 arabaya yeniden takılmasını yasaklayacak ve biz her zaman 16 arabayı 32 arabaya yeniden takacağız! O zaman teoriye göre verilerin tam yarısını kaydırmamız gerekecek ve pratikte bunu da yapabiliriz.

Tüm nesneler için, NewF(nesne), yeni bir parçaya geçiş olarak değerlendiriyoruz.

Kesin olarak 2^N idi, şimdi kesinlikle 2^(N+1) kırık.

NewF()=OldF() ile eşleşme olasılığı 0,5'tir.

Verilerin yaklaşık %50'sini aktaralım.

Optimal, ancak yalnızca ikinin güçleri için çalışır.

Prensip olarak, araba sayısı açısından ikinin gücüne bağlanma dışında her şey yolunda. Garip bir şekilde bu saf yaklaşım işe yarayabilir.

Lütfen bu durumda kümenin ikinin kuvvetlerine göre ek bölünmesinin de optimal olduğunu unutmayın. Her halükarda, 16 makinelik bir kümeye 16 makine ekleyerek, verilerin yarısını kaydırmak zorundayız - tam olarak yarısını ve vardiyayı.

Tamam, ama insanlık gerçekten başka bir şey icat etmedi mi - soru meraklı bir zihinden geliyor.

Daha eğlenceli #3. Tutarlı karma

Tabii ki, burada tutarlı karma hakkında daire içeren bir resim gereklidir.

Google'da "tutarlı karma" yazarsanız, kesinlikle bir daire çıkacaktır, tüm sonuçlar dairelerle doldurulur.

Fikir: bir daire üzerine shard tanımlayıcıları (hash'ler) çizelim ve en üstte karma sunucu tanımlayıcılarını işaretleyelim. Bir sunucu eklemeniz gerektiğinde, daireye yeni bir nokta koyarız ve ona yakın olduğu ortaya çıkan şeyi (ve yalnızca ona yakın olduğu ortaya çıkan şeyi) yeniden yerleştiririz.

Bir parça eklerken: her şeyi değil, yalnızca 2 "komşuyu" gözden geçiriyoruz, ortalama 1/n kaydırıyoruz.

Bir parçayı silerken: yalnızca silinmekte olan parçaya bakarız, yalnızca onu kaydırırız. Bir nevi optimal.

Bir parça eklerken trafiği en aza indirmek açısından çok etkili ve normal veri dengeleme açısından kesinlikle iğrenç. Çünkü çok sayıda makineye dağıttığımız tüm bu nesneleri özetlediğimizde, bunu nispeten düzensiz bir şekilde yapıyoruz: dairenin etrafındaki noktalar eşit olmayan bir şekilde aralıklıdır ve her bir düğümün yükü diğerlerinden çok farklı olabilir.

Bu problem, sanal düğümün son satırı ile çözülür. Daire üzerindeki her düğüm, her sunucu birden fazla nokta ile gösterilir. Bir sunucu, bir shard vb. ekleyerek birkaç nokta ekliyoruz. Bir şeyi her kaldırdığımızda, buna göre birkaç noktayı kaldırır ve verilerin küçük bir bölümünü kaydırırız.

Bu alandan dairelerle bahsediyorum çünkü örneğin böyle bir şema Cassandra'nın içinde. Yani, düğümler arasında kayıtları kovalamaya başladığında, çemberin size baktığını ve muhtemelen onaylamadığını bilin.

Bununla birlikte, ilk yöntemlerle karşılaştırıldığında, hayat gelişti - bir parça eklerken / çıkarırken, zaten tüm kayıtları değil, yalnızca bir kısmını inceliyoruz ve yalnızca bir kısmını kaydırıyoruz.

Dikkat, soru şu: daha da geliştirilebilir mi? Ayrıca, yükleme parçalarının tekdüzeliğini iyileştirmek mi istiyorsunuz? Bunun mümkün olduğunu söylüyorlar!

Daha fazla eğlence #4. Buluşma/HRW

Bir sonraki basit fikir (materyal eğiticidir, dolayısıyla hiçbir şey karmaşık değildir): shard_id = arg max hash(object_id, shard_id).

Buna neden Rendezvous hashing dendiğini bilmiyorum ama neden En Yüksek Rastgele Ağırlık dendiğini biliyorum. Bunu şu şekilde görselleştirmek çok kolaydır:

Örneğin, 16 parçamız var. Bir yere konulması gereken her nesne (string) için shard numarasından nesneye bağlı olarak 16 hash hesaplıyoruz. En yüksek hash değerine sahip olan kazanır.

Bu sözde HRW-hashing, diğer adıyla Rendezvous hashing'dir. Bir çubuk kadar aptal, bir parçanın sayısını hesaplama şeması, ilk olarak, göz için dairelerden daha kolaydır ve öte yandan, tekdüze bir yük verir.

Tek olumsuz yanı, yeni bir parça eklemenin bizim için daha da kötüleşmesi. Yeni bir parça eklerken, hala değişecek olan bazı hash'lerimizin olması ve her şeyi gözden geçirmemiz gerekmesi riski vardır. Parça çıkarma teknolojisi pek değişmedi.

Başka bir sorun da, çok sayıda parça ile hesaplama açısından ağır olmasıdır.

Daha eğlenceli #5. Daha fazla teknik

İlginç bir şekilde, araştırma durmuyor ve Google her yıl bazı yeni uzay teknolojileri yayınlıyor:

  • Atlama Karması - Google '2014.
  • Çoklu Araştırma—Google '2015.
  • Maglev-Google '2016.

Konuyla ilgileniyorsanız, birçok tez okuyabilirsiniz. Sorunun çözülmediğini, tüm veritabanlarında uygulanabilecek bir süper çözüm olmadığını açıkça belirtmek için bu verileri sunuyorum. Şimdiye kadar insanlar tezleri savundu.

sonuçlar

Adını Gallius Julius Caesar'dan alan parçalama denilen önemli bir temel teknik vardır: "Böl ve yönet, yönet ve böl!" Veriler bir sunucuya sığmazsa, onu 20 sunucuya bölmek gerekir.

Bütün bunları öğrendikten sonra, parçalamamanın daha iyi olacağı izlenimi edinilmelidir. Parçalamamanın daha iyi olacağına karar verirseniz, bu doğru duygudur. Sunucuya 100 $ karşılığında bellek ekleyebilir ve hiçbir şeyi parçalayamazsanız, o zaman yapmalısınız. Parçalama sırasında, verileri ileri geri aktaran, verileri kimsenin bilmediği yerde istifleyen karmaşık bir dağıtılmış sistem görünecektir. Kaçınılması mümkünse, kaçınılması gerekir.

Elle yapmamak daha iyidir, "temel" in (arama, DFS, ...) kendi kendini parçalayabilmesi daha iyidir. Her durumda, er ya da geç, yüksek yük gelecek ve bir şekilde verilerin bölünmesi gerekecek. Taban kendisi yapsa bile herhangi bir sorunla karşılaşmayacağınız bir gerçek değil. Algoritmik köktenciliği hatırlayın - her şeyin içeride nasıl çalıştığını anlamanız gerekir.

Parçalamayı ilk kez kurarken, F()'yi dikkatli bir şekilde seçin, istekleri, ağı vb. düşünün. Ancak hazır olun, muhtemelen 2 kez seçim yapmanız gerekecek ve en azından bir kez her şeyi yeniden yapmanız gerekecek.