โครงสร้างข้อมูลสำหรับแอปพลิเคชันที่ใช้ข้อมูลอย่างเข้มข้น [PDF]

 (cs-people.bu.edu)
4 คะแนน โดย GN⁺ 2024-02-10 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โครงสร้างข้อมูลแบบคีย์-ค่า เป็นองค์ประกอบหลักของระบบที่ขับเคลื่อนด้วยข้อมูล และประสิทธิภาพอาจแตกต่างกันมากตามลักษณะเวิร์กโหลดและเงื่อนไขของฮาร์ดแวร์
  • โครงสร้างทางกายภาพแบ่งได้เป็นการจัดวางข้อมูล เมทาดาทาสำหรับการค้นหา และอัลกอริทึมสำหรับการจัดเก็บและค้นคืน ซึ่งยังเรียกได้ว่า access methods, data containers, หรือ search structures
  • เวิร์กโหลดสามารถอธิบายเป็นการผสมกันของ point query, range query, การแทรก, การลบ, และการแก้ไข และความจุและต้นทุนของหน่วยความจำกับสตอเรจถาวรก็เป็นข้อกำหนดในการออกแบบเช่นกัน
  • B+-tree เด่นด้านการอ่านและ range query แต่เมื่อการแทรกและแก้ไขเพิ่มขึ้น ภาระจากการจัดโครงสร้างใหม่ของโหนดใบจะสูงขึ้น ส่วน LSM-tree ใช้การบัฟเฟอร์และการผสานเพื่อรองรับการแทรกจำนวนมาก
  • ในสภาพแวดล้อมที่การย้ายข้อมูลเป็นคอขวด จำเป็นต้องเลือกโครงสร้างเดิมหรือออกแบบโครงสร้างใหม่ให้เหมาะกับแอปพลิเคชันใหม่ การเปลี่ยนแปลงของฮาร์ดแวร์ และการเพิ่มขึ้นของข้อมูล

ปัญหาที่โครงสร้างข้อมูลแบบคีย์-ค่าแก้ไข

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

องค์ประกอบทางกายภาพและขอบเขตการใช้งาน

  • ในเชิงกายภาพ โครงสร้างข้อมูลแบบคีย์-ค่าประกอบด้วย 3 ส่วน
    • ข้อมูลที่จัดเก็บตามเลย์เอาต์เฉพาะ
    • เมทาดาทาแบบเลือกใช้เพื่อช่วยในการค้นหาข้อมูล
    • อัลกอริทึมที่รองรับการจัดเก็บและการค้นคืน
  • โครงสร้างข้อมูลถูกใช้งานในหลายรูปแบบทั้งในระบบข้อมูล ระบบปฏิบัติการ ระบบไฟล์ คอมไพเลอร์ และระบบเครือข่าย
  • ตัวอย่างในหนังสือเน้นไปที่ระบบข้อมูลขนาดใหญ่และอุปกรณ์จัดเก็บข้อมูลสำรองเป็นหลัก แต่แนวทางการวิเคราะห์และออกแบบยังนำไปใช้กับระบบ in-memory ได้เช่นกัน
  • การวิเคราะห์นี้ตั้งอยู่บนสภาพแวดล้อมที่มีลำดับชั้นของหน่วยความจำและสตอเรจมากกว่าสองระดับ

เวิร์กโหลดและต้นทุนเป็นตัวกำหนดการออกแบบ

  • แอปพลิเคชันหรือเวิร์กโหลดสามารถแสดงได้เป็นชุดผสมของการดำเนินการแบบคีย์-ค่า

    • point query

    • range query

      • การแทรก
      • การลบ
      • การแก้ไข
      • ความจุที่ต้องใช้และต้นทุนของหน่วยความจำกับสตอเรจถาวรก็เป็นส่วนหนึ่งของข้อกำหนดของแอปพลิเคชันเช่นกัน
      • โครงสร้างข้อมูลที่ควรปรับให้เหมาะสมจะแตกต่างกันไปตามประเภทของระบบ
      • ระบบไฟล์จัดการเมทาดาทาและเนื้อหาของไฟล์ด้วยโครงสร้างข้อมูลที่เหมาะกับการอัปเดตบ่อย
      • คอมไพเลอร์จัดการตัวแปรด้วย hash map ตลอดอายุของตัวแปร และแทนโครงสร้างทั้งหมดของโปรแกรมด้วย abstract syntax tree
      • อุปกรณ์เครือข่ายต้องการโครงสร้างข้อมูลเฉพาะทางเพื่อจัดเก็บและเข้าถึง routing table อย่างมีประสิทธิภาพ

