Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Leader Election Using NewSQL Database Systems
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0002-1672-6899
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0002-9484-6714
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0002-6578-3902
2015 (English)In: Distributed Applications and Interoperable Systems: 15th IFIP WG 6.1 International Conference, DAIS 2015, Held as Part of the 10th International Federated Conference on Distributed Computing Techniques, DisCoTec 2015, Grenoble, France, June 2-4, 2015, Proceedings / [ed] Alysson Bessani and Sara Bouchenak, France: Springer, 2015, p. 158-172Conference paper, Published paper (Refereed)
Abstract [en]

Leader election protocols are a fundamental building blockfor replicated distributed services. They ease the design of leader-basedcoordination protocols that tolerate failures. In partially synchronoussystems, designing a leader election algorithm, that does not permit mul-tiple leaders while the system is unstable, is a complex task. As a resultmany production systems use third-party distributed coordination ser-vices, such as ZooKeeper and Chubby, to provide a reliable leader electionservice. However, adding a third-party service such as ZooKeeper to adistributed system incurs additional operational costs and complexity.ZooKeeper instances must be kept running on at least three machinesto ensure its high availability. In this paper, we present a novel leaderelection protocol using NewSQL databases for partially synchronous sys-tems, that ensures at most one leader at any given time. The leaderelection protocol uses the database as distributed shared memory. Ourwork enables distributed systems that already use NewSQL databasesto save the operational overhead of managing an additional third-partyservice for leader election. Our main contribution is the design, imple-mentation and validation of a practical leader election algorithm, basedon NewSQL databases, that has performance comparable to a leaderelection implementation using a state-of-the-art distributed coordinationservice, ZooKeeper

Place, publisher, year, edition, pages
France: Springer, 2015. p. 158-172
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 9038
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:kth:diva-168266DOI: 10.1007/978-3-319-19129-4_13ISBN: 978-3-319-19129-4 (print)OAI: oai:DiVA.org:kth-168266DiVA, id: diva2:815345
Conference
DisCoTec 2015 The 10th International Federated Conference on Distributed Computing Techniques,June 2-5, 2015,Grenoble, France
Note

QC 20150828

Available from: 2015-05-29 Created: 2015-05-29 Last updated: 2018-11-05Bibliographically approved
In thesis
1. Scaling Distributed Hierarchical File Systems Using NewSQL Databases
Open this publication in new window or tab >>Scaling Distributed Hierarchical File Systems Using NewSQL Databases
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

For many years, researchers have investigated the use of database technology to manage file system metadata, with the goal of providing extensible typed metadata and support for fast, rich metadata search. However, earlier attempts failed mainly due to the reduced performance introduced by adding database operations to the file system’s critical path. Recent improvements in the performance of distributed in-memory online transaction processing databases (NewSQL databases) led us to re-investigate the possibility of using a database to manage file system metadata, but this time for a distributed, hierarchical file system, the Hadoop Distributed File System (HDFS). The single-host metadata service of HDFS is a well-known bottleneck for both the size of the HDFS clusters and their throughput.In this thesis, we detail the algorithms, techniques, and optimizations used to develop HopsFS, an open-source, next-generation distribution of the HDFS that replaces the main scalability bottleneck in HDFS, single node in-memory metadata service, with a no-shared state distributed system built on a NewSQL database. In particular, we discuss how we exploit recent high-performance features from NewSQL databases, such as application-defined partitioning, partition pruned index scans, and distribution aware transactions, as well as more traditional techniques such as batching and write-ahead caches, to enable a revolution in distributed hierarchical file system performance.HDFS’ design is optimized for the storage of large files, that is, files ranging from megabytes to terabytes in size. However, in many production deployments of the HDFS, it has been observed that almost 20% of the files in the system are less than 4 KB in size and as much as 42% of all the file system operations are performed on files less than 16 KB in size. HopsFS introduces a tiered storage solution to store files of different sizes more efficiently. The tiers range from the highest tier where an in-memory NewSQL database stores very small files (<1 KB), to the next tier where small files (<64 KB) are stored in solid-state-drives (SSDs), also using a NewSQL database, to the largest tier, the existing Hadoop block storage layer for very large files. Our approach is based on extending HopsFS with an inode stuffing technique, where we embed the contents of small files with the metadata and use database transactions and database replication guarantees to ensure the availability, integrity, and consistency of the small files. HopsFS enables significantly larger cluster sizes, more than an order of magnitude higher throughput, and significantly lower client latencies for large clusters.Lastly, coordination is an integral part of the distributed file system operations protocols. We present a novel leader election protocol for partially synchronous systems that uses NewSQL databases as shared memory. Our work enables HopsFS, that uses a NewSQL database to save the operational overhead of managing an additional third-party service for leader election and deliver performance comparable to a leader election implementation using a state-of-the-art distributed coordination service, ZooKeeper.

