Top Most Caching Framework - Sample Cache Implementation

I was asked in an interview to design a cache framework.
The problem statement was:
Develop a caching framework that provides the following:
1) Load data from file, database or any other source
2) Refreshes the data after a configurable interval if it is not a one time load
3) Invalidates the cached objects after a configurable interval.

Few questions that come to mind while designing is what should be cache.
And If I assume it is going to be Map, then what would be key and value.
Second critical thing is how to expose the Cache to clients.
What operations to support.

I decided for using ConcurrentHashMap as my cache.
There are several benefits of using this Map over others like:
Operations are thread safe supporting full concurrency and highly efficient.

Clients would access the Cache through a CacheProvider.
I created an interface named CacheProvider.
This is the starting point of my Cache Implementation.
Below is the code for CacheProvider:

public interface CacheProvider {
        Object getAndSet( String key);
Object setAndGet( String key );
void refresh();
void invalidateObj();
void cancel();
}


I had an initial requirement where I can invalidate objects in Cache after certain interval if there is no access.
I also decided that,
If a particular data is retrieved then its there should be fresh start of invalidation time, i.e. if I am going to configure the invalidation time as 5 min.
and If some object is not accessed for 5 mins, it would be removed from Cache.
And if some object is not accessed for 4 mins, and some client asks for this object, then there should be fresh start, means it would be invalidated after 5 mins from now, if not accessed in next 5 mins.
I would also be configuring an refresh policy, and refreshing all objects in the cache at particular interval.

Regarding data. I used Derby for testing.
I designed Cache to support data from Database, or from file, or to test simple data can be provided as command line arguments.
I know this is too early to talk about this.
But this is going to be initial requirement of where data would be stored and how MyCacheProvider would load data from data provider.

I created three classes for handling data.
CollectionManager - for managing data from command line
FileManager - for managing data from File
DBManager - for managing data from Database.

I am providing the code for all the data managers.
But if one is not interested, then one can simple ignore the below three classes.


CollectonManager:

FileManager:

DBManager:


DBManager is a class which manages data in database.  I have used Derby.  Using derby is very easy, and its useful in applications like this.  You don't need database, its just one jar. Evrything inside the jar, database, and drivers.


My DBManager class is below:


DBmanager has code for initialization, where it reads config values from a file and intializes a DB connection. 

Then, DBManager has code to create the table, populate the table with data. 
Remember, this data would be used to cache. 

Then code to retrieve all data from the database, this method would be called to refresh the whole cache with data from database. 

And method to retrieve a particular data from database. 

I started my design with a CacheProvider interface. 
Now I would extend that clas and create MyCacheProvider, also I would create a CustomKey to store in Cache.
MyCacheProvider would internally use a ConcurrentHashMap for storing data.

Below is the code of CustomCacheKey, instance of this class would act as key in the Cache, or ConcurrentHashMap inside the MyCacheProvider.

CustomCacheKey:

MyCacheProvider:
MyCacheProvider extends CacheProvider, implements getAndSet() method retrieves the value from Cache, put the same key again in the cahce with updated timestamp.
Whenever a key is retrieved from Cache, its timestamp should be updated, so we either update the timestamp of the key(CustomKey), or put a new key with same value and new timestamp in the Cache.
We have to maintain the timestamp, in order to invalidate inactive objects in Cache.

We also have methods to refresh the cache and append a user provided hashmap to cache.

MyCacheProvider should also contain methods to invalidate a particular object, and provide method to cancel or clear whole cache.

Now, I decided that clients should not directly use the MyCacheProvider, because in future I would be creating some more implementation of CacheProvider, and making it configurable.

I made a CacheHandler, and clients would use this handler, with limited operations exposed.

CacheHandler:

public class CacheHandler {
static MyCacheProvider myCacheProvider;

public static void start(){
myCacheProvider = MyCacheProvider.getCacheProvider();

}
public static Object get(String key){
Object myCachedObject = myCacheProvider.getAndSet(key);
if (myCachedObject == null) {
myCachedObject = myCacheProvider.setAndGet(key);
}
return myCachedObject;
}

public static void refreshCache(){
myCacheProvider.refresh();
}

public static void invalidateObj(){
myCacheProvider.invalidateObj();
}

public static void cancel(){
myCacheProvider.cancel();
myCacheProvider = null;
}

public static Map mapStatus(){
return myCacheProvider.mapStatus();
}
}

For simplicity I made above class a static class.

Now I am done with initial design of Cache with three classes.
MyCacheProvider, CustomCacheKey, and CacheHandler.
CacheProvider is a super interface.
And I created three classes for handling persistent data.

I have to run two tasks periodically:
Invalidate objects after specific interval
Refresh the whole cache.
I decided of one more task, which prints the Cache status.

