Redundancy: มารู้จักวิธีโคลนนิ่งกันเถอะ (ภาค 1)

ก่อนอื่นต้องขอประทานโทษที่ผมหายหน้าไปนาน เพราะผมอยู่ในช่วงสอบและผมมีภาระกิจที่ได้รับให้ทำวิจัยโครงงานหนึ่ง ซึ่งไม่ใช่ Thesis ของผมเลยนะ เป็นแค่โครงงานของวิชาหนึ่งของผม  แต่ก็ทำให้ผมต้องยุ่งกับโครงงานนี้ไปหลายวันพอสมควรครับ และหัวข้อครั้งนี้ ผมก็ขอเสนอเนื้อหาที่เกี่ยวข้องกับโครงงานที่ผมได้ไปทำนี้แหละครับ ซึ่งเกี่ยวกับกลยุทธ์ในการสร้างความซ้ำซ้อนให้กับข้อมูลหรือ Redundancy (ผมขอใช้ทับศัพท์เลยนะครับ) โดยวัตถุประสงค์ของโครงงานคือการเปรียบเทียบกลยุทธ์ของ Redundancy โดยการใช้ Simulation จริงๆผมว่าจะกล่าวถึงเรื่องนี้หลังจากผมได้นำเสนอหัวข้ออื่นๆไปอีก 8 – 10 เรื่อง แต่ผมอดใจไม่ไหวครับ เพราะผมเพิ่งทำโครงงานนี้เสร็จไปเมื่อวานนี้เอง และผมก็ค้นพบอะไรที่น่าสนใจหลายเรื่องจากการวิจัยในครั้งนี้ และมีเรื่องหนึ่งที่ผมค้นพบ และได้รับคำชมจากอาจารย์ของผมว่าทำได้น่าประทับใจ (ขออวดนิดนึงนะครับ) เพราะถือเป็นการค้นพบครั้งใหม่ในศาสตร์ด้านนี้เลยครับ แต่ผมคงไม่ได้กล่าวในที่นี้ (อาจจะไปกล่าวใน conference ใดสักที่ก็ได้ครับ) โอเคครับ…คลิ้กเข้ามา มาอ่านว่าบทความนี้กล่าวถึง Redundancy ว่าอย่างไร

Author: Sivadon Chaisiri More about author 

จริงๆหัวข้อนี้ไม่ได้เกี่ยวกับการโคลนนิ่ง (Cloning) จะเป็นโคลนแกะหรือโคลนคนก็ตามครับ แต่คำว่า Redundancy มีความหมายที่ใกล้เคียงกับคำว่า Cloning ผมจึงนำคำว่า Cloning มาเป็นหัวข้อของบทความนี้ครับ และมีภาพนายแบบมือสมัครเล่นมาเป็นภาพประกอบด้านบนด้วยครับ คำว่า Redundancy คือการทำความซ้ำซ้อน (หรือซ้ำซาก) ให้กับสรรพสิ่งอะไรสักอย่าง หากว่าคุณเคยได้ศึกษาวิชา Database มาแล้ว คุณคงเคยได้ยินคำว่า Redundancy มาบ้างแล้ว และคุณคงจะบอกได้เลยว่า Database เป็นหลักการที่ใช้ในการลด Redundancy ของข้อมูลดั่งที่เคยพบเจอในระบบที่ไม่มี Database อย่าง File Processing … แต่ทว่า ในบทความนี้ ไม่ได้เกี่ยวกับการลดความซ้ำซ้อนของข้อมูลในวิชา Database หากแต่ว่าผมจะกล่าวถึงกลยุทธ์ (Strategy) สำหรับเพิ่มความซ้ำซ้อนของข้อมูลครับ อ้าว! แล้วมันจะดีหรือ? ตอนเราเรียน Database เขาไม่อยากได้ Redundancy แล้วทำไมเราต้องไปดันทุรังเพิ่ม Redundancy ด้วย…แล้ว Redundancy มันดีอย่างไรหรือ?

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

Redundancy in Engineering

จากข้อมูลของ wikipedia [1] Redundancy คือการคัดลอกหรือทำความซ้ำซ้อนให้กับองค์ประกอบหรือชิ้นส่วนใดๆของระบบให้มีมากกว่า 1 หน่วย ด้วยจุดประสงค์ในการเพิ่มความน่าเชื่อถือ (reliability) ให้กับระบบ เสมือนเป็นการสำรองชิ้นส่วนของระบบ ในกรณีที่ชิ้นส่วนหนึ่งผิดพลาด ก็ยังมีชิ้นส่วนอื่นที่เหมือนกันทำงานแทนกันได้ ดังนั้น ระบบก็ยังทำงานได้ต่อเนื่อง โดยไม่จำเป็นต้องรอการซ่อมแซมชิ้นส่วนที่เสียหายนั้น ถ้าหากเราไม่มี Redundancy สำหรับบางระบบ อาจถือว่าเป็นเรื่องใหญ่มากครับ เช่น หากฮาร์ดดิสก์ของ Server เว็บ Amazon.com เกิดพังขึ้นมา และถ้า amazon เขาไม่มีการ Redundancy ฮาร์ดดิสก์นี้ไว้ (เช่นใช้วิธี RAID) amazon คงต้องเสียรายได้ไปใช่น้อย

สำหรับในบทความนี้ ผมจะลงรายละเอียดถึงการทำความซ้ำซ้อนให้กับข้อมูล (Data Redundancy) หรือการจัดเก็บข้อมูล (Storage Redundancy)  ที่ออกแบบมาใช้กับระบบแบบกระจาย โดยเป็นที่ต้องการมากในเครือข่ายแบบ Peer-to-Peer ครับ (คุณสามารถทำความเข้าใจพื้นฐานของ Peer-to-Peer ได้จากบทความเก่าของผมครับที่ [2] ครับ) ในที่นี้ ผมขอระบุว่าข้อมูลในที่นี้หมายถึงไฟล์ (File) หรือการทำ File Redundancy นั่นเองครับ

ขอให้เรานึกถึงระบบ Peer-to-Peer ประเภทแชร์ไฟล์ (Peer-to-Peer File Sharing) อย่าง BitTorrent และ KaZaa เป็นต้น ถ้าสมมติว่าเรามีไฟล์ที่ชื่อ A และ A มีเพียงแค่ 1 ไฟล์ในระบบ หากว่าคอมพิวเตอร์ที่เก็บไฟล์ A นี้ออกจากระบบ ก็หมายถึงไฟล์ A ต้องหายจากระบบไปด้วยนั่นเอง จึงทำให้ A ไม่มีให้บริการในระบบอีกต่อไป ซึ่งทำให้คุณสมบัติของระบบ Peer-to-Peer อย่างความคงอยู่ยาวนาน (หรือ Availability) ต้องหมดไปด้วย ดังนั้น นักวิจัยจึงนำRedundancy ในการแก้ปัญหานี้นั่นเองครับ หากว่าเรามี A เก็บอยู่บนคอมพิวเตอร์มากกว่า 1 เครื่อง (หรือมี A มากกว่า 1 ที่) A ก็ย่อมคงอยู่ในระบบยาวนานยิ่งขึ้น ถ้าหาก A ตัวหนึ่งต้องสูญหายไป ก็ยังมี A ตัวอื่นๆคงอยู่ในระบบ

เมื่อเราทำ File Redundancy เราจะได้อะไรมาบ้างเหรอครับ ผมขอสรุปสิ่งที่เราจะได้จาก Redundancy ไว้ 3 ข้อดังนี้

  1. ความคงอยู่ยาวนาน (Availability) อันนี้ก็กล่าวไว้แล้วครับ ซึ่งเป็นการเพิ่มความคงทนให้กับระบบ (Fault tolerance) วิธีหนึ่ง เพราะเรามีไฟล์มากกว่า 1 แห่ง ไฟล์ก็ยังคงอยู่ในระบบยาวนานขึ้น
  2. การแบ่งเบาภาระ (Load balancing) เช่น หากผมมีไฟล์ A บริการไว้บนคอมพิวเตอร์เซิร์ฟเวอร์ที่ชื่อ X แน่นอนครับหากว่ามีคนเข้ามาดาวน์โหลด A พร้อมกันจำนวนมากๆ คอมพิวเตอร์ X ก็ย่อมทำงานหนักไปด้วย คนที่เข้ามาโหลด A บางคนอาจจะพบปัญหา Server Busy (เคยเจอกันหรือเปล่า) อันเนื่องจาก X ทำงานหนักมากจนให้บริการไม่ไหวหรือตอบสนองการให้บริการให้ผู้ใช้ได้ไม่ทั่วถึง เป็นต้น แต่ถ้าหากผมมีคอมพิวเตอร์มากกว่า 1 เครื่องมาให้บริการ A ผมก็สามารถแบ่งเบาภาระการให้บริการไฟล์ A แก่ผู้ใช้จำนวนมากได้ด้วย
  3. แคชชิ่ง (Caching) ซึ่งเป็นการคัดลอกไฟล์ให้อยู่ใกล้ผู้ที่ต้องการไฟล์ให้มากขึ้น หรือเรียกว่าเป็นวิธีการทำ Locality (ทำให้อยู่ในพื้นที่เดียวกัน) เช่น หากผมดาวน์โหลดไฟล์ A จากคอมพิวเตอร์ที่อเมริกามาแล้ว (สมมติผมอยู่ไทย) ครั้งต่อไปหากผมต้องการ A อีกครั้ง ผมก็ใช้ A บนคอมของผมได้เลย ไม่ต้องไปโหลดจากอเมริกาใหม่ และผมยังแชร์ A ให้คนที่อยู่เมืองไทยได้โหลด A ในความเร็วที่สูงกว่าไปโหลดจากอเมริกาได้ด้วย

