Tag: Computer Science

Here are two research papers I recently read:

1. Memshare: a Dynamic Multi-tenant Key-value Cache
2. Optimizing Function Placement for Large-Scale Data-Center Applications

(my thoughts and summary on the second paper I read this month as part of my endeavor to read ten research papers in June)

Paper: MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing

This research paper introduces readers to MemC3, which stands for Memcached with CLOCK and Concurrent Cuckoo Hashing. MemC3 is Memcached with modifications to make it faster and use less space. The researchers achieve the speed boost by allowing multiple reads and a single write to happen concurrently using their own concurrent implementation of Cuckoo Hashing. The space savings are gained by using the CLOCK algorithm to implement LRU cache eviction.

The authors begin by examining the existing use cases and design choices of Memcached. They notice that most Memcached use cases are read heavy, and that Memcached either (a) uses a single thread, or (b) (in newer versions) uses a single global lock. These two observations highlight areas where Memcached’s performance can be improved.

To improve the read and write performance and to enable concurrent operations the researchers replace Memcached hash table + linked list based cache with a 4-way set associate hash table that uses Cuckoo Hashing. I hadn’t heard of Cuckoo Hashing before reading this paper, and it is quite an interesting concept. To allow multiple readers and one writer the authors develop their own concurrent Cuckoo Hashing algorithm that combines lock striping and optimistic locking in a simple and easy to understand algorithm. This section (section 3.2) was the part of the paper that I enjoyed the most.

To save space and to implement an LRU cache eviction policy the authors use the CLOCK algorithm. The paper also describes how their cache eviction algorithm works safely with their concurrent cuckoo hashing algorithm.

The paper ends with an evaluation section that compares MemC3 and Memcached in a variety of configurations and workloads and shows that MemC3 almost always outperforms Memcached.

(my thoughts and summary on the first paper I read this month as part of my endeavor to read ten research papers in June)

Paper: Early Detection of Configuration Errors to Reduce Failure Damage

This paper introduces readers to PCHECK, a tool the researchers designed to check configuration values used by programs. The goal of PCHECK is to check configuration values at system initialization time, and fail fast if any errors in these configuration values are detected. PCHECK accomplishes this by emulating application code that uses configuration values, and also ensures that this emulation does not cause any internal or external side effects.

The authors motivate the design of PCHECK by observing that most software systems do not check configuration value at system initialization time. Configuration values are typically checked right before they are used. This is a problem because an incorrect configuration value might cause the entire software system to fail, long after the system has started. This is especially problematic when a configuration error causes a fault tolerance or system resiliency component to fail; such components are typically instantiated only under exceptional circumstances, hence the configuration values used by these components might not be checked for correctness at overall system start up time.

PCHECK works by generating checkers that are run at system initialization time. These checkers emulate configuration value usage in the actual system code. PCHECK captures all the context (global variables, local dependent variables, etc.) required to emulate these usages. PCHECK checkers are side effect free and work by creating copies of all the system variables so as to not modify any state. PCHECK handles system calls, libc function calls, core Java library function calls, etc. by providing what they term a “check utility”, which is essentially a mock function that doesn’t mutate external state but validates the function call arguments. Other external dependencies that might arise while using a configuration value, such as reading/writing to an external file, sending/receiving data from the network, etc. are dealt with in a similar fashion; external files are checked for metadata (while the paper does not explicitly say what these metadata checks are, I’m assuming they are something along the lines of “Does this file exist?”, “Do I have the permissions to read/write to this file?”, etc.) and network addresses are checked for reachability. Configuration issues are detected by the PCHECK checkers by checking for the presence of Exceptions, errno values, and signs by the program (for example the program terminating with an exit(1)) that something went wrong while running the emulated configuration value usage code.

(summaries of and key takeaways from two papers I read in December)

Paper: Three States and a Plan: The A.I. of F.E.A.R (this was the first game design paper I’ve read and it was pretty awesome, combining two of my Computer Science interests — graph theory and A.I)

