東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Algorithmic engineering towards more...

Fan, Bin.

Linked to FindBook

Google Book

Amazon

博客來

Algorithmic engineering towards more efficient key-value systems.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Algorithmic engineering towards more efficient key-value systems./
Author:	Fan, Bin.
Description:	137 p.
Notes:	Source: Dissertation Abstracts International, Volume: 75-05(E), Section: B.
Contained By:	Dissertation Abstracts International75-05B(E).
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3578650
ISBN:	9781303727030

Algorithmic engineering towards more efficient key-value systems.
Fan, Bin.

Algorithmic engineering towards more efficient key-value systems. - 137 p.

Source: Dissertation Abstracts International, Volume: 75-05(E), Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2013.

Distributed key-value systems have been widely used as elemental components of many Internet-scale services at sites such as Amazon, Facebook and Twitter. This thesis examines a system design approach to scale existing key-value systems, both horizontally and vertically, by carefully engineering and integrating techniques that are grounded in recent theory but also informed by underlying architectures and expected workloads in practice. As a case study, we re-design FAWN-KV---a distributed key-value cluster consisting of "wimpy" key-value nodes---to use less memory but achieve higher throughput even in the worst case.

ISBN: 9781303727030Subjects--Topical Terms:

626642
Computer Science.

Algorithmic engineering towards more efficient key-value systems.
LDR:02909nam a2200289 4500 001 1960568
005 20140623111236.5
008 150210s2013 ||||||||||||||||| ||eng d
020 $a 9781303727030
035 $a (MiAaPQ)AAI3578650
035 $a AAI3578650
040 $a MiAaPQ $c MiAaPQ
100 1 $a Fan, Bin. $3 2096254
245 1 0 $a Algorithmic engineering towards more efficient key-value systems.
300 $a 137 p.
500 $a Source: Dissertation Abstracts International, Volume: 75-05(E), Section: B.
500 $a Adviser: David G. Anderson.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2013.
520 $a Distributed key-value systems have been widely used as elemental components of many Internet-scale services at sites such as Amazon, Facebook and Twitter. This thesis examines a system design approach to scale existing key-value systems, both horizontally and vertically, by carefully engineering and integrating techniques that are grounded in recent theory but also informed by underlying architectures and expected workloads in practice. As a case study, we re-design FAWN-KV---a distributed key-value cluster consisting of "wimpy" key-value nodes---to use less memory but achieve higher throughput even in the worst case.
520 $a First, to improve the worst-case throughput of a FAWN-KV system, we propose a randomized load balancing scheme that can fully utilize all the nodes regardless of their query distribution. We analytically prove and empirically demonstrate that deploying a very small but extremely fast load balancer at FAWN-KV can effectively prevent uneven or dynamic workloads creating hotspots on individual nodes. Moreover, our analysis provides service designers a mathematically tractable approach to estimate the worst-case throughput and also avoid drastic over-provisioning in similar distributed key-value systems.
520 $a Second, to implement the high-speed load balancer and also to improve the space efficiency of individual key-value nodes, we propose novel data structures and algorithms, including the cuckoo filter, a Bloom filter replacement that is high-speed, highly compact and delete-supporting, and optimistic cuckoo hashing, a fast and space-efficient hashing scheme that scales on multiple CPUs. Both algorithms are built upon conventional cuckoo hashing but are optimized for our target architectures and workloads. Using them as building blocks, we design and implement MemC3 to serve transient data from DRAM with high throughput and low-latency retrievals, and SILT to provide cost-effective access to persistent data on flash storage with extremely small memory footprint (e.g., 0.7 bytes per entry).
590 $a School code: 0041.
650 4 $a Computer Science. $3 626642
690 $a 0984
710 2 $a Carnegie Mellon University. $3 1018096
773 0 $t Dissertation Abstracts International $g 75-05B(E).
790 $a 0041
791 $a Ph.D.
792 $a 2013
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3578650