License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.43
URN: urn:nbn:de:0030-drops-95062
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9506/
Go to the corresponding LIPIcs Volume Portal

Grossi, Roberto ; Versari, Luca

Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables

pdf-format:
LIPIcs-ESA-2018-43.pdf (0.6 MB)

Abstract

This paper proposes round-hashing, which is suitable for data storage on distributed servers and for implementing external-memory tables in which each lookup retrieves at most one single block of external memory, using a stash. For data storage, round-hashing is like consistent hashing as it avoids a full rehashing of the keys when new servers are added. Experiments show that the speed to serve requests is tenfold or more than the state of the art. In distributed data storage, this guarantees better throughput for serving requests and, moreover, greatly reduces decision times for which data should move to new servers as rescanning data is much faster.

BibTeX - Entry

@InProceedings{grossi_et_al:LIPIcs:2018:9506,
  author =	{Roberto Grossi and Luca Versari},
  title =	{{Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9506},
  URN =		{urn:nbn:de:0030-drops-95062},
  doi =		{10.4230/LIPIcs.ESA.2018.43},
  annote =	{Keywords: consistent hashing, external memory, hash tables}
}

Keywords: consistent hashing, external memory, hash tables
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI