การแบ่งส่วน: ด้านหลัง

2.1 จะแตกและช้าลง N ครั้งได้อย่างไร

คุณสามารถแบ่งย่อยและทำให้ช้าลงอย่างแน่นอน N ครั้งดังนี้:

• ส่ง docs00...docs15 คำขอตามลำดับไม่ใช่พร้อมกัน
• ในข้อความค้นหาง่ายๆ ให้เลือกโดยไม่ใช้คีย์ WHERE something=234

ในกรณีนี้ส่วนที่เป็นอนุกรม (อนุกรม) ใช้เวลาไม่ใช่ 1% และไม่ใช่ 5% แต่ประมาณ 20% ในฐานข้อมูลสมัยใหม่ คุณยังสามารถรับ 50% ของส่วนที่ต่อเนื่องกันหากคุณเข้าถึงฐานข้อมูลโดยใช้โปรโตคอลไบนารีที่มีประสิทธิภาพอย่างมาก หรือเชื่อมโยงเป็นไลบรารีไดนามิกเข้ากับสคริปต์ Python

เวลาที่เหลือในการดำเนินการของคำขออย่างง่ายจะถูกครอบครองโดยการดำเนินการที่ไม่สามารถเทียบเคียงได้ในการแยกวิเคราะห์คำขอ การเตรียมแผน ฯลฯ นั่นคือการไม่อ่านบันทึกช้าลง

หากเราแบ่งข้อมูลออกเป็น 16 ตารางและรันตามลำดับตามธรรมเนียมในภาษาโปรแกรม PHP ตัวอย่างเช่น (การเรียกใช้กระบวนการแบบอะซิงโครนัสทำได้ไม่ดีนัก) เราจะทำงานช้าลง 16 เท่า และอาจมากกว่านั้นเพราะจะมีการเพิ่มเครือข่ายไป-กลับด้วย

ทันใดนั้น การเลือกภาษาโปรแกรมก็มีความสำคัญเมื่อทำการชาร์ดดิ้ง

จำเกี่ยวกับการเลือกภาษาการเขียนโปรแกรมเพราะถ้าคุณส่งแบบสอบถามไปยังฐานข้อมูล (หรือเซิร์ฟเวอร์การค้นหา) ตามลำดับ การเร่งความเร็วมาจากไหน แต่จะมีการชะลอตัว

2.2 เกี่ยวกับกึ่งอัตโนมัติ

ในสถานที่ต่างๆ ความซับซ้อนของเทคโนโลยีสารสนเทศทำให้เกิดความสยองขวัญแบบ chthonic ตัวอย่างเช่น MySQL ที่แกะกล่องไม่มีการติดตั้งชาร์ดดิ้งกับเวอร์ชันบางเวอร์ชันอย่างแน่นอน อย่างไรก็ตาม ขนาดของฐานข้อมูลที่ใช้ในการต่อสู้จะขยายไปสู่ค่าที่ไม่เหมาะสม

ความทุกข์ทรมานของมนุษยชาติในการเผชิญหน้ากับ DBA แต่ละคนนั้นถูกทรมานมาหลายปีและได้เขียนวิธีแก้ปัญหาการแบ่งส่วนย่อยที่ไม่ดีหลายอย่างโดยไม่ใช้อะไรเลย หลังจากนั้น จะมีการเขียนโซลูชันการชาร์ดดิ้งที่เหมาะสมมากหรือน้อยที่เรียกว่า ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...) นี่เป็นตัวอย่างที่รู้จักกันดีของรอยเปื้อนนี้

