Alexey Ragozin

POF serialization, beware of arrays

2012-02-17T13:04:00.001Z

As you may have experienced yourself, object marshaling/serialization oftenlays on performance critical path in distributed system (especially in Java). Default Java serializationis almost always is a poor choice, countless alternatives was developed toreplace it. POF (portable object format) is binary object serialization formatwhich was developed by Oracle Coherence team with both cross platform andefficiency in mind (POF can be compared to Thrift or ProtoBuf). While being compact and efficient POF is also offeringadvanced features such as access to specific attributes of object withoutdeserializing whole thing.

But sometime avoiding deserialization may be more expensivethan deserialization itself. Below is a short story of my experience worthsharing.

Recently, I was working on Coherence based solution. After another set code changes, automatic test has shown sudden performance degradation. Oneof aspect of change set was replacing reflection based filters with ones using PofExtractor.Surprisingly, times of operations which were relying on affected filters haveincreased about 20 times! While PofExtractorsare not always faster compared to ReflectionExtractorsin my practice, 20 times slowdown seems to be totally unreasonable. Anyway, switch to PofExtractor was made to avoid classpath dependency, so switching back to ReflectionExtractor was not an option.

Profiling session have showing interesting results:

objects were never completely deserialezed (as expectedwith PofExtractor),
filter execution indeed was a bottleneck,
more targeted profiling have identified method PofHelper.skipUniformValue()as a hot spot.

While PofHelper.skipUniformValue()is expected to be heavy duty method (it is used to parse POF binary stream seeking attribute to be extracted), it was eatingunproportionally large amount of CPU. Instrumentation profiling have revealedone more fact - few thousands of calls to skipUniformValue()have been made for each call to PofExtractor.extractFromEntry().

Well, that could explain HOW code gets slow, but questions are WHY and how to fix it.

Object, I was working with in application, were mostly wrapperaround a chunk of data in proprietary encoded binary format. Few attributeswere extracted and stored as fields of java objects, but larges part of object wasa single chunk of binary data. This chunk were stored as byte[] in Java and written using writeByteArray() in POF stream. Thereis another method suitable for this task writeBinary(),but using writeByteArray() justfeels more convent. That was a key mistake.

POF array vs. binary

POF can encode numbers using variable length format, writeByteArray() encodes byte[] as an array of variable lengthobjects. Well actually they are all exactly one byte at length, but generic POFdecode still inspects each byte to calculate array length (and for each byte itwould be calling skipUniformValue()which is huge method with switch case for every possible POF data type) . Oncontrary, writeBinary()writesopaque blob, so parser just reads its size and skips it in single operation.

I have replaced writeByteArray()with writeBinary() (you may alsowant to replace read code, but it is not necessary readByteArray()can parse Binaryfrom stream and convert it byte[]for you). It have solved problem.

Below is comparison of extractor times with various amountsof binary data inside object, using 2 versions of serialization.

Please mind difference in scale between diagrams, it is an order ofmagnitude!

Summary

Ok, use writeBinary()will help you with byte arrays, but what if you need to store float[] or other array type?

If arrays are not large it is ok, but if they are, then youshould avoid use of PofExtractors,use normal extractors instead.

I hope this performance issue will be fixed eventually,
butuntil it is fixed,
beware of arrays in your POF objects!

Data Grid Pattern - Canary key set

2011-12-14T05:08:00.001Z

Most of modern in-memory-data-grid products have grown fromdistributed caching. For traditional cache, loss of data is not a big deal,missing data could always be recovered from backend storage via read through.Main focus of distributed cache is data coherence between nodes (preventingstale reads, etc).

Advanced patterns like all-in-memory and proactive cachingmay provide considerable benefits over traditional read through cache. Butsimple fall back to read-through as a strategy for data recovery may not be anoption for these advanced cache usages. Read-through have two prerequisite tobe implemented:

data should be accessed by primary key,
for given primary key, you should known itsmaster data source.

Both these prerequisite may be broken in advanced solution.Having all-data in memory will allow you to execute queries in cache layerinstead of backend database. Products like Oracle Coherence, GemStone GemFireand GigaSpaces have advanced queering capabilities (including non-primary indexessupport). Offloading queries from database is a huge win, but the price is thatyou cannot rely on read-through any more. If some data is missing in cache,queries will produce incomplete results without warning.

Second read-through prerequisite also may be sacrificed,i.e. by using multiple backends (cache acting as aggregator for data setscattered across multiple databases). You can more details in my previousarticle.

Data loss imminent

Please mention, that loss of data in modernin-memory-data-grid is an exceptional event. Data is usually protected bymultiple replicas and grid can tolerate server failure. But it still possibleand you cannot ignore this aspect as you cannot ignore e.g. backing up your database.

Through all reliability provided by data grid technologydata maybe lost and it means they will be lost eventually. Nextquestion, what is your desired strategy to cope with incomplete data set?

It depends on type of application.

For some applications, it is ok to haveincomplete results from application during recovery window.
For some application, incomplete response isworst than no response. Application should guaranty that every response iscomplete and if it cannot provide complete response (e.g. part of data set ismissing in cache) it should raise an error.

First strategy is rather simple,you should monitor your grid and automatically trigger recovery procedure if disastrousevent is detected.

Second type of strategy is moretricky in implementation. Just monitoring is not an option. There would be a gap between data loss eventand reaction of monitoring system (which e.g. can switch service to offlinemode for duration recovery process). Some application are totally intolerant toinconsistent data. This data, for example, could be used in complex batch of financialrisk calculations (running for few hours in large HPC grid) and single inconsistentpiece of input data could invalidate whole batch of work.

We need a solution better thanmonitoring for such kind of applications.

Canary keys to detect missing data

We must guaranty that result of each query is consistent(i.e. all data that has to be processed has been processed, often this means -whole dataset). Here we have a paradox at hands: we must check presence of certain key/value pairs (data grid is akey/value storage) in cache, but we cannot know keys of these pairs or even theirtotal number.

Solution to this paradox lies in base approach of datadistribution used by data grids. Technique described in this article has beenused by me with Oracle Coherence grid, but idea can also be applied to otherproducts using similar type of DHT. Oracle Coherence is using partitioneddistributed hash table (DHT). In practice this means that key/value pairs arenot distributed individually, but whole partition is assigned to particular node.It also means, that you cannot lose individual key/value pair but only wholepartition at once (if you lose all replicas of that partition at the same time).Number of partitions is fixed for live time of grid (changing that numberrequires rebuild of DHT).

How this could be helpful to ensure data completeness?

We may not be caring about presence of individual key/valuepairs, instead we may check presence of all partitions (and we know their exactIDs and total number). But how we can check presence of partition (technicallypartition cannot be missing, it will be just empty)? Also we should join datacompleteness check with queering of data in the same operation otherwise wewill always have a gap of uncertainty.

Canary keys is a trick to solve this problem. Canary keysare synthetic keys, you put just on key to each partition. Every partitionshould have a canary key. So if your grid is configured to have N partitions,it should contain exactly N canary keys. If number of canary keys is less thanN, that means portion of data has been lost (poor canary has perished) and isnot recovered yet. Of cause your data loading/recovery procedure should put canarykeys back in cache once data is restored.

It is also possible (though quite awkward to be honest) to integratecanary keys check in single request with data queering. In each query youshould select canary keys along with actual data you need to retrieve. Oncequery is executed you should check presence of all canaries and then strip themfrom result set. If all of them are there, you can be sure that your result setin complete and no SLA would be broken. If some canaries are missing, youshould trigger data recovery and/or raise an error indicating that requestcannot be completed until recovery is done.

Conclusion

Technique described in this article is very advanced. Mostapplications do not require such rigorous consistency checks for everyoperations. But few do, and for them this approach may be useful (still implementationmay have its quirks).

On high level canary keys technique demonstrate how understandingof core principles of DHT can helpsolving challenging task. Understanding of low level grid operations, their guarantiesand limitation is a cornerstone in engineering of complex data processingsolution using distributed ACID-less data grid as a storage.

Garbage collection in HotSpot JVM

2011-12-04T18:25:00.001Z

In this blog you may find few in-depth articles related togarbage collection in Oracle's HotSpot and other JVMs. But if you a novice infield of garbage collection, you may feel lost due to level of details. So I decidedthat high level overview of GC modes in HotSpot would add nicely to existingfairly detailed content.

Foreword

Java (and dominating majority of other modern languages)features automatic memory management aka garbage collection. Once instance of objectbecomes unreachable from executing program, it is classified as garbage and,eventually, its memory should be added to free pool.

One of simplest approaches to automatic memory management isreference counting. But it has serious limitation though, inability to handle cycliclinks in object graph.

If we want to find all effectively unreachable objects, the onlyway is to find all reachable viarecursive object graph traversing. It may sound like a complicated task and itreally is.

Garbage collection in modern JVMs including Oracle's HotSpotis a result of lengthy evolution. Huge amounts hard work was put into them, to make them asefficient as they is now. Of cause they may have limitations, deficiencies butin most time this due to tradeoffs which was made for reason. So, please thinktwice before blaming JVM garbage collector being slow or stupid. Most likelyyou just underestimating complexity of its work.

Ok, now, let me get straight to garbage collection in HotSpotJVM circa 2011.

HotSpot JVM circa 2011

HotSpot has several GC modes. Modes are controlled with JVMcommand line options. Default GC mode dependson JVM version, client/server mode of JVM and hardware you are running on (JVMdistinguish server and desktop grade hardware by set of heuristics).

Serial GC

JVM switch: -XX:+UseSerialGC

Serial GC is generational garage collection algorithm (ifyou wander what generation means, readthis article).

Actually all GC modes in HotSpot are usinggenerational approach, so won't repeat it for every GC mode.

Young collection is a copy collection. Old space iscollected using an implementation of mark/sweep/compact (MSC) algorithm. Both,young and old, collections require stop-the-world (STW) pause and, as namesuggests, are executed by single thread. During old space collection, all liveobjects are moved to beginning of space. This allows JVM to return unusedmemory to OS.

If you enable GC logging by -XX:+PrintGCDetails you will see followingindicators of GC pauses in log:

Young collection

41.614 [GC 41.614: [DefNew:130716K->7953K(138240K), 0.0525908 secs] 890546K->771614K(906240K),0.0527947 secs] [Times: user=0.05 sys=0.00, real=0.05 secs]

Full (young + old + perm) collection

41.908 [GC 41.908: [DefNew:130833K->130833K(138240K), 0.0000257 secs]41.909: [Tenured:763660K->648667K(768000K), 1.4323505 secs] 894494K->648667K(906240K),[Perm : 1850K->1850K(12288K)], 1.4326801 secs] [Times: user=1.42 sys=0.00,real=1.43 secs]

Parallel scavenge

JVM switch: -XX:+UseParallelGC

Some phases of garbage collection could be naturally parallelizedbetween multiple threads. Parallel processing can reduce time required for GCand thus STW pause duration by keeping multiple physical CPU cores busy. Adoptionof multiprocessor/multicore hardware have made parallelization of GC a must formodern VM.

Parallel scavenge GC mode is using parallel implementationof young collection algorithm. Old space is still collected by one thread. Thus,using this mode may shorten young collection pauses (which are more frequent),but still suffers from long full collection freezes.

Log output samples for parallel scavenge.

Young collection

59.821: [GC [PSYoungGen:147904K->4783K(148288K)] 907842K->769258K(916288K), 0.2382801 secs][Times: user=0.31 sys=0.00, real=0.24 secs]

Full collection

60.060: [Full GC [PSYoungGen:4783K->0K(148288K)] [PSOldGen: 764475K->660316K(768000K)]769258K->660316K(916288K) [PSPermGen: 1850K->1850K(12288K)], 1.2817061secs] [Times: user=1.26 sys=0.00, real=1.28 secs]

Parallel old GC

JVM switch: -XX:+UseParallelOldGC

This mode is a incremental improvement over parallelscavenge mode. It adds parallel processing (parallel mark-sweep-compact (MSC)algorithm) for old space collection. Young space is using same algorithm asmode above. Old space collection still requires quite long STW pause, but nowmultiple cores could be employed to make it shorter. Unlike serial MSC,parallel version does not create single continuous free memory region at theend of heap, so JVM cannot return memory to OS after full GC in this mode.

Log output samples for parallel old GC.

Young collection

65.411: [GC [PSYoungGen:147878K->5434K(144576K)] 908129K->770314K(912576K), 0.2734699 secs][Times: user=0.41 sys=0.00, real=0.27 secs]

Full collection

65.685: [Full GC [PSYoungGen:5434K->0K(144576K)] [ParOldGen: 764879K->623094K(768000K)]770314K->623094K(912576K) [PSPermGen: 1850K->1849K(12288K)], 2.5954844 secs][Times: user=3.95 sys=0.03, real=2.60 secs]

Adaptive size policy

JVM switch: -XX:+UseAdaptiveSizePolicy

This is a special mode of parallel scavenge collector inwhich it can dynamically adjust configuration of young space to adapt for anapplication. IMHO it does not bring much benefits. Never seriously tried to usethis option.

Concurrent mark sweep

JVM switch: -XX:+UseConcMarkSweepGC

While collectors above are generally called throughputcollectors. Concurrent mark sweep (CMS) is low pause collector. It is designedto minimize stop-the-world JVM pauses and thus keep application responsive. Foryoung space collection it may use either serial copy collector or parallel one(parallel alhorithm is similar to algorithm in parallel scavenge mode, but theyare two totally different code bases and they may use slightly differentconfiguration options, e.g. adaptive size policy is not implemented for CMS).

Old (and if enabled permanent) space a collected by mostlyconcurrently. As name suggests CMS ismark sweep algorithm (notice lack of compact in its name). CMS requires onlytwo short pauses during each old space collection cycle. But unlike itsstop-the-world counterparts, CMS cannot do compaction (relocate objects inmemory) and this makes it prone to fragmentation. CMS is using sometricks to fight fragmentation, but it is still a threat.

If concurrent collector fails to reclaim memory fast enoughto keep with application needs, JVM will fall back to serial stop-the-world mark-sweep-compact algorithm to defragment (and compact) old space (notice serial word,usually such pause would be 50-500 times longer than normal CMS pause).

Log output samples for CMS.

Young collection

613.154: [GC 13.154: [DefNew:130821K->8230K(138240K), 0.0507238 secs] 507428K->388797K(906240K),0.0509611 secs] [Times: user=0.06 sys=0.00, real=0.05 secs]

Concurrent old space collection

13.433: [GC [1 CMS-initial-mark:384529K(768000K)] 395044K(906240K), 0.0045952 secs] [Times: user=0.02 sys=0.00,real=0.01 secs]

13.438: [CMS-concurrent-mark-start]

...

14.345: [CMS-concurrent-mark:0.412/0.907 secs] [Times:user=1.20 sys=0.00, real=0.91 secs]

14.345:[CMS-concurrent-preclean-start]

14.366: [CMS-concurrent-preclean:0.020/0.021 secs] [Times:user=0.03 sys=0.00, real=0.02 secs]

14.366:[CMS-concurrent-abortable-preclean-start]

...

14.707:[CMS-concurrent-abortable-preclean: 0.064/0.340 secs] [Times: user=0.36 sys=0.02,real=0.34 secs]

14.707: [GC[YG occupancy: 77441 K(138240 K)]14.708: [Rescan (non-parallel) 14.708: [grey object rescan,0.0058016 secs]14.714: [root rescan, 0.0424011 secs], 0.0485593 secs]14.756:[weak refs processing, 0.0000109 secs] [1 CMS-remark: 404346K(768000K)]481787K(906240K), 0.0487607 secs] [Times: user=0.05 sys=0.00, real=0.05 secs]

14.756: [CMS-concurrent-sweep-start]

...

14.927: [CMS-concurrent-sweep:0.116/0.171 secs] [Times:user=0.23 sys=0.02, real=0.17 secs]

14.927: [CMS-concurrent-reset-start]

14.953: [CMS-concurrent-reset:0.026/0.026 secs] [Times:user=0.05 sys=0.00, real=0.03 secs]

Times marked with greenare times of concurrent phases – CMS do its work in parallel withapplication. You can find out more about CMS pauses here.

CMS failure and fallback to mark-sweep-compact

557.079: [GC 557.079: [DefNew557.097:[CMS-concurrent-abortable-preclean: 0.010/0.109 secs] [Times: user=0.12sys=0.00, real=0.11 secs]

(promotion failed) :130817K->130813K(138240K), 0.1401674 secs]557.219: [CMS (concurrent modefailure): 731771K->584338K(768000K), 2.4659665 secs]858916K->584338K(906240K), [CMS Perm : 1841K->1835K(12288K)], 2.6065527secs] [Times: user=2.48 sys=0.03, real=2.61 secs]

You can read more about failures here.

CMS incremental mode

JVM switch: -XX:+CMSIncrementalMode

CMS is using one of more back ground threads to do GC inparallel with application. These thread will compete with application threadsfor CPU cores. Incremental mode is limiting amount of CPU time consumed by backgroundGC thread. This helps to improveapplication responsiveness if you have just 1 or 2 physical cores. Of cause oldspace collection cycles would be longer and risk of full collection fall backhigher.

G1 garbage collector

JVM switch: -XX:+UseG1GC

G1 (garbage first) is a new garbage collection mode inHotSpot JVM. It was introduced in late versions of JDK6. G1 is low pausecollector implementing incrementalversion of mark-sweep-compact algorithm. G1 breaks heap into regions of fixedsize and can collects only subset (partial collection) of them during stop-the-world(STW) pause (unlike CMS, G1 have to do most of its work during STW).Incremental approach allow G1 to employ larger number of shorter pauses insteadof fewer number longer JVM freeze (cumulative amount of pauses will still bemuch higher compared to concurrent collector like CMS) . To be accurate, G1 alsoemploys background threads to do heap marking concurrently with application (similarto CMS), but most of work is still done during STW.

G1 is using copycollection algorithm for its partial collections. Thus each collection producesseveral completely empty regions which can be returned to OS.

G1 is also exploiting generational principle. Set of regionsis considered young space and treated accordingly.

G1 has a lot of hype as a garbage collection silver bullet, butI'm personally quite skeptical about it. Here are few reasons:

G1 have to maintain few additional data structures to makepartial GC possible, it taxes performance.
It is still doing most of heavy lifting during STW pauseunlike CMS which is mostly concurrent. That IMHO will hinder G1's ability toscale as well as CMS with growing heap sizes.
Large objects (comparable to region size) are problematicfor G1 (due to fragmentation).

G1 collections in logs:

G1 young collection

[GC pause (young), 0.00176242 secs]
   [Parallel Time:   1.6 ms]
      [GC Worker Start Time (ms): 15751.4 15751.4]
     [Update RS (ms): 0.1 0.3
       Avg:   0.2, Min:  0.1, Max:   0.3]
       [Processed Buffers : 2 1
          Sum: 3, Avg: 1, Min: 1, Max: 2]
      [Ext Root Scanning (ms): 1.0 0.9
       Avg:   0.9, Min:  0.9, Max:   1.0]
      [Mark Stack Scanning (ms): 0.0 0.0
       Avg:   0.0, Min:  0.0, Max:   0.0]
      [Scan RS (ms): 0.0 0.0
       Avg:   0.0, Min:  0.0, Max:   0.0]
      [Object Copy (ms): 0.3 0.3
       Avg:   0.3, Min:  0.3, Max:   0.3]
      [Termination (ms): 0.0 0.0
       Avg:   0.0, Min:  0.0, Max:   0.0]
         [Termination Attempts : 1 1
          Sum: 2, Avg: 1, Min: 1, Max: 1]
      [GC Worker End Time (ms): 15752.9 15752.9]
      [Other:  0.1 ms]
   [Clear CT:   0.0 ms]
   [Other:   0.1 ms]
      [Choose CSet:   0.0 ms]
   [ 18M->12M(26M)]
[Times: user=0.00 sys=0.02, real=0.00secs]

G1 partial collection

[GC pause (partial), 0.01589707 secs]
   [Parallel Time: 15.6 ms]
      [GC Worker Start Time (ms): 15774.1 15774.2]
     [Update RS (ms): 0.0 0.0
       Avg:   0.0, Min:  0.0, Max:   0.0]
       [Processed Buffers : 0 3
          Sum: 3, Avg: 1, Min: 0, Max: 3]
      [Ext Root Scanning (ms): 1.0 0.7
       Avg:   0.8, Min:  0.7, Max:   1.0]
      [Mark Stack Scanning (ms): 0.0 0.0
       Avg:   0.0, Min:  0.0, Max:   0.0]
      [Scan RS (ms): 0.0 0.1
       Avg:   0.0, Min:  0.0, Max:   0.1]
     [Object Copy (ms): 14.3 14.5
       Avg: 14.4, Min: 14.3, Max: 14.5]
      [Termination (ms): 0.0 0.0
       Avg:   0.0, Min:  0.0, Max:   0.0]
         [Termination Attempts : 3 3
          Sum: 6, Avg: 3, Min: 3, Max: 3]
      [GC Worker End Time (ms): 15789.5 15789.5]
      [Other:   0.4 ms]
   [Clear CT:   0.0 ms]
   [Other:   0.2 ms]
      [Choose CSet:   0.0 ms]
   [ 13M->12M(26M)]
[Times: user=0.03 sys=0.00, real=0.02secs]

G1 full collection (incremental mode failure)

32.940: [Full GC 772M->578M(900M),1.9597901 secs]
[Times: user=2.29 sys=0.08, real=1.96secs]

Train GC

Train GC was removed from HotSpot JVM long time ago. But dueto most articles about GC are fairly out dated you may find references to itsometimes. It is gone, period.

Permanent space

In case you are wondering. Permanent space is a part of oldspace use by JVM for internal data structures (mostly related to class loadingand JIT). Permanent space is not necessary cleaned on every old space collectioniteration and sometimes you may need to use additional switches to make JVMcollect unused data in PermGen. Normally data in permanent space are, well ...,immortal, but ability of JVM to unloadclasses makes things complicated.

Using co-segments to dynamically adapt Lucene for frequent queries

2011-11-21T06:03:00.001Z

Apache Lucene is magnificent library for working withinverted indexes. While full text search is its primary use case, you may oftenfind application of Lucene in other areas too. In particular, in data mining,it can be useful for categorizing large volumes of textual information (thinkabout finding trends in news feeds). Data mining is traditional domain formap/reduce style of distributed processing, but it you want to mine datainteractively, changing rules on fly,map/reduce is not an option. Inverted indexes are more suited for interactiveuse case and Lucene is excellent in that role.

Query complexity problem

Typically "patterns" to be mined (e.g. positivewords about certain movie or description matching certain camera model) arerepresented by fairly complex Lucene queries having large numbers ofsubqueries. Another problem is having termswith low selectivity in index which may be participate as a part of complex pattern (for full text search you usually canjust drop them out of index).

These two factors make mining job very hungry for CPU.

Reducing CPU load by adding "synthetic" terms and query rewriting

Different patterns usually share a lot of common subqueries.These subqueries themselves may be quite computation expensive (e.g. phrase andspan queries). Instead of evaluating each subquery each time for any patternquery, it is possible to precalculate them. First, "synthetic" terms,are added to index (I call them hintsfor short). These hints markdocuments matching particular subquery. Then all queries to be executed shouldbe rewritten with "synthetic" terms (hints) to let Lucene use that additional information.

Such optimization may increase query throughput per CPU bysubstantial factor. In my practice, for complex queries, CPU utilization can bereduced down by 3-10 times.

Though applying this technique not so easy. There fewproblems to be solved:

matching documents against set of queries togenerate synthetic terms,
adding synthetic terms to existing index,
rewrite queries to benefit from precalculatedinformation.

All of them are tricky. Normally to add new attribute todocument you have to rebuild whole Lucene index – which is heavy and resource intensive task. This is a very badsolution. It is critical to add new subqueries interactively along with usersexploring new patterns. Using this technique does not make sense if additionalsynthetic terms cannot be added to index relatively cheaply on the fly.

Generating co-segment

Straight forward approach to generate co-segment for anumber of subquery terms would be -testing these subquery for each document in index. Lucene has MemoryIndex which is quitehandy for that. It allows to create single-document index in memory and testany queries against it. So far so good, but then you realize that you have toload and parse each of documents, it turns out to be prohibitively slow (just2-5 times faster, than rebuild whole index).

There is a much, much better way. We may query main index,get all document ID matching subquery and encode this information intoco-segement.

Querying index is blazing fast (compared to scanning through documents).

Adding co-segments to existing index

Lucene index organized into segments, which are stored infile system. Each specific group of files (segment) is an inverted index forsubset of documents. Whole index may be divided into several segments. Inverted- means data in file is sorted by terms. This means that if all our syntheticterm would be "greater" than normal terms, we could just append themat end of existing index file (instead of rebuilding whole file). After second though, we do not need to doanything with real files at all. Making Lucene think that there are few moreterms in segment is enough (read - implement own Directory merging databehind scenes making Lucene to "see" segment + all co-segments assingle file).

Rewriting queries

Once we have "synthetic" terms or hints in index, we have to rewrite querysomehow. Queries can be very sophisticated (and they are, otherwise we wouldn'tneed all these tricks).

Simple idea is just to add hint clause and additional top level MUST condition. E.g. query Qwill be written to H & Q, there His condition for "synthetic" terms. This way we do not need to careof internal Q of and ensure correctness of rewrite.

Unfortunately, using BooleanQuery to joinoriginal query with hint clause will not produce any speed improvements. Actuallythe way queries are executed in Lucene is making whole idea of"hinting" very non-trivial for implementation.

Solution was writing own HintAwareQueryto wrap around "pattern" query (vanilla Lucene query). This wrapperdo all dirty work. First it analyzes existing hints and chooses ones to beused. Second, it optimizes execution of nested query making parts of searchindex, masked-out by chosen set of hints,"invisible" to query execution.

Conclusion

So, what was achieved?

Hints can be added/removed to "live"index in matter of seconds,
Transparent from application- just wrapeverything into HintAwareQuery,
Order of magnitude speed up for complex queries.

Thanks to Lucene flexibility, which made such optimizationever possible!

More ideas

So far, hints are created manually using requests statisticsfrom application search service. Interesting idea would be to automate thisprocess, let search service itself profile requests and create hints using own statistics.

Another idea is using index masking technique for optimizingqueries without hints - e.g. if MUST clauses of top level BooleanQuery could be usedinstead of "synthetic" hints if they are simple enough (e.g. assimple as TermQuery). Such trick couldbring comparable bust for vanilla BooleanQuery without anyneed of precalculation at all.

Coherence SIG: Advanced usage of indexes

2011-11-04T15:53:00.017Z

Another my presentation Coherence SIG, this time from London.
Main theme of presentation was internal mechanics of indexes in Coherence. How indexes are stored, how queries are executed, how create custom filters and indexes - all these topics were covered.

Java GC, HotSpot's CMS promotion buffers

2011-11-02T03:40:00.002Z

Recently, I have unfairly blamed promotion local allocation buffers (PLAB) forfragmentation of old space using concurrent mark sweep garbage collector. I wasvery wrong. In this article, I'm going to explain how PLABs really work withall details.

PLABs

PLAB stand for promotion local allocation buffer. PLABs areused during youngcollection. Young collection in CMS (and all other garbage collectors inHotSpot JVM) is a stop-the-world copy collection. CMS may use multiple threadsfor young collection, each of these threads may need to allocate space forobjects being copied either in survivor or old space. PLABs are required toavoid competition of threads for shared data structures managing free memory. Eachthread have one PLAB for survival space and one for old space. Free memory insurvivor space are continuous, so do survivor PLABs, which are simply continuousblocks. On other hand, free memory in old space (using CMS collector) isfragmented and managed via sophisticated dictionary or free chunks ...

Free list space(FLS)

CMS collector cannot compact old space (actually it can, butcompaction involves long stop-the-world pause, often referred as GC freeze). Memorymanager operates with lists of free chunks to manage fragmented free space. Asa counter measure from fragmentation, chunks of free space are grouped by size.В If available, free chunk of exact requiredsize will be used to serve allocation request. If chunks of given size areexhausted, memory manager will split larger chunk into several smaller tosatisfy demand. Consecutive free chunk can also be coalesced to create largerones (coalescence is made along with sweeping during concurrent GC cycle). Thissplitting/coalesce logic is controlled by complex heuristics and chunk demandper size statistics.

Old space PLABs

Naturally old space PLABs mimic structure of indexed freelist space. Each thread preallocates certain number of chunk of each size below257 heap words (large chunk allocated from global space). Number of chunks ofeach size to be preallocated is controlled by statistics. Following JVM flagwill enabled verbose reporting of old space PLAB sizing (too verbose forproduction though).

-XX:+PrintOldPLAB

At the beginning of each young collection we will seefollowing lines in GC log

6.347: [ParNew ...
...
0[10]: 722/5239/897
0[12]: 846/5922/987
0[14]: 666/5100/850
...
1[12]: 229/3296/987
1[14]: 2/2621/850
1[16]: 69/1812/564
1[18]: 247/1160/290
...
[10]: 905
[12]: 1002
[14]: 865
[16]: 567
...

First lines are statistics from each scavenger (young collector) threadin following format:

<tid>[<chunk size>]: <num_retire>/<num_blocks>/<blocks_to_claim>

tid - GC thread ID,

chunk size - chunk size in heap words,

num_retire - number of free chunks in PLAB at the end of young GC,

num_blocks - number of chunks allocated from FLS to PLABduring young GC,

blocks_to_claim - desired number of blocks to refill PLAB.

Next few lines show estimated number of chunks (per size) to bepreallocated (per GC thread) at beginning of next young collection.

[<chunk size>]: <blocks_to_claim>

Calculatingdesired block to claim

Initial number of blocks (chunks) per chunk size is configured via -XX:+CMSParPromoteBlocksToClaim JVM command line option(-XX:+OldPLABSize is alias for thisoption if CMS GC is used). If resizing of old PLAB is not disabled by -XX:-ResizeOldPLABoption, thendesired PLAB size will be adjusted after each young GC.

Ideal desired number per chunk size is calculated by following formula:

block_to_claim_ideal = MIN(-XX:CMSOldPLABMax, MAX(-XX:CMSOldPLABMin, num_blocks / (-XX:ParallelGCThreads • -XX:CMSOldPLABNumRefills)))

,but effective value is exponentially smoothed over time

blocks_to_claim_next = (1 - w) • blocks_to_claim_prev+ w • block_to_claim_ideal

,there w is configured via -XX:OldPLABWeight (0.5 by default).

On-the-flyPLAB resizing

During young collection, if chunk list of certain size will getexhausted, thread will refill it from global free space pool (allocating samenumber of chunks as at the beginning of collection). Normally thread will have torefill chunk list few times during collection (-XX:CMSOldPLABNumRefillssets desired number of refills). Though, if initial estimate was too small, GCthread will refill its chunk list too often (refill requires global lock formemory managed, so it may be slow). If on-the-fly PLAB resizing is enabled JVMwill try to detect such conditions as resize PLAB in the middle of youngcollection.

-XX:+CMSOldPLABResizeQuickerwill enable on-the-fly PLAB resizing (disabled by default).

Few more options offer additional tuning:

-XX:CMSOldPLABToleranceFactor=4 –tolerance of the phase-change detector for on-the-fly PLAB resizing during ascavenge.

-XX:CMSOldPLABReactivityFactor=2 –gain in the feedback loop for on-the-fly PLAB resizing В during a scavenge.

-XX:CMSOldPLABReactivityCeiling=10 –clamping of the gain in the feedback loop for on-the-fly PLAB resizing during ascavenge.

Conclusion

I have spent some time digging though OpenJDK code to makesure, that I'm getting that thing now. It was educating. This article hasbrought up and explained few more arcane JVM options,В though I doubt that I will ever use them inpractice. Problem with heap fragmentation is that you have to run applicationfor really long time before fragmentation will manifest itself. Most of optionsabove require trial and error path (even though -XX:+PrintOldPLABmight give you some insights about your application) . It much easier just togive damn JVM little more memory (hey, RAM is cheap nowadays) than spend daytuning arcane options.

Anyway, I hope it was as education for you as it was for me.

Data Grid Pattern - Time series index for managing versioned data

2011-10-31T19:40:00.002Z

Many critical application are using append only approach for dealing with transactional data. In other words, they never update data records, but instead insert new records with greater timestamp (or sequence number, or any other kind of version, they are using to find latest record). Common challenge for such data model, is how to retrieve an appropriate version of record (e.g. latest version, or version at certain moment in time). A simple query for latest version for key 'A' would translate into query as complex as

select * from versions where series='A' and version = (select max(version) from versions where key='A')

This query is already too complex for data grid (and even RDBMS would not be too happy).

Accidently Ben Stopford has recently published a great article about this problem, outlining a lot of important aspects. I do not want to repeat him here, I suggest you read his article now, then continue with mine, which complements his two approaches this third one using custom index in Coherence.

Using custom index for accessing versioned data

In this approach, each version is stored as a separate entry in cache.

Entry key is composite key, including logical key (series key) and some additional field to make version key unique (e.g. transaction ID, sequence number etc). Value contains actual business data (payload) and timestamp, we are using in our queries (technically timestamp could be part of composite key).

Series key should be an affinity key also - all versions related to same series should be physically on one Coherence node (or affinity key can be a part of series key, this will also satisfy this requirement).

Normally, if you want to find certain version by series key and timestamp you have to do aggregation of all versions for this series. In two approaches mentioned by Ben Stopford, latest version is separated from all other versions (using separate cache - approach 1, using marker - approach 2). It solves problem of finding latest version, but doesn't help if we need to find version for certain moment at time.

Time series index structure

Normal Coherence indexes cannot help us much, due to complexity of query, but it is possible to create custom index, tailored specifically for this task.

Time series index is similar to traditional inverted index, but instead of storing set of entry references, it is storing a nested index, indexing only versions belonging to certain series by timestamp. Using this index structure you could find latest version or version for certain moment in time, without any aggregation, just by index lookup.

This index goes beyond standard index Coherence API, so it requires a complementary implementation of custom filter.

PROs and CONs

Below and PROs and CONs of this approach, compared to approaches from Ben's article.

PRO

Inserting new version doesn't require modifications of any other versions. In particular, you do not need to use hack, directly accessing to backing map, and you do not create extra replication traffic.
Time series index works efficiently for any point in time, not only latest versions.
It can be used with any kind of caches (even with continuous queries).

CON

Through custom index usage is straightforward, troubleshooting could be very tricky unless you understand index mechanics very well.

Source code

Time series index implementation is available at GridKit project on Google code.

Java, How to throw undeclared checked exception

2011-10-27T15:07:00.001+01:00

Usually when you have caught checked exception (e.g. IOException or Interrupted) you have to wrap it in RuntimeException to rethrow it without declaring exception in method signature. But with help of generic you can now easily break java rules and throw say IOException exception from a method which has no throws declaration.

Code below will allow to throw anything anywhere.

public class AnyThrow {

public static void throwUncheked(Throwable e) {

AnyThrow.<RuntimeException>throwAny(e);

}

@SuppressWarnings("unchecked")

private static <E extends Throwable> void throwAny(Throwable e) throws E {

throw (E)e;

}

I would say, it is very sad outcome from Java implementation of generics. While benefits from checked exception are arguable, they have provided some rules you were able rely upon. But not any more, thanks to generics.

But it is that it is :)

Data Grid Pattern - Proactive caching

2011-10-25T07:54:00.001+01:00

Classic and most widely used approach for caching is read through pattern. Look up in cache, then try to load from primary data source if entry is missing in cache - that is how it works. This pattern is easy to implement but it has few unpleasant limitations:

caching may reduce average response time, but maximum response time is still bound to back end data source response time,

cache may have stale data, expiry policy may relive this problem to some extent, but aggressive expiry is drastically reducing performance gain from caching.

All in memory pattern

Caching concept is close relative to memory hierarchy principle. Memory hierarchy is one of cornerstones of Von Neumann architecture relies on fact that we have different kinds (in terms of capacity and performance) of memory in system. With modern hardware dynamic memory capacity is often large enough to keep whole dataset. All-in-memory is term used to describe caching architecture there you have 100% of your data in cache at all times. Having all data in cache allow you to guaranty that no request will have to hit slow backend data source and thus provide more aggressive SLA for max response time. It also may be required for workloads with highly random access to data, there traditional assumptions like 80/20 are not working.

While all-in-memory approach is definitely win in terms of performance, its implementation has few serious challenges:

cache should have enough capacity to hold 100% of our data,
cache should be fault tolerant (losing a portion of data in cache will render it defunct until missing data would be reloaded),
preloading procedure is often non-trivial due to scale of data set,
cache should be kept in sync with backend data source.

Capacity and fault tolerance are provided by modern distributed caches out of box, but preloading procedures and cache update strategy are very application specific and fairly challenging to implement.

Below are few practical approaches for keeping cache in synch with primary data source.

Refresh ahead

This is approach similar to expiry policy, but instead of invalidating data, cache proactively refreshing them from master source. Refresh ahead pattern is quite simple, but not very practical though. If cached data set is large (and we are talking about all-in-memory pattern) automatic refreshing is like to overwhelm backend with requests. And even if data set is reasonably small we still have to use fairly long expiry time to make it practical.

So if you looking for all-in-memory cache, refresh ahead are unlikely to help you.

Proactive caching

In contrast with traditional (I would say reactive) caching, with proactive caching pattern you insert/update value in cache as soon as it is updated in backend data source, not at the moment data was requested from cache.

Proactive caching is not necessary should be used with all-in-memory pattern, but combination of these two is very powerful.

Polling updates from DB

An evolutionary step from refresh ahead to proactive caching, would be polling changes for database. Some daemon component should periodically (and frequently) poll database and fetch changes since last cache update. Sounds simple but you have to come out with a way how to "fetch changes since last cache update". Usually some kind of timestamp is used - each record in table to be cached has a kind of last modified field. Another few challenges:

· what if cache is representing a query result, not just a single table,

· 'last modified' field should be indexed, otherwise frequent polls will bring database to its knees,

· polling daemon should be fault tolerant,

· cache timestamp should be stored somewhere on cache side.

So, implementing this approach will require some amount of work (on both sides, database and cache), but in the end you will have very robust solution.

Only sever limitation of this approach is lag between changes in database and cache, which is no less than poll period.

Long poll

If database has some means for wait/notification in its query language, you can use long poll pattern.

Using long poll will reduce load on your database server and probably reduce lag between cache and database. Disadvantages of this approach: more code on database side and need to use dedicated thread(s) for polling (because thread will be blocked waiting notification of database side for most time).

In Oracle database long poll could be implemented using DBMS_ALERT package. Though use of DBMS_ALERT may cause serialization of update transaction and harms database performance.

Database notifications

Some databases can push data change notifications directly to clients, without need for polling. E.g. Oracle database has DCN (data change notification) mechanism. Using DCN you can register callbacks which would be notified that certain data have been changed in database. Notification mechanism has few advantages over polling

less load of database while no data is actually changing,
smaller lag between changing data in database are reaction in cache.

Notifications approach have disadvantages also

API usually more complicated, you have to learn more quirks to make it work,
connection hang problems - application is listening to event on connection which is defunct for some reason,
notifications may be lost in transition for some reason.

One particular problem with using Oracle DCN in java, was leaking of subscriptions. DCN subscription is remaining active on database side after termination java process (unless it was deregistered explicitly) and eventually you are going to hit limit for active subscriptions. Of cause you should deregister subscription before terminating of client process, but you cannot always guaranty graceful shutdown in practice.

Hooking into database replication

All mature databases have replication feature and thus replication wire protocol. Sometimes, they also provide API to hook into replication channel and programmatically receive all updates (essentially change notifications).

Replication is implemented differently in various databases (or even with different replication solution for same database). But general idea is to make cache act as replication slave for its source database.

Compared to polling or data change notifications, using of replication usually requires more effort from DBA side (they should setup replication slave of master database). It may also cost you some in licensing fees dependent on your replication solution.

MySQL slave protocol does not require any setup on master, so replication links can be created ad hoc. But MySQL has another catch, you should setup row based replication on master database unless you want to parse and execute SQL statements in your cache.

Single cache in front of multiple sources

In large scale system, primary data source may be distrusted itself (e.g. using sharded database). Having single read through cache may be a problem in this case (doing read through, you have to know which shard to consult about data missing in cache), but with proactive caching such setup it much straightforward. While in read through caching, cache responsibilities of serving requests and acquiring data are coupled. With proactive caching, responsibilities of storing data/serving read requests and feeding cache with data updates may be separated. This way, you can have single cache instance and multiple other components pushing data into it (e.g. each sharing could push its data in single cache).

In this role cache can be though as a kind "materialized view" based up on data in primary (potentially distributed) data source.

Few more links

· Coherence SIG: Using Oracle Coherence to Enable Database Partitioning and DC Level Fault Tolerance

Using Database Change Notification (DCN) with a Coherence Cache

CMS heap fragmentation. Follow up 1

2011-10-20T09:38:00.000+01:00

I have recently published an article Java GC, HotSpot's CMS and heap fragmentation. Post has lead to a number of interesting discussions and here I want to present some hard numbers from my experiments to back up these discussions.

Experiment details

Application

Test application is a synthetic application. It is allocating byte arrays of random size and eventually releasing them (with fairly complex pattern). Though application is rather simple, it shows heap space fragmentation symptoms similar to symptoms of real application. Application has 2 threads which are consuming 100% of CPU core time each. Object allocation sequence is deterministic, so I use number of young collections as time axis on diagrams.

JVM settings

64bit HotSpot JVM was used in experiments. Base line configuration is below

-server
-Xmx1700m -Xms1700m -Xmn300m
-XX:+PrintGCDetails
-XX:+PrintGCTimeStamps
-XX:+UseConcMarkSweepGC
-XX:-UseCompressedOops
-XX:+PrintPromotionFailure
-XX:CMSInitiatingOccupancyFraction=30
-XX:+UseCMSInitiatingOccupancyOnly
-XX:ParallelGCThreads=2
-XX:ConcGCThreads=1
-XX:PrintFLSStatistics=1

JVM process was limited to 2 cores (using taskset) to simulate high CPU load (real application is consuming all cores at pick loads, but for test application I would like to stick with single thread to keep its behavior deterministic and reproducible).

Live data set of application is about 1GiB (which leaves about 400MiB in old space as head room for CMS collector). These numbers are scaled down from real application setup.

For test runs with reduced old PLAB size, following options were added to JVM

-XX:OldPLABSize=16
-XX:-ResizeOldPLAB

Diagrams

Diagrams are showing max chunk size and total amount of free memory in old space on Y axis (in heap words, heap word = 8 bytes). X axis a showing number of young collections since start of JVM.

Fragmentation in different HotSpot revisions

As you can see something is really broken in HotSpot 6u24. Upgrading to version of 6u25 or above should be a good idea. See CR-6999988 for more details.

Anyway, in both revisions, reducing old PLAB size is considerably reducing fragmentation.

Adding more memory

Let's see how adding more memory to JVM will affect fragmentation. In next experiment heap size is increased by 200 MiB without increasing of live data set.

As you can see increasing CMS headroom drastically decreases fragmentation (though max available chunk size continues to decrease over time).

Adding more CPU cores

As I said before test application consumes all available cores and concurrent GC thread have to compete for CPU cycles with application. In this test, I have increased number of cores available to JVM process to three. No other parameters of experiment have been changed.

Results are little surprising. Even though average amount of free memory in lower for 3 core test vs. 2 core test , fragmentation issue goes away!

In other words, if your application is starving on CPU in may lead to increased fragmentation of CMS space and eventual Full GC freeze, even though amount of free memory reported in GC logs and via JMX does not show any indication of problem.

I really wish CMS free list space statistics would be exposed via JMX. Now I have to reconsider my baseline JVM health monitoring approach for production environments :)

Conclusions

HotSpot prior to 6u25 have severe issue leading to increased fragmentation.

Increasing CMS headroom (lag between live data set and old space size) is drastically reducing fragmentation.

CPU shortage may leading to fragmentation of memory, this problem cannot be detected by normal monitoring (only by parsing GC logs with options above).

Limiting OldPLABSize shows less fragmentation compared with default PLAB settings in all experiments (though it has negative performance impact).

Though synthetic CMS fragmentation tests have produced some interesting data it is still just a synthetic test. Real systems are much less predictable and not so easy to test unfortunately.
So, my main advice to everyone having to deal with GC issues - use thoughtful monitoring in your production environment.

Java GC, HotSpot's CMS and heap fragmentation

2011-10-12T23:04:00.008+01:00

Concurrent Mark Sweep (CMS) is one of garbage collection algorithms implemented in HotSpot JVM. CMS is designed to be mostly concurrent, requiring just two quick stop-the-world pauses per old space garbage collection cycle. But if CMS cannot keep up with allocation of memory by application, it may fallback to stop-the-world whole heap collection - infamous Full GC pause. Full GC is very noticeable application pause, on large heaps it can take several dozens of seconds to collect and compact whole heap.

There are two different failure scenarios for CMS collection (both of them are leading to longer than usual stop-the-world pauses):

concurrent mode failure,
promotion failure.

Concurrent mode failure

At beginning of each young GC, collector should ensure that there is enough free memory in old space to promote aged objects from young space. Modern CMS collector estimates size of objects to be promoted using statistics from previous collections. If old space does not have enough free bytes to hold estimated promotion amount, concurrent mode failure will be raise. Concurrent mode failure doesn't necessary lead to Full GC, in certain cases JVM will just wait for concurrent collection cycle to finish, but application will remain in STW pause until young collection will be finished.

Most frequent reason for concurrent mode failure is late initiation of CMS cycle. JVM tries to estimate amount of garbage in heap and duration of CMS cycle and start it as late as possible to avoid wasting of CPU. Unfortunately this estimation may be too optimistic. You can advise JVM to start CMS earlier using following flags:

-XX:CMSInitiatingOccupancyFraction=30
-XX:+UseCMSInitiatingOccupancyOnly

Setting above will force CMS cycle is more than 30% of old space is use. Second option disables JVM heuristics, without second parameter JVM may not obey CMS initiating occupancy fraction setting.

Normally for server type applications you would like CMS to be running continuously. If you are experiencing concurrent mode failure, even though next CMS cycle is starting right after previous, it means that CMS throughput is just not enough. In this case you should increase size of old generation and give CMS collector more head room to do its job. Alternatively you may try to dedicate more CPU cores for concurrent collector, but CPU is usually even more limited resource on modern servers than memory.

In summary, there are two reasons for concurrent mode failure STW pause mentioned above, both of them can be remedied fairly easily with JVM options.

Promotion failure

Promotion failure is more complicated situation. CMS collector is not compacting free memory in old space, instead it have to deal with fragmented free space (a set of free memory chunks). It is possible, that all free bytes are scattered though small chunks, and it is impossible to find certain amount of continuous memory to promote particular large object, even though total number of free bytes is large enough.

Heap fragmentation is well known problem, and there are few effective techniques reducing fragmentation.

CMS memory manager is using separate free lists for different size of chunks. Using these free lists, it can effectively fill small holes in fragmented memory space with objects of exact size. This technique is known to be fairly effective (and widely used in C/C++ memory managers). But, surprisingly, it doesn't seems to work well for JVM in many real live situations.

What is wrong with a way JVM allocating memory in old space?

PLABs

Update: According to comment below, I'm be very wrong here. Please read comment from Ramki and give me some time to grok this staff and rewrite section.
Also take a look at next articale which have some numbers to back me up
CMS heap fragmentation. Follow up 1

Update 2: I have written another article specifically explaining PLABs in CMS. See Java GC, HotSpot's CMS promotion buffers

Section below describes old PLAB logic, which is still present in code base, but not used any more.

Let me make a step aside and explain some details of JVM memory management. You may know that JVM is using TLABs (thread local allocation block) to avoid concurrent allocation from single memory source over multiple threads. Same idea is also used for parallel young space collector. Collecting threads are copying live objects (young collection is a copy collection) and they need to allocate memory for objects being copied. To avoid CPU cache contention (due to synchronization of caches between CPUs) each thread have two, one for young space and one for old space, PLABs (parallel or promotion local allocation buffer) of its own. Using PLAB in young space is totally make sense, free memory is always continuous there, but using PLAB for old space in practice makes a huge contribution to fragmentation.

Let me illustrate this by example.

Each collector thread is allocating chunk of continuous memory in old space. Then, during collection, these chunks are filled with objects of different size (large objects will be allocated directly in old space, but small objects will be placed in PLAB).

Once young collection is finished, our PLABs are full with objects. Then, after some time, CMS cycle takes place and sweeper mark few dead objects as free space, creating small free memory chunks.

But on next young collection, instead of reusing small chunks of memory, each GC thread will allocate new large continuous block and will fill it with small objects.

Effectively, due to using PLABs, free lists are not used for small objects and small chunks will never be reused (until JVM could coalesce them into larger chunks). In practice, in our applications, we have a lot of small objects which can live long enough to die in old space. Strings and hash map entries are just to name few such cases.

Ironically, while CMS has sophisticated free list machinery, it makes it inefficient by using PLABs.

Important: There is bug in JDK prior 6u25, which makes fragmentation even worse. See CR-6999988 for more details.

Can we workaround this issue?

Yes, we can reduce size of PLAB improving reuse of small chunks.

-XX:OldPLABSize=16
-XX:-ResizeOldPLAB

Options above will force JVM to use PLAB as small as 16 heap words (heap word = 4 bytes in 32 bit JVM or 64 bit JVM with compressed pointers enabled, 8 bytes otherwise).

My experiments have shown drastic reduction of heap fragmentation in few application with known promotion failure problems. Though options above will help you reduce fragmentation, I would recommend to use them only if you HAVE problems with fragmentation. Using PLAB is important from multi core prospective and such soft disabling of PLAB may have serious impact on young collection pause time.

Remainder: Section above was based on my missunderstaning of PLABs. Correct description can be found here.
Next section is ok :)

How to diagnose problems with fragmentation?

Monitoring heap fragmentation

Below are options, that will help you diagnose and monitor problem with CMS heap fragmentation.

-XX:+PrintGCDetails
-XX:+PrintPromotionFailure
-XX:PrintFLSStatistics=1

PrintGCDetails is MUST HAVE base line GC diagnostic option. PrintPromotionFailure will print few more details about promotion failures (see example below).

592.079: [ParNew (0: promotion failure size = 2698) (promotion failed): 135865K->134943K(138240K), 0.1433555 secs]

PrintFLSStatistics=1 will print free list statistics each young or old collection (see example below).

Statistics for BinaryTreeDictionary:
------------------------------------
Total Free Space: 40115394
Max Chunk Size: 38808526
Number of Blocks: 1360
Av. Block Size: 29496
Tree Height: 22

Most important parameter of FLS (free list space) statistics is max chunk size. If size of max chunk decreasing over time, that means increasing fragmentation of heap and risk of promotion failure.

Conclusion

Let me summarize, how to reduce risk of concurrent mode and promotion failures using CMS collector.

1. Provide CMS enough head room, more free space – less risk of fragmentation. Remember any garbage collector need some extra space to work efficiently.

2. Let CMS run continuously using initiating occupancy settings (you may want reduce number of concurrent threads though).