ทางเลือกที่ต่างกันอย่างชัดเจนของ B+-tree และ LSM-tree

  • B+-tree ถูกใช้อย่างมากเพื่อสร้างสมดุลระหว่างต้นทุนการอ่านและการเขียนในเวิร์กโหลดที่มีการแทรกและอัปเดตน้อย แต่มี point query และ range query จำนวนมาก
  • fan-out ของโหนดที่สูงช่วยลดการเข้าถึงหน่วยความจำสำรองที่ต้องใช้ระหว่างการไล่จากรากไปยังใบ และระดับบนจะถูกแคชไว้ในลำดับชั้นหน่วยความจำที่เร็วกว่า
  • มีการเก็บคีย์ทั้งหมดเรียงลำดับไว้ในโหนดใบ และเชื่อมโหนดใบเข้าด้วยกันเป็น linked list เพื่อรองรับ range query
  • เมื่อการแทรกและการอัปเดตเพิ่มขึ้น จะต้องมีการจัดโครงสร้างใหม่หรือแยกโหนดใบ ซึ่งอาจกลายเป็นคอขวดด้านประสิทธิภาพ
  • LSM-tree ใช้วิธีที่ต่างออกไปสำหรับเวิร์กโหลดที่มีการแทรกจำนวนมาก
    • ใส่การอัปเดตทั้งหมดลงในบัฟเฟอร์หน่วยความจำร่วม
    • เมื่อบัฟเฟอร์เต็มจึง flush ลงดิสก์
    • เมื่อบัฟเฟอร์สะสมมากขึ้นก็จะ merge เป็นคอลเลกชันข้อมูลที่เรียงลำดับและมีขนาดใหญ่กว่า
    • การแก้ไขจัดการด้วยนโยบาย out-of-place และอาจมีคู่คีย์-ค่าที่ใช้คีย์เดียวกันอยู่หลายรายการภายในโครงสร้าง
    • ค่าปัจจุบันของคีย์หนึ่ง ๆ คือค่าจากคู่คีย์-ค่าที่ถูกแทรกล่าสุด

โครงสร้างข้อมูลแบบปรับตัวได้

  • นอกจากแนวทางการออกแบบโครงสร้างข้อมูลโดยคาดการณ์เวิร์กโหลดล่วงหน้าแล้ว ยังกล่าวถึงโครงสร้างข้อมูลที่ค่อย ๆ เข้าใกล้รูปแบบที่เหมาะสมระหว่างการทำงานด้วย
  • ในการออกแบบดั้งเดิม B+-tree และ LSM-tree บังคับให้มีลำดับการเรียงภายในโหนดที่อยู่บนดิสก์เพื่อให้ตอบ point query หรือ range query ทั้งหมดได้
  • โครงสร้างข้อมูลแบบปรับตัวได้ สามารถเริ่มต้นจากโหนดที่ยังไม่เรียงลำดับหนึ่งโหนดหรือมากกว่านั้น แล้วค่อย ๆ จัดเรียงเมื่อมีโอกาส
  • database cracking ใช้รูปแบบการเข้าถึงของคิวรีที่เข้ามาเพื่อปรับโครงสร้างทางกายภาพของข้อมูลพื้นฐานอย่างต่อเนื่องและแบบเพิ่มพูน
  • เป้าหมายคือปรับปรุงประสิทธิภาพของคิวรีในอนาคต