ProxySQL โดยรวมแล้วเป็นโซลูชันระดับองค์กรเต็มรูปแบบสำหรับโอเพ่นซอร์ส สำหรับการกำหนดเส้นทาง และอื่นๆ แต่หนึ่งในงานที่ต้องแก้ไขคือการแบ่งส่วนข้อมูลสำหรับฐานข้อมูล ซึ่งโดยตัวมันเองไม่สามารถแยกชิ้นส่วนด้วยวิธีของมนุษย์ได้ คุณเห็นไหมว่าไม่มีสวิตช์ “shards = 16” คุณต้องเขียนคำขอแต่ละรายการใหม่ในแอปพลิเคชัน และมีจำนวนมากอยู่ในตำแหน่ง หรือวางเลเยอร์กลางระหว่างแอปพลิเคชันและฐานข้อมูลที่มีลักษณะดังนี้: “อืม ... เลือก * จากเอกสาร? ใช่จะต้องแบ่งออกเป็น 16 ขนาดเล็ก SELECT * FROM server1.document1, SELECT * FROM server2.document2 - ไปยังเซิร์ฟเวอร์นี้ด้วยชื่อล็อกอิน / รหัสผ่านไปยังเซิร์ฟเวอร์นี้กับเซิร์ฟเวอร์อื่น ถ้าใครไม่ตอบก็ ... " ฯลฯ สิ่งนี้สามารถทำได้โดยการมีรอยเปื้อนตรงกลาง มีค่าน้อยกว่าฐานข้อมูลทั้งหมดเล็กน้อย สำหรับ PostgreSQL เท่าที่ฉันเข้าใจ

การกำหนดค่าแพตช์เฉพาะแต่ละรายการเป็นหัวข้อใหญ่ที่แยกจากกันซึ่งไม่เหมาะกับรายงานฉบับเดียว ดังนั้นเราจะหารือเฉพาะแนวคิดพื้นฐานเท่านั้น เรามาพูดถึงทฤษฎีของ Buzz กันดีกว่า

2.3 ระบบอัตโนมัติที่สมบูรณ์แบบอย่างแท้จริง?

ทฤษฎีทั้งหมดของการเพิ่มสูงในกรณีของการแบ่งส่วนในตัวอักษรนี้F()หลักการพื้นฐานจะเหมือนกันโดยคร่าวๆ: shard_id = F(object)

Sharding - มันเกี่ยวกับอะไร? เรามีบันทึก 2 พันล้านรายการ (หรือ 64 รายการ) เราต้องการแบ่งมันออกเป็นหลายส่วน คำถามที่ไม่คาดคิดเกิดขึ้น - อย่างไร ฉันควรกระจายข้อมูล 2 พันล้านรายการ (หรือ 64 รายการ) บนเซิร์ฟเวอร์ 16 เครื่องตามหลักการใด

นักคณิตศาสตร์ที่แฝงอยู่ในตัวเราควรแนะนำว่าในท้ายที่สุดแล้วจะมีฟังก์ชันวิเศษบางอย่างเสมอ ซึ่งสำหรับแต่ละเอกสาร (วัตถุ บรรทัด ฯลฯ) จะเป็นตัวกำหนดว่าจะใส่ส่วนใดลงไป

เจาะลึกลงไปในคณิตศาสตร์ ฟังก์ชันนี้ไม่เพียงแต่ขึ้นอยู่กับตัววัตถุเท่านั้น (ตัวแถวเอง) แต่ยังขึ้นอยู่กับการตั้งค่าภายนอก เช่น จำนวนเศษทั้งหมดด้วย ฟังก์ชันที่สำหรับแต่ละอ็อบเจกต์ต้องบอกตำแหน่งที่จะใส่ ไม่สามารถส่งคืนค่ามากกว่าที่มีเซิร์ฟเวอร์ในระบบ และฟังก์ชั่นจะแตกต่างกันเล็กน้อย:

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

แต่ต่อไปเราจะไม่เจาะลึกถึงไวลด์ของฟังก์ชันแต่ละอย่าง เราจะพูดถึงฟังก์ชันเวทมนตร์ F () เท่านั้น

2.4 F() คืออะไร?

พวกเขาสามารถเกิดกลไกการใช้งานที่หลากหลายและแตกต่างกันได้มากมาย สรุปตัวอย่าง:

• F = แรนด์ () % nums_shards
• F = somehash (object.id) % num_shards
• F = object.date % num_shards
• F = object.user_id % num_shards
• ...
• F = shard_table [ somehash() |… object.date |… ]

ข้อเท็จจริงที่น่าสนใจ - คุณสามารถกระจายข้อมูลทั้งหมดแบบสุ่มได้โดยธรรมชาติ - เราโยนบันทึกถัดไปบนเซิร์ฟเวอร์โดยพลการบนแกนโดยพลการในตารางโดยพลการ จะไม่มีความสุขมากในเรื่องนี้ แต่จะได้ผล

