You Must Do Code Review And Do It Right

Our company started code review about one and half years ago. It is one of the smarted decisions we have made. It significantly improves the code quality and helps programmers learn from each other. Do code review, unless there is only one programmer in your company or you don't care about code quality. I just read a white paper about code review from Smart Bear. It is a very interesting paper. I also have a few tips myself to share.

First, stop sending patches through emails and pick the right tool for code review. As a start-up company, we always prefer free tools. We found Review Board really great. It was developed by a couple engineers in VMWare and used within VMWare originally. It makes the code review very convenient and efficient. We would not have started code review that early if there was no Review Board. With Review Board, all a submitter needs to do is to upload a diff. Review Board automatically pulls files from SCM systems, generates side-by-side diff view and highlights code differences and syntax. People can add conversations on any lines in the diff. Review Board works in an asynchronized way - you don't need to finish a complete review at once. You can do a review piece by piece at your own pace. Review Board also supports follow-up diff files, email notifications and many other cool features. Its interface has been improved significantly after the 1.0 release. If you are open to commercial tools, check out Code Collaborator from Smart Bear and Crucible from Atlassian. I'm not familiar with them.

Second, pick the right reviewer. The simple rule is to pick the people who know the background of your changes and have some time to do the review in the near future. Someone suggested to check the reviewer's schedule first, but I think it is too much for small companies. It would help if the review tool shows information about this. For example, the tool can show how many pending reviews the reviewer has right now and how large they are.

Third, submit reviews in the right size. According to the user study in CISCO, the white paper shows that 200-400 line changes is the right size for one review. The longer a review is, the fewer defects can be found and the more boring the review process will be. I absolutely agree with this. The longest code review I have done is about 80 files with thousands of lines of changed code. I had 3 shots of espresso to finish it and I don't think I did a good job. When a review is about 200-400 lines of changes, I feel that I can finish it in 30-60 minutes, so I can be more focus and careful to read every detail.

Forth, respect your reviewers. Keep in mind that a code review is a big favor your reviewer does you, so try to make it as easy as possible. Prepare the code review well, don't just throw a diff and let your reviewer struggle to understand it. I often review frontend code from one of our engineers. He always attaches screenshots and draws figures to explain the layout and relationship of UI components, which makes the review much easier. I think there are a few things that the submitter should always do:

• Explain the rationale behind the review and how it works
• Explain the reason why to change each of the files, which is usually not mentioned in comments in the code
• Guide the reviewer through the review, such as which files should be read first
• Attach additional documents if they help

Fifth, respect your submitters. When someone sends you a review, it shows that she trusts you. Do the review in a timely manner. If you can't do it in time, talk to the submitter and pass the review to others. More importantly, do the review with responsibility. Code review is the last step to find problems, assume that the submitter already fully tests the changes. After the review, the code will be committed to the repository. So try your best to find problems.

Sixth, a submitter should always address all comments and upload follow-up diffs. This is a ground rule in our company and it works really well. It makes sure that the submitter responds all problems and fixes them in the code. The reviewer won't give "Ship It!" until follow-up diffs are uploaded.

Seventh, code review is a good opportunity to check unit testing code. Submitters should submit unit testing code together with the functioning code and reviewers should be responsible to check if the unit testing code is good enough. Keep in mind that unit testing code is as important as functioning code, so it needs to be reviewed as well. Including unit testing code in code review has a few advantages:

• Code review covers all new code - perfect coverage.
• The reviewer gets very familiar with the changed code after reading the code, its the best time to review the unit testing code as well.
• The only chance to enforce writing unit testing code. Some testing coverage tools can also do this, but they are inflexible and not be able to find missed unit testing code in finer granularity. 
• Unit testing code help the reviewer understand the changes.

Last but not the least, build a positive code review culture. The white paper also mentions this. I think it is very important. We never had culture problems in our company, but we may have it in the future as we grow. There are a few things I think people should do.

• Everybody should realize code review is a win-win deal. Both reviewers and submitters learn something from it.
• As a reviewer, don't be harsh. Ask questions before make statements. Code review is not the stage where you show off.
• As a reviewer, don't force everybody else to write code in the exact some way as you write code. So don't fixating on small things if there is disagreement.
• As a reviewer, inject compliment when you see some cool snippets.
• As a submitter, don't be self-defensive. Remember that the review is about the code, not about people who write the code.
• As a submitter, respond to every comment, nicely. Speak out your reasons if you think some comments are not correct.

I'm happy to hear other good code review experiences.

By the way, Smart Bear also published a book, "Best Kept Secrets of Peer Code Review". I just requested for a free copy from here.


Updates on Dec. 1, 2009: modified the description of how Review Board was developed, as pointed out by one of the authors of RB: Christian Hammond. Thanks, Christian!

Write Parallel Gomoku AI Programs With The Branch & Bound Pattern

In today's lecture, we learned the Branch & Bound Pattern. The main idea of this pattern is to explore huge search spaces with multiple threads/processes while applying bounding or pruning strategies to control the size of the search space. This is a very interesting pattern. It reminds me some fun time in high school. When I was in high school. a very popular game among computer geeks was to write programs to play Gomoku (Also names Five-in-a-row). We let programs to compete with each other to see who wrote the smarted programs. The basic rule of Gomoku is straightforward: two people place black/white pieces on a 19x19 Go board in turns. Whoever make five of her colors in a row wins the game. Branch & Bound Pattern is a perfect pattern to parallelize such gaming problems.

The basic idea to make a move in Gomoku games is to go from the current state of the board, explore as many steps in the future as possible, and pick the move with the highest possibility to win finally. For example, after the first white piece is placed, the search graph is something like this:

It's not hard to see that the search space can be huge. Let's think about the four operations in the Branch & Bound Pattern. We define a function G(state) for each state. G(state) indicates the chance for the program to win finally.

As for branching, it is straightforward. When the program makes a move, it needs to calculate the G(state) for each of the to-be states and pick the best choice. G(state) is actually a recursive function of G(state') where state' is the subsequent states of state. So we need to calculate all G(state') first.

As for evaluating. G(state) is used to evaluate states in the search.

As for bounding, Gomoku game is not as trivial as SAT or integer linear programming mentioned in the pattern. It is very hard to efficiently calculate the bonding value of G(state). What we can do here is to come up with an estimated Ge(state) according to the current state and/or Ge(state) of its sub-states. There are many ideas to calculate Ge(state). For example, we can consider how many three-in-a-row  cases in each side. The more three-in-a-row cases one side has, the more likely that side will win. Usually we use several strategies and give each of them a weight. The final Ge(state) is calculated as a function of all strategies.

As for pruning, if a state has been evaluated in other branches or a state's Ge(state) is worse than the current-best G(state), we can prune the branch started by this state. Of source, there can be many tricks to do smarter pruning than this.

To parallelize the searching process, structure-based parallelization is the best fit for this problem. Because all processors should process states in a single pool, we can use either Synchronized-Single-Pool (SSP) or Asynchronized-Single-Pool (ASP) with shared current-best state and visited states. I think the best-state-first strategy may work better then the depth-first strategy. We need to carefully limit the maximum depth to search regardless which search ordering strategy we use.

It is already close to the end of the class, otherwise I think it is a good idea to have a Parallelized Gomoky Program Contest in the class ;-)

Given That Deterministic Replay is Still Slow, What Should We Do for Parallel Debugging?

Debugging has been tough, and it becomes tougher these days. One of the reasons is that people write more parallel programs and introduce concurrency bugs. Concurrent bugs are especially hard to debug, because many of them do not always show up. There can be many things that make a bug hard to fix, not being reproduced is probably the worst one.

What is the ideal way to debug a parallel program? In my mind, a parallel debugging framework should provide the following:

• In the production run, records the execution with zero or very low overhead.
• In the debugging phase, let people deterministically replay what happened when the bug manifests. It is even better if the replay can go both forward and backward.
• Programmers can attach their favorite debuggers to the replay session.

This even sounds tempting to sequential debuggers, doesn't it? However, the real world is not ideal. The main problem is that recording introduces huge overhead in the production run. A lot of research has been done to make it faster, but still, there is no very realistic solutions yet, especially for applications that run on multi-processors. In this years SOSP, there are two papers on this topic: Do You Have to Reproduce the Bug at the First Replay Attempt? -- PRES: Probabilistic Replay with Execution Sketching on Multiprocessors and ODR: Output-Deterministic Replay for Multicore Debugging. They both send out three interesting messages:

• They are both software-only solutions.
• They both make compromise - push the complexity from recording to replaying.
• They both work on multiprocessors.

This trend shows that people become more realistic about this hard problem. First, software-only solutions are preferred, because they are easier to implement. Don't get me wrong. I'm not saying hardware-based or software-hardware-hybrid solutions are unrealistic, but they indeed take longer time to become real. Second, people compromise something that is less important to make more important things to be feasible. Third, multiprocessors are so common today, so a realistic solution should work with it.

The idea of PRES is to sacrifice the efficiency of replay. Instead of reproducing the buggy execution at the first try, it requires more than one attempts to reproduce it. Meanwhile, the reward of this is that it only needs to record much less information in the production run. One could think of it as PRES drawing a "sketch" in the production run, instead of a "finished paint". Although it may need to try several times to recover the "finished paint", but "sketch" is fast and enough to catch a rough idea about what happened. If painters use this idea, why can't we? Very smart! During replaying, PRES uses both the sketch from the production run and feedbacks from previously failed attempts. The idea is that when PRES encounter a data race that has not been recorded in the production run, it makes a random guess. As soon as PRES finds out the execution does not match the sketch any more, or does not reproduce symptoms in the buggy execution, what it will do is to roll back a bit, flip some data races and give it another try. This actually reminds me about another paper, Rx, which is one of the system research papers that I like the most.

The idea of ODR is to sacrifice the accuracy of replay. Instead of reproducing the buggy execution based on internal values, it tries to reproduce an execution that has the same output as the buggy one. Output includes segment fault, core dump, print out strings and such. The reproduced execution may be different from the buggy one, but the rationale behind this idea is that if it has the same output, it is very likely that the bug that appears in the buggy execution also manifests in the reproduced execution. If output-determinism is enough, why would we want value-determinism?

There are many other good papers about deterministic replay for debugging parallel programs. If interested, you can find more from the references of these two papers.

Besides academic research, VMWare's replay debugger is a production-class parallel debugger tool. Although it only works for single processor execution, it has almost everything an ideal parallel program debugger should have. I was really really impressed. E Lewis gave talk in Google about it:

Programming is not as easy as it sounds

(After reading "Teach Yourself Programming in Ten Years" by Peter Norvig)

I found this article after I read Prof. Johnson's blog post about it. All the points from this article are so true and I think every programmer should read it.

Back to when I was in college, many students in Computer Science major thought programming is easy and kind of boring. It only requires time but less skills. Many people who have been programming for years after school still think in the same way. I think the major reason is that as computer hardware, programming languages and development tools has been improving so fast in the past decades, writing runnable and reasonably fast programs requires lower and lower learning curve. Even if you know nothing about computers, you can probably write a piece of Python code to do quite something in one or two days. However, does it really mean that programming become no-brainer now? It certainly does not.  The superficial simplicity prevents people from thinking more about it. Just like Peter Norvig, I also have a few tips about how to teach yourself programming.

First thing first, make yourself interested in programming. Maybe programming is not one of your dream jobs, but if it is what you do now, try to become interested in it. This helps you kill the pains and have more enjoyable programming time.

If you did not know computers much, try to learn something about it. I strongly recommend a few books for basic concepts: Computer Organization and Design: The Hardware/Software Interface, Computer Architecture: A Quantitative Approach,  Modern Operating Systems and Computer Networks. These books are all very well written and teach you many things you should know when you write programs. Without this knowledge, you won't be able to understand many important aspects of programming, such as pointers, why buffered I/O streams are faster, how to use threads correctly to avoid concurrency bugs and so on. Additionally, Jeff Dean has a list of numbers he believes everybody should know:

(from the slides of Jeff Dean's talk

Designs, Lessons and Advice from Building Large Distributed Systems)

Read the Design Patterns book once a year. I personally think this is the best book about programming I have ever read. It opens a new door to think about programing. When you read this book, think more beyond patterns for OO programming. There are actually programming patterns everywhere and they are powerful weapons to conquer system design problems. The more patterns you know, the more choices and beautiful ideas you will have when you design a system.

Open your mind and learn more languages even if you do not need them for work. Learning a new language helps you re-think programming. For example, say you are a Java programmer originally, when you learn Python, the first thing you may think about is dynamic typing. It may make you feel uncomfortable at the beginning, because you are so afraid that you will make typing mistakes. But after a while, you may feel dynamic typing helps you write programs faster. OK, now what, is it good or bad after all?

Read other people's code. One of the best ways to learn is to learning by examples, either good examples or bad examples. You can read open source code or read code written by your colleagues. Remember it when you think their code is good and try to improve it when you think their code is not that good. Our company has very strict code review policy. I learned a lot by reviewing other people's code and letting them review my code.

Get familiar with software development tools. There is a Chinese epigram saying "sharpen your knife before you cut wood" (工欲善其事，必先利其器). Many great development tools can significantly improve efficiency and quality of software development. Take Java as an example. Java is famous for having many great tools. Just to name a few open-source tools:

• IDE: Eclipse, NetBeans
• Buidling: Ant, Maven
• Debugging: jdb, jhat (heap analysis), jconsole (monitoring), Eclipse integrated debugging features. 
• Profiling: jprof, NetBeans Profiler (I really like this)
• Static analysis tools: FindBugs, PMD
• Unit testing: JUnit framework, Emma (check unit testing coverage)

Always keep in mind that testing rocks, debugging sucks. I did not really realize this until I started working in the company. I would say making solid testing is one of the biggest lessons I learned in the real world. Good testing can totally change the quality of a program and "life quality" of programmers. Once you adopt test-driven development, you will never go back.

Think while you do. This is more about attitude. Even if you are in charge of just a small component of a large system, don't always bind your mind to that particular component. Think about big pictures, such as how the whole system works, what are good and what are bad, how to improve it and so on. If you think more, you will find you can learn a lot even if you are working on something that you thought was boring before.

Happy programming. :-)

"Stress Testing On Concurrent Problems - CHESS

Testing concurrent problems, such as data races, deadlock and so on, could be very hard. This kind of problems only happen with certain input and highly depend on how threads/processes are scheduled. In order to have good coverage of threads/processes schedules, people need to run the same testing many times and keep their fingers crossed to run into concurrent problems if there is any. This doesn't work well for problems that happen very rarely. People sometimes also use stress testing, testing with very heavy workload, to find potential concurrent problems. But this doesn't work well either, because heavy workload may introduce more concurrent operations, but it does not mean to introduce the right concurrent operations/orders to trigger concurrent problems.

The CHESS project from Microsoft Research tried to solve this problem. CHESS uses model checking technologies to explore different concurrent schedules, more specifically - how threads interleaves with each other, to find the one with concurrent problem. Once the problematic schedule is found, CHESS is able to accurately reproduce it later and let programmers debug the program. As an example from their paper, CHESS reported a deadlock after executing 6,727 different schedules in about 20 seconds. This is apparently is one of those tricky current bugs that take days to find.

The most interesting part to me about CHESS is how it controls the state space. It is not hard to imagine that the number of different schedules of a multi-threading program can be huge. CHESS uses various technologies to shrink the search space. There are two major strategies. The first one is preemption bounding - to limit the number of preemptions and use them carefully. According their previous paper, it shows that if the schedule desides a part of the preemptions, the rest of the schedule is determined automatically. Basically a problematic schedule only depends on a few preemptions to happen at the right places. The experience shows that having at most 2 preemptions is enough to find serious concurrency bugs. The other approach CHESS uses is to cache visited program states to prune redundant search. The questions is that what can be used as program state in terms of concurrent behaviors? CHESS uses happens-before graphs. The rationale is that "two executions that generate the same happens-before graph only differ in the order of independent synchro-nizations operations".

Microsoft Research already integrated CHESS into Visual Studio 2008. It works for multi-threaded single-process application. If you are interested, download and give it a try. For latest updates about CHESS, check out its blog.

Refactor Java Loops With ParallelArray

(After reading "ReLooper: Refactoring for Loop Parallelism")

The ParallelArray Framework is a new feature in Java 7  that provides parallel operations on an array. For example, the programmers can apply a modification on each element of an array, map each element of an array to element of another array, reduce a set of element of an array to a value and so on. These operations will be parallelized by with ParallelArray Framework automatically. ReLooper is tool that helps programmer rewrite existing loops using ParallelArray to improve performance. It delivers 1.32-1.96x performance speedup on a 2-core machine.

Rewriting a loop to a parallelized version with ParallelArray is not hard. The hard part is make sure the new loop behaves correctly as the originally loop. Relooper uses several static analysis technologies to analyze a loop to make sure it can be safely parallelized with ParallelArray. If Relooper finds any potential problems, it warns the user before start refactoring. There are mainly three constraints that may prevent a loop from being parallelized.

First, the original loop should go through all elements in the array in order and there is no inter-iteration dependency. If the original loop is a for-loop. Relooper should check if the iteration variable is used as the index of the array and if the iteration variable changes from 0 to the length of the array. Relooper also checks if any control flow statements, such as break, return and continue, skip some array operations.

Second, Relooper checks if different iterations of the original loop access shared data. If there is any conflict accesses, the original loop can not be parallelized easily. This check if not trivial because of the complexity of memory reference analysis and method calls. Relooper develops an inter-procedure data-flow analysis to do the check.

Third, the original loop should not have blocking I/O operations. Because ParallelArray uses Fork/Join Framework to parallelize operations, blocking I/O can significantly hurt the performance.

