UPDATED to include compressed 64 bit numbers.

I figured this was worth doing quickly so here are some numbers for the overhead in WebSphere eXtreme Scale for storing 1m objects in a grid. I'm using a single JVM grid in this case but this applies no matter how many JVMs.

I'm storing 1 million Person objects with the following structure:

    String firstName;

    String surname;

    String street;

    String city;

    String zipcode;

I'm populating these strings with some small sample strings. I'm using a key which is just a person# string.

I did the test with 32 bit and 64 bit Sun Java 6 server JVMs on my macbook. I pulled heap usage using the jmap utility supplied with the JDK (jmap -histo:live pid).

WebSphere eXtreme Scale can store object values in two ways, as POJOs or as a compact serialized form (more efficient than normal serialization, like a byte packed version of the data in the value, only available in 7.0+). The byte mode is enabled by having a copyMode="COPY_TO_BYTES" on the backingmap definition in objectgrid.xml. Lets look at the heap size after a system GC in 64 bit JVM mode:

• 64 bit POJO    782.7MB
• 64 bit BYTE    381.0MB

So, you can see the BYTE representation is much more compact than the POJO version, about double the density.

Lets look at when we use -XX:+UseCompressedOops

• 64 bit POJO 592.0M
• 64 bit BYTE 299.4M

You can see that compressed mode significantly reduces the 64 bit overhead by about 25%.

If we do the same thing with 32 bit JVM (-d32 on Mac) then we see

• 32 bit POJO    523.6MB
• 32 bit BYTE    261.0MB

You can see 64 bit has quite a large overhead on Sun. Compressed 64 bit isn't so bad but still isn't as good as straight 32 bit. This is why we recommend 32 bit JVMs with heap sizes under 2.5Gb. It's just most efficient from a memory point of view.

In 32 bit mode, here is a break down for the POJO mode:

•  num     #instances         #bytes  class name
• ----------------------------------------------
•    1:       6016578      230933320  [C
•    2:       6017049      144409176  java.lang.String
•    3:       1000000       80000000  com.ibm.ws.objectgrid.plugins.CacheEntryHeapFactory$HeapEntry
•    4:       1000000       32000000  sample.bench.Person
•    5:        342796       19860816  [Lcom.ibm.ws.xs.util.AbstractMapEntry;

The BYTES model looks like:

•  num     #instances         #bytes  class name
• ----------------------------------------------
•    1:       1005960      108283256  [B
•    2:       1000000       80000000  com.ibm.ws.objectgrid.plugins.ByteArrayCacheEntryFactory$ByteArrayEntry
•    3:       1016742       25359464  [C
•    4:       1017199       24412776  java.lang.String
•    5:        342802       19861344  [Lcom.ibm.ws.xs.util.AbstractMapEntry;

So, our overhead here is 80 bytes per byte array entry, the values are stored as byte[]s in the 108MB chunk and the hybrid hash map takes again 19MB. So, the overhead is still 99 bytes per entry but each entry is stored more efficiently than in POJO mode and it is this saving which makes the big difference in the heap sizes seen above.

Applications interacting with the grid remotely typically use byte mode. Applications running collocated with the grid for highest performance typically use POJO mode in combination with other features but thats another blog entry.

The WXS code about to be released drops the overhead down further to 64 bytes rather than 80 and that will be available soon.

Each partition primary/replica shard is kept in its own area and we've had that design from the beginning because if we kept all data in all shards in a JVM in the same hash map then splitting them is expensive so we never did it that way.

Hopefully, this helps customers size heaps and memory. Obviously, we are continuously working to improve memory density so we can change this when ever we choose to so individual class names we use are not guaranteed at any time.

<P:123:FirstName,Billy>

<P:123:Surname,Newport>

<P:123:Country,USA>

So, if the object had 3 attributes then there are 3 entries. This is flexible in that it's easy to add attributes when they are needed. The store object approach makes that more difficult as the value has a type and it's not easy to add a new attribute. You could store a HashMap as the value which means adding an attribute is easy.

So, you get flexibility with the entry per attribute approach but you pay a heavy performance cost. If a page uses a Person data entry then you may need to make several remote calls to the cache to get this one person. If there is a list of friends then you'd do this for each person. The number of RPCs per page starts to add up pretty fast. I'm pretty sure this is why you see blog entries etc on why memcached needs crazy fast response times, it's simply because one page calls it so often. So, while for environments where extreme schema flexibility is needed, it's an option. You pay a heavy price in terms of performance.

An entity based approach where you store the object at the key uses less memory on the server simply because there are fewer entries per object, i.e. there is one versus one per attribute. Fetching a single entity is cheaper because it's one RPC and you have it all rather than one per attribute. This means that if a page has ten Person objects to be rendered and each Person has 10 attributes then the column approach uses 100 RPCs while the object approach uses 10.

The other issue here is memcached does not offer transactions. Attributes for a single 'object' may hash to different memcached servers and with UDP especially, updates are not guaranteed to work. So, consistency is definitely a problem. Updates may half work. This isn't acceptable to many and the entry per object approach avoids this issue even without transactions because sometimes, all or nothing is better than half way.

I don't think there is a one is better than the other here. For extreme flexibility on schema the attribute per entry model OR the hashmap per entry model is most flexible but it definitely has a cost in terms of performance and consistency. Fetching only exactly the subset of the attributes that you need may be a benefit but the RPC cost cannot be ignored.

Memcached is basically a dumb server. This means it's a process running on a Linux box typically which accepts client requests for keys and returns the data. Updates and deletes are also supported. This is ALL the function in the server, hence, dumb server. The client is the only piece which is 'distributed' or even knows about other servers. The clients typically get a collection of host:ip addresses (they all NEED to use the same list) and the clients hash the key over the set of online servers. If there were 4 servers running then all clients will hash data for a key over these 4 servers. Clients will write data for a key K to a particular server using this hash algorithm. One server.

Now, thats what memcached does out of the box. Note, there is no replication on the server side. If a server fails then the clients will hash keys over 3 servers but this changes everything from a hashing point of view so it's likely you'll get a very high miss rate as it's unlikely keys still hash to the same server as before given the modulo part of the hashing is now 3 instead of 4.

Clients work around this by adding a consistent hashing layer on top of the normal client. This works better and writes may be written to a server and the next server in the hash ring. This slows down writes by 2x but allows some recoverability when a server fails. The next server in the ring has the data from the dead server so it's not as bad as before BUT if this server also fails then now the cache has lost the data. It's not replicated remember, it's just written twice. After the first server failed, the clients write changes to the next server and the following server in the hash ring. The new next server in the ring does not have a copy of all the data. It was never written there. It will just have new changes since the failure. There is no active replication going on here.

Most of the materiel on the web shows various workarounds to try to make memcached 'reliable'. A lot of the facebook engineering blog entries focus on this aspect. What they had to do to make it reliable. This works for facebook but won't work in general because I don't think the majority of customers are structured like they are from a build your own mentality. I was talking to someone from one of the big internet shops last week and they always run two memcached clusters for HA. If a server in cluster A fails then they stop using cluster A and switch to B. This works but thats a 50% loss in hardware because of a single failure.

Smart servers

Commercial data grids like IBM WebSphere eXtreme Scale are very different. They handle making the data fault tolerant on the server side with built-in replication and elastic scale out and scale in. Their clients understand the server side data layout or routing. If a server fails with WebSphere eXtreme Scale then no data is lost. The software actively maintains replicas on other servers. Clients that stored an entry with a key K before will still find it. It just works. You don't need consistent hashing on the client, our client does it using routing tables instead. Adding more server processes causes the product to automatically redistribute the minimum amount of data to leverage the new memory/CPU and network available through the new JVMs.

The smart servers allow proper replication which means that the cache isn't as brittle as the memcached cache when servers come and go. If nothing ever fails then the memcached approach works but the potential cache hit rates over time if multiple failures occur mean it can be a liability. The last facebook entry I read on this showed them crawling the logs to try to recover lost data to make the 'next server' more complete. They get this issue and are jumping through hoops to handle it but again, most commercial customers won't do this. They expect the product to do this sort of stuff like replication and they view it as table steaks.

So, memcached for sure has its uses but it's got some limitations which need a fair bit of work by its users to handle correctly if its not exactly what you want or risk some bad scenarios as the cache hit rate climbs. It's very, very fast but you gotta remember, it's not doing much either... No transactions, no consistency, no replication, no isolation and so on. If you don't need these features then it's pretty fast but if you do need this stuff then it starts to slow as you add code on the client side to try and compensate for the limitations.

Virtualization takes multiple physical machines, virtualizes them and then runs them concurrently on a single server. The argument is that they are normally using little CPU so it's ok to run them all on a single box which will then run with a much higher CPU utilization, say 70/80%. The main issue is memory. Most boxes which are targets for consolation are usually older servers with slow CPUs. 5% on such a box might be 1% on a modern box. This means that many such older machines can be consolidated on to a newer more powerful server. However, while CPU is usually plentiful and cheap, the real issue is memory. That much memory can be expensive. DRAM cost goes through the roof when larger capacity DIMMs are required. This means that virtualization vendors typically recommend over committing the server memory. This basically means they are recommending swapping at the hypervisor level. This dramatically cuts the amount of memory required and lowers the TCO of the solution correspondingly.

C programs or scripts tend to respond well to paging. They typically have small working sets (active memory pages) and then rest of the process or virtual machine can be paged out without dramatically impacting the performance of the virtual machine. They typically don't regularly sweep the contents of their address space. Java, however, is a completely different animal. Java Virtual Machines only have one working set size, the whole virtual machine heap. The objects used by a Java application are typically randomly spread all over the address space of a process. Any timers which fire can cause much of the JVM to be paged in by the hypervisor and if a garbage collection is triggered then the whole JVM heap must be paged in from disk as the garbage collector sweeps ALL the memory, a very slow operation. This page in will cause other virtual machines to be paged out then they garbage collect and we get a ping pong effect. This behavior can cause major variances in response times for users of the applications hosted in the JVM. A garbage collection which normally completes in hundreds of milliseconds might take minutes to complete in such an environment and the applications within that JVM are frozen during this time. Many Java applications utilize timers for JDBC connection pooling, time outs, heart beating for cluster management and so on. The paging activity wreaks havoc on these kinds of time sensitive operations and will cause most Java applications to behave very erratically if not fail completely. Any kind of clustering framework will not survive a paging environment due to the timing sensitive nature of heart beating and similar code.

Java Virtual Machine technology needs to be improved to that it can cooperate with the host operating system or hypervisor to minimize its working set which should allow it to be paged more efficiently but garbage collection will likely still remain a tough problem to beat in an environment that is actively paging. Any virtualization vendor will struggle to keep a customer happy in an over committed memory virtualized system. These systems are frequently sold to customers with the assurance that over committing the memory is ok but this usually results in the customer being unsatisfied and then complaining to the Java application vendor about poor performance or unstable behavior. The response to these questions will likely be "Don't overcommit your memory!". The response is usually "But, the virtualization vendor said it was ok otherwise the system becomes very expensive…" and the final response from the application server vendor will be "Yep, thats right…"

Solid state disks for paging might help with the situation. But, any stateful application server with timing sensitive code will likely still encounter some issues in such as environment because of the jitter introduced by paging. WebSphere includes code to check for such jittery environments. It's a simple alarm which fires periodically and simply checks that it is fired when it expected to be fired. If the timer discovers that its several seconds later than it expected then it logs a message indicating CPU starvation is occurring. This only happened in the past on machines whose operating systems were paging OR on machines running hundreds of JVMs which suddenly all get busy and overwhelm the CPU capacity of the server. Imagine 500 threads that are all CPU bound running on a 8 core box. If each thread runs for 200ms when it gains the CPU then one second can service about 40 threads. This means around 12 seconds will elapse for any given thread before it even RUNS again. This is unacceptable for any timeout style operations with resolutions lower than that. We are seeing customers now reporting problems in virtualized servers where they have overcommitted the memory and while the local operating system is not paging, the hypervisor is. The result is the same. Erratic behavior.

In summary, this kind of behavior is not new. It's been seen before on systems which page or are simply overloaded. Either way the system was either out of CPU or out of memory or BOTH. Customers running virtualized systems need to be very careful when overcommitting either resource if predictable application behavior is required.

So, they usually say overcommit the memory and everything will be ok. Thats not true (especially for Java applications, we run into this ALL the time, don't believe the ok to overcommit advice) but thats another blog post on why swapping and Java DO NOT MIX right now. VMWare needs a way to reduce the cost of RAM so that it lowers the cost of the platform and lets people host as many virtual machines as possible on a single box without breaking the bank on memory cost.

A normal unvirtualized box runs an operating system and the OS hosts processes. One per application maybe. Memory utilization is pretty efficient. All processes can share libraries in memory, file system caches and the memory of the operating system is amortized over many processes.

This isn't the case with VMWare, a hypervisor. Each virtual machine runs its own copy of the operating system with its own file system cache. There is usually no sharing of memory between virtual machine instances (although thats changing). This means a virtualized box is inherently less memory efficient than a single operating system instance running the same applications. The multiple operating system instances are costing VMWare a lot of memory. A hypervisor may be more CPU efficient but it's not as memory efficient as a single operating system running the same applications. You can enable swapping to avoid the need for so much memory but Java applications don't work well with swapping so lets assume we are not swapping. Now, there are advantages to using a hypervisor but we are talking about the resources needed to run X applications here and memory factors in.

VMWare could get in to the operating system business but thats going to fail. Windows and Linux basically own that space. Microsoft is busy adding hypervisor capabilities to their own stack which will cost less than VMWare so hosting Microsoft applications is probably not a long term business for them.

I said at the beginning that Java is important to VMWare. Normal applications are built against a specific operating system thats evolving. VMWare is unlikely to be able to host normal applications without an operating system because they can't emulate the operating systems. They would need to host the operating system as a virtual machine and as we said earlier, thats not memory efficient.

Now, there are a lot of Enterprise applications written in Java. This means that if VMWare could host Java applications natively, i.e. if VMWare can host a Java virtual machine without an operating system then potentially they can be as memory efficient as an operating system. They can use shared memory between JVM instances for JITed code. They would only need to implement the Java API which is basically portable across machines and operating systems. This is significantly easier than emulating Linux or Windows. A Java skin gives them a way to host Enterprise Java applications natively and cut the memory overhead a hypervisor brings to the table by removing the overhead of an operating system.

A hypervisor has advantages over a native operating system in that it can move virtual machines from one box to another and suspend/resume them. Application or virtual machine mobility is a big selling point for a hypervisor. It's possible that VMWare sees Java as a way to lower the cost of virtualizing Enterprise applications. However, operating system zones and WPARs offer application mobility also so this advantage is not such a big deal anymore. A big advantage WPAR/Zones have over virtual machine mobility is that you're not bound to an operating system with WPAR/Zones. You can upgrade an application by moving it from a Linux Version N to a Linux Version N+1 machine. Moving a VMWare image doesnt upgrade the OS, the OS is still the same after you move the virtual machine. You'd need to upgrade it in the virtual machine which is more hassle than just moving a WPAR/Zone.

This native Java Virtual Machine puts them in a similar situation to Azul. Azul can run standard Java code but unless the applications are certified to be supported on it then customers are reluctant to do it and vendors are reluctant to support their products on that configuration mostly because of support/testing cost. A VMWave JVM would suffer the same consequences. Application server vendors would have to certify and support it to move applications over and that can be a tough thing to get them to do.

Buying Spring gives VMWare Spring TC and Spring DM. These are Java application containers which can probably run 80% of departmental and many enterprise Java applications (Servlets, JDBC, JPA, JMS). It's not JavaEE certified but it's probably enough to run most Java applications. If customers can move Java applications to such a container and hosting them on a virtualized environment then potentially you can lower VMWares TCO as it'll require less memory to host them.

I'm actually skeptical that VMWare offers many advantages over just running an operating system natively on the box for Java applications. Best case, VMWare would match the memory footprint of the operating system and it would likely run the applications a little slower. Application mobility is still an issue for operating system hosted applications but technologies like Solaris Zones or AIX WPARs are starting to address application mobility without the memory cost of a full virtualized environment such as VMWare.

So, to summarize. VMWare could host Java applications natively to lower TCO. This would allow them to host multiple Java applications on a single box with similar TCO best case to a conventional operating system. Hosting commercial application servers like this would likely be a support problem but as I said, many Java applications would run on a native Spring TC environment. Application mobility between boxes was a big advantage for hypervisors such as VMWare but operating system features such as Solaris Zones and AIX WPARs are rapidly eroding that advantage because applications installed in a zone or WPAR are basically portable anyway between machines and have the advantage of not being bound to an operating system version as is the case with a virtual machine image. Once customers figure this out then they may decide that using a conventional operating system with WPARs or Zones is actually a more cost efficient and easier path to swallow than picking up a new platform based on a hypervisor which would not be as memory efficient as a normal operating system would be. 

Will VMWare ultimately fail because what customers really want is not virtual machine mobility, they want application mobility?

Lets examine what exactly lock free means. Typically, it means having an atomic reference to a shared read only data structure. Threads can get a reference to the data structure and access it without fear of other threads because the data structure is read only.

If a thread wants to change the data structure then it must copy the current data structure and only update the copy with the new changes. Then, it basically does the equivalent of an optimistic database lock. It uses a compare and swap operation which will replace the atomic reference to the data structure with the new one only if no other thread can also modified it since the updating thread read the original data structure.

If the compare and swap succeeds then all is good. If not then the thread must get a reference to the current data structure and try to make the change to that one and then do compare and swap again. It has to keep trying to do this until it succeeds.

Clearly, first of all for read mostly data structures this approach is pretty cool and is a LOT better than a read/write lock. If writes are more frequent then contention will start to occur between writes as they compete to get to the compare and swap first. Frequent writes would also mean frequent copy operations. Once per loop try per thread. If you have a lot of contention AND the data structure is expensive to copy then this is going to burn a lot of CPU in those copy and update loops.

Java 5 has support for this type of lock programming. Look at the AtomicReference class and its compareAndSwap method. The trick to using it is NEVER update a data structure, always copy and then either update while copying or update after copy. Then try change the AtomicReference to the updated copy using compareAndSwap and if it fails then try updating the data structure that the AtomicReference now points to.

I think a lot of customers think of extreme performance when they think about products like IBM WebSphere eXtreme Scale. Millions of transactions per second. Hundreds of servers and so on. "We're not facebook or google, we don't need this". They may wrongly conclude it's not for them. But, the reality is there are very few customers with those kinds of requirements. However, there are many, many more customers with conventional type applications doing a couple of hundred transactions/sec or less who could readily use WebSphere eXtreme Scale to save them a lot of money for little investment especially when they have already made the investment to go SOA.

We added this type of grid starting with V6.1.0.3, prior to this we had 'normal' grids which are a fixed number of partitions and the key of a Map hashed to one of those partitions. We place the partitions on the set of online container JVMs and automatically scale them out or in if JVMs are added and removed. This grid works very well for key based grids, where the applications uses a key object to locate data in the grid.

• Start a JVM, it gets 5 primaries. (P0-P4)
  JVM#1 -> P0, P1, P2, P3, P4 
• Start another JVM, it gets 5 primaries (P5-P9). Replicas for P0-4 are placed on it and replicas for P5-9 go on JVM#1.
  JVM#1 -> P0,P1,P2,P3,P4,R5,R6,R7,R8,R9
  JVM#2 -> P5,P6,P7,P8,P9,R0,R1,R2,R3,R4
    
•  Start another JVM, it gets 5 primaries (p10-p14). The replicas for p10-p14 are placed on JVM#1 and JVM#2 and some of the replicas for P0-P9 are moved to JVM#3 to balance the load.
  
  
  

  JVM#1 -> P0,P1,P2,P3,P4,R7,R8,R9,R10,R11,R12

  JVM#2 -> P5,P6,P7,P8,P9,R2,R3,R4,R13,R14

  JVM#3 -> P10,P11,P12,P13,P14,R5,R6,R0,R1