Transcript ppt - TML
A case study in building layered DHT applications Yatin Chawathe Sriram Ramabhadran Sylvia Ratnasamy Anthony Lamarca Scott Shenker Joseph Hellerstein Contents • Introduction • Place Lab • Prefix hash trees • Evaluation • Conclusions INTRODUCTION • A case study of building an application (Place Lab) on top of generic DHT (OpenDHT) • Place Lab: End-user positioning system • Evaluate if it is feasible to use DHT as an application independent building block to implement a key component of Place Lab. • Present prefix hash tree, data structures used by Place Lab • Effect on performance INTRODUCTION • Place lab: end-user positioning system for location-enhanced applications. • Clients estimate their physical location by listening for nearby radio beacons (APs, GSM cells) in conjunction with a database of known beacon locations. • Beacon database maps beacon identifier to their location. • Beacon databases maintained by Organizations, APs (“war drivers”), centralized beacon databases (www.wigle.net) • E.g. When user arrives to new city, her device will query the mapping service for all beacon data within the region. Paper describes the design and implementation of Place Labs mapping over the OpenDHT service, 3rd party service. INTRODUCTION • Is it feasible to use a simple DHT service as a building block for a larger more complex application? • Can this application leverage the purported simplicity and deployability advantages of DHTs? • What is the performance impact of using application-independent DHTs for this application? PREFIX HASH TREE (PHT) • A distributed tree-like data structure that can be built on top of a generic DHT. • Single- or multi-dimensional queries • Build on top of a simple put/get/remove interface over any 3rd party DHT service like OpenDHT. • Range queries for new area: get (key) operation • Keys in the domain can be expressed as binary string of length D. • PHT is a binary tree, every node corresponds to a distinct prefix of the data domain being indexed. PREFIX HASH TREE (PHT) • Each node labeled with prefix that is defined recursively: L (left), L0 (left child), L1 (Right child) • Each node either 0 or 2 childs. Keys are stored only at leaf node. • PHT hash the prefix labels of PHT nodes over the DHT identifier space. • PHT node with label L: it can be located in DHT with a single get() “direct access” PHT and Place Lab • Coordination: Queries latitude-longitude • To index this coordination, linearization or space-filling curves to map multidimensional data into a single dimension. • PHT operations: • Lookup • Given Key K, returns unique leaf node Leaf(K), whose label is a prefix of K. • Range query • One-dimensional: Given two keys L and H, returns all keys L <= k <= H • Insert/delete • Requires first lookup operation • If leaf full, it must be split, most cases B+1 keys are distributed among 2 children. EVALUATION • Focus on effort on the PHT mechanism and the way it behaves both under insert loads from the mappings server and query loads from downloading clients. Performance (Fig 5, Fig 6, Fig 7) Performance (Fig 8, Fig 9, Fig 10) Performance (table 1) Performance (Fig 12, Fig 13, Fig 13) Conclusion • Place Lab differs from many traditional DHT applications in that it requires stronger semantics than simply put/get operations. • PHT provides an elegant solution for gathering the radio beacon data. • Layered approach allowed to reduce significantly the implementation overhead, however at the cost of performance. • Queries: Average 2-4 sec (depending the size of input data). • Place Lab and PHT are unable to make use of optimizations. • Simple DHT API would allow to built more richer and complex systems on top. Thank You!