SO, I am going to create three tasks:
CacheInvalidateObjTask - for invalidating the Cache objects.
CacheMapStatus - for printing the Cache status.
CacheRefreshTask - for refreshing the cache.

CacheInvalidateObjTask:

public class CacheInvalidateObjTask implements Runnable{

public void run(){
CacheHandler.invalidateObj();
}
}

CacheMapStatus:

public class CacheMapStatus implements Runnable{
Map map;

public void run(){
map = CacheHandler.mapStatus();
long time = System.currentTimeMillis();
System.out.println("Map Status.. at.." + time/1000 + " secs..");
System.out.println(map);
}

}

CacheRefreshTask:

public class CacheRefreshTask implements Runnable{

public void run(){
CacheHandler.refreshCache();
}

}

So I created three tasks.

I also created two classes, which can be skipped:

CacheConstants:

public interface CacheConstants {

// Resource provider Constants
String RESOURCE_PROVIDER_COLLECTION = "collection";
String RESOURCE_PROVIDER_DATABASE = "database";
String RESOURCE_PROVIDER_FILE = "file";
}

CacheProperties:

public class CacheProperties {

public static int CACHE_SIZE = 0;

public static long INVALIDATE_OBJ_TIMER_INTERVAL = 1000L;
public static long REFRESH_TIMER_INTERVAL =1000L;
public static long PRINT_MAP_TIMER= 1000L;

public static String RESOURCE_PROVIDER = "";

public static String RESOURCE_FILE_PATH= "";

public static String DATABASE_DRIVER = "";
public static String DATABASE_PROTOCOL = "";
public static String DATABASE_NAME = "";
public static String DATABASE_USERID = "";
public static String DATABASE_PWD = "";
public static String DATABASE_TABLE_NAME = "";
public static Boolean DATABASE_CREATE = true;
public static Boolean DATABASE_CREATE_TABLE = true;
}

To start the application, I have created a class CacheService.
CacheService uses CacheServiceHelper, and delegates the call to CacheServiceHelper.

CacheService:

CacheServiceHelper:

CacheServiceHelper contains methods to schedule the three tasks. And method to set the Env.

And a cleanup method to clear the cache:

void cleanUp(){
CacheHandler.cancel();
}


And our cache is ready.


Summary:

CacheService is the main class to start the program.
CahceServiceHelper is for handling all the startup tasks.
CacheService calls the CacheServiceHelper for initializing the environment, and starting the service.
In initialization, CacheServiceHelper sets the properties, and the resource provider.
Resource provider will provide data to store in the cache, it can be either database, or file, or command line arguments.
CacheServiceHelper, starts the service by creating three tasks and submitting them to a ScheduledthreadPool.
Tasks are:
1. Task to refresh the cache map, periodically, CacheRefreshTask
2. Task to invalidate objects inside cache map after specified time, CacheInvalidateObjTask
3. Task to print the map status to console, CacheMapStatus
Each of these tasks call CacheHandler, which is a façade for all Cache related operations.
CacheHandler, depends on MyCacheProvider for all its operations.
MyCacheProvider is the core class for handling the cache.
MyCacheProvider has a map to hold data. It holds data in a ConcurrentHashMap.

Application needs a cache.properties file with following configurable properties:
intial.cache.size - Initial cache Size.
invalidate.object.interval - Interval to invalidate the object, or remove o0bject from cache.
refresh.cache.interval - Interval for Refreshing the cache.
print.map.timer - Interval to print the contents of cache map.
source - source of the data provider.
Valied values are :
collection – if data is provided via
command Line arguments
database - if data provider is database
file - if data provider is file.


#Database properties
#if database as resource, below properties are mandatory
db.driver=
db.userId=
db.pwd=
db.protocol=
db.dbname=
#optional Database properties
db.createdatabase=
db.createTable=

# File properties.. if “file” is data provider, i.e. source property is file
file.path=C:\\test.txt

Below is the package Structure and UML class diagrams:

Classes:

!!!Any Comments would be really appreciated!!!

Top Most Problem Resolution

I observed a small team that included a very talented developer. They were asked to solve a very nasty production performance issue.

The developer had a "gut feeling" for the problem and wanted to try his solution.

This approach is akin to picking the low hanging fruit.

To solve this type of issue, it is often wise to attempt to pick the low hanging fruit and hope for a quick resolution.

However you must limit your fruit intake. After a few tries, you need to resort to proper analysis and isolate the problem.

After his initial effort failed, he again had another "gut feeling" and wanted to try for another quick fix. This pattern repeated itself several more times, until he gave up and quietly moved on.

Unfortunately the low hanging fruit was too appealing, and management was easily sold by the quick solution. The proper analysis was never done. The issue was never resolved.

Gut feelings often result in brilliant work. When they fail, there must be proper analysis. The pragmatic programmer must set aside emotionally-driven behaviors and use a more prudent approach.

