If you think about what we are tryi

If you think about what we are trying to do at a high level, there are two questions to consider: (1) How do we map objects onto nodes, and (2) How do we route a request to the node that is responsible for a given object? We start with the first question, which has a simple statement: How do we map an object with name x into the address of some node n that is able to serve that object? While traditional peer-to-peer networks have no control over which node hosts object x, if we could control how objects get distributed over the network, we might be able to do a better job of finding those objects at a later time.
A well-known technique for mapping names into an address is to use a hash table, so that
hash(x) −−→n
implies object x is first placed on node n, and at a later time a client trying to locate x would only have to perform the hash of x to determine that it is on node n. A hash-based approach has the nice property that it tends to spread the objects evenly across the set of nodes, but straightforward hashing algorithms suffer from a fatal flaw: How many possible values of n should we allow? (In hashing terminology, how many buckets should there be?) Naively, we could decide that there are, say, 101 possible hash values, and we use a modulo hash function; that is,
hash(x)
return x % 101
Unfortunately, if there are more than 101 nodes willing to host objects, then we can’t take advantage of all of them. On the other hand, if we select a number larger than the largest possible number of nodes, then there will be some values of x that will hash into an address for a node that does not exist. There is also the not-so-small issue of translating the value returned by the hash function into an actual IP address.
To address these issues, structured peer-to-peer networks use an algorithm known as consistent hashing, which hashes a set of objects x uniformly across a large ID space. Figure 9.25 visualizes a 128-bit ID space as a circle, where we use the algorithm to place both objects
hash(object name) −−→objid
and nodes
hash(IP addr) −−→nodeid

ผลลัพธ์ (ไทย) 1:

ถ้าคุณคิดว่า เกี่ยวกับสิ่งที่เรากำลังพยายามทำในระดับสูง มีสองคำถามในการพิจารณา: (1) วิธีเราแผนที่วัตถุบนโหน และ (2) วิธีทำเรากระบวนผลิตคำโหนที่รับผิดชอบสำหรับวัตถุที่กำหนดหรือไม่ เราเริ่มต้น ด้วยคำถามแรก ซึ่งมีคำสั่งอย่างง่าย: วิธีเราแมปวัตถุที่ มีชื่อ x เป็นอยู่ของ n บางโหนที่สามารถให้บริการ ในขณะที่โหนโฮสต์วัตถุควบคุมไม่มีเครือข่ายแบบเพียร์ทูเพียร์ x ถ้าเราสามารถควบคุมวิธีที่วัตถุได้รับกระจายเครือข่าย เราอาจจะสามารถทำงานดีกว่าการหาวัตถุเหล่านั้นในภายหลังได้จะใช้ตารางแฮ เทคนิครู้จักชื่อแมปไปยังอยู่นั้นhash(x) −−→nหมายถึงวัตถุ x ก่อนวางบนโหนด n และในภายหลังที่ไคลเอ็นต์พยายามที่จะค้นหา x จะมีเพียงการแฮ x ว่า ไม่บนโหนด n วิธีการแฮชโดยมีคุณสมบัติดี ที่จะมีแนวโน้มการกระจายวัตถุผ่านชุดของโหนด อัลกอริทึม hashing ตรงประสบปัญหาร้ายแรง: n จำนวนค่าที่ได้ควรเราอนุญาต (ในการ hashing ศัพท์ จำนวนกลุ่มควรมี) Naively เราได้ตัดสินใจว่า มี ว่า 101 ค่าแฮชที่ได้ และเราใช้การ modulo ฟังก์ชันแฮช นั่นก็คือhash(x)คืน x % 101อับ มีโหนมากกว่า 101 ยินดีวัตถุโฮสต์ แล้วเราไม่สามารถใช้ประโยชน์จากของพวกเขาทั้งหมด ในทางกลับกัน ถ้าเราเลือกตัวเลขที่มากกว่าจำนวนโหนที่ใหญ่ที่สุดที่เป็นไปได้ แล้วจะมีค่าบางค่าของ x ที่จะแฮชเป็นอยู่สำหรับโหนที่มีอยู่ นอกจากนี้ยังมีปัญหาไม่ให้เล็กการแปลค่าที่ส่งกลับ โดยฟังก์ชันแฮชเป็นอยู่ IP จริง ปัญหาเหล่านี้ เครือข่ายเพียร์ทูเพียร์โครงการอัลกอริทึมเป็นการ hashing สม่ำเสมอ ซึ่ง hashes ชุดของวัตถุ x ในช่อง ID ใหญ่สม่ำเสมอเมื่อเทียบเคียง รูป 9.25 visualizes ช่องรหัส 128 บิตเป็นวงกลม ที่เราใช้อัลกอริทึมการวางวัตถุทั้งสอง−−→objid แฮ (ชื่อวัตถุ)และโหน−−→nodeid แฮ (อยู่ IP)