กฎไตรลักษณ์กับ Redundancy

หากเราทำ Redundancy ได้แล้ว เราก็ไม่ได้ Availability, Load Balancing และ Caching ทันทีหรอกครับ หรืออาจจะได้มาแต่ก็ไม่ได้คงอยู่ไปตลอดกาลหรอกครับ ดั่งคำสอนของพระพุทธเจ้า “ทุกขัง อนิจจัง  อนัตตา” กฎไตรลักษณ์ ที่ว่าไม่มีสิ่งใดคงอยู่ยั่งยืนถาวร อย่างเช่น ในเรื่อง Availability หากว่าเรามีไฟล์ A จำนวน 100 แห่ง หากว่า 100 แห่งเกิดล่มไปพร้อมๆกัน เราก็คงไม่ได้มาซึ่ง Availability ของไฟล์ A อีกต่อไป แต่ก็กล่าวได้ว่ามี Avaiability ที่สูงกว่ามี A เก็บไว้แค่ 2 – 3 ที่ เป็นต้น ส่วน Load Balancing กับ Caching นั้น เราจะได้สิ่งเหล่านี้มาจำเป็นต้องอาศัยเทคนิคอื่นๆเข้ามาช่วยเสริมด้วย หรือมีเหตุการณ์บางอย่างเข้ามาสนับสนุนด้วย แต่ผมไม่ขอกล่าวไว้ในบทความนี้นะครับ ผมจะกล่าวเพียงกลยุทธ์ในการทำ Redundancy เท่านั้นครับ

กระบวนการทำ Redundancy

เรามีกระบวนการ (process) สำหรับทำความซ้ำซ้อนให้กับไฟล์ได้ 2 แบบคือ

  1. Replication หรือการคัดลอก (ก๊อปปี้) ไฟล์ให้มีมากกว่า 1 สำเนา สมมติมีทั้งหมด N สำเนา จากนั้นเราสามารถกระจายสำเนานี้ไปตามคอมพิวเตอร์ในระบบให้ช่วยจัดเก็บและให้บริการสำเนาของไฟล์นี้ครับ และแน่นอนครับ หากเรามีไฟล์ N สำเนา เราก็ควรมีคอมพิวเตอร์ทั้งหมด N เครื่องสำหรับบริการไฟล์นี้ด้วยเช่นกัน โดยคอมพิวเตอร์ 1 เครื่องจะเก็บสำเนาของไฟล์ไว้ 1 สำเนา (จากทั้งหมด N) เมื่อไหร่ก็ตามที่ผู้ใช้ต้องการเข้าถึง (หรือใช้) ไฟล์นี้ ผู้ใช้เพียงดาวน์โหลดสำเนาของไฟล์เพียง 1 สำเนาจากคอมพิวเตอร์เครื่องใดๆที่เก็บสำเนานี้ไว้อยู่
  2. Erasure Code เป็นวิธีการเข้ารหัสหรือการแปลงข้อมูลแบบหนึ่ง (Coding) ผมคงไม่อธิบายว่าเราจะสร้างกระบวนการของ Erasure code ได้อย่างไร เพราะมันก็ซับซ้อนพอสมควรครับ แต่ผมจะกล่าวถึงผลลัพธ์ของการทำ Erasure code โดยเมื่อไหร่ก็ตามที่เรานำไฟล์ (หรือข้อมูลใดๆ) ผ่านกระบวนการ Erasure code เราจะได้ชิ้นส่วนย่อย (fragment) ออกมาทั้งหมด N ชิ้น จากนั้น เราสามารถกระจายชิ้นส่วนย่อย N ชิ้น ไปตามคอมพิวเตอร์ในระบบ ซึ่งอาจจะเป็นไปได้ว่าชิ้นส่วนย่อยของไฟล์เดียวกันมากกว่า 1 ชิ้นอาจจะอยู่บนคอมพิวเตอร์เครื่องเดียวกัน และเมื่อไหร่ก็ตามที่ผู้ใช้ต้องการเข้าถึงไฟล์นี้ ผู้ใช้จำเป็นต้องดาวน์โหลดชิ้นส่วนให้ได้ทั้งหมด M ชิ้นที่ไม่ซ้ำกัน (ไม่จำเป็นต้องให้ได้ N ชิ้นนะ) เมื่อได้มา M ชิ้นแล้ว ต้องนำ M ชิ้นมาประกอบใหม่ (Reconstruct) เพื่อให้ได้ไฟล์ต้นฉบับ โดยสรุป Erasure code คือการสร้างชิ้นส่วนย่อย N ชิ้น โดยต้องการเพียง M ชิ้นที่แตกต่างกันเพื่อประกอบเป็นไฟล์ต้นฉบับ และ M ≤ N