Top Most Garbage Collection Algorithm - JDK Implementation

There are several basic strategies for garbage collection: reference counting, mark-sweep, mark-compact, and copying. In addition, some algorithms can do their job incrementally (the entire heap need not be collected at once, resulting in shorter collection pauses), and some can run while the user program runs (concurrent collectors). Others must perform an entire collection at once while the user program is suspended (so-called stop-the-world collectors). Finally, there are hybrid collectors, such as the generational collector employed by the 1.2 and later JDKs, which use different collection algorithms on different areas of the heap.

Old objects, young objects

In any application heap, some objects become garbage shortly after their creation, some survive for a long time and then become garbage, and others can remain live for the entirety of the program's run. Empirical studies have shown that for most object-oriented languages, the Java language included, the vast majority of objects -- as much as 98 percent, depending on your metric for object youth -- die young. One can measure an object's age in wall-clock seconds, in total bytes allocated by the memory management subsystem since the object was allocated, or the number of garbage collections since the object was allocated. But no matter how you measure, the studies show the same thing -- most objects die young. The fact that most objects die young has significance for the choice of collector. In particular, copying collectors perform quite well when the majority of objects die young, since copying collectors do not visit dead objects at all; they simply copy the live objects to another heap region, then reclaim the whole of the remaining space in one fell swoop.

Of the objects that survive past their first collection, a significant portion of those will become long-lived or permanent. The various garbage collection strategies perform very differently depending on the mix of short-lived and long-lived objects. Copying collectors work very well when most objects die young, because objects that die young never need to be copied at all. However, the copying collector deals poorly with long-lived objects, repeatedly copying them back and forth from one semi-space to another. Conversely, mark-compact collectors do very well with long-lived objects, because long-lived objects tend to accumulate at the bottom of the heap and then do not need to be copied again. Mark-sweep and mark-compact collectors, however, expend considerably more effort examining dead objects, because they must examine every object in the heap during the sweep phase.

algorithms

Reference counting

The most straightforward garbage collection strategy is reference counting. Reference counting is simple, but requires significant assistance from the compiler and imposes overhead on the mutator (the term for the user program, from the perspective of the garbage collector). Each object has an associated reference count -- the number of active references to that object. If an object's reference count is zero, it is garbage (unreachable from the user program) and can be recycled. Every time a pointer reference is modified, such as through an assignment statement, or when a reference goes out of scope, the compiler must generate code to update the referenced object's reference count. If an object's reference count goes to zero, the runtime can reclaim the block immediately (and decrement the reference counts of any blocks that the reclaimed block references), or place it on a queue for deferred collection.

Reference counting is simple, lends itself well to incremental collection, and the collection process tends to have good locality of reference, but it is rarely used in production garbage collectors for a number of reasons, such as its inability to reclaim unreachable cyclic structures (objects that reference each other directly or indirectly, like a circularly linked list or a tree that contains back-pointers to the parent node).

Tracing collector

None of the standard garbage collectors in the JDK uses reference counting; instead, they all use some form of tracing collector. A tracing collector stops the world (although not necessarily for the entire duration of the collection) and starts tracing objects, starting at the root set and following references until all reachable objects have been examined. Roots can be found in program registers, in local (stack-based) variables in each thread's stack, and in static variables.

Mark-sweep collectors

The most basic form of tracing collector, in which the world is stopped and the collector visits each live node, starting from the roots, and marks each node it visits. When there are no more references to follow, collection is complete, and then the heap is swept (that is, every object in the heap is examined), and any object not marked is reclaimed as garbage and returned to the free list.

The big problem with mark-sweep is that every active (that is, allocated) object, whether reachable or not, is visited during the sweep phase. Because a significant percentage of objects are likely to be garbage, this means that the collector is spending considerable effort examining and handling garbage. Mark-sweep collectors also tend to leave the heap fragmented, which can cause locality issues and can also cause allocation failures even when sufficient free memory appears to be available.

Copying collectors

In a copying collector, another form of tracing collector, the heap is divided into two equally sized semi-spaces, one of which contains active data and the other is unused. When the active space fills up, the world is stopped and live objects are copied from the active space into the inactive space. The roles of the spaces are then flipped, with the old inactive space becoming the new active space.

Copying collection has the advantage of only visiting live objects, which means garbage objects will not be examined, nor will they need to be paged into memory or brought into the cache. The duration of collection cycles in a copying collector is driven by the number of live objects. However, copying collectors have the added cost of copying the data from one space to another, adjusting all references to point to the new copy. In particular, long-lived objects will be copied back and forth on every collection.

Mark-compact collectors

The copying algorithm has excellent performance characteristics, but it has the drawback of requiring twice as much memory as a mark-sweep collector. The mark-compact algorithm combines mark-sweep and copying in a way that avoids this problem, at the cost of some increased collection complexity. Like mark-sweep, mark-compact is a two-phase process, where each live object is visited and marked in the marking phase. Then, marked objects are copied such that all the live objects are compacted at the bottom of the heap. If a complete compaction is performed at every collection, the resulting heap is similar to the result of a copying collector -- there is a clear demarcation between the active portion of the heap and the free area, so that allocation costs are comparable to a copying collector. Long-lived objects tend to accumulate at the bottom of the heap, so they are not copied repeatedly as they are in a copying collector.

Generational collection

A generational collector divides the heap into multiple generations. Objects are created in the young generation, and objects that meet some promotion criteria, such as having survived a certain number of collections, are then promoted to the next older generation. A generational collector is free to use a different collection strategy for different generations and perform garbage collection on the generations separately.

Minor collections

One of the advantages of generational collection is that it can make garbage collection pauses shorter by not collecting all generations at once. When the allocator is unable to fulfill an allocation request, it first triggers a minor collection, which only collects the youngest generation. Since many of the objects in the young generation will already be dead and the copying collector does not need to examine dead objects at all, minor collection pauses can be quite short and can often reclaim significant heap space. If the minor collection frees enough heap space, the user program can resume immediately. If it does not free enough heap space, it proceeds to collect higher generations until enough memory has been reclaimed. (In the event the garbage collector cannot reclaim enough memory after a full collection, it will either expand the heap or it will throw anOutOfMemoryError.)

The JDK 1.4.1 default collector

By default, the 1.4.1 JDK divides the heap into two sections, a young generation and an old generation. (Actually, there is also a third section, the permanent space, which is used for storing loaded class and method objects.) The young generation is divided into a creation space, often called Eden, and two survivor semi-spaces, using a copying collector.

The old generation uses a mark-compact collector. Objects are promoted from the young generation to the old generation after they have survived copying a certain number of times. A minor collection will copy live objects from Eden and one of the survivor semi-spaces into the other survivor space, potentially promoting some objects to the older generation. A major collection will collect both the young and old generation. The System.gc() method always triggers a major collection, which is one of the reasons you should use System.gc() sparingly, if at all, because major collections can take much longer than a minor collection. There is no way to programmatically trigger a minor collection.

Different algorithms can be used to perform garbage collection in the different generations, each algorithm
optimized based on commonly observed characteristics for that particular generation. Generational garbage
collection exploits the following observations, known as the weak generational hypothesis, regarding
applications written in several programming languages, including the Java programming language:
• Most allocated objects are not referenced (considered live) for long, that is, they die young.
• Few references from older to younger objects exist.

Below is the table which summarizes the algorithm used by different types of Garbage Collectors in J2SE 5.0:




Parallel Compacting collector - Old Generation:
(Mark - Summary - Compact)

Marking Phase:
Several threads would run.
Heap would be divided into regions.
One thread per region would run.
Each region has data. Data would be updated by thread with information about the size & location of the live objects.

Summary Phase:
(One thread)
Summary phase examines the density of each region & calculates a point after which, space recovered after compacting would be worth. Region left of that point is referred as "Dense Prefix".
Assume, our heap is in following stage(several cycles of GC has already run).

Our heap reached this state after several GC cycles, so, the left side of heap is dense & contains most live objects. If compacting is performed in the left most region, then very little amount of space would be recovered, and which is not worth.
Summary Phase examines the density of regions, starting from the left most, until it reaches a point where the space that could be recovered from a region and those to right of it, is worth. Worth the cost of compactng those regions.

Compaction phase:
(Multiple threads)
Summary phase calculates and stores the new location of the first byte of the live objects, in data associated with each region. Regions to the right have to be compacted. And we have to move all objects within a region to left side of that region.
Compaction phase uses the data prepared by the summary phase to identify, which regions are to be compacted, and which objects to move, and new location of the objects(in case they are to be moved). Multiple threads run independently, one in each region.

Thus, finally a single large empty block would be created at the right end.

CMS Collector - Old Generation



Initial Mark
Identifies the initial set of live objects, directly reachable form application code.

Concurrent Mark
Marks all live objects that are transitively reachable from the set(prepared by initial mark)

Remark
Revisit any object that was modified during the concurrent mark.
(Objects created while Concurrent mark was running, would be marked now)

At the end of markings, it is guaranteed all live objects on the heap have been marked.
Now, Concurrent Sweep Phase, reclaims all the garbage that has been identified.

CMS Collector is not compacting, which means it does not move the live objects to one end of the old generation.
Since the free space is not contigous, the collector can no longer use a simple pointer indicating the next free location into which the next objext can be allocated.
It employs free lists. Lists linking together unallocated regions of memory.
Each time an object needs to be allocated, the appropriate list(based on the amount of memory needed) must be searched for a region large enough to hold the object.

CMS has advantage in term of pause time, in the figure we can see that total pause time is Pause1 + Pause2. When multiple threads( i.e. n) are running, then pause time is reduced by n.


New JDK7 Garbage Collector:

The Garbage First(G1) Garbage Collecor
Like Other HotSpot GC's, G1 is generational means it has concept of old objects and new objects. GC cycles visit new objects very frequently, and old objects less frequently.
Big difference between G1 and other Garbage collector is that now there is no physical difference between young generation and old generation.
Whole heap is divided into multiple regions.
Each region is of same size.
Few set of regions belong to young generation and few set to old generation.
SO, young generation is a non-contiguous set of regions, and similar is old generation. G1 is flexible enough to move objects from new to old and vice versa any time.
Initially, a few st of regions(belonging to young generation) are considered as part of collection set. so all live objects are marked in the regions belonging to collection set. Now there is a evacuation pause, and during this pause, survivor objects from the collection set are evacuated to another set of regions(the to-spaces), and then collection set region is reclaimed.
Evacuation pauses collect the young generation, but sometimes old generations are also collected during the pause time.
In regions belonging to old generation, there is Concurrent marking(similar to CMS old generation collector). Profitable regions are marked, i.e. where performing collection is worth. There is no concurrent sweeping. The most profitable old regions identified by marking phase are collected during the evacuation pause.
Unlike CMS, G1 performs compaction over time. Compaction eliminates fragmentation, which was a big issue with CMS collector.

Reference: http://www.ibm.com/developerworks/java/library/j-jtp10283/

!!!Any Comments would be really appreciated!!!

Top Most Java Interview Question 10: Swap the values of two variables without using third variable

Have you already come across a situation where you need to swap the values of two variables without using third variable? I bet it was during an fresher interview for Java Developer position. As an interviewee you can think that it is a poorly chosen interview question and the only person who can answer this questions is the one who knows the trick in advance. I’m agree in some ways it is tough

Top Most Java

Introduction
Basics

Top Most Java Runtime Memory Management

IN Java, Memory Management means Garbage Collection and memory allocation. Memory allocation is very small process as compared to Garbage Collection. Indeed, a well playing Garbage collection makes everything easy for memory allocation. Only major issue before memory allocation is Weather sufficient Memory available?. And its Garbage Collector responsibility to ensure enough memory is available all the time, otherwise ready to a face biggest obstacle “OutOfMemory” in running application. Writing a efficient Garbage Collection algorithm is very tedious task. Thanks to JVM, that they come up with several algorithms, and by default apply the best one. In day to day programming one might never feel a need to understand those algorithms, unless you have passion for knowing whats going on under the hood. OR some day after years of programming you face “OutOfMemory” Exception, and then you check that there are plenty of options which can be used to avoid such situation, for example JVM comes with several algorithms, and you start googling which  one to use. After so many years of working over Java/J2EE i really need a feel to understand those algorithms, JVM memory management, memory sizing, and defaults.

In Java, we can entirely eliminate the problems of memory leaks.
IN my post –  http://shekup.blogspot.com/2010/02/garbage-collection-algorithm.html
I discussed the Garbage collection algorithms.
I want to share my analysis and reading about Memory Management, JVM Heap, Garbage Collection Algorithms, and tuning.

Recently I attended a session by Chris Bailey in IBM, got some insight of the Memory Management in Java.
After reading this complete post, one can would be able to efficiently manage the Memory and avoid any memory leak.

The Java Process –  

We are taking here example of 32 bit architecture. Memory management is complicated in 32 bit architecture. IN 64 bit architecture, we have huge memory, OR we can assign large chunk of memory to Java, and it comes with a cost of performance.

Java is a OS level process.  There are some restriction imposed by the OS and architecture.  32 bit architecture means Processor has registers which are 32 bit wide.  32 it can hold values between 0×0 to 0xFFFFFFFF, which is ability to address upyto 4GB of memory.  32 bit process cant use more than 4GB memory for the process itself.   ON 32 bit architecture and/or OS gives max. of 4GB of process address space.

Some memory is used by the OS and C-language runtime.  It depends on which OS you are running.  Below is a simplified diagram -

In windows it sits between nearly 2GB memory.  IN LINUX it takes nearly 1GB memory.  Area left over is termed as “User Space”, So on LINUX Java Runtime sits over 3 GB of memory, i.e. 3 GB of User Space.                                                                                                       Some of the memory of the USer Space is going to be used by Java Virtual Machine.

JVM memory contains execution engine, JIT compiler, etc. which in itself require some memory.

In the User Space some memory is used by the JVM runtime, which is termed as Java Heap. Java Heap has  min. and max. size. Minimum heap(Initial Size) size is set using        -Xms and max. heap size is set using -Xmx.  for example – Running following command on console java -Xmx1024M -Xms512M.

Apart from Java Heap there is a Native(System) Heap.                                             Native Heap is User Space – Java Heap.  Native Heap is required to run threads, used by JIT Compiler to store runtime data and executable code, Classes and ClassLoaders, JNI, java.nio.ByteBuffers, and Java runtime data.

There is automatic selection of Java Heap Sizes, and this is based one classification, i.e. weather machine is server class or client class.                                                                            
 A server class machine is defined to be one with:                                                                      
 2 or more physical processors AND  2 or more gigabytes of physical memory.                                                                                        ON machine that are not Server Class the default values are Initial heap size of 4 MB and Max. heap size of 64 MB.  ON server class machine Initial heap Size is 1/64th of the physical machine and Max. heap size of 1/4th of the physical memory.

Typically on 32bit architecture, single large chunk can’t use more than 4 GB. (Some OS limit this to 2GB or 3GB).  Based on facts we can say, we cant give more 2GB of memory to Java Heap on Windows.  Since total we have 4GB, and some is required by OS and C-language runtime, some is required by JVM , and some is required by Native Heap.  And ideally it should be around 1.5GB on Windows.  On operating systems which impose a 2 GB limit on process size, use a heap size no larger than 1430 MB.  It is generally recommended that the minimum and maximum heap sizes are set to the same value to maximize run time performance.  ( We would discuss this later)

While setting the Maximum heap size, we must consider the memory requirements of theOS and C runtime, JVM, and native heap.                                                                                    
 The memory size of the native heap, should be sufuciently large, specially when there are large number of threads involved.                                                                                                  
A number of Java objects are underpinned by the OS level resources, therefore have associated native heap memory.   When we create a java.land.Thread object, you need an execution thread( P thread on Unix). And that execution thread also has a Execution stack. and that takes memory.   Java Thread takes 160 bytes, and along with that 160 k required on native heap.

Some platforms come with high performance threads, for eg. in following BEA JRockit JVM optimized for Intel architecture.

Source – http://software.intel.com/en-us/articles/intel-technology-provides-the-basis-for-next-generation-mrtes/

Some times you are allocating some memry on Java Heap, and allocating 100 times larger memory on Native Heap. When you create a Java Object, you may be allocating off Java Heap memory also.  A small memory leak in Java Heap can lead to much bigger memory leak in Native Heap. You can get OutOfMemory in case you exhaust Java Heap, you can also get OutOfMemory Error when you exhaust Native Heap. For example, you might get - java.lang.OutOfMemoryError: unable to create new native thread.

In order to avoid any OutOfMemory error, and avoid any memory leak we need to manage memory efficiently. Memory Management is all about recognizing which objects are no longer needed, freeing the memory used by such objects, and making it available. In many modern Object oriented languages this process is automatic, and this automatic process is called Garbage Collection. There are several Algorithms which are used by Garbage Collector. Most efficient algorithm should be used by the collector. Applications consume memory, and way the memory is consumed, should be a criteria for choosing the garbage collector algorithm. A wrong choice may lead to OutOfMemory. Garbage Collector comes with default Algorithm, and which is suitable for most applications. At the end its applications responsibility to set all references to null for any object, if it is no longer required. This would be an indication to Garbage Collector that object is garbage, and it should be collected. An understanding of Garbage Collector algorithms would give you clear insight of how memory is managed, and also how application programmer can contribute to make memory management more efficient

Garbage Collection Algorithms -

Reference Counting - Most straight forward GC(Garbage Collection) algorithm is reference counting. Its most simple algorithm, where we count the number of references to each object. If count is zero for any object, consider the object to be garbage. Compiler has responsibility of increasing the count, after executing any assignment statement for any particular object. The major issue with this algorithm is that it can never claim unreachable cyclic references. for example in the following figure –          

Objects – Obja, Objb, Objx, and Objy are unreachable objects. But their reference count is one, so they can never be collected, even though they are unreachable from stack, and they are no longer used.  Reference Counting Algorithm would surely fail in collecting some no longer used objects like Obja, Objb, Objx, and Objy.

If we think a bit to find out solution to limitation of the Reference Counting algorithm, we know, any object which is not reachable from the root set(Stack) should be collected. One way to do this mark such objects in one go, and then collect them. Tracing Algorithmsstop the applications running(referred as Stop the World) start from the root set, trace every object and mark each reachable object as live. Mark Sweep is a tracing algorithm, which completes in two steps.                                                                                                            

 Step 1 – Mark all live objects(Reachable from rot set), Mark phase.                                        
 Step 2 – Any object not marked is garbage, and it is reclaimed, and memory climed by them is freed, Sweep phase.                                                                                                               

We can definitely say in Mark Sweep Algorithm objects like Obja, Objb, Objx, and Objy would be collected by Garbage Collector. Drawback of Mark Sweep lies in second step, where we are visiting every object, finding out weather it is live or garbage depending upon criteria that it is marked or not. Second major drawback of Mark Sweep is that it leaves memory fragmented, as shown in below figure –          

Above is the picture of Java Heap, after several run of Garbage Collector using MarkSweep Algorithm. the white spaces are free memory, and blue ones are currently used by objects. We can clearly see that memory is fragmented.  A fragmented memory can also also lead to OutOfMemory, which in this case means there is memory available for not enough contiguous memory is available to hold some large object. Which can come when you create a new object, but enough contiguous memory is not available to hold the object. So, we can say there are two major drawbacks of Mark Sweep –                                                           1. Every objects needs to be visited in Sweep phase.                                                                    
 2. Fragmented memory.

In order to resolve the drawbacks of the Mark Sweep, copying Algorithm was introduced, and to resolve the some drawbacks of copying, Mark Compact algorithm was used.

Copying Algorithm - Its another form of tracing algorithm, where heap is divided into two equal parts. Initial allocation of objects are done in one part only. So, only one part is containing active data, and other is unused.     

Above we can see that all objects are allocated memory in the left half of the Java Heap, and since the left half is about to fill, we trace all the objects in the left half and copy all live objects to the right half of the Heap. So left half is only left with the garbage, and that can be collected easily. Check following figures –  

Therefore, we can see we resolved both drawbacks of the Mark Sweep, we only needed to visit the garbage objects during sweep phase, and also we don’s have a fragmented memory. The major trouble with Copying Algorithm is that it requires double the space of Mark Sweep in order to give same performance. Somehow we need to incorporate the suggestions of copying Algorithm into Mark Sweep and come up with Mark CompactAlgorithm.

Mark Compact Algorithm(Mark-Sweep-Compact) - Its Mark Sweep combined with Copying, so increased complexity. Here every live object is marked in one phase. All live objects are compacted to one bottom of heap, and rest are garbage so collected. Compaction can be partial also, but if complete compaction is performed in one cycle of garbage collection, at the end heap would be similar to, result of copying garbage collector.

Above were some of the possible Garbage Collection algorithms. We can come up some more complicated and more efficient algorithms, and definitely current JVM’s are using much more complicated algorithm. One of the major challenge before any algorithm is time lost during “Stop The World”. 

Before we discuss more garbage collection algorithms, we must know one general criteris in which objects can be divided – Old Objects and Young Objects. 

One of the reality of Java Objects which can be utilized while programming garbage collection algorithm is that most of the objects die young, they are short lived. By Short lived we can say they can only survive only few cycles of garbage Collection. Any such object is called Young Objects. Some are long lived Objects, for example, in a Web Application, they stay for few hours. They are called Old Objects.  Some studies say 98% of the objects die young. Copying algorithm works very well with such objects, as they don’t visit the dead objects. Dead objects would be one side of the heap, and would reclaimed in one swoop. On the other hand in case of old objects, copying algorithm is worse, as it would keep on copying the old objects over and over from one side to another.                                  
Based on above classification and analysis, we can say we should have separate algorithms for young and old objects. And how we know weather object is young or old, best way is to keep young and old objects separate. And this was the basis of many Java Heap structure. A need to differentiate young and old objects gave birth to idea of Generational Collection.

A generational collector divides the heap into multiple generations.

HotSpot JVM(currently maintained by Oracle) divides the heap into Young and Old(Tenured) Generation. Objects are created in the young generation, and objects that meet some promotion criteria, such as having survived a certain number of collections, are then promoted to the next older generation, old(/Tenured) generation. A generational collector is free to use a different collection strategy for different generations and perform garbage collection on the generations separately. Please find below the architecture of the HotSpotJVM –

Source - http://www.oracle.com/technetwork/java/javase/gc-tuning-6-140523.html            Here we can see in figure Young Generation consists of Eden, Survivor and Virtual regions. Virtual is the address space which is virtually reserved but not allocated physical memory unless needed. Object is initially allocated to Eden(/creation), and copied to any survivor space by Copying GC, before being promoted to Tenure generation. Objects are copied between survivor spaces multiple times before being promoted to Tenure Generation.  Apart from Young and old generation, some JVM’s like HotSpot include Permanent Generation, which holds objects describing classes and methods or classes and methods themselves.  We only need to consider Young and Old generation while deciding for Algorithms.

Oracle JRockit divides heap into two generations – Nursery and Tenured. Along with Nursery and Tenured region also. Before objects being promoted to Tenure Region they are kept in keep region. And objects need to survive one GC cycle(while in keep area), before being promoted to Old(/Tenure) region.          

IBM JVM also comes into generation – Nursery and Tenured. Below is some extract from the “IBM Developer Kit and Runtime Environment, Java Technology Edition, Version 6″

