Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 92) Show all publications
Niazi, S., Ismail, M., Haridi, S., Dowling, J., Grohsschmiedt, S. & Ronström, M. (2017). HopsFS: Scaling Hierarchical File System Metadata Using NewSQL Databases. In: 15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017: . Paper presented at 15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017 (pp. 89-104). USENIX Association.
Open this publication in new window or tab >>HopsFS: Scaling Hierarchical File System Metadata Using NewSQL Databases
Show others...
2017 (English)In: 15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017, USENIX Association , 2017, 89-104 p.Conference paper, Published paper (Refereed)
Abstract [en]

Recent improvements in both the performance and scalability of shared-nothing, transactional, in-memory NewSQL databases have reopened the research question of whether distributed metadata for hierarchical file systems can be managed using commodity databases. In this paper, we introduce HopsFS, a next generation distribution of the Hadoop Distributed File System (HDFS) that replaces HDFS’ single node in-memory metadata service, with a distributed metadata service built on a NewSQL database. By removing the metadata bottleneck, HopsFS enables an order of magnitude larger and higher throughput clusters compared to HDFS. Metadata capacity has been increased to at least 37 times HDFS’ capacity, and in experiments based on a workload trace from Spotify, we show that HopsFS supports 16 to 37 times the throughput of Apache HDFS. HopsFS also has lower latency for many concurrent clients, and no downtime during failover. Finally, as metadata is now stored in a commodity database, it can be safely extended and easily exported to external systems for online analysis and free-text search.

Place, publisher, year, edition, pages
USENIX Association, 2017
National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-205355 (URN)
Conference
15th USENIX Conference on File and Storage Technologies, FAST 2017, Santa Clara, CA, USA, February 27 - March 2, 2017
Note

QC 20170424

Available from: 2017-04-13 Created: 2017-04-13 Last updated: 2017-04-24Bibliographically approved
Kroll, L., Carbone, P. & Haridi, S. (2017). Kompics Scala: Narrowing the gap between algorithmic specification and executable code (short paper). In: Proceedings of the 8th ACM SIGPLAN International Symposium on Scala: . Paper presented at ACM SIGPLAN International Symposium on Scala (pp. 73-77). ACM Digital Library.
Open this publication in new window or tab >>Kompics Scala: Narrowing the gap between algorithmic specification and executable code (short paper)
2017 (English)In: Proceedings of the 8th ACM SIGPLAN International Symposium on Scala, ACM Digital Library, 2017, 73-77 p.Conference paper, Published paper (Refereed)
Abstract [en]

Message-based programming frameworks facilitate the development and execution of core distributed computing algorithms today. Their twofold aim is to expose a programming model that minimises logical errors incurred during translation from an algorithmic specification to executable program, and also to provide an efficient runtime for event pattern-matching and scheduling of distributed components. Kompics Scala is a framework that allows for a direct, streamlined translation from a formal algorithm specification to practical code by reducing the cognitive gap between the two representations. Furthermore, its runtime decouples event pattern-matching and component execution logic yielding clean, thoroughly expected behaviours. Our evaluation shows low and constant performance overhead of Kompics Scala compared to similar frameworks that otherwise fail to offer the same level of model clarity.

Place, publisher, year, edition, pages
ACM Digital Library, 2017
Keyword
component model, message-passing, distributed systems architecture
National Category
Information Systems
Research subject
Information and Communication Technology
Identifiers
urn:nbn:se:kth:diva-218781 (URN)10.1145/3136000.3136009 (DOI)2-s2.0-85037137982 (Scopus ID)978-1-4503-5529-2 (ISBN)
Conference
ACM SIGPLAN International Symposium on Scala
Note

QC 20180111

Available from: 2017-11-30 Created: 2017-11-30 Last updated: 2018-01-13Bibliographically approved
Carbone, P., Gévay, G. E., Hermann, G., Katsifodimos, A., Soto, J., Markl, V. & Haridi, S. (2017). Large-scale data stream processing systems. In: Handbook of Big Data Technologies: (pp. 219-260). Springer International Publishing.
Open this publication in new window or tab >>Large-scale data stream processing systems
Show others...
2017 (English)In: Handbook of Big Data Technologies, Springer International Publishing , 2017, 219-260 p.Chapter in book (Other academic)
Abstract [en]

In our data-centric society, online services, decision making, and other aspects are increasingly becoming heavily dependent on trends and patterns extracted from data. A broad class of societal-scale data management problems requires system support for processing unbounded data with low latency and high throughput. Large-scale data stream processing systems perceive data as infinite streams and are designed to satisfy such requirements. They have further evolved substantially both in terms of expressive programming model support and also efficient and durable runtime execution on commodity clusters. Expressive programming models offer convenient ways to declare continuous data properties and applied computations, while hiding details on how these data streams are physically processed and orchestrated in a distributed environment. Execution engines provide a runtime for such models further allowing for scalable yet durable execution of any declared computation. In this chapter we introduce the major design aspects of large scale data stream processing systems, covering programming model abstraction levels and runtime concerns. We then present a detailed case study on stateful stream processing with Apache Flink, an open-source stream processor that is used for a wide variety of processing tasks. Finally, we address the main challenges of disruptive applications that large-scale data streaming enables from a systemic point of view.

Place, publisher, year, edition, pages
Springer International Publishing, 2017
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-216552 (URN)10.1007/978-3-319-49340-4_7 (DOI)2-s2.0-85019960984 (Scopus ID)9783319493404 (ISBN)9783319493398 (ISBN)
Note

QC 20171108

Available from: 2017-11-08 Created: 2017-11-08 Last updated: 2017-11-08Bibliographically approved
Carbone, P., Ewen, S., Fora, G., Haridi, S., Richter, S. & Tzoumas, K. (2017). State Management in Apache Flink (R) Consistent Stateful Distributed Stream Processing. Proceedings of the VLDB Endowment, 10(12), 1718-1729.
Open this publication in new window or tab >>State Management in Apache Flink (R) Consistent Stateful Distributed Stream Processing
Show others...
2017 (English)In: Proceedings of the VLDB Endowment, ISSN 2150-8097, E-ISSN 2150-8097, Vol. 10, no 12, 1718-1729 p.Article in journal (Refereed) Published
Abstract [en]

Stream processors are emerging in industry as an apparatus that drives analytical but also mission critical services handling the core of persistent application logic. Thus, apart from scalability and low-latency, a rising system need is first-class support for application state together with strong consistency guarantees, and adaptivity to cluster reconfigurations, software patches and partial failures. Although prior systems research has addressed some of these specific problems, the practical challenge lies on how such guarantees can be materialized in a transparent, non-intrusive manner that relieves the user from unnecessary constraints. Such needs served as the main design principles of state management in Apache Flink, an open source, scalable stream processor. We present Flink's core pipelined, in-flight mechanism which guarantees the creation of lightweight, consistent, distributed snapshots of application state, progressively, without impacting continuous execution. Consistent snapshots cover all needs for system reconfiguration, fault tolerance and version management through coarse grained rollback recovery. Application state is declared explicitly to the system, allowing efficient partitioning and transparent commits to persistent storage. We further present Flink's backend implementations and mechanisms for high availability, external state queries and output commit. Finally, we demonstrate how these mechanisms behave in practice with metrics and largedeployment insights exhibiting the low performance trade-offs of our approach and the general benefits of exploiting asynchrony in continuous, yet sustainable system deployments.

National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-220296 (URN)000416494000011 ()2-s2.0-85036646347 (Scopus ID)
Note

QC 20171222

Available from: 2017-12-22 Created: 2017-12-22 Last updated: 2018-01-13Bibliographically approved
Zeng, J., Barreto, J., Haridi, S., Rodrigues, L. & Romano, P. (2016). The Future(s) of Transactional Memory. In: Proceedings of the International Conference on Parallel Processing: . Paper presented at 45th International Conference on Parallel Processing, ICPP 2016, 16 August 2016 through 19 August 2016 (pp. 442-451). Institute of Electrical and Electronics Engineers (IEEE).
Open this publication in new window or tab >>The Future(s) of Transactional Memory
Show others...
2016 (English)In: Proceedings of the International Conference on Parallel Processing, Institute of Electrical and Electronics Engineers (IEEE), 2016, 442-451 p.Conference paper, Published paper (Refereed)
Abstract [en]

This work investigates how to combine two powerful abstractions to manage concurrent programming: Transactional Memory (TM) and futures. The former hides from programmers the complexity of synchronizing concurrent access to shared data, via the familiar abstraction of atomic transactions. The latter serves to schedule and synchronize the parallel execution of computations whose results are not immediately required. While TM and futures are two widely investigated topics, the problem of how to exploit these two abstractions in synergy is still largely unexplored in the literature. This paper fills this gap by introducing Java Transactional Futures (JTF), a Java-based TM implementation that allows programmers to use futures to coordinate the execution of parallel tasks, while leveraging transactions to synchronize accesses to shared data. JTF provides a simple and intuitive semantic regarding the admissible serialization orders of the futures spawned by transactions, by ensuring that the results produced by a future are always consistent with those that one would obtain by executing the future sequentially. Our experimental results show that the use of futures in a TM allows not only to unlock parallelism within transactions, but also to reduce the cost of conflicts among top-level transactions in high contention workloads.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2016
Keyword
Concurrent programming, Futures, Transactional Memory, Abstracting, Computer programming, Java programming language, Semantics, Storage allocation (computer), Atomic transaction, Concurrent access, High contentions, Parallel executions, Parallel task, Concurrency control
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-195320 (URN)10.1109/ICPP.2016.57 (DOI)000387089600050 ()2-s2.0-84990909847 (Scopus ID)9781509028238 (ISBN)
Conference
45th International Conference on Parallel Processing, ICPP 2016, 16 August 2016 through 19 August 2016
Note

QC 20161109

Available from: 2016-11-09 Created: 2016-11-02 Last updated: 2017-01-10Bibliographically approved
Rahimian, F., Payberah, A. H., Girdzijauskas, S., Jelasity, M. & Haridi, S. (2015). A Distributed Algorithm for Large-Scale Graph Partitioning. ACM Transactions on Autonomous and Adaptive Systems, 10(2), Article ID 12.
Open this publication in new window or tab >>A Distributed Algorithm for Large-Scale Graph Partitioning
Show others...
2015 (English)In: ACM Transactions on Autonomous and Adaptive Systems, ISSN 1556-4665, E-ISSN 1556-4703, Vol. 10, no 2, 12Article in journal (Refereed) Published
Abstract [en]

Balanced graph partitioning is an NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems, including the optimal storage of large sets of graph-structured data over several hosts. However, in very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable because they typically involve frequent global operations over the entire graph. In this article, we propose a fully distributed algorithm called JA-BE-JA that uses local search and simulated annealing techniques for two types of graph partitioning: edge-cut partitioning and vertex-cut partitioning. The algorithm is massively parallel: There is no central coordination, each vertex is processed independently, and only the direct neighbors of a vertex and a small subset of random vertices in the graph need to be known locally. Strict synchronization is not required. These features allow JA-BE-JA to be easily adapted to any distributed graph-processing system from data centers to fully distributed networks. We show that the minimal edge-cut value empirically achieved by JA-BE-JA is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks, JA-BE-JA outperforms Metis. We also show that JA-BE-JA computes very low vertex-cuts, which are proved significantly more effective than edge-cuts for processing most real-world graphs.

Place, publisher, year, edition, pages
ACM: , 2015
National Category
Engineering and Technology
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-170128 (URN)10.1145/2714568 (DOI)2-s2.0-84930973235 (Scopus ID)
Projects
End to End Clouds
Funder
Swedish Foundation for Strategic Research
Note

QC 20150629

Available from: 2015-06-26 Created: 2015-06-26 Last updated: 2017-12-04Bibliographically approved
Carbone, P., Fóra, G., Ewen, S., Haridi, S. & Tzoumas, K. (2015). Lightweight Asynchronous Snapshots for Distributed Dataflows. .
Open this publication in new window or tab >>Lightweight Asynchronous Snapshots for Distributed Dataflows
Show others...
2015 (English)Report (Other academic)
Abstract [en]

Distributed stateful stream processing enables the deployment and execution of large scale continuous computations in the cloud, targeting both low latency and high throughput. One of the most fundamental challenges of this paradigm is providing processing guarantees under potential failures. Existing approaches rely on periodic global state snapshots that can be used for failure recovery. Those approaches suffer from two main drawbacks. First, they often stall the overall computation which impacts ingestion. Second, they eagerly persist all records in transit along with the operation states which results in larger snapshots than required. In this work we propose Asynchronous Barrier Snapshotting (ABS), a lightweight algorithm suited for modern dataflow execution engines that minimises space requirements. ABS persists only operator states on acyclic execution topologies while keeping a minimal record log on cyclic dataflows. We implemented ABS on Apache Flink, a distributed analytics engine that supports stateful stream processing. Our evaluation shows that our algorithm does not have a heavy impact on the execution, maintaining linear scalability and performing well with frequent snapshots. 

Publisher
8 p.
Series
TRITA-ICT, 2015:08
Keyword
fault tolerance, distributed computing, stream processing, dataflow, cloud computing, state management
National Category
Computer Systems
Research subject
Information and Communication Technology; Computer Science
Identifiers
urn:nbn:se:kth:diva-170185 (URN)978-91-7595-651-0 (ISBN)
Note

QC 20150630

Available from: 2015-06-28 Created: 2015-06-28 Last updated: 2015-06-30Bibliographically approved
Roverso, R., Reale, R., El-Ansary, S. & Haridi, S. (2015). SmoothCache 2.0: CDN-quality adaptive HTTP live streaming on peer-to-peer overlays. In: ACM (Ed.), Proceedings of the 6th ACM Multimedia Systems Conference: . Paper presented at Proceedings of the 6th ACM Multimedia Systems Conference (pp. 61-72). .
Open this publication in new window or tab >>SmoothCache 2.0: CDN-quality adaptive HTTP live streaming on peer-to-peer overlays
2015 (English)In: Proceedings of the 6th ACM Multimedia Systems Conference / [ed] ACM, 2015, 61-72 p.Conference paper, Published paper (Refereed)
Abstract [en]

In recent years, adaptive HTTP streaming protocols have become the de-facto standard in the industry for the distribution of live and video-on-demand content over the Internet. This paper presents SmoothCache 2.0, a distributed cache platform for adaptive HTTP live streaming content based on peer-to-peer (P2P) overlays. The contribution of this work is twofold. From a systems perspective, to the best of our knowledge, it is the only P2P platform which supports recent live streaming protocols based on HTTP as a transport and the concept of adaptive bitrate switching. From an algorithmic perspective, the system describes a novel set of overlay construction and prefetching techniques that realize: i) substantial savings in terms of the bandwidth load on the source of the stream, and ii) CDN-quality user experience in terms of playback latency and the watched bitrate. In order to support our claims, we conduct a methodical evaluation on thousands of real consumer machines.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:kth:diva-170130 (URN)10.1145/2713168.2713182 (DOI)2-s2.0-84942520092 (Scopus ID)
Conference
Proceedings of the 6th ACM Multimedia Systems Conference
Note

QC 20150629

Available from: 2015-06-26 Created: 2015-06-26 Last updated: 2015-11-17Bibliographically approved
Kalavri, V., Ewen, S., Tzoumas, K., Vlassov, V., Markl, V. & Haridi, S. (2014). Asymmetry in Large-Scale Graph Analysis, Explained. In: Proceedings of the Second International Workshop on Graph Data ManagementExperience and Systems (GRADES 2014), June 22, 2014, Snowbird, Utah, USA.: . Paper presented at 2nd International Workshop on Graph Data Management Experiences and Systems, GRADES 2014 - Co-located with SIGMOD/PODS 2014; Snowbird, UT, United States, 22 June 2014 - 27 June 2014. .
Open this publication in new window or tab >>Asymmetry in Large-Scale Graph Analysis, Explained
Show others...
2014 (English)In: Proceedings of the Second International Workshop on Graph Data ManagementExperience and Systems (GRADES 2014), June 22, 2014, Snowbird, Utah, USA., 2014Conference paper, Published paper (Refereed)
Abstract [en]

Iterative computations are in the core of large-scale graph processing. In these applications, a set of parameters is continuously refined, until a fixed point is reached. Such fixed point iterations often exhibit non-uniform computational behavior, where changes propagate with different speeds throughout the parameter set, making them active or inactive during iterations. This asymmetrical behavior can lead to a many redundant computations, if not exploited. Many specialized graph processing systems and APIs exist that run iterative algorithms efficiently exploiting this asymmetry. However, their functionality is sometimes vaguely defined and due to their different programming models and terminology used, it is often challenging to derive equivalence between them. We describe an optimization framework for iterative graph processing, which utilizes dataset dependencies. We explain several optimization techniques that exploit asymmetrical behavior of graph algorithms. We formally specify the conditions under which, an algorithm can use a certain technique. We also design template execution plans, using a canonical set of dataflow operators and we evaluate them using real-world datasets and applications. Our experiments show that optimized plans can significantly reduce execution time, often by an order of magnitude. Based on our experiments, we identify a trade-off that can be easily captured and could serve as the basis for automatic optimization of large-scale graph-processing applications.

National Category
Engineering and Technology Computer Systems
Identifiers
urn:nbn:se:kth:diva-145335 (URN)2-s2.0-84905640971 (Scopus ID)
Conference
2nd International Workshop on Graph Data Management Experiences and Systems, GRADES 2014 - Co-located with SIGMOD/PODS 2014; Snowbird, UT, United States, 22 June 2014 - 27 June 2014
Note

QC 20150309

Available from: 2014-05-16 Created: 2014-05-16 Last updated: 2017-04-28Bibliographically approved
Rahimian, F., Payberah, A. H., Girdzijauskas, S. & Haridi, S. (2014). Distributed Vertex-Cut Partitioning. In: In the 14th IFIP international conference on Distributed Applications and Interoperable Systems (DAIS’14).: . Paper presented at 14th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS’14). (pp. 186-200). .
Open this publication in new window or tab >>Distributed Vertex-Cut Partitioning
2014 (English)In: In the 14th IFIP international conference on Distributed Applications and Interoperable Systems (DAIS’14)., 2014, 186-200 p.Conference paper, Published paper (Refereed)
Abstract [en]

Graph processing has become an integral part of big data analytics. With the ever increasing size of the graphs, one needs to partition them into smaller clusters, which can be managed and processed more easily on multiple machines in a distributed fashion. While there exist numerous solutions for edge-cut partitioning of graphs, very little effort has been made for vertex-cut partitioning. This is in spite of the fact that vertex-cuts are proved significantly more effective than edge-cuts for processing most real world graphs. In this paper we present Ja-be-Ja-vc, a parallel and distributed algorithm for vertex-cut partitioning of large graphs. In a nutshell, Ja-be-Ja-vc is a local search algorithm that iteratively improves upon an initial random assignment of edges to partitions. We propose several heuristics for this optimization and study their impact on the final partitioning. Moreover, we employ simulated annealing technique to escape local optima. We evaluate our solution on various graphs and with variety of settings, and compare it against two state-of-the-art solutions. We show that Ja-be-Ja-vc outperforms the existing solutions in that it not only creates partitions of any requested size, but also requires a vertex-cut that is better than its counterparts and more than 70% better than random partitioning.

Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743
Keyword
Big data, Graphic methods, Interoperability, Iterative methods, Simulated annealing, Data analytics, Graph processing, Local search algorithm, Multiple machine, Parallel and distributed algorithms, Random assignment, Real-world graphs, Simulated annealing techniques, Graph theory
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-145359 (URN)10.1007/978-3-662-43352-2_15 (DOI)2-s2.0-84902593727 (Scopus ID)9783662433515 (ISBN)
Conference
14th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS’14).
Note

QC 20140519

Available from: 2014-05-19 Created: 2014-05-19 Last updated: 2018-01-11Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-6718-0144

Search in DiVA

Show all publications