Fix-Rate Code vs. Rateless Code

หากเราพิจารณาดีๆนะครับ Replication ก็คือ Erasure code แบบหนึ่ง เพราะ Replication คือการสร้างชิ้นส่วน N ชิ้น แต่ตอนประกอบไฟล์เราต้องการเพียง 1 ชิ้นเท่านั้น และหากเรามีข้อมูลขนาดใหญ่ เราสามารถแบ่งไฟล์นี้หลายๆชิ้นที่มีขนาดเท่ากัน เพื่อความรวดเร็วในการขนส่งไฟล์นั่นเอง แต่ละชิ้นเรียกว่า fragment สมมติผมแบ่งไฟล์มาได้ M ชิ้น (M fragments) จากนั้น ผมก็กระจาย M ชิ้นนี้ไปตามคอมพิวเตอร์ต่างๆ นอกจากนี้แล้ว ผมยังสามารถสำเนา fragment ได้ด้วย เพื่อรับประกันความคงอยู่ยาวนานของไฟล์นั่นเอง อย่างไรก็ดี แม้ว่าผมสำเนา fragment จากทั้ง M ชิ้นมากมายเท่าไหร่ก็ตาม แต่ตอนที่ผมต้องการประกอบไฟล์ต้นฉบับ ผมต้องรวบรวม fragment ทั้ง M ชิ้นที่แตกต่างกันมาให้ได้ แน่นอนครับ ต่อให้ผมรวบรวมมาได้ M ชิ้น แต่มีอยู่ 2 ชิ้นใน M ที่เป็นชิ้นส่วนเดียวกัน ผมก็ประกอบไฟล์ต้นฉบับไม่ได้แล้วครับ ลักษณะ Erasure code เช่นนี้เรียกว่า Fix-rate code ซึ่ง Replication ก็เป็น Fix-rate code แบบหนึ่ง

นอกจาก Fix-rate แล้วยังมี Erasure code อีกแบบหนึ่ง คือ Rateless code (อย่างเช่น Fountain code) ที่สามารถผลิต fragment จำนวน N ชิ้นที่ไม่ซ้ำกันทุกๆครั้ง และเมื่อต้องการประกอบชิ้นส่วนให้ได้ไฟล์ต้นฉบับ เราต้องการเพียงแค่ M ชิ้นเท่านั้น ยกตัวอย่างเช่น สมมติเราต้องการผลิตชิ้นส่วน fragment ของไฟล์ต้นฉบับบออกมา 5 ชิ้น โดยใช้ Rateless code เราก็สามารถผลิตชิ้นส่วน f1, f2, f3, f4, f5 ออกมา หากครั้งต่อไปเราผลิต fragment จำนวน 5 ชิ้นอีกครั้ง สมมติว่าได้ x1, x2, x3, x4, x5 ข้อมูลกลุ่มใหม่นี้ จะไม่ซ้ำกับข้อมูลกลุ่มอี่นที่เคยผลิตมาก่อนหน้านี้ (นั่นคือกลุ่ม f1, f2,…, f5)  และเมื่อเราจะประกอบไฟล์ต้นฉบับ เราต้องการเพียงแค่ fragment เพียง M ชิ้น สมมติ M=3 ดังนั้น เราจึงต้องรวบรวม fragment ให้ได้ 3 ชิ้นจากทั้งหมดที่มีตอนนี้ 10 ชิ้น (ตอนนี้เรามี f1,f2,…, f5 และ x1,x2,…,x5) ซึ่งชิ้นส่วนทั้ง 3 นี้อาจจะเป็น (x1, x2, x5) ก็ได้ หรือ (f3, f4, f5) ก็ได้ หรือแม้กระทั่ง (x2, f1, f3) ก็ยังได้ ทั้งนี้เพราะว่า Ralteless นั้นผลิต fragment ไม่มีทางซ้ำกันเลย เราจึงเลือก fragment อะไรก็ได้ ขอเพียงให้ครบ M ชิ้นก็พอ  เป็นต้น