IBM JVM comes with lot more optimizations and options, but we wont be discussing much about them, may be I would explain them in another post dedicated to IBM JVM.

IN the current post I am only going to discuss about Sun HotSpot JVM.

One of the advantages of generational collection is that it can make garbage collection pauses shorter by not collecting all generations at once.  When the allocator is unable to fulfill an allocation request, it first triggers a minor collection, which only collects the young generation. A Minor Collection often leads to shorter pause, and claims significant amount of memory. If memory freed by minor collection is not enough, GC performs collection in higher generations which contains old objects. When older generations need to be collected there is a major collection that is often much slower because it involves all living objects. Old Generation collections are infrequent and take longer time to complete.  Generally, all the JVM’s are using the copying algorithm for young generation, but increase performance to give better throughput, by default they are using copyingalgorithm with multiple threads.

Regarding garbage collection in old generation, there has been lot of thought and there are few options like –   Mark-Sweep-Compact, Marking-Summary-Compact, and Concurrent Mark-Concurrent Sweep. We have already discussed Mark-Sweep-Compact algorithm. Rest two are also very similar to Mark-Sweep-Compact with slight changes.

Marking-Summary-Compact - 

Marking Phase:
Several threads would run.
Heap would be divided into regions.
One thread per region would run.
Each region has data. Data would be updated by thread with information about the size & location of the live objects.

Summary Phase: (One thread)
Summary phase examines the density of each region & calculates a point after which, space recovered after compacting would be worth. Region left of that point is referred as “Dense Prefix”. Assume, our heap is in following stage(several cycles of GC has already run). The region left to the bold line is Dense prefix. If objects from the right side are moved to left side, we can get chunk of free space on right side. Summary phase would would store the new location(in left side) for live objects in right side.

Compaction phase:(Multiple threads)
Compaction phase uses the data prepared by the summary phase to identify, which regions are to be compacted, and which objects to move, and new location of the objects(in case they are to be moved). Multiple threads run independently, one in each region. And move objects to their new location.

One drawback with above discussed algorithm, is pause time’s. IN order to reduce pause time, we have an option of Concurrent Mark-Concurrent Sweep.

Concurrent Mark Sweep(CMS Collector) – This algorithm uses multiple threads during marking phase(indeed marking is three step process-Initial Mark, concurrent Mark, and Remark), and at the end ensures all live objects are marked. After marking is done, there is concurrent sweep, and all the garbage is collected. Important point to note is there is no compaction.  Benefit of this algorithm over previous ones is that pauses time is very minimal, and drawback is that memory is left fragmented after GC runs, since there is no compaction.

J2SE 5.0 gave us several options of setting the GC – Serial, Parallel, Parallel Compacting, and CMS. Each applying a combination of two algorithms ( one for young generation and one for old). Below table summarizes the combination used by each option( we can set any one option) -

But with all kind of Mark Compact come with two limitations –                                                
 Run time is proportional to size of heap, i.e. O(Size_Of_Heap)                                                    There is always some pause time, we cant ignore them completely even in CMS also. Personally I have not observed but I believe on several 100 GigaBytes of hep, we might get pause time of 1 minute. And 1 minute is huge time.

Recently I watched a Presentation over  ”Do you really get memory” by Jevgeni Kabanov, and understood in more detail about some really latest most efficient garbage collection algorithms. Below is the extract from his presentation which i watched over infoq - http://www.infoq.com/presentations/Do-You-Really-Get-Memory

JDK6 Garbage First(G1) Garbage Collecor
Like Other HotSpot GC’s, G1 is generational means it has concept of old objects and new objects. Big difference between G1 and other Garbage collector is that now there is no physical difference between young generation and old generation.
Whole heap is divided into multiple regions.
Each region is of same size.
Few set of regions belong to young generation and few set to old generation.
SO, young generation is a non-contiguous set of regions, and similar is old generation. G1 is flexible enough to move objects from new to old and vice versa any time.

Key idea it separates whole heap into regions( possibly 100MB each). It tries to monitor how full of garbage each of region is, how quickly objects are getting allocated, and tries to predict how much memory would be needed. For example, it predicts in next 1 minute 90MB of memory would be required, and there is a region(of size 100 MB), in which mostly is garbage(>90MB), so it only need to  perform GC over this particular region, and all memory requirements would be fulfilled. So run time of garbage collection is proportional to the heap size, but proportional to the amount of memory required.

Separate regions are called Cards, and it tracks dependencies between cards, i.e. which card is referring to which card. It maintains a small graph. On every assignment card graph is updated. So, we loose a bit of speed on assignment, which is a trade off, but truse me the difference in speed is very minimal.

In 2013 -
Oracle has announced that they would remove the PermGen from the Java 8 version of HotSpot JVM.