Search

The past few years have seen a wave of enthusiasm for serverless computing, and we begin this work by analyzing the marketplace trends and underlying technical factors that have shaped the movement. We find that serverless computing addresses programming challenges in the same class as those that high-level programming languages address, suggesting that serverless computing may be viewed as high-level programming for distributed systems.We next turn our attention to one of the key shortcomings of serverless: the lack of integration between compute and state. We develop FaaSFS, a distributed file system that is compatible with POSIX applications but uses a novel consistency model with relaxed real-time ordering constraints. We call this model externally consistent sequential consistency (ECSC) and use it to scale a pre-existing single-server application to 10,000 serverless processes. We also show that under reasonable assumptions ECSC is indistinguishable from linearizability, a widely accepted strong form of consistency.Lastly, we explore whether serverless computing might lead to the demise of server hardware. By applying Amdahl's law and scaling rules for interconnect costs, we show that applications that rely on coordination protocols are particularly dependent on large servers for scalability. In contrast, those implemented with coordination-free protocols can run well on collections of small, low-cost servers or on disaggregated hardware. These approaches will likely continue to coexist, suggesting that a need for underlying server hardware will remain even as serverless abstractions thrive.

Moving toward exascale computing, the size of data stored and accessed by applications is ever increasing. However, traditional disk-based storage has not seen improvements that keep up with the explosion of data volume or the speed of processors. Multiple levels of non-volatile storage devices are being added to handle bursty I/O, however, moving data across the storage hierarchy can take longer than the data generation or analysis. Asynchronous I/O can reduce the impact of I/O latency as it allows applications to schedule I/O early and to check their status later. I/O is thus overlapped with application communication or computation or both, effectively hiding some or all of the I/O latency. POSIX and MPI-I/O provide asynchronous read and write operations, but lack the support for non-data operations such as file open and close. Users also have to manually manage data dependencies and use low-level byte offsets, which requires significant effort and expertise to adopt. In this article, we present an asynchronous I/O framework that supports all types of I/O operations, manages data dependencies transparently and automatically, provides implicit and explicit modes for application flexibility, and error information retrieval. We implemented these techniques in HDF5. Our evaluation of several benchmarks and application workloads demonstrates it effectiveness on hiding the I/O cost from the application.

The Hierarchical Data Format 5 (HDF5) has long been defined as one of the most prominent data models, binary file formats and I/O libraries for storing and managing scientific data. Introduced in the late 90s when POSIX I/O was the standard, the library has since then been continuously improved to respond and adapt to the ever-growing demands of high-performance computing (HPC) software and hardware. Given the limitations of POSIX I/O and with the emergence of new technologies such as object stores, non-volatile memory, and SSDs, the need for an interface that can efficiently store and access data at scale through new paradigms has become more and more pressing. The Distributed Asynchronous Object Storage (DAOS) file system is an emerging file system that aims at responding to those demands by taking disk-based storage out of the loop. We present in this article the research efforts that have been taking place to prepare the HDF5 library for Exascale using DAOS. By enabling and defining a new storage file format, we focus on the benefits that it delivers to the applications in terms of features and performance.

Supervisor: 青木 利晃, 先端科学技術研究科, 修士（情報科学）

Comprehending existing multi-threaded applications effectively is a challenge without proper assistance. Research has been proposed to mine programs to extract aspects of high-level design but not much to reverse-engineer the concurrent design from multi-threaded applications. To address the same, we develop a generic mathematical model to interpret run-time non-deterministic events and encode functional as well as thread-specific behaviour in form of quantifiable features, which can be fitted into a standard solver for automated inference of design aspects from multi-threaded applications. We build a tool Dcube based on the mathematical model and use various classifiers of a machine learning framework to infer design aspects related to concurrency and resource management. We collect a dataset of 480 projects from Github, CodeProject and Stack Overflow and 3 benchmark suites—CDAC Pthreads, Open POSIX Test Suites and PARSEC 3.0 and achieve an accuracy score of around 93.71% for all the design choices.

Whereas Perl-compatible regular expression matchers typically exhibit some variation of leftmost-greedy semantics, those conforming to the posix standard are prescribed leftmost-longest semantics. However, the posix standard leaves some room for interpretation, and Fowler and Kuklewicz have done experimental work to confirm differences between various posix matchers. The Boost library has an interesting take on the posix standard, where it maximises the leftmost match not with respect to subexpressions of the regular expression pattern, but rather, with respect to capturing groups. In our work, we provide the first formalisation of Boost semantics, analyze the complexity of regular expression matching when using Boost semantics, and provide efficient algorithms for both online and multipass matching.

International audience; Distributed applications are part of our everyday lives, but too often their good operation depends on central servers, all potential points of failure and performance bottlenecks. Designing systems for fully distributed communications however still requires porting common mechanisms needed for feature-rich modern applications such as user rights differentiation, multiple administrators, and end-to-end encryption. We propose a distributed access control mechanism for collaborative applications by relying on conflict-free replicated data types (CRDT), and design an access control policy CRDT able to support Google Docs and POSIX file systems as example of distributed applications. To enforce that policy, we outline a generic data model, examine different conflict resolution strategies at the data and policy levels, and consider a novel approach towards conflicts between data and policy operations.

File systems are too large to be bug free. Although handwritten test suites have been widely used to stress file systems, they can hardly keep up with the rapid increase in file system size and complexity, leading to new bugs being introduced. These bugs come in various flavors: buffer overflows to complicated semantic bugs. Although bug-specific checkers exist, they generally lack a way to explore file system states thoroughly. More importantly, no turnkey solution exists that unifies the checking effort of various aspects of a file system under one umbrella. In this article, to highlight the potential of applying fuzzing to find any type of file system bugs in a generic way, we propose H ydra , an extensible fuzzing framework. H ydra provides building blocks for file system fuzzing, including input mutators, feedback engines, test executors, and bug post-processors. As a result, developers only need to focus on building the core logic for finding bugs of their interests. We showcase the effectiveness of H ydra with four checkers that hunt crash inconsistency, POSIX violations, logic assertion failures, and memory errors. So far, H ydra has discovered 157 new bugs in Linux file systems, including three in verified file systems (FSCQ and Yxv6).

The efficient codes can take an advantage of multiple threads and/or processing nodes to partition a work that can be processed concurrently. This can reduce the overall run-time or make the solution of a large problem feasible. This paper deals with evaluation of different parallelization strategies of assembly operations for global vectors and matrices, which are one of the critical operations in any finite element software. Different assembly strategies for systems with a shared memory model are proposed and evaluated, using Open Multi-Processing (OpenMP), Portable Operating System Interface (POSIX), and C++11 Threads. The considered strategies are based on simple synchronization directives, various block locking algorithms and, finally, on smart locking free processing based on a colouring algorithm. The different strategies were implemented in a free finite element code with object-oriented architecture OOFEM [1].

Many scientific fields increasingly use high-performance computing (HPC) to process and analyze massive amounts of experimental data while storage systems in today’s HPC environments have to cope with new access patterns. These patterns include many metadata operations, small I/O requests, or randomized file I/O, while general-purpose parallel file systems have been optimized for sequential shared access to large files. Burst buffer file systems create a separate file system that applications can use to store temporary data. They aggregate node-local storage available within the compute nodes or use dedicated SSD clusters and offer a peak bandwidth higher than that of the backend parallel file system without interfering with it. However, burst buffer file systems typically offer many features that a scientific application, running in isolation for a limited amount of time, does not require. We present GekkoFS, a temporary, highly-scalable file system which has been specifically optimized for the aforementioned use cases. GekkoFS provides relaxed POSIX semantics which only offers features which are actually required by most (not all) applications. GekkoFS is, therefore, able to provide scalable I/O performance and reaches millions of metadata operations already for a small number of nodes, significantly outperforming the capabilities of common parallel file systems.

Existing Internet of Things (IoT) platforms introduce various framework-specific APIs for building user applications, which causes technology fragmentation within the IoT ecosystem and incur engineering costs. I seek to adopt standard POSIX APIs in an IoT platform, to provide an environment much like a distributed operating system (OS). Building a distributed OS for IoT systems poses several challenges due to the high degree of heterogeneity and dynamism, lack of application semantics, and novel security requirements. I propose a system called OneOS, which addresses the challenges of building a distributed OS for the Internet of Things.

The POSIX shell is 'stringy', and its ecosystem primarily supports line-oriented formats. While such formats are popular and common, contemporary programming often involves semi-structured data, like JSON or YAML. Dealing with such formats, the shell's stringiness leaves users out in the cold---the POSIX ecosystem struggles with semi-structured data. New command-line tools work well with 'modern' data formats, but each tool is its own complex language to learn. The tree-like filesystem is the shell's only real data structure. By mapping 'modern' formats onto file hierarchies, we can work effectively in the existing ecosystem. We introduce ffs, the file filesystem, a new tool for mapping semi-structured data formats to filesystems in userspace. Like /proc and /sys, our filesystem-based approach helps the shell (and other tools) manipulate structured data.

Developing and maintaining a file system is time-consuming, typically requiring years of effort. Developers often test compliance with APIs such as POSIX with hand-written regression suites that, alas, examine only a fraction of a file system's state space. Conversely, formal model checking can explore vast state spaces efficiently, increasing confidence in the file system's implementation. Yet model checking is not currently part of file system development. Our position is that file systems should be designed a priori to facilitate model checking. To this end, we introduce MCFS, an architecture for efficient and comprehensive file-system model checking. MCFS relies on two new APIs that save and restore a file system's in-memory and on-disk state. We describe our earlier attempts at model-checking file systems, including unsuccessful or inefficient ones. Those attempts led us to develop VeriFS, which implements the new APIs. We illustrate MCFS's model-checking principles with VeriFS, a FUSE-based file system we were able to quickly develop with MCFS's help.

Scientific workflows often consist of black-box stand-alone programs that each write to one or more files, resulting in significant I/O operations. When strung together, each stage of the pipeline is bottlenecked by I/O, without much ability to modify that behavior. Since computation capabilities of large-scale distributed systems grow much faster than their I/O bandwidth, processing such big data using these workflows does not scale as the amount of data grows. While most related work focuses on data aggregation by modifying source code, we propose a Function Interception Library for Collective I/O (FILCIO), to intercept I/O function calls in C’s stdio library on a POSIX file system. This aggregates outgoing data in memory before writing to disk. Our aim is to scale I/O intensive scientific workflows without needing to access and modify their source code. In this paper, we motivate the need for I/O aggregation, and discuss what applications are poised to benefit most from FILCIO. We use an I/O intensive program where nearly 100% of its overall runtime is spent writing to disk. We show that the use of FILCIO results in a speedup of 1.75x over the native approach, and extrapolate that the best improvement is when a program generates a large volume of small writes. FILCIO is available at https://github.com/jensenq/io_aggregation

The POSIX shell is a widely deployed, powerful tool for managing computer systems. The shell is the expert’s control panel, a necessary tool for configuring, compiling, installing, maintaining, and deploying systems. Even though it is powerful, critical infrastructure, the POSIX shell is maligned and misunderstood. Its power and its subtlety are a dangerous combination. We define a formal, mechanized, executable small-step semantics for the POSIX shell, which we call Smoosh. We compared Smoosh against seven other shells that aim for some measure of POSIX compliance (bash, dash, zsh, OSH, mksh, ksh93, and yash). Using three test suites—the POSIX test suite, the Modernish test suite and shell diagnostic, and a test suite of our own device—we found Smoosh’s semantics to be the most conformant to the POSIX standard. Modernish judges Smoosh to have the fewest bugs (just one, from using dash’s parser) and no quirks. To show that our semantics is useful beyond yielding a conformant, executable shell, we also implemented a symbolic stepper to illuminate the subtle behavior of the shell. Smoosh will serve as a foundation for formal study of the POSIX shell, supporting research on and development of new shells, new tooling for shells, and new shell designs.

The Rowhammer bug is a novel micro-architectural security threat, enabling powerful privilege-escalation attacks on various mainstream platforms. It works by actively flipping bits in Dynamic Random Access Memory (DRAM) cells with unprivileged instructions. In order to set up Rowhammer against binaries in the Linux page cache, the Waylaying algorithm has previously been proposed. The Waylaying method stealthily relocates binaries onto exploitable physical addresses without exhausting system memory. However, the proof-of-concept Waylaying algorithm can be easily detected during page cache eviction because of its high disk I/O overhead and long running time. This paper proposes the more advanced Memway algorithm, which improves on Waylaying in terms of both I/O overhead and speed. Running time and disk I/O overhead are reduced by 90% by utilizing Linux tmpfs and inmemory swapping to manage eviction files. Furthermore, by combining Memway with the unprivileged posix fadvise API, the binary relocation step is made 100 times faster. Equipped with our Memway+fadvise relocation scheme, we demonstrate practical Rowhammer attacks that take only 15-200 minutes to covertly relocate a victim binary, and less than 3 seconds to flip the target instruction bit.