An Efficient Data Store for a Dependable Distributed Control Unit

Abstract

Brandmeldeanlagen erfüllen eine sicherheitskritische Funktion und müssen zuverlässig arbeiten. Daher wird eine dezentrale Architektur verwendet, wenn größere Bereiche oder mehrere Gebäude abgedeckt werden sollen: Autonome Steuereinheiten werden zu einer verteilten Steuereinheit vernetzt und teilen sich einen gemeinsamen logischen Zustand. Um Fehlertoleranz und hohe Zuverlässigkeit zu gewährleisten, kann ein kontinuierlich replizierender verteilter Datenspeicher verwendet werden. Wie die CAP- und PACELC-Theoreme zeigen, müssen dabei jedoch Kompromisse eingegangen werden zwischen Datenkonsistenz, Verfügbarkeit und Latenzzeit. Im Zuge dieser Arbeit untersuchen wir, ob schwache Konsistenzmodelle – die bessere Verfügbarkeit, Latenzzeit und Nebenläufigkeit ermöglichen können – für einen korrekten und sicheren Betrieb auf Hardware mit limitierten Ressourcen ausreichen. Wir identifizieren das schwächste geeignete Konsistenzmodell und entwickeln eine passende Architektur für einen Datenspeicher, der dieses Modell auf eingebetteten Geräten bereitstellen kann. Zunächst werden aus den Produktkriterien der europäischen Normenreihe EN 54 die Anforderungen gesammelt und verwandte Arbeiten zu Konsistenzmodellen und Replikation in verteilten Systemen gesichtet. Dann entwickeln wir, dem Forschungsansatz der Design Science folgend, iterativ eine Architektur und parallel dazu einen Prototyp. Der Prototyp ermöglicht es, Probleme des Designs frühzeitig zu erkennen. Schließlich bewerten wir das Design qualitativ anhand der Anforderungen und testen den Prototyp mit einer Simulationssoftware. Diese Software kann Netzwerkprobleme wie Latenzzeiten und Verluste simulieren, um deren Auswirkungen auf den Betrieb zu messen. Das aufgezeichnete Protokoll kann zur Überprüfung der Korrektheit in Bezug auf das beabsichtigte Konsistenzmodell verwendet werden. Wir zeigen, dass das FIFO/PRAM-Konsistenzmodell den Anforderungen genügt. Das Modell stellt sicher, dass alle Teilnehmer die Schreiboperationen eines Teilnehmers in genau der Reihenfolge verarbeiten, in der sie von diesem Teilnehmer durchgeführt wurden. Wir schlagen eine Erweiterung des NDC-Frameworks vor und bauen unser Design darauf auf. Das Design beinhaltet einen Algorithmus, der FIFO-konsistente Sichten sicherstellt und das Risiko von Prioritätsumkehr ausschließt. Optimierungen für das Anti-Entropie-Protokoll tragen dazu bei, die Latenzzeit gering zu halten. Die Auswertung zeigt, dass das Design die Anforderungen erfüllen kann. Die Testergebnisse zeigen, dass der Prototyp in der Lage ist, eine konsistente Sicht bei Netzwerkfehlern aufrechtzuerhalten, allerdings auf Kosten einer leicht erhöhten Latenzzeit im Vergleich zu Eventual Consistency.

Fire Detection and Fire Alarm systems have a safety-critical role and must operate reliably. Therefore, a decentralized architecture is used when large areas or multiple buildings need to be covered: Autonomous control units are networked together to form a distributed control unit and share common logical state. To ensure fault tolerance and high reliability, a continuously replicating distributed data store may be used. However, as shown by the CAP and PACELC theorems, there are trade-offs involved between data consistency, availability, and latency. In this work, we investigate whether relaxed consistency models—which can obtain better availability, latency and concurrency—can be sufficient for correct and safe operation on resource constrained hardware. We identify the weakest consistency model suitable for the purpose, and develop a software architecture for a data store that can provide the model on constrained devices. First, we gather requirements from the product criteria defined by the European Standards series EN 54 and conduct a review of existing work on consistency models and replication in distributed systems. Then, following a design science approach, we iteratively develop a software architecture in parallel to a prototype. The prototype allows early identification of problems with the design. Finally, we evaluate the design qualitatively against the requirements and test the prototype with simulation testing software. The software can introduce networking artifacts—such as latency and message loss—to measure their effects on the executed operations. The recorded history can be used to verify correctness with respect to the intended consistency model. We show that the FIFO/PRAM consistency model is adequate. It ensures that all nodes observe write operations from one node in the order they were issued by the node. We propose an extension of the node-wide dot-based clocks (NDC) framework and base our design on it. The design incorporates an algorithm that provides FIFO consistent views while ruling out the risk of priority inversion scenarios. Optimizations for the anti-entropy protocol help to keep latency low. The evaluation finds that the design is able to meet the requirements. The testing results show that the implemented prototype is able to maintain a consistent view under network faults, at the cost of a slightly increased visibility latency compared to eventual consistency.