Posted by: javaboom on: April 19, 2008

ก่อนอื่นต้องขอประทานโทษที่ผมหายหน้าไปนาน เพราะผมอยู่ในช่วงสอบและผมมีภาระกิจที่ได้รับให้ทำวิจัยโครงงานหนึ่ง ซึ่งไม่ใช่ Thesis ของผมเลยนะ เป็นแค่โครงงานของวิชาหนึ่งของผม แต่ก็ทำให้ผมต้องยุ่งกับโครงงานนี้ไปหลายวันพอสมควรครับ และหัวข้อครั้งนี้ ผมก็ขอเสนอเนื้อหาที่เกี่ยวข้องกับโครงงานที่ผมได้ไปทำนี้แหละครับ ซึ่งเกี่ยวกับกลยุทธ์ในการสร้างความซ้ำซ้อนให้กับข้อมูลหรือ Redundancy (ผมขอใช้ทับศัพท์เลยนะครับ) โดยวัตถุประสงค์ของโครงงานคือการเปรียบเทียบกลยุทธ์ของ Redundancy โดยการใช้ Simulation จริงๆผมว่าจะกล่าวถึงเรื่องนี้หลังจากผมได้นำเสนอหัวข้ออื่นๆไปอีก 8 – 10 เรื่อง แต่ผมอดใจไม่ไหวครับ เพราะผมเพิ่งทำโครงงานนี้เสร็จไปเมื่อวานนี้เอง และผมก็ค้นพบอะไรที่น่าสนใจหลายเรื่องจากการวิจัยในครั้งนี้ และมีเรื่องหนึ่งที่ผมค้นพบ และได้รับคำชมจากอาจารย์ของผมว่าทำได้น่าประทับใจ (ขออวดนิดนึงนะครับ) เพราะถือเป็นการค้นพบครั้งใหม่ในศาสตร์ด้านนี้เลยครับ แต่ผมคงไม่ได้กล่าวในที่นี้ (อาจจะไปกล่าวใน conference ใดสักที่ก็ได้ครับ) โอเคครับ…คลิ้กเข้ามา มาอ่านว่าบทความนี้กล่าวถึง Redundancy ว่าอย่างไร
จริงๆหัวข้อนี้ไม่ได้เกี่ยวกับการโคลนนิ่ง (Cloning) จะเป็นโคลนแกะหรือโคลนคนก็ตามครับ แต่คำว่า Redundancy มีความหมายที่ใกล้เคียงกับคำว่า Cloning ผมจึงนำคำว่า Cloning มาเป็นหัวข้อของบทความนี้ครับ และมีภาพนายแบบมือสมัครเล่นมาเป็นภาพประกอบด้านบนด้วยครับ คำว่า Redundancy คือการทำความซ้ำซ้อน (หรือซ้ำซาก) ให้กับสรรพสิ่งอะไรสักอย่าง หากว่าคุณเคยได้ศึกษาวิชา Database มาแล้ว คุณคงเคยได้ยินคำว่า Redundancy มาบ้างแล้ว และคุณคงจะบอกได้เลยว่า Database เป็นหลักการที่ใช้ในการลด Redundancy ของข้อมูลดั่งที่เคยพบเจอในระบบที่ไม่มี Database อย่าง File Processing … แต่ทว่า ในบทความนี้ ไม่ได้เกี่ยวกับการลดความซ้ำซ้อนของข้อมูลในวิชา Database หากแต่ว่าผมจะกล่าวถึงกลยุทธ์ (Strategy) สำหรับเพิ่มความซ้ำซ้อนของข้อมูลครับ อ้าว! แล้วมันจะดีหรือ? ตอนเราเรียน Database เขาไม่อยากได้ Redundancy แล้วทำไมเราต้องไปดันทุรังเพิ่ม Redundancy ด้วย…แล้ว Redundancy มันดีอย่างไรหรือ?
เนื่องด้วยเนื้อหาเรื่อง Redundancy มีอยู่เยอะพอสมควรครับ ดังนั้น ผมจึงขอแบ่งเนื้อหาออกเป็นส่วนๆแล้วกันนะครับ ไม่งั้นผมคงต้องใช้เวลาในการแต่งบทความนานมากและคงไม่มีอะไรมาโพสต์ในเว็บ สำหรับเนื้อหาครั้งนี้เป็นภาคปฐมบทหรือภาค 1 ของ Redundancy ครับ
จากข้อมูลของ 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 ข้อดังนี้
หากเราทำ Redundancy ได้แล้ว เราก็ไม่ได้ Availability, Load Balancing และ Caching ทันทีหรอกครับ หรืออาจจะได้มาแต่ก็ไม่ได้คงอยู่ไปตลอดกาลหรอกครับ ดั่งคำสอนของพระพุทธเจ้า “ทุกขัง อนิจจัง อนัตตา” กฎไตรลักษณ์ ที่ว่าไม่มีสิ่งใดคงอยู่ยั่งยืนถาวร อย่างเช่น ในเรื่อง Availability หากว่าเรามีไฟล์ A จำนวน 100 แห่ง หากว่า 100 แห่งเกิดล่มไปพร้อมๆกัน เราก็คงไม่ได้มาซึ่ง Availability ของไฟล์ A อีกต่อไป แต่ก็กล่าวได้ว่ามี Avaiability ที่สูงกว่ามี A เก็บไว้แค่ 2 – 3 ที่ เป็นต้น ส่วน Load Balancing กับ Caching นั้น เราจะได้สิ่งเหล่านี้มาจำเป็นต้องอาศัยเทคนิคอื่นๆเข้ามาช่วยเสริมด้วย หรือมีเหตุการณ์บางอย่างเข้ามาสนับสนุนด้วย แต่ผมไม่ขอกล่าวไว้ในบทความนี้นะครับ ผมจะกล่าวเพียงกลยุทธ์ในการทำ Redundancy เท่านั้นครับ
เรามีกระบวนการ (process) สำหรับทำความซ้ำซ้อนให้กับไฟล์ได้ 2 แบบคือ
หากเราพิจารณาดีๆนะครับ 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 ชิ้น โดยไม่ต้องกังวลเลยว่ามันจะซ้ำกันหรือเปล่า เราก็สามารถประกอบไฟล์ต้นฉบับได้แล้ว
ในการพัฒนาระบบแบบ Redundancy จริงๆนั้น เราสามารถเพิ่มข้อมูลบางอย่าง (metadata) พ่วงไปกับ fragment แต่ละชิ้น เพื่อช่วยในการประกอบไฟล์ต้นฉบับ และยังช่วยในการตรวจสอบความถูกต้อง (Verification) โดยข้อมูลที่เราสามารถเพิ่มเข้าไปให้กับ fragment ได้แก่ Fragment ID, File ID, File Signature และ Timestamp เป็นต้น
เราไม่จำเป็นต้องใช้ 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 แล้วกัน
[1] http://en.wikipedia.org/wiki/Redundancy_%28engineering%29
[2] http://javaboom.wordpress.com/2008/03/26/piratep2p/
[3] http://wiki.freenetproject.org/FreenetZeroPointSevenKeys
ถึงออสละนะครับพี่เจอสาวสวยจากมอABAC~ด้วยแต่ดันมีแฟนแล้วแต่ไม่เป็นไรผมจะพยามครับแฟนครับไม่ใช่สามีฮรี่ๆ นอนเรื่องไปนิขอโทษด้วยจ้า
ขอบคุณมากครับ กระจ่างแล้ว ขอให้ออกภาค 2 เร็วๆนะครับ(จะเป็นไตรภาคหรือเปล่า ?)
ปล. ชอบรูปประกอบมากครับ ใช้อะไรทำเหรอครับ อยากรู้
เอางั้นเหรอครับ อิ ๆ ถ้าอยากรู้จักผมนะก็ mrsoowoi@hotmail.com แต่ผมไม่ค่อย online นะครับ
ปล. ไม่ต้องแปลกใจผมคนอุบลฯเหมือนกันครับ
สวัสดีครับ ผมอ่าน บทความอาจารย์อยู่เรื่อยๆนะครับ
แอบลุ้นให้ออกภาคที่สองเร็วๆ
ครับผม นศ ที่ส่งประกวดของ SIA2007 ครับ
ที่ได้ปรึกษาอาจารย์เรื่องการส่ง SMS ครับ ผมก้ตามอ่านของอาจารย์ แต่ไม่ได้คอมเม้นสักที
พอดี blog ผมทำเสร็จเลยได้คอมเม็นตามบล็อกต่างๆครับ
[...] ปัญหาดังกล่าวทำให้ผู้ใช้จำนวนมากหงุดหงิดกับการแก้ปัญหาของGoogle ส่งผลให้ลูกค้าไม่เชื่อถือในการให้บริการของGoogleและอาจจะเป็นเหตุให้ลูกค้าบางรายต้องหาทางเลือกอื่นจากผู้ให้บริการรายอื่นที่เป็นคู่แข่งของGoogleก็ได้ ลองอ่านตัวอย่างส่วนหนึ่งได้จาก Google Blasted Over Gmail, Google Apps Outages ผู้ใช้หลายคนโมโหมากเพราะปัญหา 502 เพราะทาง Google ใช้เวลากว่า 15 ชั่วโมงในการแก้ไข โดยปัญหามันเริ่มมาจากวันที่ 6 และ 7 สิงหาปัญหาก็หายไป แล้วก็มาเป็นอีกครั้งในวันที่ 12 สิงหา … จึงเกิดคำถามว่า ถ้า Gmail และ Google Apps อันเป็นบริการชูโรงของ Google ในการนำเสนอ Cloud Computing ของทางฝั่งGoogleมีปัญหาเช่นนี้ แล้วเราจะยังเชื่อถือ Cloud Computing ได้อีกหรือไม่? เพราะโดยหลักการของCloud Computingแล้ว มันควรจะมีความน่าเชื่อถือสูง และในกรณีของGoogleเองแล้วยิ่งไม่น่าจะเกิดเหตุการณ์502ได้เลย เพราะGoogleเองมีเซิร์ฟเวอร์ติดตั้งอยู่ทั่วโลกเกือบครึ่งล้านเครื่อง (ข้อมูลจาก Wikipdia ระบุไว้ว่ามีเซิร์ฟเวอร์กว่า 450,000 เครื่อง) และมีการใช้หลักการReplicationอันทำให้รับประกันความคงอยู่ของบริการได้สูง (High Availability) [...]
[...] Posted by javaboom on August 21, 2008 เมื่อเดือนพฤษภาคม พ.ศ.2551 บริษัท HP ได้ประกาศเปิดรับProposalเพื่อแข่งขันชิงทุนในการทำวิจัยภายใต้โครงการ HP Labs Innovation Research Program โดยหัวข้อวิจัยแบ่งออกเป็นหลายเรื่องด้วยกัน ในแต่ละภูมิภาคผู้เข้าแข่งขันต้องส่งงานวิจัยให้ตรงตามหัวข้อวิจัยที่บริษัทHPได้แบ่งไว้ตามโซน [อ้างอิง] และในวันที่ 14 สิงหาที่ผ่านมา HPก็ได้ประกาศผลและมอบรางวัล(นั่นคือทุนวิจัยปีละ $100,000) ให้กับอาจารย์ 41 ท่านจาก 34 มหาวิทยาลัย ส่วนใหญ่ก็เป็นมหาวิทยาลัยทางฝั่งสหรัฐอเมริกา สำหรับทางฝั่งเอเชียมีมหาลัยใน 6 ประเทศคือ จีน, อินเดีย, ญี่ปุ่น และสิงคโปร์ สำหรับมหาวิทยาลัยผมเองคือ Nangyang Technological University ที่สิงคโปร์ก็ติดอันดับในนั้นด้วย และอาจารย์ที่ได้รับรางวัลก็คือ Dr.Awitaman Datta ซึ่งเป็นอาจารย์ที่เพิ่งสอนผมในเทอมที่แล้ว และก็เป็นผู้ถ่ายทอดวิชาด้าน Peer-to-Peer และทำให้ผมได้เข้าใจกลยุทธ์ในการทำ Redundancy หลายๆแบบที่ผมเคยเขียนไว้ในหัวข้อ “Redundancy: มารู้จักวิธีการโคลนนิ่งกันเถอ…“ [...]
[...] center (หลักการ Redundancy) [...]
[...] เอ… ทำไมพวกเขาไม่ได้ทำ replication หรือ redundancy กันหรือ ? ไม่เป็นครับ [...]
April 20, 2008 at 3:35 pm
อ่านแล้วสงสัยครับ เรื่อง rateless code นั้น ที่บอกว่าเราต้องการรวบรวมชิ้นส่วนข้อมูลมาให้ได้เพียง M ชิ้นโดยไม่ต้องกังวลเลยว่ามันจะซ้ำกัน ก็สามารถประกอบขึ้นมาใหม่ได้ แต่ถ้ามันเกิดซ้ำกันล่ะครับ อะไรจะเกิดขึ้น (มีอะไรรับประกันได้ว่ามันจะไม่ซ้ำ ) แล้วชิ้นส่วน M ชิ้นที่ว่านี้ถ้ามันเป็นส่วนที่ไม่สามารถนำมารวมกันได้หรือเกิดความซ้ำซ้อน แบบ partial redundance จะทำอย่างไรครับ ขอความกรุณาช่วยตอบให้หายสงสัยทีครับ