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.