การแบ่งส่วน

1.1 ชาร์ดดิ้งคืออะไร?

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

ฉันไม่พบมาตรฐานคำศัพท์เดียวที่จะได้รับการอนุมัติจากบรรพบุรุษผู้ก่อตั้งและได้รับการรับรองโดย ISO ความเชื่อมั่นภายในส่วนบุคคลเป็นเช่นนี้: การแบ่งพาร์ติชันโดยเฉลี่ยคือการ "ตัดฐานออกเป็นชิ้น ๆ " ด้วยวิธีที่ไม่ได้ตั้งใจ

• การแบ่งพาร์ติชันในแนวตั้ง - ตามคอลัมน์ ตัวอย่างเช่น มีตารางขนาดยักษ์ที่มีข้อมูลสองพันล้านรายการใน 60 คอลัมน์ แทนที่จะเก็บตารางขนาดยักษ์ไว้เพียงตารางเดียว เราเก็บตารางขนาดยักษ์อย่างน้อย 60 ตาราง แต่ละรายการมีข้อมูล 2 พันล้านรายการ และนี่ไม่ใช่ฐานคอลัมน์ แต่เป็นการแบ่งพาร์ติชันตามแนวตั้ง (เป็นตัวอย่างของคำศัพท์เฉพาะ)
• การแบ่งพาร์ติชันในแนวนอน - เราตัดทีละบรรทัดอาจอยู่ในเซิร์ฟเวอร์

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

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

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

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

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

1.2 การแบ่งส่วนที่แบ่งแยกไม่ได้

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

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

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

ส่งผลให้ต่อไปนี้:

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

ทำไมต้องแบนด์วิธ? บางครั้งเราอาจมีปริมาณข้อมูลที่ไม่พอดี - ไม่ชัดเจนว่าอยู่ที่ไหน แต่ไม่พอดี - ใน 1 {เคอร์เนล | ดิสก์ | เซิร์ฟเวอร์ | ...}. มีทรัพยากรไม่เพียงพอ นั่นคือทั้งหมด เพื่อที่จะทำงานกับชุดข้อมูลขนาดใหญ่นี้ คุณต้องตัดมันออก

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

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

1.3 ตัวอย่างง่ายๆ "วิธีการทำด้วยมือ"

การแบ่งกลุ่มตามเงื่อนไขสามารถตัดออกได้โดยใช้ตารางทดสอบ test.documents สำหรับเอกสาร 32 ฉบับ และสร้างตารางทดสอบ 16 ตารางจากตารางนี้ แต่ละเอกสารประมาณ 2 เอกสาร test.docs00, 01, 02, ..., 15

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

ทำไม? เนื่องจากเบื้องต้นเราไม่ทราบว่ามีการแจกจ่าย id อย่างไรหากรวมตั้งแต่ 1 ถึง 32 ก็จะมีเอกสาร 2 ฉบับพอดีมิฉะนั้นจะไม่ใช่

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

น่าเสียดายที่ทั้งหมดนี้ไม่ฟรี ฉันสงสัยว่าในกรณีของมาตรฐาน SQL แบบบัญญัติ (ฉันไม่ได้อ่านมาตรฐาน SQL ซ้ำเป็นเวลานาน บางทีมันอาจจะไม่ได้รับการอัปเดตเป็นเวลานาน) ไม่มีไวยากรณ์ที่เป็นมาตรฐานอย่างเป็นทางการสำหรับการพูดกับเซิร์ฟเวอร์ SQL ใด ๆ : "เซิร์ฟเวอร์ SQL ที่รัก สร้าง 32 ชาร์ดให้ฉันและแบ่งเป็น 4 ดิสก์ แต่ในการใช้งานแต่ละครั้ง มักจะมีไวยากรณ์เฉพาะสำหรับการทำสิ่งเดียวกันโดยพื้นฐาน PostgreSQL มีกลไกสำหรับการแบ่งพาร์ติชัน MySQL มี MariaDB Oracle อาจทำทั้งหมดนี้มานานแล้ว

อย่างไรก็ตาม หากเราทำด้วยมือโดยไม่มีการสนับสนุนฐานข้อมูลและอยู่ในกรอบของมาตรฐาน เราจะจ่ายเงินแบบมีเงื่อนไขด้วยความซับซ้อนของการเข้าถึงข้อมูล . เมื่อมี SELECT * FROM เอกสาร WHERE id=123 ตอนนี้ 16 x SELECT * FROM docsXX และเป็นการดีถ้าเราพยายามรับการบันทึกด้วยคีย์ น่าสนใจกว่ามากหากเราพยายามบันทึกช่วงแรกๆ ตอนนี้ (หากเราเน้นว่าเป็นคนโง่และยังคงอยู่ในกรอบของมาตรฐาน) ผลลัพธ์ของ 16 SELECT * FROM เหล่านี้จะต้องรวมกันในแอปพลิเคชัน

การเปลี่ยนแปลงด้านประสิทธิภาพใดที่คุณคาดหวังได้

• โดยสัญชาตญาณ - เชิงเส้น
• ในทางทฤษฎี - sublinear เพราะกฎหมายของอัมดาห์ล
• ในทางปฏิบัติ อาจจะเกือบจะเป็นเส้นตรง อาจจะไม่ใช่ก็ได้