• Enemy A.I.in F.E.A.R = FSM to express states + A* to plan sequence of actions to reach goal state.
• Separating goals from how the goals can be achieved (i.e. actions) leads to less complex code, code reusability, and facilitates code composition to build more complex systems.
• The planning system in F.E.A.R is called Goal-Oriented Action Planning and is based on STRIPS with several modifications.
• A* is used to find the sequence of actions with the least cost to reach a goal state. A* is used on a graph in which the nodes are states of the world and the edges are actions that cause the world to change from one state to another.
• Effects and preconditions for actions are represented as a fixed size array capturing the state of the world AND as procedural functions.
• Squad behavior is implemented by periodically clustering A.I. that are in close physical proximity and issuing squad orders. These orders are simply goals that the A.I. prioritizes (according to its current goals) and satisfies if appropriate.

Paper: Kraken: Leveraging Live Traffic Tests to Identify and Resolve Resource Utilization Bottlenecks in Large Scale Web Services

• Kraken is a system that load tests production systems (data centers or services) at Facebook by diverting live user traffic to the systems under test, and monitoring metrics like p99 latency and 5xx error rates to determine if traffic to the system under test should be increased or decreased, and by what amount.
• Real user traffic is the best representative of load to your system. By using real user traffic to test production systems you don’t have to worry about capturing complex system dependencies and interactions that arise out of a SOA.
• Kraken diverts traffic by modifying edge weights (from POPs to data centers), and cluster weights (from web frontend cluster load balancers to the web frontend clusters), and server weights (from service load balancers to individual servers that make up the service).
• Kraken reads test input and updates configuration files that are read by Proxygen to implement the edge and cluster weighting. Kraken then reads system metrics from Gorilla to dynamically determine how to adjust the edge and cluster weights based on how the system under test is performing.
• Kraken tests allow Facebook to measure a server’s, cluster’s, and region’s capacity.
• Kraken helps increase system utilization by exposing bottlenecks. By analyzing system metrics and how they change under different levels of load, Facebook was able to fix problems in their system. One of the issues identified in a system was poor load balancing, for which pick-2 load balancing was used as a solution.

(summaries of and key takeaways from two papers I read last month)

Paper: SLIK: Scalable Low-Latency Indexes for a Key-Value Store

• Building a low latency, consistent, and scalable secondary index for a NoSQL distributed store is hard.
• Partitioning your secondary index independently of your data (i.e. not co-locating your secondary index with the data) is key for high performance.
• SLIK returns consistent data without the need for transactions at write time by using what they term an “ordered write approach”. The SLIK client library shields applications from consistency checking by primary key hashes at read time.
• I’ve used rule-based programming languages like Prolog before, but I did not know that rule-based programming can be used for non-AI related tasks like concurrent, pipelined RPC requests like SLIK does in its client API implementation.
• SLIK reuses its underlying system’s (i.e. RAMCloud‘s) storage system to store a representation of the secondary indexes SLIK builds for fast recovery in the face of failure.
• Measure n times (where n >= 2) cut once: SLIK keeps its design simple by not implementing a garbage collection mechanism to handle invalid secondary index entries. The paper explains how the space saving gained by a garbage collector in their system are negligible.
• By performing expensive operations like index creation in the background without locking the entire table SLIK ensures that performance never suffers.

Paper:  Caching Doesn’t Improve Mobile Web Performance (Much)

• Measure n times (where n >= 2) cut once: a 10% increase in cache hit rate in Flywheel only lead to a 1-2% reduction in mobile page load times. This is because of the inherent limitations in web page design and cell phone device hardware (as revealed and evaluated in this paper). A systematic evaluation of the problem (i.e. quantifying the gains of caching in mobile web performance) might have saved engineering effort in improving cache hit rate.
• I was surprised that page load time was used as an evaluation criteria for cache performance, when above-the-fold load time seems like a more appropriate metric. As revealed in section 3.3 of the paper, this is because above-the-fold load time is harder to measure.
• The load time for the critical path of a web page determines its overall page load time, and if the elements along the path are not cacheable, then more caching will have zero benefit to page load time. As proved in the experiments detailed in the paper, the amount of data on the critical path that can be cached is much smaller than the amount of overall data that can be cached for most mobile web pages.
• The bottleneck for mobile web performance is the slow CPUs on mobile devices. Since the computational complexity involved with rendering the page is so high, caching does not give us the page load time reductions we expect on mobile devices.