4.5 Scaling GeographicallyThe leade

4.5 Scaling Geographically
The leader and followers configuration allows TAO to
scale to handle a high workload, since read throughput
scales with the total number of follower servers in all
tiers. Implicit in the design, however, is the assumption
that the network latencies from follower to leader and
leader to database are low. This assumption is reasonable
if clients are restricted to a single data center, or even to
a set of data centers in close proximity. It is not true,
however, in our production environment.
As our social networking application’s computing and
network requirements have grown, we have had to expand
beyond a single geographical location: today, follower
tiers can be thousands of miles apart. In this configuration,
network round trip times can quickly become
the bottleneck of the overall architecture. Since read
misses by followers are 25 times as frequent as writes in
our workloads, we chose a master/slave architecture that
requires writes to be sent to the master, but that allows
read misses to be serviced locally. As with the leader/-
follower design, we propagate update notifications asynchronously to maximize performance and availability, at the expense of data freshness.
The social graph is tightly interconnected; it is not possible
to group users so that cross-partition requests are
rare. This means that each TAO follower must be local
to a tier of databases holding a complete multi-petabyte
copy of the social graph. It would be prohibitively expensive to provide full replicas in every data center.
Our solution to this problem is to choose data center
locations that are clustered into only a few regions, where
the intra-region latency is small (typically less than 1 millisecond).
It is then sufficient to store one complete copy
of the social graph per region. Figure 2 shows the overall
architecture of the master/slave TAO system.
Followers behave identically in all regions, forwarding
read misses and writes to the local region’s leader tier.
Leaders query the local region’s database regardless of
whether it is the master or slave. Writes, however, are
forwarded by the local leader to the leader that is in the
region with the master database. This means that read
latency is independent of inter-region latency.
The master region is controlled separately for each
shard, and is automatically switched to recover from the
failure of a database. Writes that fail during the switch
are reported to the client as failed, and are not retried.
Note that since each cache hosts multiple shards, a server
may be both a master and a slave at the same time. We
prefer to locate all of the master databases in a single region. When an inverse association is mastered in a different region, TAO must traverse an extra inter-region link to forward the inverse write.
TAO embeds invalidation and refill messages in the
database replication stream. These messages are delivered in a region immediately after a transaction has been replicated to a slave database. Delivering such messages earlier would create cache inconsistencies, as reading from the local database would provide stale data. At Facebook TAO and memcache use the same pipeline for delivery of invalidations and refills [21].
If a forwarded write is successful then the local leader
will update its cache with the fresh value, even though
the local slave database probably has not yet been updated by the asynchronous replication stream. In this
case followers will receive two invalidates or refills from
the write, one that is sent when the write succeeds and
one that is sent when the write’s transaction is replicated
to the local slave database.
TAO’s master/slave design ensures that all reads can
be satisfied within a single region, at the expense of potentially returning stale data to clients. As long as a user
consistently queries the same follower tier, the user will
typically have a consistent view of TAO state. We discuss
exceptions to this in the next section.
5 Implementation
Previous sections describe how TAO servers are aggregated to handle large volumes of data and query rates. This section details important optimizations for performance
and storage efficiency.
5.1 Caching Servers
TAO’s caching layer serves as an intermediary between
clients and the databases. It aggressively caches objects
and associations to provide good read performance.
TAO’s memory management is based on Facebook’s
customized memcached, as described by Nishtala et
al. [21]. TAO has a slab allocator that manages slabs of
equal size items, a thread-safe hash table, LRU eviction
among items of equal size, and a dynamic slab rebalancer
that keeps the LRU eviction ages similar across all types
of slabs. A slab item can hold one node or one edge list.
To provide better isolation, TAO partitions the available
RAM into arenas, selecting the arena by the object
or association type. This allows us to extend the cache
lifetime of important types, or to prevent poor cache citizens from evicting the data of better-behaved types. So
far we have only manually configured arenas to address
specific problems, but it should be possible to automatically
size arenas to improve TAO’s overall hit rate.
For small fixed-size items, such as association counts,
the memory overhead of the pointers for bucket items in
the main hash table becomes significant. We store these
items separately, using direct-mapped 8-way associative
caches that require no pointers. LRU order within each bucket is tracked by simply sliding the entries down. We
achieve additional memory efficiency by adding a table
that maps the each active atype to a 16 bit value. This
lets us map (id1, atype) to a 32-bit count in 14 bytes; a
negative entry, which records the absence of any id2 for
an (id1, atype), takes only 10 bytes. This optimization
allows us to hold about 20% more items in cache for a
given system configuration.
5.2 MySQL Mapping
Recall that we divide the space of objects and associations
into shards. Each shard is assigned to a logical
MySQL database that has a table for objects and a table
for associations. All of the fields of an object are serialized
into a single ‘data‘ column. This approach allows
us to store objects of different types within the same table,
Objects that benefit from separate data management
polices are stored in separate custom tables.
Associations are stored similarly to objects, but to support
range queries, their tables have an additional index
based on id1, atype, and time. To avoid potentially expensive
SELECT COUNT queries, association counts
are stored in a separate table.
5.3 Cache Sharding and Hot Spots
Shards are mapped onto cache servers within a tier using
consistent hashing [15]. This simplifies tier expansions
and request routing. However, this semi-random assignment
of shards to cache servers can lead to load imbalance:
some followers will shoulder a larger portion of
the request load than others. TAO rebalances load among
followers with shard cloning, in which reads to a shard
are served by multiple followers in a tier. Consistency
management messages for a cloned shard are sent to all
followers hosting that shard.
In our workloads, it is not uncommon for a popular
object to be queried orders of magnitude more often than
other objects. Cloning can distribute this load across
many followers, but the high hit rate for these objects
makes it worthwhile to place them in a small client-side
cache. When a follower responds to a query for a hot
item, it includes the object or association’s access rate.
If the access rate exceeds a certain threshold, the TAO
client caches the data and version. By including the version
number in subsequent queries, the follower can omit
the data in replies if the data has not changed since the
previous version. The access rate can also be used to
throttle client requests for very hot objects.
5.4 High-Degree Objects
Many objects have more than 6,000 associations with the
same atype emanating from them, so TAO does not cache
the complete association list. It is also common that assoc
get queries are performed that have an empty result
(no edge exists between the specified id1 and id2). Unfortunately, for high-degree objects these queries will always go to the database, because the queried id2 could
be in the uncached tail of the association list.
We have addressed this inefficiency in the cache implementation by modifying client code that is observed
to issue problematic queries. One solution to this problem
is to use assoc count to choose the query direction,
since checking for the inverse edge is equivalent. In
some cases where both ends of an edges are high-degree
nodes, we can also leverage application-domain knowledge to improve cacheability. Many associations set the time field to their creation time, and many objects include their creation time as a field. Since an edge to a
node can only be created after the node has been created,
we can limit the id2 search to associations whose time
is ≥ than the object’s creation time. So long as an edge
older than the object is present in cache then this query
can be answered directly by a TAO follower.

6 Consistency and Fault Tolerance
Two of the most important requirements for TAO are
availability and performance. When failures occur we
would like to continue to render Facebook, even if the
data is stale. In this section, we describe the consistency
model of TAO under normal operation, and how TAO
sacrifices consistency under failure modes.
6.1 Consistency
Under normal operation, objects and associations in TAO
are eventually consistent [33, 35]; after a write, TAO
guarantees the eventual delivery of an invalidation or refill
to all tiers. Given a sufficient period of time during
which external inputs have quiesced, all copies of data
in TAO will be consistent and reflect all successful write
operations to all objects and associations. Replication
lag is usually less than one second.
In

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

4.5 ขนาดกันทางภูมิศาสตร์เต่าจะช่วยให้กำหนดผู้นำและผู้ติดตามมาตราเพื่อจัดการปริมาณสูง ตั้งแต่อ่านประมวลเครื่องชั่งน้ำหนักกับจำนวนสหเซิร์ฟเวอร์ทั้งหมดระดับการ นัยในการออกแบบ อย่างไร เป็นสมมติฐานที่เวลาแฝงเครือข่ายจากผู้ติดตามกับผู้นำ และผู้นำฐานข้อมูลต่ำ สมมติฐานนี้ไม่สมเหตุสมผลถ้าลูกค้าถูกจำกัดไปยังศูนย์ข้อมูลเดียว หรือแม้แต่การชุดของข้อมูลศูนย์ใกล้ ไม่เป็นความจริงอย่างไรก็ตาม ในสภาพแวดล้อมของเราผลิตเป็นแอพลิเคชันของสังคมเครือข่ายของคอมพิวเตอร์ และความต้องการของเครือข่ายได้เติบโต เรามีการขยายนอกเหนือจากตำแหน่งที่ตั้งทางภูมิศาสตร์เดียว: หล่อวันนี้ระดับสามารถพันไมล์แยก ในการกำหนดค่านี้เครือข่ายคนตลอดเวลาได้อย่างรวดเร็วคอขวดของสถาปัตยกรรมโดยรวม ตั้งแต่อ่านพุ่ง ด้วยลูกศิษย์มี 25 ครั้งเป็นบ่อยครั้งเป็นการเขียนในปริมาณงานของเรา เราเลือกสถาปัตยกรรมหลัก/ทาสที่ต้องเขียนแบบ ส่ง แต่ที่ทำอ่านพุ่งจะให้บริการในท้องถิ่น เช่นเดียวกับผู้นำ / -หล่อแบบ เราเผยแพร่แจ้งแบบอะซิงโครนัสเพื่อเพิ่มประสิทธิภาพและพร้อมใช้งาน ค่าใช้จ่ายข้อมูลสดกราฟทางสังคมคือมกราคมคับ เป็นไปไม่ได้กลุ่มผู้ใช้ที่ข้ามพาร์ทิชันร้องขอให้หายาก หมายความ ว่า ผู้ติดตามเต่าแต่ละต้องเป็นท้องถิ่นการระดับของฐานข้อมูลเก็บแบบสมบูรณ์หลายเพตะไบต์copy of the social graph. It would be prohibitively expensive to provide full replicas in every data center.Our solution to this problem is to choose data centerlocations that are clustered into only a few regions, wherethe intra-region latency is small (typically less than 1 millisecond).It is then sufficient to store one complete copyof the social graph per region. Figure 2 shows the overallarchitecture of the master/slave TAO system.Followers behave identically in all regions, forwardingread misses and writes to the local region’s leader tier.Leaders query the local region’s database regardless ofwhether it is the master or slave. Writes, however, areforwarded by the local leader to the leader that is in theregion with the master database. This means that readlatency is independent of inter-region latency.The master region is controlled separately for eachshard, and is automatically switched to recover from thefailure of a database. Writes that fail during the switchare reported to the client as failed, and are not retried.Note that since each cache hosts multiple shards, a servermay be both a master and a slave at the same time. Weprefer to locate all of the master databases in a single region. When an inverse association is mastered in a different region, TAO must traverse an extra inter-region link to forward the inverse write.TAO embeds invalidation and refill messages in theลำธารที่จำลองแบบฐานข้อมูล ข้อความเหล่านี้จะถูกส่งในพื้นที่ทันทีหลังจากธุรกรรมได้ถูกทำสำเนาไปยังฐานข้อมูลของทาส ส่งข้อความดังกล่าวก่อนจะสร้างแคชไม่สอดคล้องกัน เท่าที่อ่านจากฐานข้อมูลภายในจะมีข้อมูลเก่า ที่ Facebook เต่าและ memcache ใช้ขั้นตอนเดียวกันสำหรับการจัดส่ง invalidations และเติมสินค้า [21]ถ้าเขียนส่งต่อเสร็จแล้วผู้นำท้องถิ่นจะปรับปรุงแคที่สด แม้ว่าฐานข้อมูลท้องถิ่นทาสคงมียังไม่ได้อัพเดต โดยลำธารจำลองแบบอะซิงโครนัส ในที่นี้กรณีลูกศิษย์จะได้รับสอง invalidates หรือ refills จากเขียน จะถูกส่งเมื่อเขียนสำเร็จ และที่ส่งของเขียนธุรกรรมถูกจำลองแบบในฐานข้อมูลท้องถิ่นทาสเต่าหลัก/ทาสออกแบบมั่นใจว่า สามารถอ่านทั้งหมดมีความพึงพอใจภายในภาคหนึ่ง ค่าใช้จ่ายอาจส่งคืนข้อมูลเก่าไปยังไคลเอนต์ จึงเป็นผู้ใช้สอบถามอย่างสม่ำเสมอระดับเดียวกันของผู้ติดตาม ผู้ใช้จะโดยทั่วไปมีมุมมองสอดคล้องรัฐเต่า เราพูดคุยข้อยกเว้นนี้ในส่วนถัดไป ใช้งาน 5ส่วนก่อนหน้านี้อธิบายถึงวิธีรวมเซิร์ฟเวอร์เต่าจัดการจำนวนมากของข้อมูลและสอบถามราคา ส่วนนี้รายละเอียดสำคัญเพิ่มประสิทธิภาพการปฏิบัติงานและจัดเก็บอย่างมีประสิทธิภาพ5.1 เซิร์ฟเวอร์แคเต่าแคชั้นทำหน้าที่เป็นตัวกลางระหว่างไคลเอนต์และฐานข้อมูล อุกอาจเก็บวัตถุและสมาคมเพื่อให้ประสิทธิภาพดีอ่านจัดการหน่วยความจำของเต่าขึ้นอยู่กับของ Facebookกำหนด memcached ตามที่อธิบายไว้ โดย Nishtala etal. [21] เต่ามีตัวจัดสรรพื้นที่จัดการแผ่นของสินค้าขนาดเท่า ตารางแฮชเธรดปลอดภัย ขับไล่ LRUระหว่างรายการของขนาดเท่า และ rebalancer พื้นแบบไดนามิกที่ช่วยให้อายุขับไล่ LRU คล้ายในชนิดทั้งหมดของแผ่นคอนกรีต สินค้าพื้นสามารถเก็บโหนหรือขอบหนึ่งรายการจะให้ดีแยก เต่ากั้นที่มีรามเป็นสถาน เลือกเวที โดยวัตถุหรือชนิดการเชื่อมโยง นี้ช่วยให้เราสามารถขยายแคชีวิตสำคัญชนิด หรือ เพื่อป้องกันไม่ให้ประชาชนยากจนแค evicting ข้อมูลชนิด better-behaved ดังนั้นไกลเรายังกำหนดสถานที่อยู่ด้วยตนเองเท่านั้นระบุปัญหา แต่ควรเป็นไปโดยอัตโนมัติขนาดสถานที่ปรับปรุงรวมตีเต่าสำหรับสินค้าขนาดขนาดเล็ก เช่นสมาคมนับค่าใช้จ่ายในหน่วยความจำของตัวชี้สำหรับกลุ่มสินค้าในตารางแฮหลักเป็นสำคัญ เราเก็บเหล่านี้สินค้าแยกต่างหาก แมปโดยตรง 8-อย่างสัมพันธ์กันแคชที่ต้องไม่ชี้ สั่ง LRU ภายในแต่ละกลุ่มมีติดตาม โดยเพียงแค่เลื่อนรายการลง เราบรรลุประสิทธิภาพหน่วยความจำเพิ่มเติม ด้วยการเพิ่มตารางที่แผนผัง atype ใช้งานแต่ละค่าเป็น 16 บิต นี้ทำให้เราแผนที่ (id1, atype) เพื่อการนับจำนวน 32 บิตในไบต์ 14 มีรายการ การบันทึกการขาดงานของ id2 ใด ๆ สำหรับการ (id1, atype), ใช้เวลาเพียง 10 ไบต์ เพิ่มประสิทธิภาพนี้ให้เรากดค้างไว้ประมาณ 20% สินค้าในแคชสำหรับการการกำหนดค่าระบบ 5.2 การแม็ป MySQLนึกว่า เราแบ่งพื้นที่ของวัตถุและความสัมพันธ์ของเป็นเศษภาชนะ ชาร์ดละไว้เป็นตรรกะฐานข้อมูล MySQL ที่มีตารางสำหรับวัตถุและตารางสำหรับความสัมพันธ์ของการ ฟิลด์ของวัตถุทั้งหมดจะทำให้อนุกรมลงในคอลัมน์เดียว 'ข้อมูล' วิธีการนี้ช่วยให้เราเก็บวัตถุชนิดต่าง ๆ ภายในตารางเดียวกันวัตถุที่ได้รับประโยชน์จากการจัดการข้อมูลที่แยกต่างหากด้านนโยบายจะถูกเก็บในตารางต่าง ๆ เองเชื่อมโยงจะถูกเก็บไว้ในทำนองเดียวกัน กับวัตถุ แต่ เพื่อสนับสนุนสอบถามช่วง ตารางมีดัชนีเพิ่มเติมตาม id1, atype และเวลา เพื่อหลีกเลี่ยงอาจมีราคาแพงเลือกจำนวนแบบสอบถาม สมาคมนับจะถูกเก็บในตารางแยกต่างหาก 5.3 แค Sharding และฮอตสปอตเศษภาชนะถูกแมปไปยังแคชเซิร์ฟเวอร์ภายในโดยใช้ระดับสอดคล้อง hashing [15] นี้ช่วยให้ง่ายขยายชั้นและขอสาย อย่างไรก็ตาม กำหนดกึ่งสุ่มนี้ของ shards แคช เซิร์ฟเวอร์อาจโหลดไม่สมดุล:ลูกศิษย์บางจะไหล่ส่วนใหญ่ของโหลดคำขออื่น ๆ โหลด rebalances เต่าระหว่างลูกศิษย์ มีชาร์ดโคลน ที่อ่านไปชาร์ดมีบริการ โดยลูกศิษย์หลายในระดับ ความสอดคล้องจัดการหาชาร์ดโคลนจะถูกส่งไปทั้งหมดลูกศิษย์ที่โฮสต์ที่ชาร์ดในปริมาณงานของเรา มันไม่ใช่เรื่องแปลกสำหรับนิยมวัตถุจะ สอบถามสั่งของขนาดมากขึ้นกว่าวัตถุอื่น ๆ โคลนสามารถกระจายโหลดนี้ข้ามลูกศิษย์หลาย แต่ตีอัตราสูงสำหรับวัตถุเหล่านี้ทำให้มันคุ้มค่าที่จะทำได้ในขนาดเล็กฝั่งไคลเอ็นต์แคช เมื่อผู้ติดตามจัดทำแบบสอบถามสำหรับแบบร้อนสินค้า รวมวัตถุหรืออัตราการเข้าถึงของสมาคมถ้าอัตราการเข้าถึงเกินกว่ากำหนดขีดจำกัด เต่าไคลเอนต์เก็บข้อมูลและรุ่น โดยการรวมรุ่นหมายเลขสามารถละเว้นการหล่อในแบบสอบถามภายหลังข้อมูลในการตอบถ้าข้อมูลไม่เปลี่ยนแปลงตั้งแต่การรุ่นก่อนหน้านี้ อัตราการเข้าใช้ในการเค้นคำขอไคลเอ็นต์วัตถุที่ร้อนมาก 5.4 วัตถุสูงองศาวัตถุมากมีมากกว่า 6000 ความสัมพันธ์กับการเกิดจากพวกเขา ดังนั้นเต่าไม่แค atype เดียวกันรายชื่อสมาคมที่สมบูรณ์ ก็ทั่วไปที่รศนพรับทำแบบสอบถามที่มีผลลัพธ์ที่ว่างเปล่า(ไม่ขอบอยู่ระหว่าง id1 ระบุ id2) อับ องศาสูงวัตถุ แบบสอบถามเหล่านี้จะเสมอไปไป เพราะ id2 สอบถามได้อยู่ในหางของรายการสมาคม uncachedเรามี addressed inefficiency นี้ในการดำเนินการแคช โดยการปรับเปลี่ยนรหัสลูกค้าที่จะสังเกตออกแบบสอบถามปัญหา หนึ่งวิธีแก้ไขปัญหานี้จะใช้นับของรศนพเพื่อเลือกทิศทางของแบบสอบถามตั้งแต่การตรวจสอบขอบผกผันเป็นเทียบเท่า ในบางกรณีที่ทั้งสองปลายของขอบมีองศาสูงโหน เราสามารถใช้ประโยชน์จากโดเมนโปรแกรมประยุกต์ความรู้เพื่อปรับปรุง cacheability ไปยัง การเชื่อมโยงหลายตั้งค่าฟิลด์เวลาเวลาการสร้าง และวัตถุมากรวมเวลาสร้างเป็นเขต ตั้งแต่ขอบจะเป็นเท่านั้นสามารถสร้างโหนหลังจากที่มีการสร้างโหนดเราสามารถจำกัดการค้นหา id2 สมาคมครั้ง≥เวลาสร้างของวัตถุได้ ตราบขอบเก่ากว่าวัตถุอยู่ในแคชแล้วแบบสอบถามนี้สามารถตอบได้โดยตรง โดยผู้ติดตามเต่า 6 ความสอดคล้องกันและยอมรับข้อบกพร่องสองความสำคัญที่สุดสำหรับเต่าความพร้อมใช้งานและประสิทธิภาพ เมื่อเกิดความล้มเหลวของเราต้องการต่อไปจะทำให้ Facebook แม้ว่าการข้อมูลเก่าได้ ในส่วนนี้ เราอธิบายความสอดคล้องรูปแบบของเต่าภายใต้การดำเนินงานปกติ และเต่าบูชาความสอดคล้องภายใต้โหมดความล้มเหลว 6.1 ความสอดคล้องภายใต้การดำเนินงานปกติ วัตถุ และความสัมพันธ์ในเต่าไม่สอดคล้องกันในที่สุด [33, 35]; หลังจากเขียน เต่ารับประกันการจัดส่งสุดของ invalidation หรือเติมการระดับทั้งหมด กำหนดรอบระยะเวลาระหว่างเพียงพออินพุตภายนอกที่มี quiesced สำเนาข้อมูลทั้งหมดเต่าจะให้สอดคล้อง และสะท้อนถึงการเขียนที่ประสบความสำเร็จทั้งหมดการดำเนินการวัตถุและความสัมพันธ์ของ จำลองแบบความล่าช้าโดยปกติจะน้อยกว่า 1 วินาทีใน

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

4.5 ปรับภูมิศาสตร์ผู้นำและการกำหนดค่าติดตามช่วยให้อบตเพื่อปรับขนาดการจัดการภาระงานสูงเนื่องจากการอ่านผ่านการชั่งน้ำหนักที่มีจำนวนรวมของเซิร์ฟเวอร์ติดตามในทุกชั้น โดยปริยายในการออกแบบ แต่เป็นสมมติฐานที่ว่าศักยภาพเครือข่ายจากผู้ตามผู้นำและผู้นำไปยังฐานข้อมูลอยู่ในระดับต่ำ สมมติฐานนี้เป็นที่เหมาะสมหากลูกค้ามีการ จำกัด การศูนย์ข้อมูลเดียวหรือแม้กระทั่งชุดของศูนย์ข้อมูลในบริเวณใกล้ มันไม่เป็นความจริงแต่ในสภาพแวดล้อมการผลิตของเรา. ในฐานะที่เป็นคอมพิวเตอร์แอพลิเคชันเครือข่ายสังคมของเราและความต้องการเครือข่ายที่มีการเติบโตที่เราได้มีการขยายตัวเกินกว่าที่ตั้งทางภูมิศาสตร์เดียว: วันนี้ลูกศิษย์ชั้นสามารถหลายพันไมล์ ในการกำหนดค่านี้เวลาการเดินทางรอบเครือข่ายได้อย่างรวดเร็วจะกลายเป็นคอขวดของสถาปัตยกรรมโดยรวม ตั้งแต่อ่านคิดถึงโดยผู้ติดตาม 25 ครั้งบ่อยเท่าที่เขียนในปริมาณงานของเราเราเลือกหลัก/ สถาปัตยกรรมทาสที่ต้องเขียนจะถูกส่งไปหลักแต่ที่ช่วยให้คิดถึงการอ่านที่จะได้รับการบริการในประเทศ เช่นเดียวกับผู้นำ / - การออกแบบที่ติดตามเราเผยแพร่ถ่ายทอดสดการแจ้งเตือนปรับปรุงเพื่อเพิ่มประสิทธิภาพและความพร้อมที่ค่าใช้จ่ายของความสดข้อมูล. กราฟทางสังคมที่เชื่อมต่อกันแน่น; มันเป็นไปไม่ได้กับผู้ใช้งานกลุ่มเพื่อให้การร้องขอข้ามพาร์ติชันเป็นของหายาก ซึ่งหมายความว่าแต่ละสาวก TAO ต้องมีในท้องถิ่นเพื่อชั้นของฐานข้อมูลถือหลายpetabyte สมบูรณ์สำเนาของกราฟทางสังคม มันจะราคาแพงเพื่อให้เลียนแบบเต็มรูปแบบในทุกศูนย์ข้อมูล. ทางออกของปัญหานี้คือการเลือกศูนย์ข้อมูลสถานที่ที่มีการจัดกลุ่มเข้ามาในภูมิภาคเพียงไม่กี่ที่แฝงภายในภูมิภาคที่มีขนาดเล็ก(ปกติน้อยกว่า 1 มิลลิวินาที) มันก็เพียงพอที่จะเก็บสำเนาที่สมบูรณ์แบบของกราฟทางสังคมต่อภูมิภาค รูปที่ 2 แสดงให้เห็นโดยรวมของสถาปัตยกรรมของหลัก/ ทาสระบบอบต. ติดตามประพฤติเหมือนกันในทุกภูมิภาคส่งต่ออ่านคิดถึงและเขียนไปยังชั้นผู้นำภูมิภาคท้องถิ่น. ผู้นำสืบค้นฐานข้อมูลภูมิภาคท้องถิ่นโดยไม่คำนึงถึงไม่ว่าจะเป็นหลักหรือทาส เขียน แต่จะส่งต่อโดยผู้นำท้องถิ่นที่จะเป็นผู้นำที่อยู่ในพื้นที่ที่มีฐานข้อมูลหลัก ซึ่งหมายความว่าการอ่านแฝงเป็นอิสระจากความล่าช้าระหว่างภูมิภาค. ภาคหลักจะถูกควบคุมแยกต่างหากสำหรับแต่ละที่แตกออกมาและจะเปลี่ยนโดยอัตโนมัติในการกู้คืนจากความล้มเหลวของฐานข้อมูล เขียนว่าล้มเหลวในระหว่างสวิทช์จะมีการรายงานให้กับลูกค้าตามที่ล้มเหลวและไม่ได้ลอง. โปรดทราบว่าเนื่องจากแต่ละแคชเจ้าภาพเศษหลายเซิร์ฟเวอร์อาจจะเป็นทั้งต้นแบบและทาสในเวลาเดียวกัน เราชอบที่จะค้นหาทั้งหมดของฐานข้อมูลหลักในพื้นที่เดียว เมื่อความสัมพันธ์ผกผันเป็นที่เข้าใจในพื้นที่ที่แตกต่างกัน TAO ต้องสำรวจการเชื่อมโยงระหว่างภูมิภาคเป็นพิเศษในการส่งต่อการเขียนผกผัน. อบฝังโมฆะและข้อความเติมเงินในกระแสจำลองแบบฐานข้อมูล ข้อความเหล่านี้จะถูกส่งในพื้นที่ทันทีหลังจากที่การทำธุรกรรมได้รับการจำลองแบบไปยังฐานข้อมูลเป็นทาส ส่งมอบข้อความดังกล่าวก่อนหน้านี้จะสร้างความไม่สอดคล้องกันแคชการอ่านจากฐานข้อมูลท้องถิ่นจะให้ข้อมูลเก่า ที่ Facebook TAO และการใช้ memcache ท่อเหมือนกันสำหรับการจัดส่งของ invalidations และเติม [21]. ถ้าเขียนส่งต่อจะประสบความสำเร็จแล้วผู้นำท้องถิ่นจะปรับปรุงแคชมีมูลค่าสดแม้ว่าฐานข้อมูลทาสท้องถิ่นอาจจะยังไม่ได้รับการปรับปรุงโดยกระแสการจำลองแบบไม่ตรงกัน ในการนี้ผู้ติดตามกรณีที่จะได้รับสองเลิกหรือเติมจากการเขียนหนึ่งที่จะถูกส่งเมื่อเขียนที่ประสบความสำเร็จและหนึ่งที่จะถูกส่งเมื่อการทำธุรกรรมการเขียนที่ถูกจำลองแบบไปยังฐานข้อมูลทาสท้องถิ่น. อบตโท / ออกแบบทาสเพื่อให้แน่ใจว่าทุกคนอ่านสามารถจะความพึงพอใจที่อยู่ในภูมิภาคเดียวที่ค่าใช้จ่ายที่อาจเกิดขึ้นจากข้อมูลเก่าที่กลับมาให้กับลูกค้า ตราบใดที่ผู้ใช้แบบสอบถามอย่างต่อเนื่องชั้นลูกศิษย์เดียวกันผู้ใช้จะมักจะมีมุมมองที่สอดคล้องกันของรัฐTAO เราหารือข้อยกเว้นนี้ในส่วนถัดไป. 5 การดำเนินงานส่วนที่ก่อนหน้าอธิบายถึงวิธีการอบเซิร์ฟเวอร์จะรวมในการจัดการปริมาณข้อมูลขนาดใหญ่และอัตราแบบสอบถาม ส่วนนี้มีรายละเอียดที่สำคัญการเพิ่มประสิทธิภาพในการดำเนินงานและประสิทธิภาพการจัดเก็บ. 5.1 แคชเซิร์ฟเวอร์ชั้นแคชTAO ทำหน้าที่เป็นตัวกลางระหว่างลูกค้าและฐานข้อมูล มันเก็บวัตถุที่อุกอาจและสมาคมเพื่อให้มีประสิทธิภาพที่ดีในการอ่าน. จัดการหน่วยความจำ TAO อยู่บนพื้นฐานของ Facebook ที่กำหนดเอง memcached ตามที่อธิบาย Nishtala et al, [21] TAO มีจัดสรรแผ่นที่จัดการแผ่นรายการที่มีขนาดเท่ากันตารางแฮชด้ายปลอดภัย, การขับไล่อาร์ในรายการที่มีขนาดเท่ากันและ rebalancer แผ่นแบบไดนามิกที่ช่วยให้การขับไล่อาร์ทุกเพศทุกวัยที่คล้ายกันในทุกประเภทของแผ่น รายการแผ่นสามารถเก็บหนึ่งโหนดหรือรายการขอบหนึ่ง. เพื่อให้การแยกที่ดีกว่า TAO พาร์ติชันที่มีRAM เข้าไปโดยสิ้นเชิงการเลือกสถานที่เกิดเหตุโดยวัตถุหรือประเภทการเชื่อมโยง นี้จะช่วยให้เราสามารถขยายแคชอายุการใช้งานประเภทที่สำคัญหรือเพื่อป้องกันไม่ให้ประชาชนที่ยากจนจากแคชขี้บ่นข้อมูลประเภทดีประพฤติ ดังนั้นขณะนี้เราได้เพียงโดยสิ้นเชิงการกำหนดค่าให้ตนเองอยู่ปัญหาเฉพาะแต่มันควรจะเป็นไปโดยอัตโนมัติโดยสิ้นเชิงขนาดในการปรับปรุงอัตราการตีโดยรวมของอบต. สำหรับรายการขนาดคงที่ขนาดเล็กเช่นนับสมาคมค่าใช้จ่ายในหน่วยความจำของตัวชี้สำหรับรายการถังในตารางแฮหลักเป็นสำคัญ เราเก็บเหล่านี้รายการแยกใช้โดยตรงเชื่อมโยงแมป 8 ทางศาสนาที่จำเป็นต้องมีตัวชี้ไม่มี เพื่ออาร์ในแต่ละถังมีการติดตามโดยเพียงแค่เลื่อนรายการลง เราบรรลุประสิทธิภาพหน่วยความจำเพิ่มเติมโดยการเพิ่มตารางที่แผนที่แต่ละATYPE ใช้งานเป็นค่า 16 บิต นี้จะช่วยให้เรา map (id1, ATYPE) เพื่อนับ 32 บิต 14 ไบต์; รายการเชิงลบซึ่งบันทึกการขาดของ id2 ใด ๆ(ที่ id1, ATYPE) ใช้เวลาเพียง 10 ไบต์ การเพิ่มประสิทธิภาพนี้ช่วยให้เราสามารถที่จะถือประมาณ 20% รายการอื่น ๆ ในแคชสำหรับการกำหนดค่าระบบที่กำหนด. 5.2 MySQL แมปจำได้ว่าเราแบ่งพื้นที่ของวัตถุและสมาคมลงในเศษ ที่แตกออกมาแต่ละคนจะได้รับมอบหมายให้ตรรกะฐานข้อมูล MySQL ที่มีโต๊ะสำหรับวัตถุและโต๊ะสำหรับสมาคม ทุกด้านของวัตถุที่มีการต่อเนื่องเป็นคอลัมน์เดียว 'ข้อมูล' วิธีการนี้จะช่วยให้เราเก็บวัตถุที่แตกต่างกันในตารางเดียวกันวัตถุได้รับประโยชน์จากการจัดการข้อมูลที่แยกต่างหากที่เจ้าหน้าที่ตำรวจจะถูกเก็บไว้ในตารางที่กำหนดเองแยกต่างหาก. สมาคมจะถูกเก็บไว้ในทำนองเดียวกันกับวัตถุ แต่ที่จะสนับสนุนคำสั่งช่วงตารางของพวกเขาจะมีดัชนีที่เพิ่มขึ้นตามใน id1, ATYPE ที่และเวลา เพื่อหลีกเลี่ยงการอาจมีราคาแพงSELECT คำสั่ง COUNT นับสมาคมถูกเก็บไว้ในตารางที่แยกต่างหาก. 5.3 sharding แคชและฮอตสปอตเศษถูกแมปไปยังเซิร์ฟเวอร์แคชภายในชั้นโดยใช้hashing สอดคล้องกัน [15] นี้ง่ายขยายชั้นและการกำหนดเส้นทางการร้องขอ แต่นี้ได้รับมอบหมายกึ่งสุ่มของเศษไปยังเซิร์ฟเวอร์แคชสามารถนำไปสู่ความไม่สมดุลของการโหลด: สาวกบางคนจะแบกรับส่วนขนาดใหญ่ของการโหลดคำขอกว่าคนอื่น ๆ อบต rebalances โหลดในหมู่สาวกที่มีโคลนเศษซึ่งในการอ่านเศษถูกเสิร์ฟโดยผู้ติดตามหลายคนในชั้น สอดคล้องข้อความสำหรับการจัดการเศษโคลนจะถูกส่งไปทั้งหมดติดตามโฮสติ้งที่แตกออกมาว่า. ในปริมาณงานของเราก็ไม่ได้เป็นเรื่องผิดปกติที่เป็นที่นิยมวัตถุที่จะสอบถามคำสั่งของขนาดบ่อยกว่าวัตถุอื่นๆ โคลนสามารถกระจายโหลดนี้ทั่วติดตามจำนวนมากแต่อัตราการตีสูงสำหรับวัตถุเหล่านี้จะทำให้มันคุ้มค่าที่จะวางไว้ในด้านลูกค้าขนาดเล็กแคช เมื่อมีการตอบสนองต่อการติดตามแบบสอบถามสำหรับร้อนรายการจะมีวัตถุหรืออัตราการเข้าถึงของสมาคม. ถ้าอัตราการเข้าถึงเกินกว่าเกณฑ์ที่กำหนดที่ TAO ลูกค้าแคชข้อมูลและรุ่น โดยรวมถึงรุ่นจำนวนในการสืบค้นภายหลังลูกศิษย์สามารถละเว้นข้อมูลในการตอบกลับหากข้อมูลไม่ได้เปลี่ยนแปลงตั้งแต่รุ่นก่อนหน้านี้ อัตราการเข้าถึงนอกจากนี้ยังสามารถใช้ในการเค้นการร้องขอของลูกค้าสำหรับวัตถุที่ร้อนมาก. 5.4 องศาสูงวัตถุวัตถุหลายคนมีมากกว่า6,000 สมาคมกับATYPE เดียวกันเล็ดลอดออกมาจากพวกเขาดังนั้น TAO ไม่แคชรายการสมาคมสมบูรณ์ นอกจากนี้ยังเป็นเรื่องปกติที่รองได้รับคำสั่งจะถูกดำเนินการที่มีผลที่ว่างเปล่า(ไม่มีขอบอยู่ระหว่าง id1 ระบุและ id2) แต่น่าเสียดายที่ในระดับปริญญาสูงวัตถุแบบสอบถามเหล่านี้มักจะไปที่ฐานข้อมูลเพราะ id2 สอบถามอาจจะอยู่ในหางuncached ของรายการสมาคม. เราได้รับการแก้ไขการขาดประสิทธิภาพในการดำเนินงานแคชโดยการปรับเปลี่ยนรหัสลูกค้าที่มีการตั้งข้อสังเกตในการออกปัญหาคำสั่ง หนึ่งในการแก้ไขปัญหานี้คือการใช้การนับรองในการเลือกทิศทางแบบสอบถามตั้งแต่การตรวจสอบขอบผกผันเทียบเท่า ในบางกรณีที่ปลายทั้งสองด้านของขอบระดับสูงโหนดเรายังสามารถใช้ประโยชน์จากความรู้การประยุกต์ใช้โดเมนเพื่อปรับปรุงcacheability สมาคมหลายคนตั้งเขตเวลาในการเวลาการสร้างของพวกเขาและวัตถุจำนวนมากรวมถึงเวลาสร้างของพวกเขาเป็นเขตข้อมูล ตั้งแต่ขอบไปยังโหนดสามารถถูกสร้างขึ้นหลังจากโหนดที่ได้รับการสร้างขึ้นเราสามารถจำกัด การค้นหา id2 สมาคมที่มีเวลาเป็น≥กว่าเวลาการสร้างวัตถุ ตราบใดที่ขอบเก่ากว่าวัตถุที่มีอยู่ในแคชแล้วคำนี้สามารถตอบได้โดยตรงโดยการเป็นผู้ตามอบต. 6 สอดคล้องและความผิดพลาดสองความต้องการที่สำคัญที่สุดสำหรับการอบที่มีความพร้อมและประสิทธิภาพการทำงาน ความล้มเหลวที่เกิดขึ้นเมื่อเราต้องการที่จะยังคงที่จะทำให้ Facebook แม้ว่าข้อมูลเก่า ในส่วนนี้เราจะอธิบายความสอดคล้องรูปแบบของอบตภายใต้การดำเนินงานปกติและวิธีการที่อบต. เสียสละความมั่นคงภายใต้ความล้มเหลว6.1 สอดคล้องภายใต้การดำเนินงานปกติวัตถุและสมาคมในTAO สอดคล้องในที่สุด [33, 35] หลังจากที่เขียน TAO รับประกันการส่งมอบที่สุดของโมฆะหรือเติมเงินให้กับทุกชั้น กำหนดระยะเวลาที่เพียงพอในช่วงที่ปัจจัยการผลิตจากภายนอกได้ quiesced สำเนาข้อมูลทั้งหมดในTAO จะสอดคล้องและสะท้อนให้เห็นถึงการเขียนที่ประสบความสำเร็จทุกการดำเนินงานเพื่อวัตถุทั้งหมดและสมาคม การจำลองแบบล่าช้ามักจะน้อยกว่าหนึ่งวินาที. ใน

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