สรุปความแตกต่างระหว่าง Fix-rate กับ Rateless ให้เราพิจารณาที่การรับประกัน Availability หรือความคงอยู่ยาวนานของข้อมูล เมื่อเราใช้ Fix-rate code เราจำเป็นต้องสำเนาหรือทำ replication ให้กับ fragment ให้มีจำนวนเยอะๆ เพราะเดิมทีเมื่อข้อมูลผ่านกระบวนการ Fix-rate แล้ว เราจะได้ fragment จำนวน M ชิ้น ดังนั้น เราต้องทำสำเนา fragment ใน M ชิ้นนี้ให้มีมากขึ้น สมมติว่าสำเนาแล้ว fragment ที่มีในระบบทั้งหมด N ชิ้น เมื่อไหร่ก็ตามที่เราจะประกอบไฟล์ต้นฉบับ เราต้องรวบรวม fragment ที่แตกต่างกันให้ได้ M ชิ้น ซึ่งต่างจาก Rateless code ที่เราไม่จำเป็นต้องทำ replication เลย เพราะว่า Rateless สามารถผลิต fragment ที่แตกต่างกันทุกครั้ง สมมติว่า Rateless ผลิต fragment มาได้ N ชิ้น เราเพียงรวบรวมมาให้ได้ M ชิ้น โดยไม่ต้องกังวลเลยว่ามันจะซ้ำกันหรือเปล่า เราก็สามารถประกอบไฟล์ต้นฉบับได้แล้ว

Fragment Metadata

ในการพัฒนาระบบแบบ Redundancy จริงๆนั้น เราสามารถเพิ่มข้อมูลบางอย่าง (metadata) พ่วงไปกับ fragment แต่ละชิ้น เพื่อช่วยในการประกอบไฟล์ต้นฉบับ และยังช่วยในการตรวจสอบความถูกต้อง (Verification) โดยข้อมูลที่เราสามารถเพิ่มเข้าไปให้กับ fragment ได้แก่ Fragment ID, File ID, File Signature และ Timestamp เป็นต้น

  • Fragment ID เป็นรหัสประจำตัวของ Fragment โดย Fragment 2 ตัวใดๆ (ของไฟล์เดียวกัน) ต้องมี Fragment ID ที่ต่างกัน โดยปกติเราจะรัน Fragment ID เป็นเลขจำนวนเต็มแบบเรียงลำดับ (Sequence number) เช่น 0, 1, 2, … เป็นต้น หรืออาจจะใช้ Hash function เพื่อสร้าง signature ไว้เป็นรหัสประจำตัวของ fragment ID และยังมีประโยชน์ต่อการตรวจสอบความถูกต้องในการอัพโหลดหรือดาวน์โหลด fragment อีกด้วย
  • File ID เป็นรหัสประจำตัวของไฟล์ต้นฉบับของ fragment เราอาจจะใช้ hash function เพื่อช่วยในการสร้าง ID ของ file ก็ได้ หรือใช้หลักการอื่นๆอย่างเช่น หลักการสร้าง Key ที่ใช้ใน Freenet (อ่านเพิ่มใน [3]) เป็นต้น
  • File Signature เป็นลายเซ็น (signature) ของไฟล์ต้นฉบับของ fragment เราจะใช้ลายเซ็นนี้ตรวจสอบความถูกต้องในการประกอบไฟล์ต้นฉบับ  ซึ่งเราสามารถใช้ hash function ในการสร้าง File signature ก็ได้ หรือเราสามารถใช้ File ID เป็น File Signature เพื่อลดขนาดของ metadata
  • Timestamp เป็นการระบุวันเวลาของไฟล์ อาจจะมีประโยชน์ในการตรวจสอบ version ของไฟล์

เราไม่จำเป็นต้องใช้ Metadata เหล่านี้ครบทุกตัว มันขึ้นอยู่กับความต้องการของระบบ และเราสามารถเพิ่ม metadata ตามความต้องการได้ (เช่น index หรือ description ของไฟล์ที่จะช่วยในการค้นหาไฟล์โดยอิงจาก keyword) แต่ metadata ที่ผมยกตัวอย่างมานี้ จะมีเพิ่มความสะดวกในการค้นหา fragment และช่วยตรวจสอบความถูกต้องในการประกอบไฟล์ต้นฉบับ เช่น หากเราต้องการค้นหา fragment ของไฟล์ที่ชื่อ A เราก็เพียงแต่ค้นหา fragment ที่มี File ID เหมือนกับ File ID ของ A และเลือกเฉพาะ fragment ที่มี fragment ID ไม่เหมือนกับ fragment ที่รวบรวมมาได้แล้ว เป็นต้น และข้อมูลอย่าง File Signature เป็นสิ่งสำคัญที่ใช้ในการตรวจสอบความถูกต้องในการประกอบไฟล์ และจริงๆเราไม่จำเป็นต้องเก็บ File Signature เข้าไปใน metadata เลย แต่ผู้ใช้จำเป็นต้องทราบ File Signature เอง (เช่น BitTorrent จะเก็บ file signature และ fragment signature ไว้ในไฟล์นามสกุล torrent) เมื่อเราประกอบไฟล์เรียบร้อย เราก็เพียงนำ signature ของไฟล์ที่ประกอบได้ไปเทียบกับ signature ของไฟล์ต้นฉบับที่เราทราบอยู่แล้ว ถ้า signature ตรงกันก็แปลว่าเราประกอบไฟล์ได้สมบูรณ์

โปรดติตตามตอนต่อไป 

โอเคครับ ภาค 1 ของ Redundancy นี้ผมต้องการปูพื้นฐานเท่านั้นครับ สำหรับภาค 2 ผมจะกล่าวถึงกลยุทธ์หรือ Strategy ของการทำ Redundancy เพราะการทำ Redundancy มันก็มีราคาของมันอยู่ ผมหมายความว่า การทำ Redundancy ไม่ใช่ว่าเราจะผลิต fragment ของไฟล์หรือสำเนาไฟล์มากมายเท่าไหร่ก็ได้ตามใจชอบ เพราะการทำ redundancy ย่อมต้องใช้ bandwidth ของเครือข่ายในการกระจายไฟล์และต้องใช้พื้นที่จัดเก็บข้อมูลหรือ storage สำหรับจัดเก็บfragment ถ้าหากเราทำ redundancy อย่างไม่ยั้งคิด เราก็ย่อมต้องบริโภค bandwidth ของเครือข่ายและพื้นที่จัดเก็บข้อมูลอย่างฟุ่มเฟือยไปด้วยครับ โอเคครับ ไว้ติดตามภาค 2 แล้วกัน

Reference

[1] http://en.wikipedia.org/wiki/Redundancy_%28engineering%29

[2] https://javaboom.wordpress.com/2008/03/26/piratep2p/

[3] http://wiki.freenetproject.org/FreenetZeroPointSevenKeys

