การวิจัยหลักในบทความนี้คือรหัสอัลกอริทึมที่สอดคล้องกัน
อัลกอริทึมการแฮชที่สอดคล้องกันถูกเสนอโดย MIT ในปี 1997 (ดู 0) เป้าหมายการออกแบบคือการแก้ปัญหาฮอตพอตในอินเทอร์เน็ตและความตั้งใจดั้งเดิมนั้นคล้ายกับปลาคาร์พมาก การแฮชที่สอดคล้องกันแก้ไขปัญหาที่เกิดจากอัลกอริทึมการแฮชแบบง่ายที่ใช้โดยปลาคาร์พเพื่อให้ DHT สามารถนำไปใช้อย่างแท้จริงในสภาพแวดล้อม P2P
การแฮชที่สอดคล้องกันเสนอเงื่อนไขการปรับตัวสี่ประการที่อัลกอริทึมการแฮชควรพบในสภาพแวดล้อมแคชที่เปลี่ยนแปลงแบบไดนามิก:
ความสมดุลหมายความว่าผลลัพธ์ของแฮชสามารถแจกจ่ายไปยังแคชทั้งหมดให้มากที่สุดเท่าที่จะเป็นไปได้เพื่อให้สามารถใช้พื้นที่แคชทั้งหมดได้ อัลกอริทึมแฮชจำนวนมากสามารถปฏิบัติตามเงื่อนไขนี้ได้
Monotonity หมายถึงหากมีการส่งเนื้อหาบางอย่างไปยังแคชที่เกี่ยวข้องผ่านการแฮชและแคชใหม่จะถูกเพิ่มเข้าไปในระบบ ผลลัพธ์ของแฮชควรตรวจสอบให้แน่ใจว่าเนื้อหาที่จัดสรรดั้งเดิมสามารถแมปกับแคชใหม่โดยไม่ต้องแมปกับบัฟเฟอร์อื่น ๆ ในคอลเลกชันแคชเก่า
อัลกอริทึมการแฮชแบบง่ายมักจะไม่สามารถตอบสนองความต้องการของการ monotonicity เช่นแฮชเชิงเส้นที่ง่ายที่สุด:
x → ax + b mod (p)
ในสูตรข้างต้น P หมายถึงขนาดของแคชทั้งหมด ไม่ยากที่จะเห็นว่าเมื่อขนาดแคชเปลี่ยนไป (จาก P1 เป็น P2) ผลลัพธ์แฮชดั้งเดิมทั้งหมดจะเปลี่ยนไปดังนั้นจึงไม่เป็นไปตามข้อกำหนดของความซ้ำซากจำเจ
การเปลี่ยนแปลงผลลัพธ์แฮชหมายความว่าเมื่อพื้นที่แคชเปลี่ยนแปลงความสัมพันธ์การแมปทั้งหมดจะต้องได้รับการปรับปรุงในระบบ ในระบบ P2P การเปลี่ยนแปลงแคชนั้นเทียบเท่ากับการเข้าร่วมหรือออกจากระบบ สถานการณ์นี้เกิดขึ้นบ่อยครั้งในระบบ P2P ซึ่งจะนำมาซึ่งการคำนวณและการส่งสัญญาณขนาดใหญ่ ความน่าเบื่อต้องการให้อัลกอริทึมแฮชสามารถหลีกเลี่ยงสถานการณ์นี้ได้
ในสภาพแวดล้อมแบบกระจายเทอร์มินัลอาจไม่เห็นแคชทั้งหมด แต่สามารถมองเห็นบางส่วนเท่านั้น เมื่อเทอร์มินัลต้องการแมปเนื้อหากับแคชผ่านกระบวนการแฮชเนื่องจากช่วงแคชที่เห็นโดยเทอร์มินัลที่แตกต่างกันอาจแตกต่างกันผลลัพธ์ของการแฮชนั้นไม่สอดคล้องกัน ผลลัพธ์สุดท้ายคือเนื้อหาเดียวกันถูกแมปเข้ากับพื้นที่แคชที่แตกต่างกันโดยเทอร์มินัลที่แตกต่างกัน เห็นได้ชัดว่าสถานการณ์นี้ควรหลีกเลี่ยงเพราะมันทำให้เนื้อหาเดียวกันถูกเก็บไว้ในบัฟเฟอร์ที่แตกต่างกันลดประสิทธิภาพของการจัดเก็บระบบ คำจำกัดความของการกระจายเป็นความรุนแรงของสถานการณ์ข้างต้น อัลกอริทึมการแฮชที่ดีควรจะสามารถหลีกเลี่ยงความไม่สอดคล้องกันได้มากที่สุดนั่นคือเพื่อลดการกระจายตัว
ปัญหาการโหลดคือการดูปัญหาการกระจายอำนาจจากมุมมองอื่น เนื่องจากเทอร์มินัลที่แตกต่างกันอาจแมปเนื้อหาเดียวกันกับบัฟเฟอร์ที่แตกต่างกันสำหรับบัฟเฟอร์เฉพาะจึงอาจถูกแมปกับเนื้อหาที่แตกต่างกันโดยผู้ใช้ที่แตกต่างกัน เช่นเดียวกับการกระจายตัวสถานการณ์นี้ควรหลีกเลี่ยงดังนั้นอัลกอริทึมการแฮชที่ดีควรจะสามารถลดภาระบัฟเฟอร์ได้
บนพื้นผิวการแฮชที่สอดคล้องกันคือการกำหนดเป้าหมายปัญหาการบัฟเฟอร์แบบกระจาย แต่ถ้าคุณคิดว่าการบัฟเฟอร์เป็นเพียร์ในระบบ P2P และเนื้อหาที่แมปเป็นทรัพยากรที่ใช้ร่วมกันต่าง ๆ (ข้อมูลไฟล์สตรีมสื่อ ฯลฯ ) คุณจะพบว่าทั้งสองกำลังอธิบายปัญหาเดียวกัน
ในอัลกอริทึมการแฮชที่สอดคล้องกันแต่ละโหนด (สอดคล้องกับเพียร์ในระบบ P2P) มี ID ที่กำหนดแบบสุ่ม เมื่อการแมปเนื้อหาไปยังโหนดการดำเนินการแฮชที่สอดคล้องกันจะดำเนินการโดยใช้คำหลักของเนื้อหาและ ID ของโหนดและรับค่าคีย์ การแฮชที่สอดคล้องกันต้องการให้ค่าคีย์และโหนด ID อยู่ในช่วงค่าเดียวกัน ค่าคีย์ที่ง่ายที่สุดและ ID สามารถเป็นหนึ่งมิติเช่นชุดของจำนวนเต็มตั้งแต่ 0000 ถึง 9999
เมื่อจัดเก็บเนื้อหาตามค่าคีย์เนื้อหาจะถูกเก็บไว้ในโหนดโดยมี ID ใกล้เคียงกับค่าคีย์มากที่สุด ตัวอย่างเช่นหากค่าคีย์คือ 1001 มีโหนดที่มี ID 1000, 1010, 1100 ในระบบและเนื้อหาจะถูกแมปกับ 1,000 โหนด
ในการสร้างเส้นทางที่จำเป็นสำหรับการสืบค้นแฮชความสอดคล้องต้องการแต่ละโหนดเพื่อจัดเก็บข้อมูลตำแหน่ง (ที่อยู่ IP) ของโหนดอัปลิงค์ (ค่า ID มีค่ามากกว่าที่เล็กที่สุดในโหนดของตัวเอง) และโหนด Downlink (ค่า ID น้อยกว่าที่ใหญ่ที่สุดในโหนดของตัวเอง) เมื่อโหนดต้องการค้นหาเนื้อหาก็สามารถตัดสินใจที่จะเริ่มคำขอแบบสอบถามไปยังโหนดอัปลิงค์หรือดาวน์ลิงก์ตามค่าคีย์ของเนื้อหา หากโหนดที่ได้รับการร้องขอแบบสอบถามพบว่ามีเป้าหมายที่ร้องขอจะสามารถส่งคืนการยืนยันโดยตรงไปยังโหนดที่เริ่มร้องขอการสืบค้น หากพบว่ามันไม่ได้อยู่ในขอบเขตของตัวเองก็สามารถส่งต่อคำขอไปยังโหนดอัปลิงค์/ดาวน์ลิงก์ได้
เพื่อรักษาข้อมูลการกำหนดเส้นทางที่กล่าวถึงข้างต้นเมื่อโหนดเข้าร่วม/ออกจากระบบโหนดที่อยู่ติดกันจะต้องอัปเดตข้อมูลการกำหนดเส้นทางในเวลาที่เหมาะสม สิ่งนี้ต้องการให้โหนดไม่เพียง แต่เก็บข้อมูลตำแหน่งโหนดดาวน์ลิงก์โดยตรง แต่ยังรู้ข้อมูลโหนด downlink ทางอ้อมที่ระดับความลึก (N-HOP) ทางอ้อมและรักษารายการโหนดแบบไดนามิก เมื่อโหนดออกจากระบบโหนดอัปลิงค์จะพยายามเชื่อมต่อโดยตรงกับโหนด downlink ที่ใกล้ที่สุด หลังจากการเชื่อมต่อสำเร็จจะได้รับรายการโหนด Downlink จากโหนด Downlink ใหม่และอัปเดตรายการโหนดของตัวเอง ในทำนองเดียวกันเมื่อมีการเพิ่มโหนดใหม่ลงในระบบก่อนอื่นให้ค้นหาโหนด downlink ตาม ID ของตัวเองและรับรายการโหนด downlink จากนั้นขอให้โหนดอัปลิงค์ปรับเปลี่ยนรายการโหนด downlink ดังนั้นจึงกู้คืนความสัมพันธ์การกำหนดเส้นทาง
หารือ
แฮชที่สอดคล้องกันโดยทั่วไปแก้ปัญหาที่สำคัญที่สุดในสภาพแวดล้อม P2P - วิธีการกระจายการจัดเก็บและการกำหนดเส้นทางในโทโพโลยีเครือข่ายแบบไดนามิก แต่ละโหนดจะต้องรักษาข้อมูลของโหนดใกล้เคียงจำนวนน้อยและเมื่อโหนดเข้าร่วม/ออกจากระบบมีเพียงโหนดที่เกี่ยวข้องจำนวนน้อยเท่านั้นที่มีส่วนร่วมในการบำรุงรักษาทอพอโลยี ทั้งหมดนี้ทำให้แฮชที่สอดคล้องกันเป็นอัลกอริทึม DHT ที่ใช้งานได้จริงครั้งแรก
อย่างไรก็ตามอัลกอริทึมการกำหนดเส้นทางของการแฮชที่สอดคล้องกันยังคงมีข้อบกพร่อง ในระหว่างกระบวนการสืบค้นข้อความแบบสอบถามจะต้องผ่านขั้นตอน o (n) (o (n) หมายถึงความสัมพันธ์ตามสัดส่วนกับ n และ n หมายถึงจำนวนทั้งหมดของโหนดในระบบ) ก่อนที่จะถึงโหนดการสืบค้น ไม่ยากเลยที่จะจินตนาการว่าเมื่อระบบมีขนาดใหญ่มากจำนวนโหนดอาจเกินหนึ่งล้านและประสิทธิภาพการสืบค้นดังกล่าวก็ยากที่จะตอบสนองความต้องการการใช้งาน จากมุมมองอื่นแม้ว่าผู้ใช้จะสามารถทนต่อความล่าช้าได้นานข้อความจำนวนมากที่สร้างขึ้นในระหว่างกระบวนการสืบค้นจะนำโหลดที่ไม่จำเป็นไปยังเครือข่าย
แพ็คเกจ herotrix; นำเข้า java.util.collection; นำเข้า java.util.sortedMap นำเข้า java.util.treemap; คลาสสาธารณะประกอบด้วย {t> {// hash อัลกอริทึมส่วนตัวสุดท้าย hashfunction hashfunction; // จำนวนของโหนดเสมือนจริง t> (); Public Compaseenthash (hashfunction hashfunction, int numberofreplicas, คอลเลกชัน <t> โหนด) {this.hashfunction = hashfunction; this.numberofreplicas = numberofreplicas; สำหรับ (t node: โหนด) {add (node);}} โมฆะสาธารณะเพิ่ม (t node) {สำหรับ (int i = 0; i <numberofreplicas; i ++) {circle.put (hashfunction.hash (node.toString ()+i), node); i ++) {circle.remove (hashfunction.hash (node.toString ()+i));}} // อัลกอริทึมคีย์สาธารณะรับ (ปุ่มวัตถุ) {ถ้า (circle.isempty ()) {return null; if (! circle.containskey (hash)) {sortedmap <จำนวนเต็ม, t> tailmap = circle.tailmap (แฮช); hash = tailmap.isempty ()? circle.firstkey (): tailmap.firstkey ();} return circle.get (แฮช);}}ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับภาษา Java ที่สอดคล้องกัน Hash Algorithm Notes (ตัวอย่างรหัส) ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!