These constraints make a lot of sense, but in my opinions, they do not completely kill the opportunity to parallelize a loop. It would be better if the paper can describe what should be done if any of them happen. Is there anything smart Relooper can do to still parallelize the code, or programmers have to be involved to make the decision or even adjust the code?

Relooper is implemented as an Eclipse plug-in and you can download it from its website. I really appreciate the author's effort to make it real and usable.

Refactor Java Programs To Take Advantage of Concurrency

(After reading "Refactoring sequential Java code for concurrency via concurrent libraries".)

There are more and more new libraries and language supports to help programmer write better concurrent code. They greatly benefit writing new code, but how about existing code? We probably need new code refactoring technologies to improve existing code.  This paper proposed a tool, CONCURRENCER, which can refactor existing sequential Java programs to take advantage of the java.util.concurrent (j.u.c) library. CONCURRENCER contains three main refactoring technologies.

First, it can convert usages of an int field into AtomicInteger. This can make sure that access to this field become thread-safe. Besides AtomicInteger, the j.u.c library also provides a few other atomic data types.

Second, it can convert usage of HashMap into ConcurrentHashMap. The traditionally way to make a map thread-safe is to use lock to protect every operation on this map, which introduce unnecessary contention.  ConcurrentHashMap is a pretty cool class in the j.u.c library to solve this problem. It uses a smarter locking mechanism to allow concurrent retrieval operations and partial-concurrent update operations. It divides the hash table into chunks and each chunk has its own update lock. So different chunks can be updated concurrently.

Third, the most complex, it can convert a recursive method to a new version based on the Fork/Join framework. To solve a divide-and-conquer problem, the Fork/Join Framework recursively solve one task by using multiple threads to solve its sub-tasks, wait all of them to finish and then aggregate the results for the original task. I wrote about this framework before. According to the experiments, this refactoring strategy can improve the average performance of a sequential recursive method to 2.97x (on 4-core systems).

I like this paper because I think it is practical. Each of these three refactoring ideas looks small, but if they can be correctly applied, they can much improve the code quality and performance of existing sequential programs. The authors also mentioned that they keep looking for refactoring opportunities to take advantage of other features in the j.u.c library.

One problem of CONCURRENCER is that it depends on the programmer to pick the code to refactor. It would be more helpful if it can collaborate with other static analysis tools to find this code automatically.

"Creeping Featurism is a Strength" if it is done right.

(Reading notes for Chapter 11 of "Beautiful Architecture" GNU Emacs: Creeping Featurism Is a Strength)

This chapter describes the software architecture of Emacs and discusses its creeping featurism "problem". Creeping featurism means that people tend to put more and more features into a system and eventually make it too complicated to manage. Many people think creeping featurism leads to no good, but if it can certainly become a strength if it is done right. Software becomes very complicated these days and people expect more and more from software. So a closed system is very hard to be very successful. We can see this tendency from desktop applications, like Firefox, iPhoto and so on, to enterprise software, like SplunkBase, to web-based applications, like Facebook.

Extension is especially important for open source software which usually has a lot of uncentralized developers and users.  I will talk about a few thoughts on how to make a software system open to extensions but in the meantime prevent creeping featurism.

Firstly, a system should have a fairly simple data model. The book chapter compares the data model of Emacs and the data model of Microsoft Word. I think this is a very good example. The simplicity of Emacs data model, strings of characters, makes it much easier to extend then MS Word, I'm not criticizing MS Word, after all, Emacs is an editor, not a word processor.

Secondly, the interface between the core part of a system and its other rich features should be clear and well defined. Emacs' MVC model is a good example again. Views are automatically updated once a relevant model change is detected. The core controller is written in C, but the controller code of most command we use is written in Emacs Lisp, which is also used as the major language to develop extensions. This design lets extensions integrated into the whole system naturally. Most extension code can be modified without recompiling the core Emacs, even without restarting Emacs.

Thirdly, a system should have a good default set of features that fit common needs. Most Emacs users only use a small subset of its features, but a complete installation of Emacs is already pretty big, it takes time to start and occupies quite some system resource when running. This is actually one of the major attacks from Vi advocators. To find the balance between efficiency and reasonable set of features is hard. This article presents one solution of having different sets of default features, like expert mode, normal mode, hardcore mode and such.

Fourthly, to make it very easy to install an extension. If it takes hours to install an extension, I don't believe people will do it at all. Emacs extensions are not trivial to install. For most of them, you need to modify your ".emacs" configuration file and copy package files to the right place. For some of them, it even requires compiling and/or installing new stuff. Software like Eclipse and Firefox do a better job on this.

