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,
thenwe can’t take advantage of all of them.On the other hand, ifwe 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 ที่เต็มใจที่จะโฮสต์วัตถุthenwe ไม่สามารถใช้ประโยชน์จากพวกเขาทั้งหมด บนมืออื่น ๆ เลือก ifweจำนวนมากกว่าจำนวนโหน ใหญ่ที่สุดที่เป็นไปได้แล้วมีจะมีบางค่าของ x ที่จะแฮชเป็นอยู่สำหรับโหนดที่ไม่ได้มีอยู่ นอกจากนี้ยังมีเรื่องไม่ให้เล็กแปลมาฟังก์ชันแฮชเป็นอยู่ IP จริงปัญหาเหล่านี้ เครือข่ายเพียร์ทูเพียร์โครงสร้างใช้อัลกอริทึมการหรือที่เรียกว่า hashing สม่ำเสมอ ซึ่ง hashes ชุดของวัตถุ x สม่ำเสมอเมื่อเทียบเคียงข้ามรหัสที่กว้างขวางขึ้น รูป 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 โหนดยินดีที่จะเป็นเจ้าภาพวัตถุthenwe ไม่สามารถใช้ประโยชน์ทั้งหมดของ them.On มืออื่น ๆ , ifwe เลือกจำนวนขนาดใหญ่กว่าที่ใหญ่ที่สุดที่เป็นไปได้จำนวนโหนดแล้วจะเป็นบางส่วนของค่า 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 ขั้นตอนวิธีประสบจากข้อบกพร่องร้ายแรง : วิธีการหลายที่สุดค่า
n จะอนุญาตไหม ( แฮชศัพท์กี่ถังควร
มี ? ) ยัง เราสามารถตัดสินใจว่า , พูด , 101 เป็นไปได้กัญชา
ค่า และเราใช้แฮชฟังก์ชันมอดุโล นั่นคือ กัญชา ( x )

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

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