Abstract [sv]

I många år har forskare undersökt användningen av databasteknik för att hantera metadata i filsystem, med målet att tillhandahålla förlängbar metadata med stöd för snabb och uttrycksfull metadatasökning. Tidigare försök misslyckades dock huvudsakligen till följd av den reducerade prestanda som infördes genom att lägga till databasoperationer på filsystemets kritiska väg. De senaste prestandaförbättringarna för OLTP databaser som lagras i minnet (NewSQL databaser) ledde oss till att undersöka möjligheten att använda en databas för att hantera filsystemmetadata, men den här gången för ett distribuerat hierarkiskt filsystem, Hadoop Distributed Filesystem (HDFS). Metadata i HDFS lagras på en maskin, vilket är en känd flaskhals för såväl storlek som prestandan för HDFS kluster.I denna avhandling redogör vi för de algoritmer, tekniker och optimeringar som används för att utveckla HopsFS, en med öppen källkod, nästa generationens distribution av HDFS som ersätter lagringen av metadata i HDFS, där den lagras enbart i minnet på en nod, med ett distribuerat system med delat tillstånd byggt på en NewSQL databas. I synnerhet diskuteras hur vi utnyttjar nyligen framtagen högpresterande funktionalitet från NewSQL-databaser, exempelvis applikationsdefinierad partitionering, partitionsskuren indexskanning och distributionsmedvetna transaktioner, samt mer traditionella tekniker som batching och skrivcache, som banar väg för en revolution inom prestanda för distribuerade filsystem.HDFS design är optimerad för lagring av stora filer, det vill säga filer som sträcker sig från megabyte till terabyte i storlek. Men i många installationer i produktionsystem har det observerats att nästan 20 procent av filerna i systemet är mindre än 4 KB i storlek och så mycket som 42 procent av alla filsystemsoperationer utförs på filer mindre än 16 KB i storlek. HopsFS introducerar en nivåbaserad uppdelning av olika filstorlekar för mer effektiv lagring . Nivåerna varierar från högsta nivån där en NewSQL-databas lagrar i minnet mycket små filer (<1 KB), till nästa nivå där små filer (<64 KB) lagras i SSD-enheter (Solid State Drives) en NewSQL-databas, till den största delen, det befintliga Hadoop-blocklagringsskiktet för mycket stora filer. Vårt tillvägagångssätt bygger på att utöka HopsFS med en utfyllningsteknik för filer, där vi lägger in innehållet i små filer tillsammans med metadata och använder databasstransaktioner och databasreplikation för att garantera de små filernas tillgänglighet, integritet och konsistens säkerställs. HopsFS möjliggör signifikant större klusterstorlekar, mer än en storleksordning högre transaktionsgenomströmning, och signifikant lägre latens för klienter till stora kluster.Slutligen är koordinering en central del av protokollet för distribuerade filsystemsoperationer. Vi presenterar ett nytt ledarval protokoll för delvis synkrona system som använder NewSQL databaser som delat minne. Vårt arbete möjliggör HopsFS, som använder en NewSQL-databas för att spara in på de operativa kostnader det skulle medföra att hantera en ytterligare tredjepartstjänst för ledarval. Protokollets prestanda kan jämföras med en ledarval implementation I ZooKeeper, som är en modern distribuerad koordinationsservice.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2018. p. 196
Series
TRITA-EECS-AVL ; 2018 : 79
National Category
Computer Systems
Research subject
Information and Communication Technology
Identifiers
urn:nbn:se:kth:diva-238605 (URN)978-91-7729-987-5 (ISBN)
Public defence
2018-12-07, Sal-B, Electrum, Kungliga Tekniska Högskolan, Kistagången 16, Kista, Stockholm, 13:45 (English)
Opponent
Supervisors
Available from: 2018-11-05 Created: 2018-11-05 Last updated: 2018-11-06Bibliographically approved

Open Access in DiVA

fulltext(249 kB)124 downloads
File information
File name FULLTEXT01.pdfFile size 249 kBChecksum SHA-512
be3ea59c587e4bec58e71f8e2ca4e2009c182aabea0616bf060f263845ad891747c17a072ed29f9d01ad7667e32e67c8822ff4eb705b6fb6a9c15217e37d71b4
Type fulltextMimetype application/pdf

Other links

Publisher's full textConference websiteThe final publication is available at www.springerlink.com

Search in DiVA

By author/editor
Niazi, SalmanDowling, JimIsmail, Mahmoud
By organisation
Software and Computer systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 124 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 138 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf