Log-structured File System Notes

Assumption

Log-structured file systems are based on the assumption that files are cached in main memory and that increasing memory sizes will make the caches more and more effective at satisfying read requests. As a result, disk traffic will become dominated by writes.

Problems of existing file systems

• 1. Spread information around the disk (separate inode from file content).

• 2. File systems tend to write synchronously: the application must wail for the write rather than continuing while the write is handled in the background.

Log-structured file system

The goal is to improve write performance by buffering a sequence of file system changes in the file cache and then writing all the changes to disk sequentially in a single disk write operation.

Two key design issues:

• 1. How to retrieve information from the log.

• 2. How to manage the free space on disk.

Reference

http://www.cs.berkeley.edu/~brewer/cs262/LFS.pdf

Paxos Algorithm

The Paxos algorithm is a consensus algorithm for a fault-tolerant distributed system. A consensus algorithm ensures that a single one among the proposed valued is selected. In Paxos, there are three types of agent: proposers, accepters, learners.

The algorithm runs as follows:

1. A proposer selects a proposal number (integer) n and sends to a majority of acceptors. This is called a 'prepare' request. Here majority means greater than half of the acceptors. If an acceptor receives a 'prepare' request with number n greater than that of any 'prepare' request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

2. If the proposer receives a response to its prepare requests from a majority of acceptors, it send an 'accept' request to each of those acceptors for a proposal for a proposal numbered n with a value v. The v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals. If an acceptor receives an 'accept' request numbered n, it must accept it if and only if it has not already promised to only consider proposals having an identifier greater than N.

3. Each acceptor responds to all learners whenever it accept a proposal.

C++ next_permutation implementation

template<typename Iter>
bool next_permutation(Iter first, Iter last) {
    // Empty
    if (first == last) return false;
    Iter i = first;
    ++i;
    // Only one element
    if (i == last) return false;
    i = last;
    --i;
       
    for(;;) {
        Iter ii = i;
        --i;
        // Check if there are two adjacent elements
        // such that the first one is smaller than the second one
        if (*i < *ii) {
            Iter j = last;
            // Find the first element that are bigger than i
            while (!(*i < *--j)) {}
            std::iter_swap(i, j);
            // Reverse the decreasing sequence
            std::reverse(ii, last);
            return true;
        }
        // No, this is the last permutation
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

Codeforces 216A

Here is the link: http://www.codeforces.com/problemset/problem/216/A

Basically you can think of the hexagon as a cuboid which you can see the top, front, and right side. So given a, b and c, the number of tiles is a * b * c - (a - 1) * (b - 1) * (c - 1). Pretty tricky, right?

Java Annotation

It's a great technology that helps your class focuses on what should be done, reduces the complexity of your class and makes your code clean. Here let's go through our own JUnit example to see how annotations work.

Here we create our own annotation:

import java.lang.annotation.*;

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface Test {

}

Of course, the annotations don't do anything by themselves. We need a tool to process these annotations:

import java.lang.reflect.*;

public class TestRunner {

    public static void runTests(Object obj) {
        try {
            Class cl = obj.getClass();
            for (Method m : cl.getDeclaredMethods()) {
                Test t = m.getAnnotation(Test.class);
                if (t != null) {
                    m.invoke(obj, null);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Now we can write our own test cases:

public class UnitTest {

    public UnitTest() {
        TestRunner.runTests(this);
    }
 
    @Test
    public void testCase1() {
        System.out.println("Test Case 1");
    }
 
    @Test
    public void testCase2() {
        System.out.println("Test Case 2");
    }
 
    public static void main(String[] args) {
        new UnitTest();
    }
}