16 thoughts on “Redundancy: มารู้จักวิธีโคลนนิ่งกันเถอะ (ภาค 1)

  1. soowoi says:

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

  2. javaboom says:

    ขอบคุณครับกับคำถาม จริงๆผมใส่ reference ให้คุณได้ไปอ่านเพิ่มเติมไว้แล้วนะครับ ที่ http://en.wikipedia.org/wiki/Fountain_code วิธีการนี้ อย่างที่บอกนะครับ เขาจะไม่ทำ replication ครับ ดังนั้น มันไม่มีทางซ้ำ ยกเว้นว่ามีใครอยากจะทำให้มันซ้ำ หรือมันก็อาจจะมีโอกาสซ้ำเหมือนๆกับปัญหา collision ที่เกิดกับ hash function ครับ พอดีผมไม่ได้จะเจาะลึกงานวิจัยด้าน rateless เท่าไหร่ครับ ถ้าคุณสนใจเรื่อง rateless คุณสามารถค้นหา paper อ่านเพิ่มเติมได้ครับ แต่ถ้าจะถามว่าอะไรจะรับประกันว่าไม่ซ้ำ เขาทำกันไง ผมตอบได้เลยว่ามันไม่มีอะไรรับประกัน 100% โดยไม่มีการประมวลผลมาช่วยในการ verify หรอกครับ

    เอาอย่าง MD5 เขาก็บอกว่าถ้า data ต่างกันมันก็มี signature ต่างกัน แล้วเป็นไงล่ะครับ เราก็ยังหา data ที่ต่างกันแต่ signature เหมือนกันได้อยู่ดี มันเป็นเพียง Theory ครับคุณ หากจะไปทำในเชิงปฏิบัติเขาก็ต้องเพิ่มความซับซ้อนอะไรบางอย่างมากขึ้น เช่น SHA-1 มันแค่ 160 บิต โอกาสเกิด collision มันก็สูง เขาก็เลยพัฒนา SHA-512 อันนี้โอกาสเกิด collision ก็ยากขึ้นครับ แต่ก็ใช่ว่าจะรับประกันว่าจะไม่เกิดขึ้น … ในทางเดียวกันครับ rateless ก็เช่นกัน ไม่ได้รับประกันว่าจะไม่เกิดความซ้ำซ้อนขึ้น 100% ทั้งนี้ เพราะข้อจำกัดของคอมพิวเตอร์ หรือที่เรียกว่า key space หรือ bit depth ของคอมพิวเตอร์มันจำกัด ถ้าคอมพิวเตอร์ไม่มีข้อจำกัด ผมกล้าพูดครับว่าไม่มีทางซ้ำกันแน่ๆครับ ไม่งั้นเราก็คงไม่มีปัญหา Y2K, Y10K มาให้ปวดหัวหรอกครับ และ Primary key ในระบบ Database สักวันมันจะซ้ำกันครับ ถ้าหากเรามี data เยอะถึงระดับหนึ่ง เดี๋ยวมันก็จะ overflow ครับ แต่เดี๋ยวเขาก็หาวิธีแก้เองแหละครับ จะด้วย hardware หรือ software ก็เหอะ

    แต่ผมก็ว่ามันไม่ใช่ประเด็นที่เราจะต้องกังวลว่าซ้ำไม่ซ้ำนะครับ ถ้ามีชิ้นส่วนที่ซ้ำกันใน M ชิ้นที่รวบรวมมาได้ ก็แค่รายงานว่าประกอบไม่ได้หรือไม่สำเร็จครับ และจะรู้ได้ไงว่ามันประกอบไม่สำเร็จ rateless มันเป็นทฤษฎี math ครับ (ผมไม่แน่ใจว่ามี implement จริงๆแล้วหรือยัง) ไปอ่านรายละเอียดได้ มันมีวิธี reconstruct ของมันอยู่ ซ้ำไม่ซ้ำมันก็ check ได้ครับ และผมก็มีอีกวิธีสำหรับ verify ว่าประกอบสมบูรณ์หรือเปล่า โดยการใช้ hash นั่นเองครับ เช่น คุณสามารถ check หลังจากประกอบเสร็จ (เพื่อไม่เปลือง computation) เมื่อเราประกอบไฟล์เสร็จแล้ว เราก็หาsignature แล้วก็ไปตรวจกับ signature ของต้นฉบับ เราก็ทราบแล้วว่ามันประกอบสมบูรณ์หรือไม่ มันก็ไม่ต่างจากวิธีที่ใช้ในการ download ไฟล์ หรือระบบ P2P อื่นๆอย่าง BitTorrent ที่เขาใช้ hash มารับประกันว่าประกอบไฟล์ได้สมบูรณ์หรือเปล่า โดยสรุป ถ้าประกอบไม่สมบูรณ์ก็รายงานข้อผิดพลาดครับ และก็ไปค้นหา fragment อื่นๆอีกทีที่ไม่ซ้ำ หลายๆระบบ (เช่น BitTorrent, Chord, FreeNet,และอีกมากมาย) เขาก็จะแนบ signature หรือ ID (อาจจะเป็น sequence ID หรือ fragment ID) ของแต่ละ fragment ไปเลยครับ เพื่อช่วยในการค้นหา fragment ที่ไม่ซ้ำกันนั่นเอง

  3. JinGjOe says:

    ถึงออสละนะครับพี่เจอสาวสวยจากมอABAC~ด้วยแต่ดันมีแฟนแล้วแต่ไม่เป็นไรผมจะพยามครับแฟนครับไม่ใช่สามีฮรี่ๆ นอนเรื่องไปนิขอโทษด้วยจ้า

  4. javaboom says:

    ถึงคุณ Soowoi อีกครั้งครับ ขอขอบคุณกับคำถามของคุณอีกครั้ง เดี๋ยวผมจะเพิ่ม section ย่อยในหัวข้อ Fragment Metadata ครับ เพื่อเน้นว่าตอน implement ระบบ redundancy จริงๆแล้ว เขาต้องมี metadata ใส่เพิ่มเข้าไปให้กับ fragment ด้วยครับ เช่นมี signature หรือ fragment ID เป็นต้น

  5. javaboom says:

    ถึงน้องจิงโจ้ครับ…ความพยายามอยู่ไหนความสำเร็จอยู่นั่นครับน้อง ไม่ได้ด้วยกลก็ต้องเล่ห์ครับ🙂

  6. soowoi says:

    ขอบคุณมากครับ กระจ่างแล้ว ขอให้ออกภาค 2 เร็วๆนะครับ(จะเป็นไตรภาคหรือเปล่า ?)

    ปล. ชอบรูปประกอบมากครับ ใช้อะไรทำเหรอครับ อยากรู้🙂

  7. javaboom says:

    ด้วยความยินดีครับคุณ Soowoi ถ้ามีคนถามคำถามดีๆอย่างคุณ Soowoi ผมก็มีกำลังใจเขียน article อื่นๆอีกครับ แต่จะได้สัก column ต้องใช้เวลาเยอะพอควร ต้องค้นคว้า และมีบ้างก็ต้องวิจัยครับ เพื่อให้ได้ประโยคและความเข้าใจของผมเอง แต่มันก็ต้องตั้งบนฐานที่เป็นที่ยอมรับด้วยครับ

    ภาพประกอบผมทำบนเครื่อง MacBook Pro สุดที่รักของผมครับ ใช้โปรแกรม PhotoBooth ไว้ถ่ายรูป โดยใส่ mirror เป็น filter ครับ

    ปล. คุณ Soowoi สามารถ msn มาคุยกับผมได้นะครับ (ถ้าว่าง) ที่ javaboom แอทฮอตเมลครับ คุณเป็นคนมีภูมิความรู้ใช่ย่อยนะครับ อยากรู้จักครับ ไม่แน่…ผมก็รู้จักคุณแล้ว แต่คุณใช้นามแฝง มีอะไรก็แนะนำผมได้ครับ

  8. soowoi says:

    เอางั้นเหรอครับ อิ ๆ ถ้าอยากรู้จักผมนะก็ mrsoowoi@hotmail.com แต่ผมไม่ค่อย online นะครับ

    ปล. ไม่ต้องแปลกใจผมคนอุบลฯเหมือนกันครับ

  9. สวัสดีครับ ผมอ่าน บทความอาจารย์อยู่เรื่อยๆนะครับ

    แอบลุ้นให้ออกภาคที่สองเร็วๆ

  10. javaboom says:

    ถึง Misui ขอบใจครับ จะพยายามออกภาค 2 เร็วๆครับ มันเขียนยากพอควรครับ เพราะเป็นเรื่องใหม่พอควร จะใส่ข้อมูลอะไรต้องทำการบ้านให้ดีน่ะครับ พอดีมันมี column เก่าที่ draft ไว้หลายเรื่อง กะจะทยอยที่ draft ออกมาทีละนิดก่อนนะครับ…อดใจภาค 2 คิดว่าหลัง 28 เมษานี้ได้ชมแน่ๆ ปล.แล้วคุณคือใครครับ ออกนามหน่อย ผมจะได้นึกหน้าได้น่ะครับ

  11. ครับผม นศ ที่ส่งประกวดของ SIA2007 ครับ
    ที่ได้ปรึกษาอาจารย์เรื่องการส่ง SMS ครับ ผมก้ตามอ่านของอาจารย์ แต่ไม่ได้คอมเม้นสักที
    พอดี blog ผมทำเสร็จเลยได้คอมเม็นตามบล็อกต่างๆครับ

  12. javaboom says:

    อ่อครับ Misui จำหน้าได้แล้วครับ ยังไงก็ฝากประชาสัมพันธ์ blog ผมหน่อยแล้วกันนะครับ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s