ลำดับชั้นฮาร์ดแวร์และกำแพงหน่วยความจำ

  • ความก้าวหน้าของฮาร์ดแวร์สร้างทั้งความท้าทายและโอกาสใหม่ในการออกแบบโครงสร้างข้อมูล
  • ในลำดับชั้นของสตอเรจ ระดับล่างให้พื้นที่จัดเก็บมากกว่าในราคาต่ำกว่า แต่มีความหน่วงในการเข้าถึงสูง ขณะที่ระดับบนซึ่งอยู่ใกล้โปรเซสเซอร์มากกว่าจะเร็วกว่า แต่มีขนาดเล็กกว่าและมีต้นทุนต่อไบต์สูงกว่า
  • ชั้นที่เป็นคอขวดสำหรับแอปพลิเคชันหนึ่ง ๆ จะแตกต่างกันไปตามขนาดข้อมูลของแอปพลิเคชันและความจุของแต่ละชั้น
  • เดิมที B+-tree ถูกออกแบบมาเพื่อเพิ่ม fan-out ให้สูงที่สุดเพื่อลดการเข้าถึงดิสก์ แต่เมื่อหน่วยความจำมีขนาดใหญ่ขึ้นและข้อมูลอยู่ใน RAM หรือหน่วยความจำเสริมแบบไม่ลบเลือน trade-off ก็เปลี่ยนไปอย่างมาก
  • B+-tree แบบ in-memory ให้ประสิทธิภาพดีที่สุดเมื่อมี fan-out ขนาดเล็ก
  • กำแพงหน่วยความจำ (memory wall) หมายถึงแนวโน้มที่ช่องว่างระหว่างความเร็วของโปรเซสเซอร์กับความเร็วของหน่วยความจำนอกชิปกว้างขึ้น
  • ตั้งแต่ต้นทศวรรษ 2000 เป็นต้นมา ระบบปฏิบัติการและระบบจัดการข้อมูลได้รับการออกแบบใหม่เพื่อเพิ่มประสิทธิภาพการใช้แคชเมมโมรี

พื้นที่การออกแบบและแนวทาง

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

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-02-10
ความคิดเห็นบน Hacker News

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

    • จัดอยู่ใน ระดับสูงสุด ของหนังสือ/เอกสารเทคนิคที่เคยอ่านมาได้อย่างง่ายดาย

  • หนึ่งในผู้เขียนหนังสือเล่มนี้บริหาร แล็บวิจัย ในสาขานี้อยู่
    ยังมีเครื่องมือเจ๋ง ๆ ที่ช่วยออกแบบโครงสร้างข้อมูลที่เหมาะสมที่สุดด้วย: http://daslab.seas.harvard.edu/datacalculator/

    • หาไม่ค่อยเจอว่าเครื่องมือตัวจริงอยู่ตรงไหน

  • อยากรู้ว่ามีแหล่งข้อมูลแนะนำเพิ่มเติมเกี่ยวกับหัวข้อนี้ไหม
    เปเปอร์นั้นยอดเยี่ยม และก็รู้จัก Designing Data-Intensive Applications ของ Martin Kleppmann อยู่แล้ว แต่หนังสือเล่มนั้นใกล้กับฐานข้อมูลมากกว่าโครงสร้างข้อมูล

  • ถ้าจะออกแบบโครงสร้างสำหรับเก็บข้อมูลเชิงวิเคราะห์บางประเภท กลับไม่มีการเปรียบเทียบที่สำคัญมากระหว่าง array of structs กับ struct of arrays

    • ในหัวข้อ 6.1 มีการพูดถึงข้อดีข้อเสียและเหตุผลของ การจัดเก็บแบบเน้นแถวและแบบเน้นคอลัมน์
      ดังนั้นจึงมีการอภิปรายอยู่ เพียงแต่ไม่ได้อธิบายด้วยคำว่า array of structs/struct of arrays เท่านั้น

  • อยากซื้อสักเล่ม แต่ใน Amazon ราคา 100 ดอลลาร์

    • ยังรอให้ใครสักคนมาปฏิวัติอุตสาหกรรมหนังสือเพื่อทลาย การพึ่งพา Amazon อยู่
      เป็นโครงสร้างที่พังซึ่งทั้งผู้เขียนก็เสียประโยชน์และผู้อ่านก็เสียประโยชน์

  • ต้องมี สารบัญ

    • ถ้าเปิดด้วย Firefox จะเห็นสารบัญทั้งหมด: https://imgur.com/a/cgdy0nY
    • อัปโหลด PDF แล้วขอให้ ChatGPT 4 ทำสารบัญให้ แต่มันค่อนข้างลำบากในการประมวลผล
      แม้จะบอกให้ละเว้นหัวกระดาษและท้ายกระดาษก็ยังเหมือนเดิม และคิดว่าระดับล่าสุดน่าจะดีขึ้นกว่านี้มากแล้ว