Finally, to have a good platform for people to share and look for extensions is important. If a system is designed to be extend, extensions should be managed efficiently and provide good communication between people who write extensions and people to require new features.

Making enterprise software extendable and control its feature scale is quite different from to do so to open source software. I will probably write another post about that.

Why to implement a JVM in Java?

(Reading notes for Chapter 10 of "Beautiful Architecture" - The Strength of Metacircular Virtual Machine: Jikes RVM)

I heard about Jikes RVM before as popular in the Java runtime environment research community, but I didn't think through what exactly implementing a JVM in Java benefits research in particular, or in general. I still held this question before I read this chapter.

This chapter is pretty clear. I especially like the part talking about myths surrounding runtime environments. It would be better if the book can also compare Jikes with other metacircular architectures, not necessary JVMs. Combining this chapter and some other articles, I think the advantages to implement a JVM in Java are two folds. First of all, it offers an opportunity to have better understanding of the language, especially how applications talk with run time environment and performance-critical features. So we can implement them in a better way. Secondly, in terms of performance, this implementation moves the Java/non-Java boundary crossing overhead below JVM instead of above JVM, which opens doors to more efficient implementation ideas and dynamic optimization opportunities. However, the question is that whether it is desirable to build a production-class JVM in Java. I still doubt it.

As a big system fan, I'm interested on how Jikes bootstraps itself and communicates with hardware/OS. I went through some research literals and found this paper, Implementing Jalapeño in Java, is a must-read. Jalapeño is the predecessor of Jikes. This paper describes the original motivation of the Jalapeño project in IBM Research and the challenges they encountered at the early age. Very interesting. You can find answers for these questions:

• How do they implement the first few essence components of a JVM, a not-very-efficient baseline compiler, a dynamic class loader, a simple memory manager and a debugger?
• How do they generate a boot-strap image of these components and load it to start Jalapeño?
• How does Jalapeño interface the hardware - through a special class MAGIC.
• How does Jalapeño interface the operating system - via ~1000 line C code to invoke system calls through the standard C library.

One thing that would have made this paper even more interesting is to talk more about the trade-offs between different implementation alternatives.

From Thread.join(), to invokeAll(), to the Fork/join Framework

Fork/join Framework (FJF) is new in Java 7. It was developed by Doug Lea based on his paper "A Java Fork/Join Framework". Simply speaking, the Fork/join Framework helps parallelize divide-and-conquer algorithms by multi-threading. It divides a big chuck of work into smaller pieces, sends them to a set of threads to process, waits until all of them are done and aggregates the results.

This idea seems to be simple and straightforward, but there are a lot of things to think about to make it work well. Without too much thinking deeper, this idea can be implemented by just what Java Thread class provides. For each task, if it is small enough, solve directly; otherwise create several threads and let each new thread handle a smaller chuck. Then call join() method on each new threads to wait until all of them finish. Finally merge results. There are a few problems of this approach. First of all, creating threads is expensive. When a task is fairly small, the time spent in creating more threads is even longer than the computing time spent in solving the task itself. Second, there will be a lot of threads created. These threads compete for CPU cycles which result in worse performance. Third, programmer needs to write specific code for each divide-and-conquer algorithm. It makes code harder to write, read and maintain.

If you are familiar with the java.util.concurrency package introduced since Java 5, you may want to suggest to use a thread pool based executor and call invokeAll() to process divided tasks. This saves the overhead of creating threads and limits the number of threads - a big step ahead, but there is good odds that this idea will not work well either.

• The tasks queue, most likely an unbounded blocking queue, that is shared by all threads in an executor could become a bottleneck, because every thread needs to lock the queue when it gets tasks from the queue or puts new sub-tasks into the queue.
• What should happen when a thread is done its job? It may not be able to process the next queued task because that task may still be waiting for join its sub-tasks. In this case, how could this thread pick another task to continue instead of being idle?
• Programmers still have to write a fairly big amount of code in addition to the code that runs the algorithm itself.

The Fork/join Framework solves these problems. Each worker thread maintains its own tasks scheduling queue. This prevent one single shared queue from being a bottleneck. What should a thread do when its own tasks queue becomes empty?