มีวิธีการที่ชาญฉลาดกว่าเล็กน้อยในการแยกย่อยด้วยฟังก์ชันแฮชที่ทำซ้ำได้หรือสม่ำเสมอ หรือแยกย่อยด้วยแอตทริบิวต์บางอย่าง มาดูแต่ละวิธีกัน

F = แรนด์ ()

กระจายไปทั่วไม่ใช่วิธีการที่ถูกต้อง ปัญหาหนึ่ง: เรากระจายบันทึก 2 พันล้านรายการของเราบนเซิร์ฟเวอร์หนึ่งพันเซิร์ฟเวอร์แบบสุ่ม และเราไม่รู้ว่าบันทึกนั้นอยู่ที่ไหน เราต้องดึง user_1 ออกมา แต่เราไม่รู้ว่ามันอยู่ที่ไหน เราไปที่เซิร์ฟเวอร์นับพันและจัดเรียงทุกอย่าง - วิธีนี้ไม่มีประสิทธิภาพ

F = โซแฮช ()

กระจายผู้ใช้ด้วยวิธีสำหรับผู้ใหญ่: คำนวณฟังก์ชันแฮชที่ทำซ้ำได้จาก user_id นำส่วนที่เหลือหารด้วยจำนวนเซิร์ฟเวอร์ และติดต่อเซิร์ฟเวอร์ที่ต้องการทันที

เราจะทำเช่นนี้ทำไม? จากนั้นเรามีโหลดสูงและไม่มีอะไรที่เหมาะกับเซิร์ฟเวอร์เดียว ถ้าลงตัวชีวิตจะเรียบง่ายมาก

เยี่ยมมาก สถานการณ์ดีขึ้นแล้ว เพื่อที่จะได้รับหนึ่งบันทึก เราไปที่เซิร์ฟเวอร์ที่รู้จักหนึ่งเซิร์ฟเวอร์ล่วงหน้า แต่ถ้าเรามีช่วงของคีย์ ในช่วงทั้งหมดนี้ เราจำเป็นต้องผ่านค่าทั้งหมดของคีย์ และในขีดจำกัด ให้ไปที่เศษชิ้นส่วนมากที่สุดเท่าที่เรามีคีย์ในช่วงนั้น หรือแม้กระทั่ง แต่ละเซิร์ฟเวอร์ แน่นอนว่าสถานการณ์ดีขึ้น แต่ไม่ใช่สำหรับทุกคำขอ ข้อความค้นหาบางส่วนได้รับผลกระทบ

การแบ่งส่วนตามธรรมชาติ (F = object.date % num_shards)

บางครั้ง บ่อยครั้ง 95% ของทราฟฟิกและ 95% ของโหลดเป็นคำขอที่มีการชาร์ดดิ้งตามธรรมชาติ ตัวอย่างเช่น 95% ของข้อความค้นหาการวิเคราะห์ทางสังคมแบบมีเงื่อนไขจะส่งผลต่อข้อมูลในช่วง 1 วัน 3 วัน 7 วันที่ผ่านมาเท่านั้น และอีก 5% ที่เหลืออ้างอิงถึงช่วงสองสามปีที่ผ่านมา แต่ 95% ของคำขอจึงแบ่งตามวันที่โดยธรรมชาติ ความสนใจของผู้ใช้ระบบจึงมุ่งเน้นไปที่ช่วงสองสามวันที่ผ่านมา

ในกรณีนี้ คุณสามารถแบ่งข้อมูลตามวันที่ เช่น ตามหนึ่งวัน และติดตามการตอบกลับคำขอรายงานสำหรับบางวันหรือวัตถุจากวันนี้ไปยังชาร์ดนี้และไป

ชีวิตกำลังดีขึ้น - ตอนนี้เราไม่เพียงรู้ตำแหน่งของวัตถุใดวัตถุหนึ่งเท่านั้น แต่เรายังรู้เกี่ยวกับระยะอีกด้วย หากเราไม่ได้ถามถึงช่วงวันที่ แต่เป็นช่วงของคอลัมน์อื่นๆ แน่นอน เราจะต้องผ่านเศษชิ้นส่วนทั้งหมด แต่ตามกฎของเกม เรามีเพียง 5% ของคำขอดังกล่าว