ผลลัพธ์ (ไทย) 2:

ถ้าคุณคิดว่าสิ่งที่เรากำลังพยายามที่จะทำในระดับสูงมีสองคำถามที่จะต้องพิจารณาคือ (1) เราทำแผนที่วัตถุวิธีบนโหนดและ (2) เส้นทางที่เราทำวิธีการร้องขอไปยังโหนดที่มีหน้าที่รับผิดชอบ วัตถุที่กำหนดหรือไม่ เราเริ่มต้นด้วยคำถามแรกที่มีคำสั่งที่เรียบง่าย: วิธีการที่เราทำแผนที่วัตถุที่มีชื่อ x เข้าไปอยู่ของโหนด n บางอย่างที่สามารถให้บริการวัตถุที่? ในขณะที่เครือข่ายแบบ peer-to-peer แบบดั้งเดิมไม่มีการควบคุมมากกว่าที่โฮสต์โหนดวัตถุ x, ถ้าเราสามารถควบคุมวิธีการที่วัตถุที่ได้รับการกระจายผ่านเครือข่ายที่เราอาจจะสามารถทำผลงานที่ดีขึ้นในการหาวัตถุเหล่านั้นในเวลาต่อมา.
ดี
เทคนิคที่รู้จักกันสำหรับชื่อการทำแผนที่เป็นอยู่คือการใช้ตารางแฮชเพื่อให้กัญชา(x) - → n
หมายถึง x วัตถุถูกวางไว้เป็นครั้งแรกใน n โหนดและในเวลาต่อมาลูกค้าพยายามหา x จะมีเพียง เพื่อดำเนินการแฮชของ x เพื่อตรวจสอบว่ามันบนโหนด n วิธีการที่ใช้กัญชามีคุณสมบัติที่ดีที่ว่ามันมีแนวโน้มที่จะแพร่กระจายวัตถุสม่ำเสมอทั่วชุดของโหนด แต่ขั้นตอนวิธีการคร่ำเครียดตรงไปตรงมาทนทุกข์ทรมานจากข้อบกพร่องร้ายแรง: วิธีการที่เป็นไปได้หลายค่าของ n ที่เราควรจะช่วยให้? (ใน hashing ศัพท์กี่ถังควรจะมี?) อย่างไร้เดียงสาเราสามารถตัดสินใจได้ว่ามีการพูดค่าแฮชที่เป็นไปได้ 101 และเราจะใช้ฟังก์ชั่นแบบโมดูโลแฮช; นั่นคือแฮช (x) กลับมา x 101% แต่ถ้ามีมากกว่า 101 โหนดยินดีที่จะเป็นเจ้าภาพวัตถุแล้วเราไม่สามารถใช้ประโยชน์จากทั้งหมดของพวกเขา ในทางกลับกันถ้าเราเลือกหมายเลขที่มีขนาดใหญ่กว่าจำนวนที่เป็นไปได้ที่ใหญ่ที่สุดของโหนดแล้วจะมีบางส่วนของค่า x ที่จะสับลงในที่อยู่สำหรับโหนดที่ไม่ได้อยู่ นอกจากนี้ยังมีปัญหาที่ไม่ให้เล็ก ๆ แปลค่าส่งกลับโดยฟังก์ชันแฮชเข้าไปในที่อยู่ IP ที่เกิดขึ้นจริง. เพื่อแก้ไขปัญหาเหล่านี้มีโครงสร้างเครือข่ายแบบ peer-to-peer ใช้วิธีที่เรียกว่าคร่ำเครียดสอดคล้องซึ่ง hashes ชุดของ วัตถุ x สม่ำเสมอทั่วพื้นที่ ID ขนาดใหญ่ รูปที่ 9.25 visualizes พื้นที่รหัส 128 บิตเป็นวงกลมที่เราใช้อัลกอริทึมที่จะวางวัตถุทั้งแฮช(ชื่อวัตถุ) - → ObjId และโหนดกัญชา (IP addr) - → nodeid