Here comes the smartest trick in Fork/join Framework - the "work-stealing" strategy. A scheduling queue of each thread is a double-end queue. When a task needs to be divided into smaller tasks, it sends all its sub-tasks to one worker thread. So as the time goes, the head of a queue contains bigger tasks and the tail of a queue contains smaller tasks. For each thread, it processes tasks from the tail of its queue (FIFO fashion). This utilizes data locality and also tries to concentrate on all sub-tasks of one task as much as possible. When a worker thread finishes all its own tasks, it "steals" tasks from the head of other threads' queues (LIFO fashion). There is a good chance that this thread will pick a big task and thus it can further divide this tasks without affecting other on-going work. It won't need to "steal" again in the near future. For each double-end queue, one thread works on one end and other threads may work on the other end, but not very often. This is very good to prevent contention on queues.

Last but not the least, with the Fork/join Framework, programmers can focus on the code that tackles their own problems. The code could be much cleaner and easier to read.

In his paper, Doug also evaluates the Fork/join Framework by solving a few real problems. He mentioned that the performance can also be affected by garbage collection, memory locality and bandwidth, task synchronization and task locality. These aspects should be considered careful when design the algorithm to utilize the Fork/join Framework. I like this paper, it is a typical Doug-style paper and it is a lot of fun to read.

The Fork/join Framework is a part of JSR-166. It can be downloaded from the JSR-166 interest site.

Five Myths About RESTful Web Services

I will try to avoid comparison between REST and WS-*, because there are already a LOT of discussion  about it and some people get biased sometimes. I just want to describe some of my understanding about RESTful services in this post.

Myth #1, REST is a new technology.

REST is not a new technology, it is not a new standard either, at least for now. It is a new way to think about web-based application architecture. REST architecture can be implemented by existing technologies and it won't be hard to do it. I really like the idea of REST because it explicitly describes a good way to architect a system.

The very key of REST-style architecture is Resource Oriented Architecture (ROA), mainly as opposite to Service Oriented Architecture (SOA). Many advantages of REST-style web services are based on this key. For example, URLs becomes cleaner and bookmark-able in RESTful web services, because each URL always represents a certain resource.

Myth #2, REST is too new, so there is no good framework to use.

As stated in Myth #1, RESTful web services can be implemented by existing technologies. In the meantime, people develop framework to make developing RESTful services easier. Sun started working on JSR-311 since 2007 to provide standard APIs to help develop RESTful services. There are already a few server side framework to use, to name a few Java framework: Restlet, RESTEasy from JBoss, and Jersey from Glassfish.

Myth #3, REST is panacea. Any applications can be built in REST style.

I don't think this is true, although many people think it is. The real question is that is the application resource oriented or service oriented. Some applications are inherent SOA. If you make it RESTful, it will just look awkward. Take a simple banking system as an example. If we use service oriented style, a withdraw transaction can be described as:

withdraw(String accountNumber, float amount);

However, if we really want to make it resource oriented, it would be anti-intuitive, say what should be the resource, an account or an amount of money? Which HTTP method should we use?

Myth #4, as long as a service is invoked by an URL and responses XML, it is RESTful service.

Certainly not true. Take Flickr API as an example. Although Flickr API offers three different types of request format, REST, XML-RPC and SOAP, they can be called in the format as:

http://api.flickr.com/services/rest/?method=method-name&param1=value1&......

most of these APIs are essentially service oriented. They are not RESTful web services.

However, most of them can be modified to be RESTful. For example, there are three APIs that work on photo tags:

• flickr.photos.addTags
• flickr.photos.removeTag
• flickr.photos.setTags

If we consider tags as resource, we need one URL to identify them:

http://api.flickr.com/services/rest/v1/photo/photo-id/tag-name

A PUT method on this URL add this tag to this photo and a DELETE method on the URL removes this tag from this photo.

Myth #5: REST is easy.

I think REST is a very clean way to design a system. But I won't agree that REST is significantly easier than other ways. Developers still need to learn a lot of things to build a successful system. There are still many decisions to make and some of them can be tricky. Just to name a few:

• How to define resources and presentations?
• How to apply HTTP methods?
• How to use cache? What resources can be cache and what can not? When to invalidate cache?
• Be really careful about POST.
• Security?

Facebook invites everyone to be involved

Facebook announced the Facebook Platform in May 2007 which I think is definitely one of the smartest moves Facebook has ever taken. There was only a few applications available in May 2007, but today, there are more than 350,000 active applications and 250 of which have more than one million monthly active users. The Facebook Platform provides an interface to developers to build applications within Facebook, it is just like an operating system provides an interface between hardware and programmers. One big difference is that Facebook's platform also provides a huge amount of very valuable social networking data.