ดูเหมือนว่าเราได้หาทางออกที่ดีสำหรับทุกสิ่ง แต่มีปัญหาสองประการ:

• โซลูชันนี้ได้รับการปรับให้เหมาะกับกรณีเฉพาะ เมื่อ 95% ของคำขอเกี่ยวข้องกับสัปดาห์ที่แล้วเท่านั้น
• เนื่องจาก 95% ของคำขอเข้าถึงในสัปดาห์ที่แล้ว คำขอทั้งหมดจะตกอยู่กับเศษส่วนเดียวที่ให้บริการในสัปดาห์ที่แล้ว ชิ้นส่วนนี้จะละลาย ในขณะที่ชิ้นส่วนอื่นๆ จะไม่ได้ใช้งานในช่วงเวลานี้ ในเวลาเดียวกัน คุณไม่สามารถโยนทิ้งได้ ต้องเก็บข้อมูลที่เก็บถาวรด้วย

ไม่ต้องบอกว่านี่เป็นแผนการแยกย่อยที่ไม่ดี - เราตัดข้อมูลร้อนออก อย่างไรก็ตาม จำเป็นต้องดำเนินการบางอย่างกับชาร์ดที่ร้อนที่สุด

ปัญหาได้รับการแก้ไขโดยการแสดงตลกการกระโดดและการพอกนั่นคือการเพิ่มจำนวนของแบบจำลองสำหรับวันปัจจุบันที่กำลังลุกไหม้ จากนั้นจำนวนแบบจำลองจะค่อยๆ ลดลงเมื่อวันนี้กลายเป็นอดีตและเข้าสู่ที่เก็บถาวร ไม่มีวิธีแก้ปัญหาในอุดมคติที่เรียกว่า “คุณแค่ต้องกระจายข้อมูลไปทั่วคลัสเตอร์ด้วยฟังก์ชันแฮชวิเศษในทางที่ผิด”

2.5 ราคาที่ต้องจ่าย

เรารู้อย่างเป็นทางการแล้ว ตอนนี้เรารู้ "ทุกอย่าง" แล้ว จริงอยู่ เราไม่รู้ว่าอาการปวดศีรษะขนาดใหญ่หนึ่งอันและอาการปวดศีรษะขนาดเล็กกว่าสองอัน

1. ความเจ็บปวดธรรมดา: มีรอยเปื้อนไม่ดี

นี่คือตัวอย่างจากตำราเรียนซึ่งแทบจะไม่เคยเกิดขึ้นในสนามรบ แต่ทันใดนั้น

• ตัวอย่างเช่นมีวันที่โดยไม่มีวันที่เท่านั้น!
• การกระจายที่ไม่สม่ำเสมอ (รับรู้ได้) โดยไม่ได้ตั้งใจ

พวกเขาเลือกกลไกการแบ่งส่วนข้อมูล และ/หรือข้อมูลที่เปลี่ยนแปลง และแน่นอนว่า PM ไม่ได้แจ้งข้อกำหนด (เราไม่มีข้อผิดพลาดในโค้ด PM มักจะไม่รายงานข้อกำหนด) และการกระจาย กลายเป็นความไม่สม่ำเสมออย่างมหึมา นั่นคือพวกเขาพลาดเกณฑ์

ในการจับคุณต้องดูขนาดของเศษ เราจะเห็นปัญหาอย่างแน่นอนในขณะที่เศษชิ้นหนึ่งของเราร้อนเกินไปหรือใหญ่กว่าชิ้นอื่น 100 เท่า คุณสามารถแก้ไขได้โดยการเปลี่ยนคีย์หรือฟังก์ชันการแบ่งส่วน

นี่เป็นปัญหาง่ายๆ พูดตามตรง ฉันไม่คิดว่าอย่างน้อยหนึ่งคนจากร้อยคนจะเจอปัญหานี้ในชีวิต แต่ทันใดนั้นมันก็ช่วยใครซักคนได้

2. ความเจ็บปวด "อยู่ยงคงกระพัน": การรวมตัว, การเข้าร่วม

วิธีการเลือกที่รวมข้อมูลนับพันล้านบันทึกจากตารางหนึ่งสำหรับบันทึกพันล้านรายการจากอีกตารางหนึ่ง