ผลลัพธ์ (ไทย) 3:

ถ้าคุณคิดเกี่ยวกับสิ่งที่เรากำลังพยายามทำอยู่ในระดับสูง มี 2 คำถามที่ต้องพิจารณา ( 1 ) อย่างไรเราแผนที่วัตถุไปยังโหนด และ ( 2 ) วิธีการทำเราเส้นทางการร้องขอไปยังโหนดที่เป็นผู้รับผิดชอบสำหรับการคัดค้าน ? เราเริ่มคำถามแรก ซึ่งมีข้อความง่าย : วิธีการทำเราแผนที่วัตถุที่มีชื่อ X เป็นที่อยู่ของโหนด n ที่สามารถใช้วัตถุที่ในขณะที่เครือข่ายแบบดั้งเดิมไม่มีการควบคุมที่โหนดโยธาวัตถุ x ถ้าเราสามารถควบคุมวิธีการที่วัตถุได้รับการกระจายผ่านเครือข่าย เราก็อาจจะไม่ได้งานที่ดีขึ้นของการค้นหาวัตถุเหล่านั้นในเวลาต่อมา .
ที่รู้จักกันดีชื่อแผนที่เป็นเทคนิคที่อยู่คือการใช้ตารางแฮช ดังนั้น
กัญชา ( X ) −−→ n
หมายถึงวัตถุ x เป็นครั้งแรกที่วางอยู่บนโหนด nและในเวลาต่อมาลูกค้าพยายามหา x จะต้องดําเนินการ hash ของ X เพื่อตรวจสอบว่ามันเป็นปมอันแฮ วิธีการที่ใช้ มี ดี คุณสมบัติ มันมีแนวโน้มที่จะกระจายวัตถุเท่ากันทั่วชุดของโหนด แต่ตรงไปตรงมา hashing ขั้นตอนวิธีประสบจากข้อบกพร่องร้ายแรง : วิธีการหลายที่สุดค่า ของพวกเราให้ ? ( แฮชคำศัพท์กี่ถังควรมี ? ) ยัง เราสามารถตัดสินใจว่า , พูด , 101 ได้รับค่ากัญชา และเราใช้แฮชฟังก์ชันมอดุโล นั่นคือ กัญชา ( x )

กลับมา x% 101
ขออภัยหากมีมากกว่า 101 โหนดจะโฮสต์วัตถุ เราก็ไม่สามารถใช้ประโยชน์จากทั้งหมดของพวกเขา ในทางกลับกัน ถ้าเราเลือกหมายเลขที่มีขนาดใหญ่กว่าที่สุดจำนวนของโหนด ,แล้วจะมีค่าของ X จะสับลงที่อยู่สำหรับโหนดที่ไม่มีอยู่จริง นอกจากนี้ยังมีไม่เล็กเพื่อให้ปัญหาของการแปลคุ้มค่าที่ส่งกลับโดยฟังก์ชัน hash เป็น IP จริง
เพื่อแก้ไขปัญหาเหล่านี้ โครงสร้างเครือข่ายเพียร์ - ใช้ขั้นตอนวิธี hashing เรียกว่าสอดคล้องกันซึ่ง hashes ชุดของวัตถุ x อย่างสม่ำเสมอทั่วพื้นที่ ไอดีใหญ่รูปที่ 13 ทั้ง 128 บิตรหัสพื้นที่เป็นวงกลม ซึ่งเราใช้วิธีวางทั้งวัตถุ
กัญชา ( ชื่อวัตถุและปม

) −−→ objid แฮก IP ( บาป ) −−→ nodeid