Refine
Year of publication
Document Type
- In Proceedings (31)
- Article (12)
- ZIB-Report (5)
- Other (4)
- Book chapter (3)
- Doctoral Thesis (1)
- Master's Thesis (1)
- Poster (1)
Is part of the Bibliography
- no (58)
Keywords
- DHT (3)
- Paxos (2)
- Algorithms (1)
- Distributed System (1)
- P2P (1)
- Range Queries (1)
- Storage (1)
- Transaktionen (1)
- heuristic search (1)
- multidimensional data sets (1)
- pattern databases (1)
- range queries (1)
- routing (1)
- strenge Konsistenz (1)
- strong consistency (1)
- structured overlays (1)
- transactions (1)
DataWarp: First Experiences
(2015)
General solutions of state machine replication have to ensure that all replicas apply the same commands in the same order, even in the presence of failures. Such strict ordering incurs high synchronization costs due to the use of distributed consensus or a leader.
This paper presents a protocol for linearizable state machine replication of conflict-free replicated data types (CRDTs) that neither requires consensus nor a leader. By leveraging the properties of state-based CRDTs—in particular the monotonic growth of a join semilattice—synchronization overhead is greatly reduced. In addition, updates just need a single round trip and modify the state ‘in-place’ without the need for a log. Furthermore, the message size overhead for coordination consists of a single counter per message. While reads in the presence of concurrent updates are not wait-free without a coordinator, we show that more than 97 % of reads can be handled in one or two round trips under highly concurrent accesses.
Our protocol achieves high throughput without auxiliary processes such as command log management or leader election. It is well suited for all practical scenarios that need linearizable access on CRDT data on a fine-granular scale.
Typical applications in data science consume, process and produce large amounts of data, making disk I/O one of the dominating — and thus worthwhile optimizing — factors of their overall performance. Distributed processing frameworks, such as Hadoop, Flink and Spark, hide a lot of complexity from the programmer when they parallelize these applications across a compute cluster. This exacerbates reasoning about I/O of both the application and the framework, through the distributed file system, such as HDFS, down to the local file systems.
We present SFS (Statistics File System), a modular framework to trace each I/O request issued by the application and any JVM-based big data framework involved, mapping these requests to actual disk I/O.
This allows detection of inefficient I/O patterns, both by the applications and the underlying frameworks, and builds the basis for improving I/O scheduling in the big data software stack.
General solutions of state machine replication have to ensure that all replicas apply the same commands in the same order, even in the presence of failures. Such strict ordering incurs high synchronization costs caused by distributed consensus or by the use of a leader.
This paper presents a protocol for linearizable state machine replication of conflict-free replicated data types (CRDTs) that neither requires consensus nor a leader. By leveraging the properties of state-based CRDTs - in particular the monotonic growth of a join semilattice - synchronization overhead is greatly reduced. In addition, updates just need a single round trip and modify the state `in-place' without the need for a log. Furthermore, the message size overhead for coordination consists of a single counter per message. While reads in the presence of concurrent updates are not wait-free without a coordinator, we show that more than 97% of reads can be handled in one or two round trips under highly concurrent accesses.
Our protocol achieves high throughput without auxiliary processes like command log management or leader election. It is well suited for all practical scenarios that need linearizable access on CRDT data on a fine-granular scale.
We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries.