After five years of blood, sweat, and tears, TreeTracker Join ( \(\mathsf{TTJ}\) ) has finally been published. The research itself is very interesting and kept me hooked for five years. As a postmortem, I reflect on some of what I learned during the process. I’m hoping this post can be …
Motivation What I’m looking for Motivation Quite often, I stumble upon personal websites from academia with sentence like “I’m always in search of collaborators”. I figured I may try to write a sentence like that somewhere on my page as well. I think the most important reason for …
To celebrate the release of sphinxcontrib-pseudocode , the first sphinx-doc extension I have ever written, I document some implementation details behind this extension. Introduction Background Implementation Details Generating Unique IDs Handling JS scripts and code Support References Development Environment Setup Conclusion Introduction sphinxcontrib-pseudocode allows one to write \(\LaTeX\)…
Requirement Background Motherboard CPU CPU Cooler Graphics Card Storage Drive RAM Power Supply Unit (PSU) PC Chassis Tools My Choice Reference This page contains my note on how to build a PC. Requirement I use this PC mostly for research. The requirement is listed below: Large memory. 32GiB at least …
The paper presents a method to synthesize functional programs that transform recursive data structures (e.g., lists, trees) Examples: see Figure 6 (e.g., join , cprod ) essentially shows how one can orchestrate a list of operators to generate the desired program Three techniques type-aware inductive generalization purpose: create hypotheses that …
It has been a very long time since my last post. As you might know, I left AWS and started to work on my PhD. Research takes almost all my time. I have written a lot for my research, which consumes all my blogging energy. However, I decided to try …
As you all probably have noticed, I have been quiet since October last year. Here is a status update on my side: September last year, I was laid off due to the strategic change of my last employer and I was busy with job hunting. Luckily, I’m able to …
Concurrency is a big topic that I’m planning to write about more for the upcoming days. In this post, I’ll cover the concept “semaphore”, a very important concept when we talk about synchronization. I’ll walk through concept and offer an implementation of semaphore in C++ with a …
In this post, I discuss how we can have a secure connection with MariaDB by first understanding the computer science fundamentals behind the steps. Once we have built the concept model, the steps linked above are self-explanatory. In addition, this post applies the same concept to understand SSL ccertificate. Concepts …
Problem Background System Design Additional Reading Problem How can we design a distributed file system that: are scalable (e.g., supports hundreds of petabytes and beyond; extreme workload case) flexible to adjust to different workloads while maintaining good performance? Background Object-based storage (an abstraction layer between application and hard disks …
Problem Background System Design Problem How can we design programming interface for persistent memory (i.e., storage-class memory)? Background Storage-class memory (SCM) provides interface of memory (load and store instructions) but the persistence of disks System Design Expose SCM as a persistent memory abstraction to provide direct access to the …
Problem System Design Goal Resilient Distributed Datasets (RDD) Problem How to design a system that support in-memory computation (with real-time interaction support) in large cluster efficiently with fault-tolerance? Prior systems are lack of abstraction for leveraging distributed memory (intermediate computing result reuse is problem: has to save and then read …
Problem Background System Design Problem GPU data access needs explicit management by each individual GPU program. How can we provide an illusion similar to VM to physical pages such that all the data access can be done automatically (i.e., without stating that how data should be fetched from host …
Problem System Design Overview Architecture Dandelion Compilers Dandelion Runtime Problem How to design a system that provides programmability for heterogeneous distributed systems? Challenges are Heterogeneous: different programming models, architecture expertise Distributed resources: data movement, scheduling Concurrency: synchronization, consistency System Design Overview Goals: make it simple…
Problem Background System Design Overview System transactions TxOS Design Implementation Problem How to implement transaction with ACID guarantee in OS to provide concurrency control? Background Problems that can be solved by using transactions: Security vulnerbilities in the file system that are caused by time-of-check-to-time-of-use (TOCTTOU) race conditions Unsuccessful software installation …
Problem Background Theme for supporting concurrent and parallel programming “Heavyweight” Process Model “Lightweight” User-level Threads Kernel Threads User-level threads multiplexed on kernel threads System Design Reference Problem User-level library Management in application’s address space High performance and very flexible Lack functionality Operating system kernel Poor performance (compared…
Problem Background System Design Problem How to build a system that is able to securely manage multi-tenant networked applications on embedded infrastructure? Goals: High density/scalability Fast boot Lightweight VM-level isolation “Embedded cloud” Background OS are traditionally designed to run on a wide range of hardware, and support a variety …
Problem Background System Design Problem How can we refactor a commerical OS to follow libOS architecture and achieve a better performance than VMM approach? Background Three categories of services in OS implementations: Why does a guest OS need a kernel? Because the host interface is virtual hardware System Design Goals …
Problem Background System Design Remarks Problem How can we design an OS for I/O intensive applications such that most I/O operations do not need kernel mediation? Background The authors make a classic efficiency argument: servers usually perform conceptually simple operations, but in practice this results in too much …
Problem Background System Design Ballooning Content-based Page Sharing Managing Memory with Taxes Others Remarks Problem How to design a memory management system inside VMM to manage memory allocated to each guest OS (i.e., VM)? This is challenging as each guest OS also has its own resource manager and how …
Problem Background System Design Further reading Problem Provide a high performance resource-managed virtual machine monitor (VMM) that provides performance guarantees to concurrent execution of multiple operating systems: “hosting up to 100 virtual machine in- stances simultaneously on a modern server” Background Big picture Two types of VMMs Virtualization techniques 1 …
Problem Superpage definition and benefits Superpage issues System Designs Allocation Incremental Promotion Demotions Fragmentation Control Auxiliary data structure: population map Remarks Problem How to design a general and transparent superpage management system to achieve high and sustained performance for real workloads and negligible degradation in pathological situations? Superpage definition…
Problem System Designs Dataflow: Synthesis Model of Computation Fast context switch: procedure chaining Mechanism to reduce syncrhonization overhead Remarks Problem Design an OS for a parallel and distributed computational environment and achieve the following three goals: High performance Self-tuning capability to dynamic load and configuration changes A simple, uniform and …
Main Point The following statements provide different angles of stating the same “end-to-end argument”: Functions placed at low levels of a system may be redundant or of little value when compared with the cost of providing them at that low level; low level mechanisms to support these functions are justified …
Problem Approach Background: extensibility OS per application Microkernels Virtual machines Download untrusted code into kernel System designs High-level Architecture Exokernel principles Key Mechanisms Secure bindings Visible revocation Abort protocol Capabilities Others Specific Abstractions Network Multiplexing the network: packet filter Application-specific safe handlers (ASH) Problem How can…
Problem System designs Architecture File System Process Management Remarks Problem How to design a interative-use system with easy use (i.e., write, test, and run programs) given the hardware constraint? System designs Architecture File System Untyped data (byte oriented) Structure of files is controlled by the programs which uses them …
This post aims to prepare myself for the upcoming CS380L Advanced Operating Systems offered by Christopher J. Rossbach . The questions are actually from his HW1 aka. “Swapping in the state from undergraduate OS”. Brush up Definitions Short answer Virtual memory addressing Page replacement Multiprocessing Achieving fast file reads Synchronization Networking …
Almost two years ago, I write a post on how to modify an array in one function through another function in C. I did pretty detailed study through GDB there but I find that the illustration is lengthy to read. In this post, I try to show the same concept …
Basic graph concepts
list out the basic concepts in SSD
Binary search idea can be generalized to other problems
A study of trie data structure
“Weighted Voting for Replicated Data” paper reading
“The Andrew File System (AFS)” paper reading
“Petal: Distributed Virtual Disks” paper reading
“Sun’s Network File System (NFS)” paper reading
“MapReduce: Simplified Data Processing on Large Clusters” paper reading
“Scaling Distributed Machine Learning with the Parameter Server” paper reading
“Dynamo: Amazon’s Highly Available Key-value Store” paper reading
“Fast Crash Recovery in RAMCloud” paper reading
“PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees” paper reading
“BLEU: a Method for Automatic Evaluation of Machine Translation” paper reading
“Existential Consistency: Measuring and Understanding Consistency at Facebook” paper reading
“PNUTS: Yahoo!’s Hosted Data Serving Platform” paper reading
Cache, Lease, Consistency, Invalidation
State Machine Replication Approach
Lamport Clocks, Vector Clocks
This post is reference guide that points to the concepts, system design principles, system concepts mentioned in my posts. System Concepts Protocol System Designs System Principles System Concepts Logical Clocks, Vector Clocks State Machine : A process whose state depends entirely on the starting state and sequence of operations Replication : All servers exhibit the same behavior Sharding :…
“Why do computers stop and what can be done about it?” paper reading
“Introduction to Distributed System Design” paper reading