P2P: Chord protocol
ทบทวนเรื่อง P2P Chord #CSW
Chord เป็น P2P Lookup protocol แบบหนึ่ง สำหรับ P2P distributed hash table (DHT) ที่มีการเชื่อมต่อระบบเครือข่าย เสมือนเป็น overlay network (หรือมองเป็น logical network อีก layer) และสามารถ route ข้อมูลถึงกันผ่าน finger table ได้
Chord มีการใช้ hash function ในการแปลงค่า (เช่น ชื่อไฟล์, URL, IP) ให้กลายเป็นตัวเลข
เช่น sha(192.168.1.1) = 0xcafe40103418d96eef6e36a92cf0c202092adc62981
เมื่อได้ข้อมูลเป็นตัวเลข ก็สามารถที่จะเรียงลำดับข้อมูลได้ เมื่อจัดลำดับได้ ก็จะสามารถใช้ Binary Search ทำให้ ความเร็วในการค้นหาข้อมูลเร็วขึ้นในระดับ O(log N)
เริ่มต้น ต้องกำหนด Chord address space ว่าจะใช้กี่บิต ในกรณีเพื่อให้ง่ายแต่การอธิบายของใช้เพียง 3 บิต และวาดออกมาเป็น Chord-ring ได้ดังนี้
สมมติว่าโหนด N0 หมายเลข IP 147.127.240.72 และได้ share ไฟล์ s1.mp3 กับ s2.mp3 ส่วนโหนดอื่น ๆ ก็ตามรูป
Map resources to ID
ขั้นตอนของ Chord P2P จะต้องทำการแปลง resource ทั้งหมด ให้กลายเป็นหมายเลขโดย hash function (SHA-1) สมมุติว่าแปลงออกมาได้ดังนี้
ขั้นตอนต่อไปคือการ map ค่าของโหนดกับ ไฟล์ที่จะ share ตามทิศทาง ตามเข็มนาฬิกา โดย โหนด จะรับผิดชอบ “ให้ข้อมูล” ที่อยู่ ของ shared resources ที่อยู่ก่อนหน้าตัวเองเท่านั้น (ในที่วงเอาไว้) ดังรูป ขอย้ำว่าเฉพาะที่อยู่ ไม่ใช่ตัว content จริง ๆ
Node responsibility
- โหนด N0 อยู่ที่ตำแหน่ง K0 จะทราบว่า K7 อยู่ที่ไหน
- โหนด N3 อยู่ที่ตำแหน่ง K3 จะทราบว่า K1 และ K2 อยู่ที่ไหน
- โหนด N6 อยู่ที่ตำแหน่ง K6 จะทราบว่า K4 และ K5 อยู่ที่ไหน
Finger table
ถ้าไม่มี finger table การค้นหาข้อมูลก็จะต้องไล่ไปทีละโหนดที่อยู่ติดกัน ตามเข็มนาฬิกา ซึ่งจะไม่ได้ความเร็วที่ O(logN) ดังนั้น จะต้องสร้าง finger table มาช่วยดังนี้
การสร้าง finger table ใช้วิธีการนำค่า node id + 2^bit (ตั้งแต่ 0 ถึง n-1) ในกรณีนี้ ใช้ 3 บิต
ที่โหนด N0
- รับผิดชอบค่า K7 ทราบว่า K7 เก็บอยู่ที่ไหน แต่ถ้าเป็นค่าอื่น ๆ ต้องใช้ finger table ในการถามโหนดอื่น
- จากตาราง finger table ต้องการหาค่า K1 ให้ถาม N3, หาค่า K2-K3 ให้ถาม N3, หาค่า K4 และอื่น ๆ ให้ถาม N6
ที่โหนด N3
- รับผิดชอบค่า K1, K2 ทราบว่า K1, K2 เก็บอยู่ที่ไหน แต่ถ้าเป็นค่าอื่น ๆ ต้องใช้ finger table ในการถามโหนดอื่น
- จากตาราง finger table ต้องการหาค่า K4 ให้ถาม N6, หาค่า K5-K6 ให้ถาม N6, หาค่า K7 และอื่น ๆ ให้ถาม N0
ที่โหนด N6
- รับผิดชอบค่า K4, K5 ทราบว่า K4, K5 เก็บอยู่ที่ไหน แต่ถ้าเป็นค่าอื่น ๆ ต้องใช้ finger table ในการถามโหนดอื่น
- จากตาราง finger table ต้องการหาค่า K7 ให้ถาม N0, หาค่า K0-K1 ให้ถาม N0, หาค่า K2 และอื่น ๆ ให้ถาม N3
ทดลองใช้งาน
ตัวอย่าง 1: ต้องการค้นหาค่า prg.exe โดยเริ่มหาที่ N3
- สมมติว่าแปลงค่า prg.exe => ได้เป็น K7
- N3 รับผิดชอบเฉพาะ K1 กับ K2 (รู้ที่อยู่ของ K1 กับ K2 เก็บอยู่ที่ไหน) ซึ่งไม่มี K7 ดังนั้น N3 จึงต้องส่งข้อมูลต่อ โดยใช้ตาราง finger table
- ใช้ตาราง finger table ของ N3 ค่า K7 ต้องไปถาม N0
- N0 รับผิดชอบ K7 อยู่ จึงตอบ N3 โดยตรงได้ว่าไฟล์ K7 อยู่ที่ N6 (ส่งที่อยู่ของ N6 ที่เก็บ prg.exe)
- N3 โหลดไฟล์ prg.exe จาก N6 ได้
จะเห็นได้ว่า N3 ถาม N0 ข้าม N6 และได้คำตอบเลย ถ้ามี โหนด อยู่ในคอร์ดริง เยอะ ๆ ก็จะข้ามจำนวนโหนดในคอร์ดริง ได้ทีละ ครึ่ง ทำให้ค้นหาข้อมูลได้เร็วขึ้นกว่าเดิม
ตัวอย่าง 2: ต้องการค้นหาค่า d1.doc โดยเริ่มหาที่ N6
- สมมติว่าแปลงค่า d1.doc => ได้เป็น K2
- N6 รับผิดชอบเฉพาะ K4 กับ K5 ซึ่งไม่มี K2 ดังนั้น N6 จึงต้องส่งข้อมูลต่อ โดยใช้ตาราง finger table
- จากตาราง finger table ของ N6 ค่า K2 ต้องไปถาม N3
- N3 รับผิดชอบ K2 อยู่ จึงตอบ N6 โดยตรงได้ว่าไฟล์ K7 อยู่ที่ N3 (ตัวเอง)
- N6 โหลดไฟล์ d1.doc จาก N3
ข้อจำกัด
- การ map key-value โดยใช้ hash นั้นจะเป็นแบบตรงตัว ข้อความคล้ายกัน ผลการ hash จะไม่มีสัมพันธ์กัน เช่น หาค่า s1.mp หากแปลงโดยใช้ค่า hash(s1.mp3) ผลจะแตกต่างจาก hash(s1) ซึ่งไม่สามารถใช้ wildcard ได้ อาจจะต้อง map key ไว้หลาย ๆ แบบ เพื่อให้ค้นหาค่าเจอ
- hash function ที่ใช้ จะต้องมีการกระจายตัวของค่าที่ผ่าน hash function ที่ดี เพื่อให้ค่าไม่ไปกระจุกอยู่ที่ใดที่หนึ่ง เพื่อให้การค้นหาทำได้รวดเร็ว มีการกระจายโหลด
- ค่า address space จะต้องกว้างมากพอ เพื่อรองรับจำนวน resources ที่จะ share ร่วมกัน รวมถึงป้องกัน การชนกัน จากผลการ hash ที่เกิดขึ้นได้ ในทางปฏิบัติ จะใช้ ที่ 160 บิต address space