ในความเป็นจริงคำตอบที่ถูกต้องไม่เป็นที่รู้จัก ด้วยการประยุกต์ใช้เทคนิคการแบ่งย่อยอย่างชาญฉลาด คุณสามารถบรรลุการลดระดับเชิงเส้นในประสิทธิภาพของแอปพลิเคชันของคุณ และแม้แต่ DBA ก็ยังมาพร้อมกับโป๊กเกอร์ที่ร้อนแรง

มาดูกันว่าสิ่งนี้จะสำเร็จได้อย่างไร เป็นที่ชัดเจนว่าแค่ตั้งค่าเป็น PostgreSQL shards=16 แล้วมันก็ดับเอง มันไม่น่าสนใจ ลองคิดดูว่าเราจะทำให้แน่ใจว่าเราชะลอการแตกย่อยลง 16 เท่าคูณ 32 ได้อย่างไร สิ่งนี้น่าสนใจจากมุมมองของวิธีที่จะไม่ทำเช่นนี้

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

1.4 กฎหมายอัมดาห์ล

มีส่วนที่ต่อเนื่องกันเสมอ

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

มีส่วนที่สอดคล้องกันอยู่เสมอ อาจมีขนาดเล็กมองไม่เห็นอย่างสมบูรณ์เมื่อเทียบกับพื้นหลังทั่วไปอาจมีขนาดมหึมาและส่งผลต่อการขนานกันอย่างมาก แต่ก็มีอยู่เสมอ

นอกจากนี้ อิทธิพลของมันยังเปลี่ยนแปลงและสามารถเติบโตได้อย่างมาก เช่น ถ้าเราตัดโต๊ะ - มาเพิ่มเงินเดิมพันกันเถอะ - จาก 64 ระเบียนเป็น 16 ตารางจาก 4 ระเบียน ส่วนนี้จะเปลี่ยนไป แน่นอนว่าเมื่อพิจารณาจากข้อมูลจำนวนมหาศาล เรากำลังทำงานบนโทรศัพท์มือถือและโปรเซสเซอร์ 2 MHz 86 และเรามีไฟล์ไม่เพียงพอที่สามารถเปิดพร้อมกันได้ เห็นได้ชัดว่าเราเปิดไฟล์ทีละไฟล์ด้วยอินพุตดังกล่าว

• มันคือ Total = Serial + Parallel โดยที่ ตัวอย่างเช่น ขนานคืองานทั้งหมดภายในฐานข้อมูล และอนุกรมกำลังส่งผลลัพธ์ไปยังไคลเอนต์
• กลายเป็นTotal2 = Serial + Parallel/N + Xserial ตัวอย่างเช่น เมื่อ ORDER BY โดยรวม Xserial>0

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

• ค้นหา 16 ตารางเหล่านี้ในพจนานุกรมภายในของฐานข้อมูล
• เปิดไฟล์;
• จัดสรรหน่วยความจำ
• ยกเลิกการจัดสรรหน่วยความจำ
• รวมผล;
• ซิงโครไนซ์ระหว่างคอร์

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

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

สมมติว่าเรามีบางส่วนของการประมวลผลคำขอที่ใช้เวลาเพียง 5%: serial = 0.05 = 1 / 20

ตามสัญชาตญาณ ดูเหมือนว่าด้วยส่วนที่ต่อเนื่องกันซึ่งใช้เวลาเพียง 1/20 ของการประมวลผลคำขอ หากเราประมวลผลคำขอแบบขนานสำหรับ 20 คอร์ มันจะกลายเป็นประมาณ 20 คอร์ ในกรณีที่เลวร้ายที่สุด 18 เร็วกว่าเท่าตัว

อันที่จริงคณิตศาสตร์เป็นสิ่งที่ไร้หัวใจ :

ผนัง = 0.05 + 0.95/num_cores, เร่งความเร็ว = 1 / (0.05 + 0.95/num_cores)

ปรากฎว่าหากคุณคำนวณอย่างรอบคอบด้วยส่วนที่ต่อเนื่องกัน 5% การเร่งความเร็วจะเป็น 10 เท่า (10.3) ซึ่งเท่ากับ 51% เมื่อเทียบกับอุดมคติทางทฤษฎี

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

เมื่อเหลืองานต่อเนื่องเพียง 1% และ 99% ถูกต่อขนานกัน ค่าเร่งความเร็วจะดีขึ้นเล็กน้อย:

สำหรับการสืบค้นทางเทอร์โมนิวเคลียร์อย่างสมบูรณ์แบบ ซึ่งโดยปกติจะใช้เวลาหลายชั่วโมงจึงจะเสร็จสมบูรณ์ และงานเตรียมการและการประกอบผลลัพธ์ใช้เวลาน้อยมาก (อนุกรม = 0.001) เราจะเห็นประสิทธิภาพที่ดีอยู่แล้ว:

โปรดทราบว่าเราจะไม่เห็น 100% . ในกรณีที่ดีเป็นพิเศษ คุณสามารถดูได้ เช่น 99.999% แต่ไม่ใช่ 100%