3. If you still having problems – reduce old PLAB size.

4. Avoid spurious allocation of very large objects in application (resize of large hash table is a good example). Regular allocation of large objects is ok, though.

Coherence write behind, finding not-yet-stored entries

2011-10-07T11:52:00.003+01:00

Write behind strategy may be very useful in certain cases. Using Coherence you can use this pattern in very smart way - synchronously replicate your data in memory over several nodes, then asynchronously write to slow external storage. This way you will not lose any data in case of single server outage. One unpleasant thing is that Coherence does not retain sequence of updates in certain cases, but wait, this is a distributed system after all :)

But there is a catch. Let's assume you are receiving message via JMS, put data to Coherence grid, start processing etc. But you do not want to acknowledge message until it is written to persistent storage.

While Coherence let your data survive single node failure, there could be network failure, logical bug in your system or outage of persistent storage your are writing to. You want to be consistent, you can process message, but you do not want to confirm its delivery (delete it from one persistent storage) until it is not written into another persistent storage.

So, is it possible to find which entries in cache are not persisted yet?

Yes, it is. Internally Coherence marks not-yet-stored entries with special flag. This flag is usually invisible for application, but we can access it using some low level Coherence API.

Below is StoreFlagExtractor returning FALSE for vulnerable entries.

public class StoreFlagExtractor extends AbstractExtractor implements PortableObject {

private static final long serialVersionUID = 20010915L;

public StoreFlagExtractor() {

}

@Override

public int compare(Object object1, Object object2) {

// make no sense

throw new UnsupportedOperationException();

}

@Override

public int compareEntries(com.tangosol.util.QueryMap.Entry entry1, com.tangosol.util.QueryMap.Entry entry2) {

// make no sense

throw new UnsupportedOperationException();

}

@Override

public Object extract(Object object) {

// decorator can be extracted only from binary entry

throw new UnsupportedOperationException();

}

@Override

@SuppressWarnings("rawtypes")

public Object extractFromEntry(java.util.Map.Entry entry) {

BinaryEntry binEntry = (BinaryEntry) entry;

Binary binValue = binEntry.getBinaryValue();

return extractInternal(binValue, binEntry);

}

@Override

public Object extractOriginalFromEntry(com.tangosol.util.MapTrigger.Entry entry) {

BinaryEntry binEntry = (BinaryEntry) entry;

Binary binValue = binEntry.getOriginalBinaryValue();

return extractInternal(binValue, binEntry);

}

private Object extractInternal(Binary binValue, BinaryEntry entry) {

if (ExternalizableHelper.isDecorated(binValue)) {

Binary store = ExternalizableHelper.getDecoration(binValue, ExternalizableHelper.DECO_STORE);

if (store != null) {

Object st = ExternalizableHelper.fromBinary(store, entry.getSerializer());

return st;

}

return Boolean.TRUE;

}

@Override

public void readExternal(PofReader paramPofReader) throws IOException {

// do nothing

}

@Override

public void writeExternal(PofWriter paramPofWriter) throws IOException {

// do nothing

}

~~Using this extractor you can easily query unstored entries, set listeners and even build indexes and CQ for such entries.~~
UPDATE: Changes of STORE decoration are not triggering cache events (only backing map events) and index updates. Nor CQ nor indexes nor listener would not work.

Tech talk on Highload++ Moscow, Secret of garbage collection in Java

2011-10-04T19:06:00.000+01:00

Today I was speaking at Highload++ conference at Moscow.
Below is slide deck in russian.

TechTalk: Garbage collection in Java, Mocow, Oct 13

2011-10-03T05:57:00.003+01:00

If you happen to be in Moscow, I'm glad to invite you on my tech talk about GC tunning in JVM.
Event will occur 13 Oct at 19:00, language is russian.

UPDATE
Below are slides from event (in english).

HotSpot JVM garbage collection options cheat sheet (v2)

2011-09-08T12:00:00.002+01:00

In this article I have collected a list of options related to GC tuning in JVM. This is not a comprehensive list, I have only collected options which I use in practice (or at least understand why I may want to use them).

Compared to previous version a few useful diagnostic options was added. Additionally section for G1 specific options was introduced.

PDF version

HotSpot GC collectors

HotSpot JVM may use one of 6 combinations of garbage collection algorithms listed below.

Young collector	Old collector	JVM option
Serial (DefNew)	Serial Mark-Sweep-Compact	`-XX:+UseSerialGC`
Parallel scavenge (PSYoungGen)	Serial Mark-Sweep-Compact (PSOldGen)	`-XX:+UseParallelGC`
Parallel scavenge (PSYoungGen)	Parallel Mark-Sweep-Compact (ParOldGen)	`-XX:+UseParallelOldGC`
Serial (DefNew)	Concurrent Mark Sweep	`-XX:+UseConcMarkSweepGC -XX:-UseParNewGC`
Parallel (ParNew)	Concurrent Mark Sweep	`-XX:+UseConcMarkSweepGC -XX:+UseParNewGC`
G1		`-XX:+UseG1GC`

GC logging options

Please note that many of logging options could be modified on running JVM using JMX (e.g. via JConsole).

JVM option	Description
General options
-verbose:gc or -XX:+PrintGC	Print basic GC info
-XX:+PrintGCDetails	Print more elaborated GC info
-XX:+PrintGCTimeStamps	Print timestamps for each GC event (seconds count from start of JVM)
-XX:+PrintGCDateStamps	Print date stamps at garbage collection events (e.g. 2011-09-08T14:20:29.557+0400: [GC... )
-XX:+PrintGC\ TaskTimeStamps	Print timestamps for individual GC worker thread tasks (very verbose)
-Xloggc:	Redirects GC output to a file instead of console
-XX:+Print\ TenuringDistribution	Print detailed demography of young space after each collection
-XX:+PrintTLAB	Print TLAB allocation statistics
-XX:+PrintReferenceGC	Print times for weak/soft/JNI/etc reference processing during STW pause
-XX:+PrintJNIGCStalls	Reports if GC is waiting for native code to unpin object in memory
-XX:+PrintGC\ ApplicationStoppedTime	Print pause summary after each stop-the-world pause
-XX:+PrintGC\ ApplicationConcurrentTime	Print time for each concurrent phase of GC
-XX:+Print\ ClassHistogramAfterFullGC	Prints class histogram after full GC
-XX:+Print\ ClassHistogramBeforeFullGC	Prints class histogram before full GC
-XX:+HeapDump\ AfterFullGC	Creates heap dump file after full GC
-XX:+HeapDump\ BeforeFullGC	Creates heap dump file before full GC
-XX:+HeapDump\ OnOutOfMemoryError	Creates heap dump in out-of-memory condition
-XX:HeapDumpPath=<path>	Specifies path to save heap dumps
CMS specific options
`-XX:PrintCMSStatistics=2`	Print additional CMS statistics if n >= 1
`-XX:+Print\` `CMSInitiationStatistics`	Print CMS initiation details
`-XX:PrintFLSStatistics=2`	Print additional info concerning free lists
`-XX:PrintFLSCensus=2`	Print additional info concerning free lists
`-XX:+PrintPromotionFailure`	Print additional diagnostic information following promotion failure
`-XX:+CMSDumpAt\` `PromotionFailure`	Dump useful information about the state of the CMS old generation upon a promotion failure.
`-XX:+CMSPrint\` `ChunksInDump`	In a CMS dump enabled by option above, include more detailed information about the free chunks.
`-XX:+CMSPrint\` `ObjectsInDump`	In a CMS dump enabled by option above, include more detailed information about the allocated objects.

JVM sizing options

JVM option	Description
-Xms2048m -Xmx2g or ‑XX:InitialHeapSize=2g ‑XX:MaxHeapSize=2g	Initial and max size of heap space (young space + tenured space). Permanent space does not count to this size.
-XX:NewSize=64m -XX:MaxNewSize=64m	Initial and max size of young space.
-XX:NewRatio=3	Alternative way to specify young space size. Sets ration of young vs tenured space (e.g. -XX:NewRatio=2 means that young space will be 2 time smaller than tenuted space).
`-XX:SurvivorRatio=15`	Sets size of single survivor space as a portion of Eden space size (e.g. -XX:NewSize=64m -XX:SurvivorRatio=6 means that each survivor space will be 8m and eden will be 48m).
`-XX:PermSize=256m` `-XX:MaxPermSize=256m`	Initial and max size of permanent space.
`-Xss256k` or `-XX:ThreadStackSize=256k`	Sets size of stack area dedicated to each thread. Thread stacks do not count to heap size.
`-XX:MaxDirectMemorySize=2g`	Maximum size of off-heap memory available for JVM

Young collection tuning

JVM option	Description
-XX:Initial\ TenuringThreshold=8	Initial value for tenuring threshold (number of collections before object will be promoted to tenured space).
-XX:Max\ TenuringThreshold=15	Max value for tenuring threshold.
-XX:Pretenure\ SizeThreshold=2m	Max object size allowed to be allocated in young space (large objects will be allocated directly in old space). Thread local allocation bypasses this check so if TLAB is large enough object exciding size threshold still may be allocated in young.
-XX:+AlwaysTenure	Promote all objects surviving young collection immediately to tenured space (equivalent of -XX:MaxTenuringThreshold=0)
-XX:+NeverTenure	Objects from young space will never get promoted to tenured space while survivor space is large enough to keep them.
Thread local allocation blocks
-XX:+UseTLAB	Use thread local allocation blocks in young space. Enabled by default.
-XX:+ResizeTLAB	Allow JVM to adaptively resize TLAB for threads.
-XX:TLABSize=1m	Initial size of TLAB for thread
-XX:MinTLABSize=64k	Minimal allowed size of TLAB

CMS tuning options

JVM option	Description
Controlling initial mark phase
-XX:+UseCMSInitiating\ OccupancyOnly	Only use occupancy as a criterion for starting a CMS collection.
-XX:CMSInitiating\ OccupancyFraction=70	Percentage CMS generation occupancy to start a CMS collection cycle. A negative value means that CMSTriggerRatio is used.
-XX:CMSBootstrap\ Occupancy=10	Percentage CMS generation occupancy at which to initiate CMS collection for bootstrapping collection stats.
-XX:CMSTriggerRatio=70	Percentage of MinHeapFreeRatio in CMS generation that is allocated before a CMS collection cycle commences.
-XX:CMSTriggerPermRatio=90	Percentage of MinHeapFreeRatio in the CMS perm generation that is allocated before a CMS collection cycle commences, that also collects the perm generation.
-XX:CMSWaitDuration=2000	Once CMS collection is triggered, it will wait for next young collection to perform initial mark right after. This parameter specifies how long CMS can wait for young collection.
Controlling remark phase
-XX:+CMSParallel\ RemarkEnabled	Whether parallel remark enabled (only if ParNewGC), enabled by default
-XX:+CMSParallel\ SurvivorRemarkEnabled	Whether parallel remark of survivor space enabled (effective only with option above), enabled by default
-XX:+CMSScavengeBeforeRemark	Force young collection before remark phase.
-XX:+CMSScheduleRemark\ EdenSizeThreshold	If Eden used is below this value, don't try to schedule remark
-XX:CMSScheduleRemark\ EdenPenetration=20	The Eden occupancy % at which to try and schedule remark pause
-XX:CMSScheduleRemark\ SamplingRatio=4	Start sampling Eden top at least before young generation occupancy reaches 1/ of the size at which we plan to schedule remark
-XX:CMSRemarkVerifyVariant=1	Choose variant (1,2) of verification following remark
Parallel execution
-XX:+UseParNewGC	Use parallel algorithm for young space collection.
-XX:+CMSConcurrentMTEnabled	Use multiple threads for concurrent phases.
-XX:ConcGCThreads=2	Number of parallel threads used for concurrent phase.
-XX:ParallelGCThreads=2	Number of parallel threads used for stop-the-world phases.
CMS incremental mode
-XX:+CMSIncrementalMode	Enable incremental CMS mode. Incremental mode is meant for severs with small number of CPU. Do not use it on modern hardware.
Miscellaneous options
-XX:+CMSClassUnloadingEnabled	If not enabled, CMS will not clean permanent space. You should always enable it in multiple class loader environments such as JEE or OSGi.
-XX:+ExplicitGCInvokes\ Concurrent	Let System.gc() trigger concurrent collection instead of full GC.
‑XX:+ExplicitGCInvokes\ ConcurrentAndUnloadsClasses	Same as above but also triggers permanent space collection.

Miscellaneous GC options

JVM option	Description
-XX:+DisableExplicitGC	JVM will ignore application calls to System.gc()
-XX:SoftRefLRU\ PolicyMSPerMB=1000	Soft references time to live in milliseconds per MB of free space in the heap
OutOfMemoryError conditions
-XX:+UseGCOverheadLimit	Use policy to limit of proportion of time spent in GC before an OutOfMemory error is thrown
-XX:GCTimeLimit=98	Limit of proportion of time spent in GC before an OutOfMemory error is thrown (used with GCHeapFreeLimit)
-XX:GCHeapFreeLimit=2	Minimum percentage of free space after a full GC before an OutOfMemoryError is thrown (used with GCTimeLimit)

G1 (garbage first) GC options

G1 is still evolving, so table below have known supported JVM version column

JVM option	JVM	Description
-XX:G1HeapRegionSize=8m	6u26	Size of heap region for G1 collector. Region size could be from 1MiB to 32MiB. Default is initial heap size / 2048.
-XX:G1ConfidencePercent=50	6u26	Confidence coefficient for G1 pause prediction heuristics
-XX:G1ReservePercent=10	6u26	It determines the minimum reserve we should have in the heap to minimize the probability of promotion failure
-XX:MaxGCPauseMillis=200	6u26	GC time per MMU time slice in milliseconds (for G1 only)
-XX:GCPauseIntervalMillis=300	6u26	Time slice for MMU specification in milliseconds (for G1 only). Should be greater than parameter above.

Alexey Ragozin

POF serialization, beware of arrays

POF array vs. binary

Summary

Data Grid Pattern - Canary key set

Data loss imminent

Canary keys to detect missing data

Conclusion

See also

Garbage collection in HotSpot JVM

Foreword

HotSpot JVM circa 2011

Serial GC

Young collection

Full (young + old + perm) collection

Parallel scavenge

Young collection

Full collection

Parallel old GC

Young collection

Full collection

Adaptive size policy

Concurrent mark sweep

Young collection

Concurrent old space collection

CMS failure and fallback to mark-sweep-compact

CMS incremental mode

G1 garbage collector

G1 young collection

G1 partial collection

G1 full collection (incremental mode failure)

Train GC

Permanent space

More reading

Using co-segments to dynamically adapt Lucene for frequent queries

Query complexity problem

Reducing CPU load by adding "synthetic" terms and query rewriting

Generating co-segment

Adding co-segments to existing index

Rewriting queries

Conclusion

More ideas

Coherence SIG: Advanced usage of indexes

Java GC, HotSpot's CMS promotion buffers

PLABs

Free list space(FLS)

Old space PLABs

Calculatingdesired block to claim

On-the-flyPLAB resizing

Conclusion

See also

Data Grid Pattern - Time series index for managing versioned data

Using custom index for accessing versioned data

Time series index structure

PROs and CONs

PRO

CON

Source code

Java, How to throw undeclared checked exception

Data Grid Pattern - Proactive caching

All in memory pattern

Refresh ahead

Proactive caching

Polling updates from DB

Long poll

Database notifications

Hooking into database replication

Single cache in front of multiple sources

Few more links

CMS heap fragmentation. Follow up 1

Experiment details

Application

JVM settings

Diagrams

Fragmentation in different HotSpot revisions

Adding more memory

Adding more CPU cores

Conclusions

Java GC, HotSpot's CMS and heap fragmentation

Concurrent mode failure