• วิธีการคำนวณ "อย่างรวดเร็ว" ... randcol ระหว่าง aaa และ bbb อยู่ที่ไหน
• วิธี "อย่างชาญฉลาด" ทำ... users_32shards JOIN posts_1024 shards?

คำตอบสั้น ๆ : ไม่มีทาง ทน!

หากคุณแจกจ่ายข้อมูลนับพันล้านรายการไปยังเซิร์ฟเวอร์หนึ่งพันเครื่องในตารางแรกเพื่อให้ทำงานได้เร็วขึ้น และทำเช่นเดียวกันในตารางที่สอง เซิร์ฟเวอร์หนึ่งพันถึงหนึ่งพันเซิร์ฟเวอร์ควรพูดคุยกันเป็นคู่ การเชื่อมต่อนับล้านจะใช้งานได้ไม่ดี หากเราส่งคำขอไปยังฐานข้อมูล (การค้นหา พื้นที่จัดเก็บ ที่เก็บเอกสาร หรือระบบไฟล์แบบกระจาย) ที่ไม่เหมาะสมกับการแบ่งส่วนย่อย คำขอเหล่านี้จะช้าลงอย่างมาก

ประเด็นสำคัญคือ คำขอบาง รายการมักจะถูกละเลงไม่สำเร็จและจะช้าลง สิ่งสำคัญคือต้องพยายามลดเปอร์เซ็นต์ให้น้อยที่สุด ด้วยเหตุนี้ จึงไม่มีความจำเป็นต้องรวมข้อมูลขนาดมหึมากับบันทึกนับพันล้านคูณพันล้าน หากเป็นไปได้ที่จะจำลองตารางขนาดเล็กซึ่งสัมพันธ์กับตารางแชร์ขนาดยักษ์ไปยังโหนดทั้งหมด คุณควรทำ หากการรวมเป็นแบบโลคอลจริง ๆ ในทางใดทางหนึ่ง เป็นไปได้ที่จะวางผู้ใช้และโพสต์ของเขาเคียงข้างกัน แบ่งพวกมันในลักษณะเดียวกัน และทำการรวมทั้งหมดภายในเครื่องเดียวกัน - คุณต้องทำอย่างนั้น .

นี่คือหลักสูตรการบรรยายแยกต่างหากเป็นเวลาสามวัน ดังนั้นเรามาต่อกันที่ความเจ็บปวดอันเลวร้ายครั้งสุดท้ายและอัลกอริทึมต่างๆ ในการจัดการกับมัน

2.6. ความเจ็บปวดที่ซับซ้อน / ยาวนาน: การทำซ้ำ

เตรียมตัวให้พร้อม: หากคุณชาร์ดข้อมูลของคุณเป็นครั้งแรกในชีวิต โดยเฉลี่ยแล้วคุณจะชาร์ดข้อมูลเพิ่มอีกห้าครั้ง

ไม่ว่าคุณจะกำหนดค่าคลัสเตอร์กี่คลัสเตอร์ คุณก็ยังต้องปรับเปลี่ยนใหม่

หากคุณฉลาดและโชคดีมาก ให้หักโหมอย่างน้อยหนึ่งครั้ง แต่เมื่อคุณแน่ใจแล้ว เพราะในขณะที่คุณคิดว่า 10 หน่วยก็เพียงพอสำหรับผู้ใช้แล้ว มีคนเขียนคำขอ 30 หน่วยในขณะนั้น และวางแผนที่จะขอทรัพยากรที่ไม่รู้จัก 100 หน่วย เศษไม่เคยเพียงพอ ไม่ว่าในกรณีใด คุณจะพลาดการใช้ Sharding Scheme แรก - คุณจะต้องเพิ่มจำนวนเซิร์ฟเวอร์เพื่อเพิ่มหรือทำอย่างอื่นเสมอ - โดยทั่วไปแล้ว ยังไงก็ตาม ด้วยวิธีใดก็ตาม การจัดแพ็คเกจข้อมูลใหม่

เป็นเรื่องดีถ้าเรามีกำลังที่ดีของสอง: มี 16 ชาร์ดของเซิร์ฟเวอร์ ตอนนี้เป็น 32 จะสนุกกว่าถ้าเป็น 17 เป็น 23 ซึ่งเป็นจำนวนเฉพาะแบบวาซิมัลสองตัว ฐานข้อมูลทำอย่างไร อาจมีเวทมนตร์บางอย่างอยู่ข้างใน?