4.5 การภูมิศาสตร์
ผู้นำและผู้ติดตามปรับแต่งช่วยให้เต่า

ขนาดเพื่อจัดการกับภาระงานสูง เนื่องจากอ่านระดับ throughput
กับจำนวนของผู้ติดตามเซิร์ฟเวอร์ทั้งหมด
ชั้น . ความนัยในการออกแบบ , อย่างไรก็ตาม , เป็นสมมุติฐาน
ที่เกิดจากผู้ตาม ผู้นำ และเครือข่าย เพื่อให้ผู้นำ
ฐานข้อมูลน้อย สมมติฐานนี้สมเหตุสมผล
ถ้าลูกค้าจะถูก จำกัด ไปยังศูนย์ข้อมูลเดียว หรือแม้กระทั่ง
ชุดของศูนย์ข้อมูลในบริเวณใกล้เคียง . มันไม่ได้เป็นจริง
อย่างไรก็ตามในสภาพแวดล้อมการผลิตของเรา .
เป็นคอมพิวเตอร์โปรแกรมเครือข่ายสังคมและเครือข่าย
ความต้องการเติบโต เราต้องขยาย
เกินกว่าที่ตั้งทางภูมิศาสตร์เดียว : วันนี้ ผู้ตาม
ชั้นสามารถพันไมล์ . ในการตั้งค่านี้
เครือข่ายการเดินทางรอบครั้งได้อย่างรวดเร็วกลายเป็น
คอขวดของสถาปัตยกรรมโดยรวม ตั้งแต่อ่าน
คิดถึงโดยผู้ติดตาม 25 ครั้ง เป็นบ่อย ตามที่เขียนใน
งานของเรา เราเลือก Master / Slave สถาปัตยกรรม
ต้องเขียนส่งอาจารย์ แต่ที่ช่วยให้
อ่านพลาดเป็นบริการในประเทศ เช่นเดียวกับผู้นำ - ผู้ตาม
ออกแบบเราเผยแพร่การปรับปรุงการแจ้งเตือนอะที่จะเพิ่มประสิทธิภาพและความพร้อมในค่าใช้จ่ายของตุนข้อมูล .
กราฟทางสังคมเชื่อมโยงอย่างแน่นหนา ; มันเป็นไปไม่ได้
ให้กลุ่มผู้ใช้ ดังนั้นขอข้ามฉากกั้น
ของหายาก ซึ่งหมายความว่าแต่ละเทาผู้ตามต้องท้องถิ่น
เพื่อระดับของฐานข้อมูลถือสำเนาหลายเพตะไบต์
สมบูรณ์ของกราฟสังคมมันคงจะแพงให้เต็มจําลองทุกศูนย์ข้อมูล .
โซลูชั่นของเราปัญหานี้คือการเลือกข้อมูลแบบศูนย์
สถานที่ที่เป็นเพียงไม่กี่พื้นที่ที่
ภายในเขตศักยภาพขนาดเล็ก ( มักจะน้อยกว่า 1 มิลลิวินาที ) .
มันก็เพียงพอที่จะเก็บหนึ่งเสร็จสมบูรณ์คัดลอก
ของ กราฟทางสังคมต่อภูมิภาค รูปที่ 2 แสดงโดย
สถาปัตยกรรมของเจ้านายทาสเทาระบบ .
ลูกศิษย์ทำตัวเหมือนกันทุกพื้นที่ ส่งต่อ
อ่านขาดและเขียนไปยังท้องถิ่นเขต หัวหน้าชั้น
ผู้นำสอบถามฐานข้อมูลท้องถิ่นภูมิภาคไม่ว่า
ไม่ว่าจะเป็น Master หรือ Slave เขียน , อย่างไรก็ตาม ,
ส่งต่อโดยผู้นำท้องถิ่นผู้นำที่อยู่ใน
เขตกับ Master ฐานข้อมูล ซึ่งหมายความว่าอ่าน
แฝงเป็นอิสระระหว่างภาค ( .
อาจารย์เขตควบคุมแยกต่างหากสำหรับแต่ละ
เศษแก้ว และจะเปลี่ยนโดยอัตโนมัติเพื่อกู้คืนจาก
ความล้มเหลวของฐานข้อมูล เขียนที่ล้มเหลวในช่วงสลับ
แจ้งลูกค้าล้มเหลว และไม่ได้ retried .
หมายเหตุ เนื่องจากแต่ละแคชโฮสต์หลายแผล , เซิร์ฟเวอร์
อาจเป็นทั้งเจ้านายและทาสในเวลาเดียวกัน เรา
ต้องการค้นหาทั้งหมดของฐานข้อมูลหลักในภูมิภาคเดียว เมื่อความสัมพันธ์ผกผันคือมาสเตอร์ในภูมิภาคต่าง ๆ เต๋าจะต้องเข้าไปเสริมระหว่างภูมิภาคการเชื่อมโยงไปข้างหน้าตรงกันข้ามเขียน .
เต่าฝังเรียงพี่เรียงน้องและข้อความเติมใน
ฐานข้อมูลแบบกระแสข้อมูล ข้อความเหล่านี้จะถูกส่งในพื้นที่ทันทีหลังจากรายการได้ถูกนำไปเป็นทาสของฐานข้อมูลส่งข้อความดังกล่าวก่อนจะสร้างความไม่สอดคล้องกัน แคช เท่าที่อ่านจากฐานข้อมูลท้องถิ่นจะให้ข้อมูลเก่า ที่ Facebook เกาะเต่า memcache ใช้ท่อเดียวกัน ส่งมอบ invalidations และเติมสินค้า [ 21 ] .
ถ้าส่งต่อเขียนสำเร็จแล้ว ผู้นำท้องถิ่น
จะอัปเดตของแคชกับค่าสด แม้ว่า
ฐานข้อมูลทาสท้องถิ่นอาจยังไม่อัพเดทตามกระแสแบบไม่ตรงกัน ในการติดตามคดีนี้จะได้รับการ หรือสอง

เขียนเติมจาก หนึ่งที่ถูกส่งเมื่อเขียนสำเร็จและ
ที่ส่งเมื่อเขียนไปยังฐานข้อมูลธุรกรรมแบบ

ทาสท้องถิ่น อบต. หลัก / ทาสการออกแบบเพื่อให้แน่ใจว่า ทั้งหมดที่อ่านสามารถ
พอใจในภูมิภาคเดียวที่ค่าใช้จ่ายของที่อาจจะกลับมาค้างข้อมูลให้กับลูกค้า ตราบใดที่ผู้ใช้
อย่างต่อเนื่องสอบถามแถวผู้ตามเดียวกันผู้ใช้จะ
มักจะมีมุมมองที่สอดคล้องกันของเต๋า รัฐ เราคุยกัน
ข้อยกเว้นนี้ ในส่วนถัดไป .
5
ก่อนหน้านี้ ส่วนการอธิบายวิธีเต๋าเซิร์ฟเวอร์รวมเพื่อจัดการปริมาณมากของข้อมูลและอัตราการ