Facebook's original goal is to let people connect to people. But connection itself is not going to be interesting enough to attract more people and connection needs people to grow. So Facebook needs applications to make itself interesting and useful. Instead of developing all kinds of applications by itself, Facebook give the opportunities to everyone. Facebook needs applications and applications need existing social network data. This is apparently a win-win game. Very smart!

Facebook Platform is very interesting to take a look at because it fits well into the software architecture of modern web-based applications. Before looking into how Facebook does it, ask yourself what you will do if you are asked to design such a platform. There are a few questions to answer:

• How to let developers access data in Facebook, with something that they are already familiar with, like SQL?
• How to let developers draw web content, with something that they are already familiar with, like HTML and CSS?
• How to let developers write dynamic web content, with something that they are already familiar with, like client-side JavaScripts?
• How to let developers do all above in a secured way?

I never developed Facebook applications, but after skipping through their documentation, the design is nice and straightforward to follow. When you develop a Facebook application, you use FQL to access data. FQL is very like SQL. It supports complex operation to reduce the number of requests you need to query. To draw web content, you have basically two choices, use FBML or an IFrame-based application. Jesse Farmer has a pretty nice introduction for FBML. But if you want to re-use some existing code, IFrame-based approach might work better for you. This article describes how to choose tween FBML and IFrame. Facebook Platform make dynamic and Ajax style content possible by providing FBJS. FBJS is a good balance between security and flexibility. One big problem of using FBJS is that many great JavaScript libraries won't work properly.

Facebook Platform is good, but its problem is that applications written with Facebook Platform need to run within Facebook. In many cases, applications that are outside of Facebook also want to utilize the social networking information in Facebook. Facebook announced Facebook Connect in Nov, 2008. It allows applications out of Facebook to access Facebook users' identity information, social graph and streams. A lot of good web applications start using Facebook Connect, such as Aardvark and many others. This is good for applications, because they can utilize the social networks that people already create in Facebook, instead of letting people create hundreds of different social networks. This is also critical for Facebook itself. Facebook oversees one way to gain revenue as to provide something like Paypal. This can becomes true only if Facebook Connect has a massive adoption.

Domain specific distributed programming platform

(Reading notes for Chapter 3 of "Beautiful Architecture" - Architecting for Scale)


This chapter talks about Project Darkstar, a Sun-led open source distributed programming platform for online games and virtual worlds. One major thing I learned from this Chapter is to analyze a particular domain thoroughly and design a distributed programming platform for it, instead of trying to build a platform that works everywhere. Nowadays, distributing computing is an unavoidable task in front of almost every programmer. However, to write robust and efficient distributed programs is not trivial at all. It requires deep knowledge of how computer systems work and very careful design. Distributed programs are also much more difficult to test and debug. Does it mean that we need to train very programmer for it? No! Programmers should not be distracted from their own domain specific tasks. In this case,  to have a platform helps programmers focus on what they are good at and quickly scale their programs up. Unfortunately, distributed computing is very complicated and it often involves many design trade-offs. There is no one general  design that fit in everywhere. Project Darkstar is designed for the uniqueness of massively multiplayer online games (MMOs) and virtual world.

The target domain of Project Darkstar has a similar programming model with many web based services. It has a server and a huge amount of clients (players). Players send Tasks to server to query or update states. In the meantime, it has a few differences which lead to the design trade-offs of this system. I am especially interested in the design of its data model. I also found this technique report cover many details about this. It is very interesting to read.

First, latency is more critical than throughput for MMOs and virtual worlds. It requires very low latency to make sure that people can play games smoothly. This become an especially big problem when we talk about data storage, because data accessing is slow due to disk performance. Achieving low latency could be hard even in a non-distributed environment. Project Darkstar uses a distributed caching system with callbacks to avoid frequent permanent storage accesses and network communication.

Second, data access pattern is different. MMOs and virtual worlds have thick clients, which interactive with users by fancy graphic interfaces. Servers usually just keep states. So servers process a lot of small data access and about half of them are modifications. On the other hands, for most other web-based applications, clients are significantly simpler and servers handle most of the work. This character also mainly affects the design of the storage layer.

Third, users of MMOs and virtual worlds are more open to tolerate temporary data unavailability or even loss. So the design of Project Darkstar trade offs on this.

Fourth, a centralized and globally shared data management is especially important for MMOs and virtual worlds. The reason is two folds. It does not require game designer to divide games into playing areas. Every player is able to interact with every other player. It also prevents cheating more effectively.

Besides data storage, Project Darkstar also put a lot of efforts in other aspects of scaling an application, such as load balancing (demo), dynamic scaling, transaction management and so on.