คำตอบที่ถูกต้องคือ ไม่ ไม่มีเวทมนตร์อยู่ข้างใน พวกมันมีนรกอยู่ในตัว

ต่อไปเราจะพิจารณาสิ่งที่สามารถทำได้ "ด้วยมือ" บางทีเราจะเข้าใจว่า "เป็นเครื่องอัตโนมัติ"

บนหน้าผาก #1. ย้ายทุกอย่าง

สำหรับวัตถุทั้งหมด เราถือว่า NewF (วัตถุ) เปลี่ยนเป็นชิ้นส่วนใหม่

โอกาสในการจับคู่ NewF()=OldF() มีน้อย

มาครอบคลุมเกือบทุกอย่าง

โอ้.

ฉันหวังว่าจะไม่มีการถ่ายโอนบันทึกทั้งหมด 2 พันล้านบันทึกจากเศษเก่าไปยังใหม่ วิธีการไร้เดียงสาเป็นที่เข้าใจได้: มี 17 เครื่อง, 6 เครื่องถูกเพิ่มในคลัสเตอร์, 2 พันล้านบันทึกถูกแยกออก, พวกเขาเปลี่ยนจาก 17 เครื่องเป็น 23 เครื่อง ทุกๆ 10 ปี คุณสามารถทำได้ด้วยซ้ำ แต่โดยรวมแล้วมันเป็นการย้ายที่ไม่ดี

บนหน้าผาก #2. ย้ายครึ่ง

การปรับปรุงที่ไร้เดียงสาครั้งต่อไป - เลิกใช้แผนงี่เง่าแบบนี้กันเถอะ - จะห้ามรถ 17 คันไม่ให้เปลี่ยนรหัสเป็น 23 คัน และเราจะเปลี่ยนรหัสรถ 16 คันเป็น 32 คันเสมอ! จากนั้นตามทฤษฎีแล้ว เราจะต้องเปลี่ยนข้อมูลเพียงครึ่งหนึ่งเท่านั้น และในทางปฏิบัติเราก็สามารถทำได้เช่นกัน

สำหรับวัตถุทั้งหมด เราถือว่า NewF (วัตถุ) เปลี่ยนเป็นชิ้นส่วนใหม่

มันคือ 2^N อย่างเคร่งครัด ตอนนี้มันเป็นเศษชิ้นส่วน 2^(N+1) อย่างเคร่งครัด

ความน่าจะเป็นของการจับคู่ NewF()=OldF() คือ 0.5

มาถ่ายโอนข้อมูลประมาณ 50% กันเถอะ

เหมาะสมที่สุด แต่ใช้ได้กับยกกำลังสองเท่านั้น

โดยหลักการแล้วทุกอย่างเรียบร้อยดียกเว้นการผูกมัดกับพลังของสองในแง่ของจำนวนรถยนต์ วิธีการที่ไร้เดียงสานี้ แปลกพอใช้ได้ผล

โปรดทราบว่าการแบ่งคลัสเตอร์เพิ่มเติมด้วยยกกำลังสองในกรณีนี้ก็เหมาะสมที่สุดเช่นกัน ไม่ว่าในกรณีใด การเพิ่มเครื่อง 16 เครื่องในคลัสเตอร์ 16 เครื่อง เราจำเป็นต้องย้ายข้อมูลครึ่งหนึ่ง - ครึ่งหนึ่งและเปลี่ยน

โอเค แต่มนุษย์ไม่ได้คิดค้นสิ่งอื่นจริง ๆ หรือไม่ - คำถามนี้เกิดจากจิตใจที่อยากรู้อยากเห็น

สนุกมากขึ้น #3. การแฮชที่สม่ำเสมอ

แน่นอนว่าต้องมีรูปภาพที่มีวงกลมเกี่ยวกับการแฮชที่สอดคล้องกันที่นี่

หากคุณ google "constant hashing" วงกลมจะออกมาอย่างแน่นอน ผลลัพธ์ทั้งหมดจะเต็มไปด้วยแวดวง

แนวคิด: วาดตัวระบุชาร์ด (แฮช) บนวงกลม และทำเครื่องหมายตัวระบุเซิร์ฟเวอร์ที่แฮชไว้ด้านบน เมื่อคุณต้องการเพิ่มเซิร์ฟเวอร์ เราใส่จุดใหม่บนวงกลม และสิ่งที่กลายเป็นสิ่งที่อยู่ใกล้กับมัน (และเฉพาะสิ่งที่กลายเป็นสิ่งที่อยู่ใกล้กับมัน) เราจะย้าย

เมื่อเพิ่มเศษ: เราไม่ได้มองทุกอย่าง แต่มี "เพื่อนบ้าน" เพียง 2 คนเท่านั้นที่เราเปลี่ยนโดยเฉลี่ย 1/n

เมื่อลบชาร์ด: เราดูเฉพาะชาร์ดที่ถูกลบ เราจะเปลี่ยนเฉพาะชาร์ดเท่านั้น ชนิดที่ดีที่สุด

มีประสิทธิภาพมากในแง่ของการลดปริมาณการรับส่งข้อมูลเมื่อเพิ่มเศษส่วน และน่ารังเกียจอย่างยิ่งในแง่ของความสมดุลของข้อมูลปกติ เนื่องจากเมื่อเราแฮชออบเจกต์ทั้งหมดที่เราแจกจ่ายไปยังเครื่องจำนวนมาก เราทำค่อนข้างไม่สม่ำเสมอ: จุดรอบวงกลมมีระยะห่างไม่เท่ากัน และโหลดของแต่ละโหนดอาจแตกต่างจากที่เหลืออย่างมาก

ปัญหานี้แก้ไขได้โดยบรรทัดสุดท้ายของโหนดเสมือน แต่ละโหนด แต่ละเซิร์ฟเวอร์ในวงกลมจะถูกระบุด้วยจุดมากกว่าหนึ่งจุด ด้วยการเพิ่มเซิร์ฟเวอร์ ชาร์ด และอื่นๆ เรากำลังเพิ่มจุดเล็กๆ น้อยๆ แต่ละครั้งที่เราลบบางอย่าง เราจะลบจุดสองสามจุดตามนั้นและเปลี่ยนส่วนเล็กๆ ของข้อมูล

ฉันกำลังพูดถึงพื้นที่นี้ด้วยวงกลมเพราะ ตัวอย่างเช่น โครงร่างดังกล่าวอยู่ในคาสแซนดรา นั่นคือเมื่อเธอเริ่มไล่ตามบันทึกระหว่างโหนด ให้รู้ว่าวงกลมนั้นกำลังมองมาที่คุณและอาจไม่เห็นด้วย

อย่างไรก็ตาม เมื่อเทียบกับวิธีแรก ชีวิตดีขึ้น - เมื่อเพิ่ม / ลบเศษ เราได้ตรวจสอบบันทึกทั้งหมดแล้ว แต่เพียงบางส่วน และเปลี่ยนเพียงบางส่วนเท่านั้น

ความสนใจ คำถามคือ: สามารถปรับปรุงต่อไปได้หรือไม่? และยังปรับปรุงความสม่ำเสมอของการโหลดชิ้นส่วนอีกด้วย? พวกเขาบอกว่าเป็นไปได้!

สนุกมากขึ้น #4. นัดพบ/ชม

แนวคิดง่ายๆ ถัดไป (เนื้อหานี้เป็นการศึกษา ดังนั้นจึงไม่มีอะไรซับซ้อน): shard_id = arg max hash(object_id, shard_id)

ทำไมจึงเรียกว่า Rendezvous hashing ฉันไม่รู้ แต่ฉันรู้ว่าทำไมจึงเรียกว่าน้ำหนักสุ่มสูงสุด มันง่ายมากที่จะเห็นภาพดังนี้:

ตัวอย่างเช่น เรามีเศษชิ้นส่วน 16 ชิ้น สำหรับแต่ละออบเจ็กต์ (สตริง) ที่ต้องใส่ในที่ใดที่หนึ่ง เราคำนวณ 16 แฮชขึ้นอยู่กับออบเจ็กต์จากหมายเลขชาร์ด ใครก็ตามที่มีค่าแฮชสูงสุดจะเป็นผู้ชนะ

นี่คือสิ่งที่เรียกว่า HRW-hashing หรือที่เรียกว่า Rendezvous hashing แผนการคำนวณจำนวนเศษเล็กเศษน้อยเป็นใบ้อย่างแรกนั้นง่ายกว่าวงกลมและให้การโหลดที่สม่ำเสมอในทางกลับกัน

ข้อเสียเพียงอย่างเดียวคือการเพิ่มชิ้นส่วนใหม่ทำให้เราแย่ลง มีความเสี่ยงที่เมื่อเพิ่มชาร์ดใหม่ เรายังมีแฮชบางอย่างที่จะเปลี่ยนแปลง และอาจจำเป็นต้องตรวจสอบทุกอย่าง เทคโนโลยีการกำจัดชิ้นส่วนไม่ได้เปลี่ยนแปลงมากนัก

ปัญหาอีกประการหนึ่งคือการคำนวณที่หนักและมีเศษจำนวนมาก

สนุกมากขึ้น #5. เทคนิคเพิ่มเติม

ที่น่าสนใจคือ การวิจัยไม่หยุดนิ่ง และ Google เผยแพร่เทคโนโลยีอวกาศใหม่ๆ ทุกปี:

• กระโดดแฮช - Google '2014
• Multi Probe—Google '2015
• Maglev-Google '2016.

หากคุณสนใจในเรื่องนี้ คุณสามารถอ่านวิทยานิพนธ์มากมาย ฉันนำเสนอข้อมูลนี้เพื่อให้ชัดเจนว่าปัญหายังไม่ได้รับการแก้ไข ไม่มีโซลูชันขั้นสูงที่สามารถนำไปใช้กับฐานข้อมูลทั้งหมดได้ จนถึงขณะนี้ผู้คนปกป้องวิทยานิพนธ์

ข้อสรุป

มีเทคนิคพื้นฐานที่สำคัญที่เรียกว่า sharding ซึ่งตั้งชื่อตาม Gallius Julius Caesar: "แบ่งแยกและปกครอง ปกครองและแบ่งแยก!" หากข้อมูลไม่พอดีกับเซิร์ฟเวอร์เดียว จำเป็นต้องแยกออกเป็น 20 เซิร์ฟเวอร์

เมื่อเรียนรู้ทั้งหมดนี้แล้ว เราควรได้รับความประทับใจว่าจะดีกว่าที่จะไม่แตกเป็นชิ้นเล็กชิ้นน้อย หากคุณตัดสินใจว่าจะเป็นการดีกว่าที่จะไม่แตก นี่คือความรู้สึกที่ถูกต้อง หากคุณสามารถเพิ่มหน่วยความจำให้กับเซิร์ฟเวอร์ได้ในราคา $100 และไม่แบ่งชิ้นส่วนใด ๆ คุณก็ควรทำ เมื่อทำการ Sharding ระบบกระจายที่ซับซ้อนจะปรากฏขึ้นพร้อมการถ่ายโอนข้อมูลไปมา ซ้อนข้อมูลไว้ในที่ใดโดยไม่มีใครรู้ ถ้าเลี่ยงได้ก็ต้องเลี่ยง

เป็นการดีกว่าที่จะไม่ทำด้วยมือ จะเป็นการดีกว่าที่ "ฐาน" (การค้นหา, DFS, ...) สามารถแยกส่วนเองได้ ไม่ว่าในกรณีใด ไม่ช้าก็เร็ว ไฮโหลดจะมา และข้อมูลก็จะต้องถูกแยกออกไป ไม่ใช่ความจริงที่ว่าแม้ว่าฐานจะทำได้เอง แต่คุณจะไม่ประสบปัญหาใด ๆ จำเกี่ยวกับอัลกอริทึมฟันดาเมนทัลลิสม์ - คุณต้องเข้าใจว่าทุกอย่างทำงานอย่างไร

เมื่อตั้งค่าการแบ่งกลุ่มเป็นครั้งแรก ให้เลือก F() อย่างรอบคอบ คิดถึงคำขอ เครือข่าย ฯลฯ แต่เตรียมตัวให้พร้อม คุณอาจต้องเลือก 2 ครั้ง และอย่างน้อยหนึ่งครั้งคุณจะต้องทำทุกอย่างใหม่