tag:blogger.com,1999:blog-86230740105628469572012-02-06T11:49:12.808-05:00Changing BitsMike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.comBlogger831100tag:blogger.com,1999:blog-8623074010562846957.post-50116165796587746142012-01-14T11:19:00.000-05:002012-01-14T11:19:13.107-05:00ToChildBlockJoinQuery in LuceneInmy <a href="http://blog.mikemccandless.com/2012/01/searching-relational-content-with.html">lastpost</a> I described a known limitationof <code>BlockJoinQuery</code>: it joins in only one direction (fromchild to parent documents). This can be a problem because someapplications need to join in reverse (from parent to child documents)instead.<br><br>This is now fixed! Ijust <a href="https://issues.apache.org/jira/browse/LUCENE-3685">committed</a>a new query, <code>ToChildBlockJoinQuery</code>, to perform the joinin the opposite direction. I also renamed the previous queryto <code>ToParentBlockJoinQuery</code>.<br><br>You use it just like <code>BlockJoinQuery</code>, except in reverse:it wraps any other <code>Query</code> matching parent documents andtranslates it into a <code>Query</code> matching child documents. Theresulting <code>Query</code> can then be combined with other queriesagainst fields in the child documents, and you can then sort by childfields as well.<br><br> Using songs and albums as an example: imagine you index eachsong (child) and album (parent) as separate documents in a singledocument block. With <code>ToChildBlockJoinQuery</code>, you can nowrun queries like:<pre><br /> albumName:thunder AND songName:numb<br /></pre>or<pre><br /> albumName:thunder, sort by songTitle<br /></pre>Any query with constraints against album and/or song fields will work,and the returned hits will be individual songs (not grouped).<br><br><code>ToChildBlockJoinQuery</code> will be available in Lucene 3.6.0and 4.0.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5011616579658774614?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-64831882418171993092012-01-08T18:52:00.000-05:002012-01-08T18:52:36.503-05:00Searching relational content with Lucene's BlockJoinQuery<a href="http://lucene.apache.org/java">Lucene's</a> <a href="http://lucene.apache.org/java/docs/index.html#14+September+2011+-+Lucene+Core+3.4.0">3.4.0release</a> adds a new feature called <em>index-time join</em> (alsosometimes called sub-documents, nested documents or parent/child documents),enabling efficient indexing and searching of certain typesof <a href="http://en.wikipedia.org/wiki/Relational_model">relationalcontent</a>.<br><br> Most search engines can't directly index relational content,as documents in the index logically behave like a single flat databasetable. Yet, relational content is everywhere! A job listing site haseach company joined to the specific listings for that company. Eachresume might have separate list of skills, education and past workexperience. A music search engine has an artist/band joined to albumsand then joined to songs. A source code search engine would haveprojects joined to modules and then files.<br><br>Perhaps the PDF documents you need to search are immense, so you breakthem up and index each section as a separate Lucene document; in thiscase you'll have common fields (title, abstract, author, datepublished, etc.) for the overall document, joined to the sub-document(section) with its own fields (text, page number, etc.). XMLdocuments typically contain nested tags, representing joinedsub-documents; emails have attachments; office documents can embedother documents. Nearly all search domains have some form ofrelational content, often requiring more than one join.<br><br>If such content is so common then how do search applications handle ittoday?<br><br>One obvious "solution" is to simply use a relational database insteadof a search engine! If relevance scores are less important and youneed to do substantial joining, grouping, sorting, etc., then using adatabase could be best overall. Most databases include some form atext search, some even using Lucene.<br><br>If you still want to use a search engine, then one common approachis to<a href="http://en.wikipedia.org/wiki/Denormalization"><em>denormalize</em></a>the content up front, at index-time, by joining all tables andindexing the resulting rows, duplicating content in the process. Forexample, you'd index each song as a Lucene document, copying over allfields from the song's joined album and artist/band. This workscorrectly, but can be horribly wasteful as you are indexing identicalfields, possibly including large text fields, over and over.<br><br>Another approach is to do the join yourself, outside ofLucene, by indexing songs, albums and artist/band as separate Lucenedocuments, perhaps even in separate indices. At search-time, youfirst run a query against one collection, for example the songs. Thenyou iterate through <b>all</b> hits, gathering up (joining) the fullset of corresponding albums and then run a second query against thealbums, with a large OR'd list of the albums from the first query,repeating this process if you need to join to artist/band as well.This approach will also work, but doesn't scale well as you may haveto create possibly immense follow-on queries.<br><br>Yet another approach is to use a software package that hasalready implemented one of theseapproaches for you! <a href="http://www.elasticsearch.org/">elasticsearch</a>,<a href="http://lucene.apache.org/solr/">Apache Solr</a>, <a href="http://jackrabbit.apache.org/">Apache Jackrabbit</a>, <a href="http://www.hibernate.org/subprojects/search.html">Hibernate Search</a> and many others all handle relational content in some way.<br><br>With <code>BlockJoinQuery</code> you can now directly searchrelational content yourself!<br><br><div class="separator" style="clear: both; text-align: center;"><a href="http://www.amazon.com/Mountain-Three-Wolf-Short-Sleeve/dp/B002HJ377A" style="clear:right; float:right;"><img border="0" height="358" width="400" src="http://1.bp.blogspot.com/-OCajpCiqBNA/TwmzR95meRI/AAAAAAAAAKs/bSZ2qZMj1F8/s400/threeWolf.jpg" /></a></div>Let's work through a simple example: imagine you sell shirts online.Each shirt has certain common fields such as name, description,fabric, price, etc. For each shirt you have a number ofseparate <a href="http://en.wikipedia.org/wiki/Stock-keeping_unit">stockkeeping units</a> or SKUs, which have their own fields like size,color, inventory count, etc. The SKUs are what you actually sell, andwhat you must stock, because when someone buys a shirt they buy aspecific SKU (size and color).<br><br>Maybe you are <a href="http://news.bbc.co.uk/2/hi/8061031.stm">lucky enough</a> to sell the incredible<a href="http://www.amazon.com/Mountain-Three-Wolf-Short-Sleeve/dp/B002HJ377A">Mountain Three-wolf Moon Short Sleeve Tee</a>, with these SKUs (size, color):<ul> <li> small, blue <li> small, black <li> medium, black <li> large, gray</ul>Perhaps a user first searches for "wolf shirt", gets a bunch of hits,and then drills down on a particular size and color, resulting in thisquery:<pre><br /> name:wolf AND size=small AND color=blue<br /></pre>which should match this shirt. <code>name</code> is a shirt fieldwhile the <code>size</code> and <code>color</code> are SKU fields.<br><br>But if the user drills down instead on a small gray shirt:<pre><br /> name:wolf AND size=small AND color=gray<br /></pre>then this shirt should not match because the small size only comes inblue and black.<br><br> How can you run these queriesusing <code>BlockJoinQuery</code>? Start by indexing each shirt(parent) and all of its SKUs (children) as separate documents, usingthe new <code>IndexWriter.addDocuments</code> API to add one shirt andall of its SKUs as a single <em>document block</em>. This methodatomically adds a block of documents into a single segment as adjacentdocument IDs, which <code>BlockJoinQuery</code> relies on. You shouldalso add a marker field to each shirt document (e.g. <code>type =shirt</code>), as <code>BlockJoinQuery</code> requiresa <code>Filter</code> identifying the parent documents.<br><br>To run a <code>BlockJoinQuery</code> at search-time, you'll first needto create the <em>parent filter</em>, matching only shirts.Note that the filter must use <code>FixedBitSet</code>under the hood, like <code>CachingWrapperFilter</code>:<pre><br /> Filter shirts = new CachingWrapperFilter(<br /> new QueryWrapperFilter(<br /> new TermQuery(<br /> new Term("type", "shirt"))));<br /></pre>Create this filter once, up front and re-use it any time you need toperform this join.<br><br>Then, for each query that requires a join, because it involvesboth SKU and shirt fields, start with the child query matching onlySKU fields:<pre><br /> BooleanQuery skuQuery = new BooleanQuery();<br /> skuQuery.add(new TermQuery(new Term("size", "small")), Occur.MUST);<br /> skuQuery.add(new TermQuery(new Term("color", "blue")), Occur.MUST);<br /></pre>Next, use <code>BlockJoinQuery</code> to translate hits from the SKUdocument space up to the shirt document space:<pre><br /> BlockJoinQuery skuJoinQuery = new BlockJoinQuery(<br /> skuQuery, <br /> shirts,<br /> ScoreMode.None);<br /></pre>The <code>ScoreMode</code> enum decides how scores for multiple SKUhits should be aggregated to the score for the corresponding shirthit. In this query you don't need scores from the SKU matches, but ifyou did you can aggregatewith <code>Avg</code>, <code>Max</code> or <code>Total</code> instead.<br><br>Finally you are now free to build up an arbitrary shirt queryusing <code>skuJoinQuery</code> as a clause:<pre><br /> BooleanQuery query = new BooleanQuery();<br /> query.add(new TermQuery(new Term("name", "wolf")), Occur.MUST);<br /> query.add(skuJoinQuery, Occur.MUST);<br /></pre>You could also just run <code>skuJoinQuery</code> as-is if the querydoesn't have any shirt fields.<br><br>Finally, just run this <code>query</code> like normal! Thereturned hits will be only shirt documents; if you'd also like to seewhich SKUs matched for each shirt,use <code>BlockJoinCollector</code>:<pre><br /> BlockJoinCollector c = new BlockJoinCollector(<br /> Sort.RELEVANCE, // sort<br /> 10, // numHits<br /> true, // trackScores<br /> false // trackMaxScore<br /> );<br /> searcher.search(query, c);<br /></pre>The provided <code>Sort</code> must use only shirt fields (you cannotsort by any SKU fields). When each hit (a shirt) is competitive, thiscollector will also record all SKUs that matched for that shirt, whichyou can retrieve like this:<pre><br /> TopGroups<Integer> hits = c.getTopGroups(<br /> skuJoinQuery,<br /> skuSort,<br /> 0, // offset<br /> 10, // maxDocsPerGroup<br /> 0, // withinGroupOffset<br /> true // fillSortFields<br /> );<br /></pre>Set <code>skuSort</code> to the sort order for the SKUs within eachshirt. The first <code>offset</code> hits are skipped (use this forpaging through shirt hits). Under each shirt, atmost <code>maxDocsPerGroup</code> SKUs will be returned.Use <code>withinGroupOffset</code> if you want to page within theSKUs. If <code>fillSortFields</code> is true then each SKU hit willhave values for the fields from <code>skuSort</code>.<br><br>The hits returned by <code>BlockJoinCollector.getTopGroups</code>are SKU hits, grouped by shirt. You'd get the exact same results ifyou had denormalized up-front and then used grouping to group resultsby shirt.<br><br>You can also do more than one join in a single query; the joins can benested (parent to child to grandchild) or parallel (parent to child1and parent to child2).<br><br>However, there are some important limitations of index-time joins:<ul> <li> The join must be computed at index-time and "compiled" into the index, in that all joined child documents must be indexed along with the parent document, as a single document block. <br> <br> <li> Different document types (for example, shirts and SKUs) must share a single index, which is wasteful as it means non-sparse data structures like <code>FieldCache</code> entries consume more memory than they would if you had separate indices. <br> <br> <li> If you need to re-index a parent document or any of its child documents, or delete or add a child, then the entire block must be re-indexed. This is a big problem in some cases, for example if you index "user reviews" as child documents then whenever a user adds a review you'll have to re-index that shirt as well as all its SKUs and user reviews. <br> <br> <li> There is no <code>QueryParser</code> support, so you need to programmatically create the parent and child queries, separating according to parent and child fields. <br> <br> <li> The join can currently only go in one direction (mapping child docIDs to parent docIDs), but in some cases you need to map parent docIDs to child docIDs. For example, when searching songs, perhaps you want all matching songs sorted by their title. You can't easily do this today because the only way to get song hits is to group by album or band/artist. <br> <br> <li> The join is a one (parent) to many (children), inner join.</ul>As usual, patches are welcome!<br><br>Thereis <a href="https://issues.apache.org/jira/browse/LUCENE-3602">workunderway</a> to create a more flexible, but likely less performant,query-time join capability, which should address a number of the abovelimitations.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6483188241817199309?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-35589482517157705352011-11-10T06:32:00.000-05:002011-11-10T06:32:22.728-05:00SearcherLifetimeManager prevents a broken search user experience<br/><br/>In the past, search indices were usually very static: you built themonce, called <code>optimize</code> at the end and shipped them off,and didn't change them very often.<br/><br/>But these days it's just the opposite: most applications have verydynamic indices, constantly being updated with a stream of changes,and you <em>never</em> call <code>optimize</code> anymore.<br/><br/>Lucene's near-real-time search, especially with recent improvementsincluding <a href="http://blog.mikemccandless.com/2011/11/near-real-time-readers-with-lucenes.html">managerclasses</a> to handle the tricky complexities of sharing searchersacross threads, offers very fast search turnaround on index changes.<br/><br/>But there is a serious yet often overlooked problem with thisapproach. To see it, you have to put yourself in the shoes of a user.Imagine Alice comes to your site, runs a search, and is lookingthrough the search results. Not satisfied, after a few seconds shedecides to refine that first search. Perhaps she drills down on oneof the nice facets you presented, or maybe she clicks to the nextpage, or picks a different sort criteria (any follow-on action willdo). So a new search request is sent back to your server, includingthe first search plus the requested change (drill down, next page,change sort field, etc.).<br/><br/>How do you handle this follow-on search request? Just pull the latestand greatest searcher fromyour <a href="http://blog.mikemccandless.com/2011/11/near-real-time-readers-with-lucenes.html"><code>SearcherManager</code></a>or <a href="http://blog.mikemccandless.com/2011/11/near-real-time-readers-with-lucenes.html"><code>NRTManager</code></a>and search away, right?<br/><br/>Wrong!<br/><br/>If you do this, you risk a broken search experience for Alice, becausethe new searcher may be different from the original searcher used forAlice's first search request. The differences could be substantial,if you had just opened a new searcher after updating a bunch ofdocuments. This means the results of Alice's follow-on search mayhave shifted: facet counts are now off, hits are sorted differently sosome hits may be duplicated on the second page, or may be lost (ifthey moved from page 2 to page 1), etc. If you use the new (will bein Lucene3.5.0) <a href="https://issues.apache.org/jira/browse/LUCENE-2215"><code>searchAfter</code></a>API, for efficient paging, the risk is even greater!<br/><br/>Perversely, the frequent searcher reopening that you thought providessuch a great user experience by making all search results so fresh,can in fact have just the opposite effect. Each reopen risks breakingall current searches in your application; the more activeyour site, the more searches you might break!<br/><br/>It's deadly to intentionally break a user's search experience: theywill (correctly) conclude your search is buggy, eroding their trust,and then take their business to your competition.<br/><br/>It turns out, this is easy to fix! Instead of pulling the latestsearcher for every incoming search request, you should try to pull thesame searcher used for the initial search request in the session.This way all follow-on searches see exactly the same index.<br/><br/>Fortunately, there's a new class coming in Lucene 3.5.0, thatsimplifies this: <code>SearcherLifetimeManager</code>. The class isagnostic to how you obtain the fresh searchers(i.e., <code>SearcherManager</code>, <code>NRTManager</code>, or yourown custom source) used for an initial search.Just likeLucene's <a href="http://blog.mikemccandless.com/2011/11/near-real-time-readers-with-lucenes.html">other manager classes</a>, <code>SearcherLifetimeManager</code> is veryeasy to use. Create the manager once, up front:<pre><br /> SearcherLifetimeManager mgr = new SearcherLifetimeManager();<br /></pre>Then, when a search request arrives, if it's an initial (notfollow-on) search, obtain the most current searcherin <a href="http://blog.mikemccandless.com/2011/11/near-real-time-readers-with-lucenes.html">theusual way</a>, but then record this searcher:<pre><br /> long token = mgr.record(searcher);<br /></pre>The returned <code>token</code> uniquely identifies the specificsearcher; you must save it somewhere the user's search results, forexample by placing it in a hidden HTML form field.<br/><br/>Later, when the user performs a follow-on search request, make surethe original <code>token</code> is sent back to the server, and thenuse it to obtain the same searcher:<pre><br /> // If possible, obtain same searcher version as last<br /> // search:<br /> IndexSearcher searcher = mgr.acquire(token);<br /> if (searcher != null) {<br /> // Searcher is still here<br /> try {<br /> // do searching...<br /> } finally {<br /> mgr.release(searcher);<br /> // Do not use searcher after this!<br /> searcher = null;<br /> }<br /> } else {<br /> // Searcher was pruned -- notify user session timed<br /> // out<br /> }<br /></pre>As long as the original searcher is still available, the manager willreturn it to you; be sure to <code>release</code> that searcher(ideally in a <code>finally</code> clause).<br/><br/>It's possible searcher is no longer available: for example if Aliceran a new search, but then got hungry, went off to a long lunch, andfinally returned then clicked "next page", likely the originalsearcher will have been pruned!<br/><br/>You should gracefully handle this case, for example by notifying Alicethat the search had timed out and asking her to re-submit the originalsearch (which will then get the latest and greatest searcher).Fortunately, you can reduce how often this happens, by controlling howaggressively you prune old searchers:<pre><br /> mgr.prune(new PruneByAge(600.0));<br /></pre>This removes any searchers older than 10 minutes (you can alsoimplement a custom pruning strategy). You should call it from aseparate dedicated thread (not a searcher thread), ideally the samethread that's periodically indexing changes and opening new searchers.<br/><br/>Keeping many searchers around will necessarily tie up resources (openfile descriptors, RAM, index files on disk thatthe <code>IndexWriter</code> would otherwise have deleted). However,because the reopened searchers share sub-readers, the resourceconsumption will generally be well contained, in proportion to howmany index changes occurred between each reopen. Just be sure touse <code>NRTCachingDirectory</code>, to ensure you don't bump upagainst open file descriptor limits on your operating system (thisalso gives a good speedup in reopen turnaround time).<br/><br/>Don't erode your users' trust by intentionally breaking theirsearches!<br/><br/><a href="https://issues.apache.org/jira/browse/LUCENE-3486">LUCENE-3486</a>has the details.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3558948251715770535?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-56947741654556603092011-11-03T14:12:00.000-04:002011-11-03T14:12:06.087-04:00Near-real-time readers with Lucene's SearcherManager and NRTManager<a href="http://blog.mikemccandless.com/2011/09/lucenes-searchermanager-simplifies.html">Lasttime</a>, I described the useful <code>SearcherManager</code> class,coming in the next (3.5.0) Lucene release, to periodically reopen your<code>IndexSearcher</code> when multiple threads need to share it.This class presents a verysimple <code>acquire</code>/<code>release</code> API, hiding thethread-safe complexities of opening and closing theunderlying <code>IndexReader</code>s.<br><br>But that example used a non near-real-time (NRT)<code>IndexReader</code>, which has relatively high turnaround timefor index changes to become visible, since you must call<code>IndexWriter.commit</code> first.<br><br>If you have access to the <code>IndexWriter</code> that's activelychanging the index (i.e., it's in the same JVM as your searchers), usean NRT reader instead! NRT readers let youdecouple <em>durability</em> to hardware/OS crashesfrom <em>visibility</em> of changes to a new <code>IndexReader</code>.How frequently you commit (for durability) and how frequently youreopen (to see new changes) become fully separate decisions.This <em>controlledconsistency model</em> that Lucene exposes is a nice "best of bothworlds" blend between thetraditional <a href="http://en.wikipedia.org/wiki/Immediate_consistency">immediate</a>and <a href="http://en.wikipedia.org/wiki/Eventual_consistency">eventual</a>consistency models.<br><br>Since reopening an NRT reader bypasses the costly commit, and sharessome data structures directly in RAM instead of writing/readingto/from files, itprovides <a href="http://blog.mikemccandless.com/2011/06/lucenes-near-real-time-search-is-fast.html">extremelyfast turnaround time</a> on making index changes visible to searchers.Frequent reopens such as every 50 milliseconds, even under relativelyhigh indexing rates, is easily achievable on modern hardware.<br><br>Fortunately, it's trivial to use <code>SearcherManager</code> with NRTreaders: use the constructor that takes <code>IndexWriter</code>instead of <code>Directory</code>:<pre><br /> boolean applyAllDeletes = true;<br /> ExecutorService es = null;<br /> SearcherManager mgr = new SearcherManager(writer, applyAllDeletes,<br /> new MySearchWarmer(), es);<br /></pre>This tells <code>SearcherManager</code> that its source for new<code>IndexReader</code>s is the provided <code>IndexWriter</code>instance (instead of a <code>Directory</code> instance). After that,use the <code>SearcherManager</code> <a href="http://blog.mikemccandless.com/2011/09/lucenes-searchermanager-simplifies.html">justas before</a>.<br><br>Typically you'll set the <code>applyAllDeletes</code> boolean to<code>true</code>, meaning each reopened reader is required to applyall previous deletion operations (<code>deleteDocuments</code>or <code>updateDocument/s</code>) up until that point.<br><br>Sometimes your usage won't require deletions to be applied. Forexample, perhaps you index multiple versions of each document overtime, always deleting the older versions, yet during searching youhave some way to ignore the old versions. If that's the case, you canpass <code>applyAllDeletes=false</code> instead. This will make theturnaround time quite a bit faster, as the primary-key lookupsrequired to resolve deletes can be costly. However, if you're usingLucene's trunk (to be eventually released as 4.0), another option isto use <code>MemoryCodec</code> on your <code>id</code> fieldto <a href="http://blog.mikemccandless.com/2011/06/primary-key-lookups-are-28x-faster-with.html">greatlyreduce the primary-key lookup time</a>.<br><br>Note that some or even all of the previous deletes may still beapplied even if you pass <code>false</code>. Also, the pendingdeletes are never <em>lost</em> if you pass <code>false</code>: theyremain buffered and will still eventually be applied.<br><br>If you have some searches that can tolerate unapplied deletes andothers that cannot, it's perfectly fine to create two<code>SearcherManager</code>s, one applying deletes and one not.<br><br>If you pass a non-null <code>ExecutorService</code>, then each segmentin the index can be searched concurrently; this is a way to gainconcurrency within a single search request. Most applications do notrequire this, because the concurrency across multiple searches issufficient. It's also not clear that this is effective in general asit adds per-segment overhead, and the available concurrency is afunction of your index structure. Perversely, a fully optimized indexwill have no concurrency! Most applications should pass<code>null</code>.<br><br><br><br><code><font size=+2><b>NRTManager</b></font></code><br><br>What if you want the fast turnaround time of NRT readers, but needcontrol over when specific index changes become visible to certainsearches? Use <code>NRTManager</code>!<br><br><code>NRTManager</code> holds onto the <code>IndexWriter</code>instance you provide and then exposes the same APIs for making indexchanges (<code>addDocument/s</code>, <code>updateDocument/s</code>,<code>deleteDocuments</code>). These methods forward to theunderlying <code>IndexWriter</code>, but then return a<em>generation</em> token (a Java <code>long</code>) which you canhold onto after making any given change. The generation onlyincreases over time, so if you make a group of changes, just keep thegeneration returned from the last change you made.<br><br>Then, when a given search request requires certain changes to bevisible, pass that generation back to<code>NRTManager</code> to obtain a searcher that's guaranteed toreflect all changes for that generation.<br><br>Here's one example use-case: let's say your site has a forum, and youuse Lucene to index and search all posts in the forum. Suddenly auser, Alice, comes online and adds a new post; in your server, youtake the text from Alice's post and add it as a document to the index,using<code>NRTManager.addDocument</code>, saving the returned generation.If she adds multiple posts, just keep the last generation.<br><br>Now, if Alice stops posting and runs a search, you'd like to ensureher search covers all the posts she just made. Of course, if yourreopen time is fast enough (say once per second), unless Alicetypes <em>very</em> quickly, any search she runs will already reflecther posts.<br><br>But pretend for now you reopen relatively infrequently (say once every5 or 10 seconds), and you need to be certain Alice's search covers herposts, so you call <code>NRTManager.waitForGeneration</code> to obtainthe <code>SearcherManager</code> to use for searching. If the latestsearcher already covers the requested generation, the method returnsimmediately. Otherwise, it blocks, requesting a reopen (see below),until the required generation has become visible in a searcher, andthen returns it.<br><br>If some other user, say Bob, doesn't add any posts and runs a search,you don't need to wait for Alice's generation to be visible whenobtaining the searcher, since it's far less important when Alice'schanges become immediately visible to Bob. There's (usually!) nocausal connection between Alice posting and Bob searching, so it'sfine for Bob to use the most recent searcher.<br><br>Another use-case is an index verifier, where you index a document andthen immediately search for it to perform end-to-end validation thatthe document "made it" correctly into the index. That immediatesearch must first wait for the returned generation to becomeavailable.<br><br>The power of <code>NRTManager</code> is you have full control overwhich searches must see the effects of which indexing changes; this isa further improvement in Lucene's controlled consistencymodel. <code>NRTManager</code> hides all the tricky details oftracking generations.<br><br>But: don't abuse this! You may be tempted to always wait for lastgeneration you indexed for all searches, but this would result in verylow search throughput on concurrent hardware since all searches wouldbunch up, waiting for reopens. With proper usage, only a small subsetof searches should need to wait for a specific generation, like Alice;the rest will simply use the most recent searcher, like Bob.<br><br>Managing reopens is a little trickier with <code>NRTManager</code>,since you should reopen at higher frequency whenever a search iswaiting for a specific generation. To address this, there's theuseful <code>NRTManagerReopenThread</code> class; use it like this:<pre><br /> double minStaleSec = 0.025;<br /> double maxStaleSec = 5.0;<br /> NRTManagerReopenThread thread = new NRTManagerReopenThread(<br /> nrtManager,<br /> maxStaleSec,<br /> minStaleSec);<br /> thread.start();<br /> ...<br /> thread.close();<br /></pre>The <code>minStaleSec</code> sets an upper bound on how frequentlyreopens should occur. This is used whenever a searcher is waiting fora specific generation (Alice, above), meaning the longest such a searchshould have to wait is approximately 25 msec. <br><br>The <code>maxStaleSec</code> sets a lower bound on how frequentlyreopens should occur. This is used for the periodic "ordinary"reopens, when there is no request waiting for a specific generation(Bob, above); this means any changes done to the index more thanapproximately 5.0 seconds ago will be seen when Bob searches. Notethat these parameters are approximate targets and not hard guaranteeson the reader turnaround time. Be sure to eventuallycall <code>thread.close()</code>, when you are done reopening (forexample, on shutting down the application).<br><br>You are also free to use your own strategy forcalling <code>maybeReopen</code>; you don't have to use <code>NRTManagerReopenThread</code>. Just remember that gettingit right, especially when searches are waiting for specificgenerations, can be tricky!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5694774165455660309?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com5tag:blogger.com,1999:blog-8623074010562846957.post-72886013511615820822011-10-25T11:55:00.001-04:002011-10-25T11:55:43.003-04:00Accuracy and performance of Google's Compact Language DetectorTo get a sense of the accuracy and performance of Google's <ahref="http://code.google.com/p/chromium-compact-language-detector">CompactLanguage Detector</a>, I ran some tests against two other packages: <br/> <br/><ul> <li> <a href="http://tika.apache.org">Apache Tika</a>, implemented in Java, using its <a href="http://tika.apache.org/0.10/api/org/apache/tika/language/LanguageIdentifier.html">LanguageIdentification</a> class <li> <a href="http://code.google.com/p/language-detection"><code>language-detection</code></a>, a project on <a href="http://code.google.com">Google code</a>, also implemented in Java <br/></ul> <br/>For the test corpus I used a <ahref="http://shuyo.wordpress.com/2011/09/29/langdetect-is-updatedadded-profiles-of-estonian-lithuanian-latvian-slovene-and-so-on/">thecorpus described here</a>, created by the author of<code>language-detection</code>. It contains 1000 texts from each of21 languages, randomly sampled from the <ahref="http://www.statmt.org/europarl">Europarl corpus</a>.<br/><br/>It's not a perfect test (no test ever is!): the content is alreadyvery clean plain text; there are no domain, language, encoding hintsto apply (which you'd normally have with HTML content loaded overHTTP); it "only" covers 21 languages (versus at least 76 that CLD candetect).<br/><br/>CLD and <code>language-detection</code> cover all 21 languages, butTika is missing Bulgarian (<code>bg</code>), Czech (<code>cs</code>),Lithuanian (<code>lt</code>) and Latvian (<code>lv</code>), so I onlytested on the remaining subset of 17 languages that all three detectorssupport. This works out to 17,000 texts totalling 2.8 MB.<br/><br/>Many of the texts are very short, making the test challenging: theshortest is 25 bytes, and 290 (1.7%) of the 17000 are 30 bytes orless.<br/><br/>In addition to the challenges of the corpora, the differences in thedetectors make the comparison somewhat apples to oranges. Forexample, CLD detects at least 76 languages, while<code>language-detection</code> detects 53 and Tika detects 27,so this biases against CLD, and <code>language-detection</code> to alesser extent, since their classification task is harder relative toTika's.<br/><br/>For CLD, I disabled its <ahref="http://blog.mikemccandless.com/2011/10/additions-to-compact-language-detector.html">optionto abstain</a> (<code>removeWeakMatches</code>), so that it alwaysguesses at the language even when confidence is low, to match theother two detectors. I also turned off the<code>pickSummaryLanguage</code>, as this was also hurting accuracy;now CLD simply picks the highest scoring match as the detectedlanguage.<br/><br/>For <code>language-detection</code>, I ran with the default<code>ALPHA</code> of 0.5, and set the random seed to 0.<br/><br/>Here are the raw results:<br/><br/>CLD results (total 98.82% = 16800 / 17000):<br/><font face=Courier><table border=0><tr><td> <b>da</b> </td><td align=right>93.4% </td><td> da=934</td><td> nb=54</td><td> sv=5</td><td> fr=2</td><td> eu=2</td><td> is=1</td><td> hr=1</td><td> en=1</td><td> </td></tr><tr><td> <b>de</b> </td><td align=right>99.6% </td><td> de=996</td><td> en=2</td><td> ga=1</td><td> cy=1</td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>el</b> </td><td align=right>100.0% </td><td> el=1000</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>en</b> </td><td align=right>100.0% </td><td> en=1000</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>es</b> </td><td align=right>98.3% </td><td> es=983</td><td> pt=4</td><td> gl=3</td><td> en=3</td><td> it=2</td><td> eu=2</td><td> id=1</td><td> fi=1</td><td> da=1</td></tr><tr><td> <b>et</b> </td><td align=right>99.6% </td><td> et=996</td><td> ro=1</td><td> id=1</td><td> fi=1</td><td> en=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>fi</b> </td><td align=right>100.0% </td><td> fi=1000</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>fr</b> </td><td align=right>99.2% </td><td> fr=992</td><td> en=4</td><td> sq=2</td><td> de=1</td><td> ca=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>hu</b> </td><td align=right>99.9% </td><td> hu=999</td><td> it=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>it</b> </td><td align=right>99.5% </td><td> it=995</td><td> ro=1</td><td> mt=1</td><td> id=1</td><td> fr=1</td><td> eu=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>nl</b> </td><td align=right>99.5% </td><td> nl=995</td><td> af=3</td><td> sv=1</td><td> et=1</td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>pl</b> </td><td align=right>99.6% </td><td> pl=996</td><td> tr=1</td><td> sw=1</td><td> nb=1</td><td> en=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>pt</b> </td><td align=right>98.7% </td><td> pt=987</td><td> gl=4</td><td> es=3</td><td> mt=1</td><td> it=1</td><td> is=1</td><td> ht=1</td><td> fi=1</td><td> en=1</td></tr><tr><td> <b>ro</b> </td><td align=right>99.8% </td><td> ro=998</td><td> da=1</td><td> ca=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>sk</b> </td><td align=right>98.8% </td><td> sk=988</td><td> cs=9</td><td> en=2</td><td> de=1</td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>sl</b> </td><td align=right>95.1% </td><td> sl=951</td><td> hr=32</td><td> sr=8</td><td> sk=5</td><td> en=2</td><td> id=1</td><td> cs=1</td><td> </td><td> </td></tr><tr><td> <b>sv</b> </td><td align=right>99.0% </td><td> sv=990</td><td> nb=9</td><td> en=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr></table></font><br/><br/>Tika results (total 97.12% = 16510 / 17000):<br/><font face=Courier><table border=0><tr><td> <b>da</b> </td><td align=right>87.6% </td><td> da=876</td><td> no=112</td><td> nl=4</td><td> sv=3</td><td> it=1</td><td> fr=1</td><td> et=1</td><td> en=1</td><td> de=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>de</b> </td><td align=right>98.5% </td><td> de=985</td><td> nl=3</td><td> it=3</td><td> da=3</td><td> sv=2</td><td> fr=2</td><td> sl=1</td><td> ca=1</td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>el</b> </td><td align=right>100.0% </td><td> el=1000</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>en</b> </td><td align=right>96.9% </td><td> en=969</td><td> no=10</td><td> it=6</td><td> ro=4</td><td> sk=3</td><td> fr=3</td><td> hu=2</td><td> et=2</td><td> sv=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>es</b> </td><td align=right>89.8% </td><td> es=898</td><td> gl=47</td><td> pt=22</td><td> ca=15</td><td> it=6</td><td> eo=4</td><td> fr=3</td><td> fi=2</td><td> sk=1</td><td> nl=1</td><td> et=1</td><td> </td><td> </td></tr><tr><td> <b>et</b> </td><td align=right>99.1% </td><td> et=991</td><td> fi=4</td><td> fr=2</td><td> sl=1</td><td> no=1</td><td> ca=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>fi</b> </td><td align=right>99.4% </td><td> fi=994</td><td> et=5</td><td> hu=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>fr</b> </td><td align=right>98.0% </td><td> fr=980</td><td> sl=6</td><td> eo=3</td><td> et=2</td><td> sk=1</td><td> ro=1</td><td> no=1</td><td> it=1</td><td> gl=1</td><td> fi=1</td><td> es=1</td><td> de=1</td><td> ca=1</td></tr><tr><td> <b>hu</b> </td><td align=right>99.9% </td><td> hu=999</td><td> ca=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>it</b> </td><td align=right>99.4% </td><td> it=994</td><td> eo=4</td><td> pt=1</td><td> fr=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>nl</b> </td><td align=right>97.8% </td><td> nl=978</td><td> no=8</td><td> de=3</td><td> da=3</td><td> sl=2</td><td> ro=2</td><td> pl=1</td><td> it=1</td><td> gl=1</td><td> et=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>pl</b> </td><td align=right>99.1% </td><td> pl=991</td><td> sl=3</td><td> sk=2</td><td> ro=1</td><td> it=1</td><td> hu=1</td><td> fi=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>pt</b> </td><td align=right>94.4% </td><td> pt=944</td><td> gl=48</td><td> hu=2</td><td> ca=2</td><td> it=1</td><td> et=1</td><td> es=1</td><td> en=1</td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>ro</b> </td><td align=right>99.3% </td><td> ro=993</td><td> is=2</td><td> sl=1</td><td> pl=1</td><td> it=1</td><td> hu=1</td><td> fr=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>sk</b> </td><td align=right>96.2% </td><td> sk=962</td><td> sl=21</td><td> pl=13</td><td> it=2</td><td> ro=1</td><td> et=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>sl</b> </td><td align=right>98.5% </td><td> sl=985</td><td> sk=7</td><td> et=4</td><td> it=2</td><td> pt=1</td><td> no=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>sv</b> </td><td align=right>97.1% </td><td> sv=971</td><td> no=15</td><td> nl=6</td><td> da=6</td><td> de=1</td><td> ca=1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr></table></font><br/><br/><code>Language-detection</code> results (total 99.22% = 16868 / 17000):<br/><font face=Courier><table border=0><tr><td> <b>da</b> </td><td align=right>97.1% </td><td> da=971</td><td> no=28</td><td> en=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>de</b> </td><td align=right>99.8% </td><td> de=998</td><td> da=1</td><td> af=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>el</b> </td><td align=right>100.0% </td><td> el=1000</td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>en</b> </td><td align=right>99.7% </td><td> en=997</td><td> nl=1</td><td> fr=1</td><td> af=1</td><td> </td><td> </td></tr><tr><td> <b>es</b> </td><td align=right>99.5% </td><td> es=995</td><td> pt=4</td><td> en=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>et</b> </td><td align=right>99.6% </td><td> et=996</td><td> fi=2</td><td> de=1</td><td> af=1</td><td> </td><td> </td></tr><tr><td> <b>fi</b> </td><td align=right>99.8% </td><td> fi=998</td><td> et=2</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>fr</b> </td><td align=right>99.8% </td><td> fr=998</td><td> sv=1</td><td> it=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>hu</b> </td><td align=right>99.9% </td><td> hu=999</td><td> id=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>it</b> </td><td align=right>99.8% </td><td> it=998</td><td> es=2</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>nl</b> </td><td align=right>97.7% </td><td> nl=977</td><td> af=21</td><td> sv=1</td><td> de=1</td><td> </td><td> </td></tr><tr><td> <b>pl</b> </td><td align=right>99.9% </td><td> pl=999</td><td> nl=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>pt</b> </td><td align=right>99.4% </td><td> pt=994</td><td> es=3</td><td> it=1</td><td> hu=1</td><td> en=1</td><td> </td></tr><tr><td> <b>ro</b> </td><td align=right>99.9% </td><td> ro=999</td><td> fr=1</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> <b>sk</b> </td><td align=right>98.7% </td><td> sk=987</td><td> cs=8</td><td> sl=2</td><td> ro=1</td><td> lt=1</td><td> et=1</td></tr><tr><td> <b>sl</b> </td><td align=right>97.2% </td><td> sl=972</td><td> hr=27</td><td> en=1</td><td> </td><td> </td><td> </td></tr><tr><td> <b>sv</b> </td><td align=right>99.0% </td><td> sv=990</td><td> no=8</td><td> da=2</td><td> </td><td> </td><td> </td></tr></table></font><br/><br/>Some quick analysis:<ul><li> The language-detection library gets the best accuracy, at 99.22%, followed by CLD, at 98.82%, followed by Tika at 97.12%. Net/net these accuracies are very good, especially considering how short some of the tests are! <br/><br/><li> The difficult languages are Danish (confused with Norwegian), Slovene (confused with Croatian) and Dutch (for Tika and <code>language-detection</code>). Tika in particular has trouble with Spanish (confuses it with Galician). These confusions are to be expected: the languages are very similar. </ul><br/>When <code>language-detection</code> was wrong, Tika was alsowrong 37% of the time and CLD was also wrong 23% of the time. Thesenumbers are quite low! It tells us that the errors are somewhatorthogonal, i.e. the libraries tend to get different test cases wrong.For example, it's not the case that they are all always wrong on the shorttexts.<br/><br/>This means the libraries are using different overall signals toachieve their classification (for example, perhaps they were trainedon different training texts). This is encouraging since it means, intheory, one could build a language detection library combining thesignals of all of these libraries and achieve better overall accuracy.<br/><br/>You could also make a simple majority-rules voting system across these(and other) libraries. I tried exactly that approach: if any languagereceives 2 or more votes from the three detectors, select that as thedetected language; otherwise, go with <code>language-detection</code>choice. This gives the best accuracy of all: total 99.59% (= 16930 /17000)!<br/><br/>Finally, I also separately tested the run time for each package. Eachtime is the best of 10 runs through the full corpus:<br/><br/><font face=Courier><table><tr><td><b>CLD</b></td><td align=right> 171 msec</td><td align=right> 16.331 MB/sec</td></tr><tr><td><b><code>language-detection</code></b></td><td align=right> 2367 msec</td><td align=right> 1.180 MB/sec</td></tr><tr><td><b>Tika</b></td><td align=right> 42219 msec</td><td align=right> 0.066 MB/sec</td></tr></table></font><br/><br/>CLD is incredibly fast! <code>language-detection</code> is an orderof magnitude slower, and Tika is another order of magnitude slower(not sure why).<br/><br/>I used <a href="http://code.google.com/p/language-detection/downloads/detail?name=langdetect-09-13-2011.zip&can=2&q=">the09-13-2011 release</a> of <code>language-detection</code>, the currenttrunk (svn revision 1187915) of <a href="https://svn.apache.org/repos/asf/tika/trunk/">Apache Tika</a>,and the current trunk (hg revision b0adee43f3b1) of <ahref="http://code.google.com/p/chromium-compact-language-detector/source/browse/">CLD</a>.All sources for the performance tests are <a href="http://code.google.com/a/apache-extras.org/p/luceneutil/source/browse/#hg%2Flangdetect">available from here</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7288601351161582082?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com10tag:blogger.com,1999:blog-8623074010562846957.post-10912248987556873102011-10-24T14:10:00.000-04:002011-10-24T14:11:12.770-04:00Additions to Compact Language Detector API<br />I've made some small improvements after <a href="http://blog.mikemccandless.com/2011/10/language-detection-with-googles-compact.html">my quick initial port</a> of <a href="http://code.google.com/p/chromium-compact-language-detector">Google's Compact Language Detection Library</a>, starting with some helpful Python constants:<br /><ul><br /><li> <code>cld.ENCODINGS</code> has all the encoding names recognized by CLD; if you pass the encoding hint it must be one of these.<br /><br /><li> <code>cld.LANGUAGES</code> has the list of all base languages known (but not necessarily detectable) by CLD.<br /><br /><li> <code>cld.EXTERNAL_LANGUAGES</code> has the list of external languages known (but not necessarily detectable) by CLD.<br /><br /><li> <code>cld.DETECTED_LANGUAGES</code> has the list of detectable languages.<br /></ul><br />I haven't found a reliable way to get the full list of detectable languages; for now, I've started with all languages that are covered by the unit test, total count 75, which should be a lower bound on the true count.<br /><br />I also exposed control over whether CLD should abstain from a given matched language if the confidence is too low, by adding a parameter <code>removeWeakMatches</code> (required in C and optional in Python, default <code>False</code>). Turn this option on if abstaining is OK in your use case, such as a browser toolbar offering to translate content. Turn it off when testing accuracy vs other language detection libraries (unless they also abstain!).<br /><br />Finally, CLD has an algorithm that tries to pick the best "summary" language, and it doesn't always just pick the highest scoring match. For example, the code has this comment:<br /><pre><br /> // If English and X, where X (not UNK) is big enough,<br /> // assume the English is boilerplate and return X.<br /></pre>See the <a href="http://code.google.com/p/chromium-compact-language-detector/source/browse/encodings/compact_lang_det/compact_lang_det_impl.cc#1984">CalcSummaryLanguage function</a> for more details!<br /><br />I found this was hurting accuracy in testing so I added a parameter <code>pickSummaryLanguage</code> (default <code>False</code>) to also turn this on or off.<br /><br />Finally, I fixed the Python binding to release the <a href="http://wiki.python.org/moin/GlobalInterpreterLock">GIL</a> while CLD is running, so multiple threads can now detect without falsely blocking one another.<br /><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-1091224898755687310?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-56710230595662574322011-10-21T15:47:00.000-04:002011-10-24T14:11:37.524-04:00Language detection with Google's Compact Language Detector<br />Google's <a href="http://www.google.com/chrome">Chrome browser</a> has a useful translate feature, where it detects the language of the page you've visited and if it differs from your local language, it offers to translate it.<br /><br />Wonderfully, Google has open-sourced <a href="http://code.google.com/chromium">most of Chrome's source code</a>, including the embedded CLD (Compact Language Detector) library that's used to detect the language of any UTF-8 encoded content. It looks like CLD was extracted from the language detection library used in <a href="http://toolbar.google.com/">Google's toolbar</a>.<br /><br />It turns out the <a href="http://src.chromium.org/viewvc/chrome/trunk/src/third_party/cld/">CLD part of the Chromium source tree</a> is nicely standalone, so I pulled it out into a <a href="http://code.google.com/p/chromium-compact-language-detector/">new separate Google code project</a>, making it possible to use CLD directly from any C++ code.<br /><br />I also added basic initial Python binding (one method!), and ported the small C++ unit test (verifying detection of known strings for 64 different languages) to Python (it passes!).<br /><br />So detecting language is now very simple from Python:<br /><pre><br /> import cld<br /> topLanguageName = cld.detect(bytes)[0]<br /></pre>The detect method returns a tuple, including the language name and code (such as <code>RUSSIAN</code>, <code>ru</code>), an <code>isReliable</code> boolean (<code>True</code> if CLD is quite sure of itself), the number of actual text bytes processed, and then details for each of the top languages (up to 3) that were identified.<br /><br />You must provide it clean (interchange-valid) UTF-8, so any encoding issues must be sorted out before-hand.<br /><br />You can also optionally provide hints to the detect method, including the declared encoding and language (for example, from an HTTP header or an embedded <code>META http-equiv</code> tag in the HTML), as well as the domain name suffix (so the top level domain suffix <code>es</code> would boost the chances for detecting Spanish). CLD uses these hints to boost the priors for certain languages. There is this fun comment in the code in front of the tables holding the per-language prior boots:<pre><br /> Generated by dsites 2008.07.07 from 10% of Base<br /></pre>How I wish I too could build tables off of 10% of Base!<br /><br />The code itself looks very cool and I suspect (but haven't formally verified!) its quite accurate. I only understand bits and pieces about how it works; you can read some details <a href="http://www.globalbydesign.com/blog/2010/12/06/inside-googles-language-detection-tool">here</a> and <a href="http://www.archive.org/~aaron/iipc/language-detection-investigation.html">here</a>.<br /><br />It's also not clear just how many languages it can detect; I see there are 161 "base" languages plus 44 "extended" languages, but then I see many test cases (102 out of 166!) commented out. This was likely done to reduce the size of the ngram tables; possibly Google could provide the full original set of tables for users wanting to spend more RAM in exchange for detecting the long tail.<br /><br /><a href="http://src.chromium.org/viewvc/chrome/trunk/src/third_party/cld/">This port</a> is all still very new, and I extracted CLD quickly, so likely there are some problems still to work out, but the fact that it passes the Python unit test is encouraging. The <a href="http://code.google.com/p/chromium-compact-language-detector/source/browse/README.txt">README.txt</a> has some more details.<br /><br />Thank you Google!<br /><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5671023059566257432?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com29tag:blogger.com,1999:blog-8623074010562846957.post-31689486293785719952011-09-26T11:29:00.000-04:002011-09-28T06:54:15.006-04:00Lucene's SearcherManager simplifies reopen with threadsModern computers have wonderful hardware concurrency, within and across CPU cores, RAM and IO resources, which means your typical server-based search application should use multiple threads to fully utilize all resources.<p>For searching, this usually means you'll have one thread handle each search request, sharing a single <code>IndexSearcher</code> instance. This model is effective: the Lucene developers work hard to minimize internal locking in all Lucene classes. In fact, we recently removed thread contention during indexing (specifically, flushing), resulting in <a href="http://blog.mikemccandless.com/2011/05/265-indexing-speedup-with-lucenes.html">massive gains in indexing throughput</a> on highly concurrent hardware.<p>Since <code>IndexSearcher</code> exposes a fixed, point-in-time view of the index, when you make changes to the index you'll need to reopen it. Fortunately, since version 2.9, Lucene has provided the <code>IndexReader.reopen</code> method to get a new reader reflecting the changes.<p>This operation is efficient: the new reader shares already warmed sub-readers in common with the old reader, so it only opens sub-readers for any newly created segments. This means reopen time is generally in proportion to how many changes you made; however, when a large merge had completed it will be longer. It's best to warm the new reader before putting it into production by running a set of "typical" searches for your application, so that Lucene performs one-time initialization for internal data structures (norms, field cache, etc.).<p>But how should you properly reopen, while search threads are still running and new searches are forever arriving? Your search application is popular, users are always searching and there's never a good time to switch! The core issue is that you must never close your old <code>IndexReader</code> while other threads are still using it for searching, otherwise those threads can easily hit cryptic exceptions that often mimic index corruption.<p>Lucene tries to detect that you've done this, and will throw a nice <code>AlreadyClosedException</code>, but we cannot guarantee that exception is thrown since we only check up front, when the search kicks off: if you close the reader when a search is already underway then all bets are off.<div class="separator" style="clear: both; text-align: center;"><img border="0" height="201" width="150" style="clear:right; float:right; margin-left:1em; margin-bottom:1em" src="http://4.bp.blogspot.com/-xnjkxEz-WYA/ToBW8Ot98DI/AAAAAAAAAJU/x8QopWum8tA/s1600/restroom.jpg" /></div><p>One simple approach would be to temporarily block all new searches and wait for all running searches to complete, and then close the old reader and switch to the new one. This is how janitors often clean a bathroom: they wait for all current users to finish and block new users with the all-too-familiar plastic yellow sign.<p>While the bathroom cleaning approach will work, it has an obviously serious drawback: during the cutover you are now forcing your users to wait, and that wait time could be long (the time for the slowest currently running search to finish).<p>A much better solution is to immediately direct new searches to the new reader, as soon as it's done warming, and then separately wait for the still-running searches against the old reader to complete. Once the very last search has finished with the old reader, close it.<p>This solution is fully concurrent: it has no locking whatsoever so searches are never blocked, as long as you use a separate thread to perform the reopen and warming. The time to reopen and warm the new reader has no impact on ongoing searches, except to the extent that reopen consumes CPU, RAM and IO resources to do its job (and, sometimes, this can in fact interfere with ongoing searches).<p>So how exactly do you implement this approach? The simplest way is to use the reference counting APIs already provided by <code>IndexReader</code> to track how many threads are currently using each searcher. Fortunately, as of Lucene 3.5.0, there will be a new <code>contrib/misc</code> utility class, <code>SearcherManager</code>, originally created as an example for <a href="http://www.manning.com/hatcher3/">Lucene in Action, 2nd edition</a>, that does this for you! (<a href="https://issues.apache.org/jira/browse/LUCENE-3445">LUCENE-3445</a> has the details.)<p>The class is easy to use. You first create it, by providing the <code>Directory</code> holding your index and a <code>SearchWarmer</code> instance:<pre><br /> class MySearchWarmer implements SearchWarmer {<br /> @Override<br /> public void warm(IndexSearcher searcher) throws IOException {<br /> // Run some diverse searches, searching and sorting against all<br /> // fields that are used by your application<br /> }<br /> }<br /><br /> Directory dir = FSDirectory.open(new File("/path/to/index"));<br /> SearcherManager mgr = new SearcherManager(dir,<br /> new MySearchWarmer());<br /></pre><p>Then, for each search request:<pre><br /> IndexSearcher searcher = mgr.acquire();<br /> try {<br /> // Do your search, including loading any documents, etc.<br /> } finally {<br /> mgr.release(searcher);<br /><br /> // Set to null to ensure we never again try to use<br /> // this searcher instance after releasing:<br /> searcher = null;<br />}<br /></pre><p>Be sure you fully consume <code>searcher</code> before releasing it! A common mistake is to release it yet later accidentally use it again to load stored documents, for rendering the search results for the current page.<p>Finally, you'll need to periodically call the <code>maybeReopen</code> method from a separate (ie, non-searching) thread. This method will reopen the reader, and only if there was actually a change will it cutover. If your application knows when changes have been committed to the index, you can reopen right after that. Otherwise, you can simply call <code>maybeReopen</code> every X seconds. When there has been no change to the index, the cost of <code>maybeReopen</code> is negligible, so calling it frequently is fine.<p>Beware the potentially high transient cost of reopen and warm! During reopen, as you must have two readers open until the old one can be closed, you should budget plenty of RAM in the computer and heap for the JVM, to comfortably handle the worst case when the two readers share no sub-readers (for example, after a full optimize) and thus consume 2X the RAM of a single reader. Otherwise you might hit a swap storm or <code>OutOfMemoryError</code>, effectively taking down entire whole search application. Worse, you won't see this problem early on: your first few hundred reopens could easily use only small amounts of added heap, but then suddenly on some unexpected reopen the cost is far higher. Reopening and warming is also generally IO intensive as the reader must load certain index data structures into memory.<p>Next time I'll describe another utility class, <code>NRTManager</code>, available since version 3.3.0, that you should use instead if your application uses Lucene's fast-turnaround near-real-time (NRT) search. This class solves the same problem (thread-safety during reopening) as <code>SearcherManager</code> but adds a fun twist as it gives you more specific control over which changes must be visible in the newly opened reader.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3168948629378571995?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com6tag:blogger.com,1999:blog-8623074010562846957.post-5203389353126710012011-06-30T06:09:00.004-04:002011-06-30T08:38:17.755-04:00Primary key lookups are 2.8X faster with MemoryCodecA few days ago I committed the new <a href="https://issues.apache.org/jira/browse/LUCENE-3209">MemoryCodec</a> to Lucene's trunk (to be 4.0). This codec indexes all terms and postings into a compact <a href="http://blog.mikemccandless.com/2010/12/using-finite-state-transducers-in.html">finite-state transducer</a> (FST) and then, at search time, avoids I/O by performing all terms and postings enumerations in memory using the FST.<br /><br />If your application needs fast primary-key lookups, and you can afford the required additional memory, this codec might be a good match for the <tt>id</tt> field. To test this, I switched Lucene's nightly benchmark to use <tt>MemoryCodec</tt> (just for its <tt>id</tt> field), and performance jumped from around 179 K to 509 K lookups per second:<br /><br /><a href="http://people.apache.org/~mikemccand/lucenebench/PKLookup.html"><img style="cursor:pointer; cursor:hand;width: 600px; height: 302px;" src="http://2.bp.blogspot.com/-RvDf4osoNEk/TgxMaLuDtlI/AAAAAAAAAIM/TIIvCHOUmL0/s1600/PKLookupMemCodec.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5623954047385187922" /></a><br /><br />This is an awesome improvement! It's particularly impressive as the <tt>id</tt> field was previously indexed using <tt>PulsingCodec</tt>, which was <a href="http://blog.mikemccandless.com/2010/06/lucenes-pulsingcodec-on-primary-key.html">already faster than the default <tt>StandardCodec</tt></a>.<br /><br />This is the performance for a single thread, and should scale up linearly if you use multiple threads. Each lookup resolves 4,000 keys in order at once from the <tt>id</tt> field, performing the lookups segment by segment for best performance (<a href="http://code.google.com/a/apache-extras.org/p/luceneutil/source/browse/perf/SearchPerfTest.java#353">see the source code</a>). The index has 27.6 M docs across multiple segments.<br /><br />Of course, there is added memory required, specifically 188 MB for this index, which works out to 7.1 bytes per document on average.<br /><br />There are two sources of <tt>MemoryCodec</tt>'s gains. First, the obvious one: since everything is in memory, you never wait for an I/O seek operation, as long as you ensure the sneaky OS <a href="http://blog.mikemccandless.com/2011/04/just-say-no-to-swapping.html">never swaps out your process memory</a>.<br /><br />Second, I separately added a new <a href="https://issues.apache.org/jira/browse/LUCENE-3225"><tt>seekExact</tt> API</a> to <tt>TermsEnum</tt>, enabling codecs to save CPU if the caller does not need to know the following term when the target term doesn't exist, as is the case here. <tt>MemoryCodec</tt> has an optimized implementation for <tt>seekExact</tt> (and so does the cool <a href="http://blog.mikemccandless.com/2010/10/lucenes-simpletext-codec.html"><tt>SimpleTextCodec</tt></a>!). Eventually other codecs should as well, by using the <a href="https://issues.apache.org/jira/browse/LUCENE-3030">block tree terms index</a>, but we're not there yet.<br /><br />The <tt>id</tt> field in the nightly benchmark omits term freq and positions, however <tt>MemoryCodec</tt> is fully general: you can use it for any field (not just primary-key), storing positions, payloads, etc. Also, its values are zero-padded sequential integers (00000001, 00000002, 00000003, etc.), which is likely important for performance as it allows maximal sharing in the FST. I haven't tested but I suspect had I used something more random, such as <a href="http://en.wikipedia.org/wiki/Globally_unique_identifier">GUIDs</a>, memory usage would be higher and lookup performance worse as each segment's FST would be less dense (share less).<br /><br />Of course, Lucene is not a database, and you normally use it for its fast search performance, not primary-key lookups. The one common search use case where you do require primary-key lookups is during indexing, when deleting or updating documents by an <tt>id</tt> field. Near-realtime search with updates or deletions <a href="http://blog.mikemccandless.com/2011/06/lucenes-near-real-time-search-is-fast.html">relies on this</a>, since the deleted documents must be resolved during reopen, so we also see a healthy speedup in the NRT reopen time:<br /><br /><a href="http://people.apache.org/~mikemccand/lucenebench/nrt.html"><img style="cursor:pointer; cursor:hand;width: 600px; height: 308px;" src="http://1.bp.blogspot.com/-x4CBP_7F-O4/TgxMhavx5EI/AAAAAAAAAIU/_YbOYHIti78/s1600/NRTMemCodec.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5623954171678024770" /></a><br /><br />The NRT latencey dropped from around 52 milliseconds to 43 milliseconds, a 17% improvement. This is "only" 17% because opening a new reader must also do other things like flush the indexed documents as a new segment.<br /><br />Perhaps more importantly, the variance also dropped substantially, which is expected because with <tt>MemoryCodec</tt> and <tt>NRTCachingDirectory</tt>, NRT reopen is fully I/O free (performs no reads or writes when opening a new reader).<br /><br />One limitation of <tt>MemoryCodec</tt> is it's an all-or-nothing deal: all terms and postings are in memory, or they aren't. <a href="https://issues.apache.org/jira/browse/LUCENE-3069">LUCENE-3069</a>, still to be done (any volunteers?), aims to fix this, by enabling you to separately choose whether terms and/or postings data should be in memory.<br /><br />I suspect an even more specialized codec, for example one that requires the field values to be compact integers, and also requires that the values are unique (only supports primary-key fields), could do even better than <tt>MemoryCodec</tt> by storing the mapping in global (across all segments) parallel arrays. Such a codec would no longer be general; it'd only work for primary-key fields whose values are compact integers. But it'd have faster lookups than <tt>MemoryCodec</tt> and should use less memory per document. This codec could simply wrap any other codec, i.e. it would create the arrays on reader initialization, and delegate persisting the postings into the index to the wrapped codec.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-520338935312671001?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com1tag:blogger.com,1999:blog-8623074010562846957.post-53066266497645449932011-06-14T13:27:00.004-04:002011-06-14T13:46:35.369-04:00Near-real-time latency during large mergesI looked into the curious issue I described in my <a href="http://blog.mikemccandless.com/2011/06/lucenes-near-real-time-search-is-fast.html">last post</a>, where the NRT reopen delays can become "spikey" (take longer) during a large merge.<br /><br />To show the issue, I modified the NRT test to kick off a background optimize on startup. This runs a single large merge, creating a 13 GB segment, and indeed produces spikey reopen delays (purple):<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://people.apache.org/~mikemccand/NRTNoRateLimit.html"><img style="cursor:pointer; cursor:hand;width: 600px; height: 363px;" src="http://1.bp.blogspot.com/-A3JN33lTesg/Tfeaw5owp2I/AAAAAAAAAH8/iqBTypzBjrQ/s1600/NRTNoRateLimit.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5618129225064163170" /></a><br /><br />The large merge finishes shortly after 7 minutes, after which the reopen delays become healthy again. Search performance (green) is unaffected.<br /><br />I also added Linux'd dirty bytes to the graph, as reported by <tt>/proc/meminfo</tt>; it's the saw-tooth blue/green series on the bottom. Note that it's divided by 10, to better fit the Y axis; the peaks are around 800-900 MB.<br /><br />The large merge writes bytes a fairly high rate (around 30 MB/sec), but Linux buffers those writes in RAM, only actually flushing them to disk every 30 seconds; this is what produces the saw-tooth pattern.<br /><br />From the graph you can see that the spikey reopen delays generally correlate to when Linux is flushing the dirty pages to disk. Apparently, this heavy write IO interferes with the read IO required when resolving deleted terms to document IDs. To confirm this, I ran the same stress test, but with only adds (no deletions); the reopen delays were then unaffected by the ongoing large merge.<br /><br />So finally the mystery is explained, but, how to fix it?<br /><br />I know I could <a href="http://www.westnet.com/~gsmith/content/linux-pdflush.htm">tune Linux's IO</a>, for example to write more frequently, but I'd rather find a Lucene-only solution since we can't expect most users to tune the OS.<br /><br />One possibility is to make a RAM resident terms dictionary, just for primary-key fields. This could be very compact, for example by using an FST, and should give lookups that never hit disk unless the OS has <a href="http://blog.mikemccandless.com/2011/04/just-say-no-to-swapping.html">frustratingly swapped out your RAM data structures</a>. This can also be separately useful for applications that need fast document lookup by primary key, so someone should at some point build this.<br /><br />Another, lower level idea is to simply rate limit byte/sec written by merges. Since big merges also impact ongoing searches, likely we could help that case as well. To try this out, I made a simple prototype (see <a href="https://issues.apache.org/jira/browse/LUCENE-3203">LUCENE-3202</a>), and then re-ran the same stress test, limiting all merging to 10 MB/sec:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://people.apache.org/~mikemccand/NRTRateLimit.html"><img style="cursor:pointer; cursor:hand;width: 600px; height: 364px;" src="http://3.bp.blogspot.com/-L5r585dC6hY/Tfea4bXMwvI/AAAAAAAAAIE/nNqNU-TomXU/s1600/NRTRateLimit.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5618129354376397554" /></a><br /><br />The optimize now took 3 times longer, and the peak dirty bytes (around 300 MB) is 1/3rd as large, as expected since the IO write rate is limited to 10 MB/sec. But look at the reopen delays: they are now much better contained, averaging around 70 milliseconds while the optimize is running, and dropping to 60 milliseconds once the optimize finishes. I think the ability to limit merging IO is an important feature for Lucene!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5306626649764544993?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-63230379279065424662011-06-07T18:19:00.009-04:002011-06-09T10:03:46.674-04:00Lucene's near-real-time search is fast!Lucene's near-real-time (NRT) search feature, available since 2.9, enables an application to make index changes visible to a new searcher with fast turnaround time. In some cases, such as modern social/news sites (e.g., <a href="http://linkedin.com/">LinkedIn</a>, <a href="http://twitter.com/">Twitter</a>, <a href="http://facebook.com/">Facebook</a>, <a href="http://stackoverflow.com/">Stack Overflow</a>, <a href="http://news.ycombinator.com/">Hacker News</a>, <a href="http://dzone.com/">DZone</a>, etc.), fast turnaround time is a hard requirement.<br /><br />Fortunately, it's trivial to use. Just open your initial NRT reader, like this:<br /><tt><br /> // w is your IndexWriter<br /> IndexReader r = IndexReader.open(w, true);<br /></tt><br />(That's the 3.1+ API; prior to that use <tt>w.getReader()</tt> instead).<br /><br />The returned reader behaves just like one opened with <tt>IndexReader.open</tt>: it exposes the point-in-time snapshot of the index as of when it was opened. Wrap it in an <tt>IndexSearcher</tt> and search away!<br /><br />Once you've made changes to the index, call <tt>r.reopen()</tt> and you'll get another NRT reader; just be sure to close the old one.<br /><br />What's special about the NRT reader is that it searches uncommitted changes from <tt>IndexWriter</tt>, enabling your application to decouple fast turnaround time from index durability on crash (i.e., how often <tt>commit</tt> is called), something not previously possible.<br /><br />Under the hood, when an NRT reader is opened, Lucene flushes indexed documents as a new segment, applies any buffered deletions to in-memory bit-sets, and then opens a new reader showing the changes. The reopen time is in proportion to how many changes you made since last reopening that reader.<br /><br />Lucene's approach is a nice compromise between <a href="http://en.wikipedia.org/wiki/Immediate_consistency">immediate consistency</a>, where changes are visible after each index change, and <a href="http://en.wikipedia.org/wiki/Eventual_consistency">eventual consistency</a>, where changes are visible "later" but you don't usually know exactly when.<br /><br />With NRT, your application has <em>controlled consistency</em>: you decide exactly when changes must become visible.<br /><br />Recently there have been some good improvements related to NRT:<ul><li> New default merge policy, <a href="http://blog.mikemccandless.com/2011/02/visualizing-lucenes-segment-merges.html"><tt>TieredMergePolicy</tt></a>, which is able to select more efficient non-contiguous merges, and favors segments with more deletions.<br /><br /> <li> <tt>NRTCachingDirectory</tt> takes load off the IO system by caching small segments in RAM (<a href="https://issues.apache.org/jira/browse/LUCENE-3092">LUCENE-3092</a>).<br /><br /> <li> When you open an NRT reader you can now optionally specify that deletions do not need to be applied, making reopen faster for those cases that can tolerate temporarily seeing deleted documents returned, or have some other means of filtering them out (<a href="https://issues.apache.org/jira/browse/LUCENE-2900">LUCENE-2900</a>).<br /><br /> <li> Segments that are 100% deleted are now dropped instead of inefficiently merged (<a href="https://issues.apache.org/jira/browse/LUCENE-2010">LUCENE-2010</a>).<br /></ul><br /><b>How fast is NRT search?</b><br /><br />I created a <a href="http://code.google.com/a/apache-extras.org/p/luceneutil/source/browse/perf/NRTPerfTest.java">simple performance test</a> to answer this. I first built a starting index by indexing all of Wikipedia's content (25 GB plain text), broken into 1 KB sized documents.<br /><br />Using this index, the test then reindexes all the documents again, this time at a fixed rate of 1 MB/second plain text. This is a very fast rate compared to the typical NRT application; for example, it's almost twice as fast as <a href="http://blog.twitter.com/2011/02/superbowl.html">Twitter's recent peak during this year's superbowl</a> (4,064 tweets/second), assuming every tweet is 140 bytes, and assuming Twitter indexed all tweets on a single shard.<br /><br />The test uses <tt>updateDocument</tt>, replacing documents by randomly selected ID, so that Lucene is forced to apply deletes across all segments. In addition, 8 search threads run a fixed <tt>TermQuery</tt> at the same time.<br /><br />Finally, the NRT reader is reopened once per second.<br /><br />I ran the test on modern hardware, a 24 core machine (dual x5680 Xeon CPUs) with an <a href="http://www.ocztechnology.com/ocz-vertex-3-sata-iii-2-5-ssd.html">OCZ Vertex 3 240 GB SSD</a>, using Oracle's 64 bit <tt>Java 1.6.0_21</tt> and Linux Fedora 13. I gave <tt>Java</tt> a 2 GB max heap, and used <tt>MMapDirectory</tt>.<br /><br />The test ran for 6 hours 25 minutes, since that's how long it takes to re-index all of Wikipedia at a limited rate of 1 MB/sec; here's the resulting QPS and NRT reopen delay (milliseconds) over that time:<br /><br /><a href="http://people.apache.org/~mikemccand/NRTMMap.html" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img boder="0" style="cursor:pointer; cursor:hand;width: 600px; height: 364px;" src="http://3.bp.blogspot.com/-eIz5ug2ef14/Te-ynIR96cI/AAAAAAAAAH0/SvvtFxKp1hA/s1600/NRTMMap.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5615632934752653266" /></a><br /><br />The search QPS is green and the time to reopen each reader (NRT reopen delay in milliseconds) is blue; the graph is an interactive <a href="http://dygraphs.com/">Dygraph</a>, so if you click through above, you can then zoom in to any interesting region by clicking and dragging. You can also apply smoothing by entering the size of the window into the text box in the bottom left part of the graph.<br /><br />Search QPS dropped substantially with time. While annoying, this is expected, because of how deletions work in Lucene: documents are merely marked as deleted and thus are still visited but then filtered out, during searching. They are only truly deleted when the segments are merged. <tt>TermQuery</tt> is a worst-case query; harder queries, such as <tt>BooleanQuery</tt>, should see less slowdown from deleted, but not reclaimed, documents.<br /><br />Since the starting index had no deletions, and then picked up deletions over time, the QPS dropped. It looks like <tt>TieredMergePolicy</tt> should perhaps be even more aggressive in targeting segments with deletions; however, finally around 5:40 a very large merge (reclaiming many deletions) was kicked off. Once it finished the QPS recovered somewhat.<br /><br />Note that a real NRT application with deletions would see a more stable QPS since the index in "steady state" would always have some number of deletions in it; starting from a fresh index with no deletions is not typical.<br /><br /><b>Reopen delay during merging</b><br /><br />The reopen delay is mostly around 55-60 milliseconds (mean is 57.0), which is very fast (i.e., only 5.7% "duty cycle" of the every 1.0 second reopen rate). There are random single spikes, which is caused by Java running a full GC cycle. However, large merges can slow down the reopen delay (once around 1:14, again at 3:34, and then the very large merge starting at 5:40). Many small merges (up to a few 100s of MB) were done but don't seem to impact reopen delay. Large merges have been a challenge in Lucene for some time, also causing trouble for ongoing searching.<br /><br />I'm not yet sure why large merges so adversely impact reopen time; there are several possibilities. It could be simple IO contention: a merge keeps the IO system very busy reading and writing many bytes, thus interfering with any IO required during reopen. However, if that were the case, <tt>NRTCachingDirectory</tt> (used by the test) should have prevented it, but didn't. It's also possible that the OS is [poorly] choosing to evict important process pages, such as the terms index, in favor of IO caching, causing the term lookups required when applying deletes to hit page faults; however, this also shouldn't be happening in my test since I've <a href="http://blog.mikemccandless.com/2011/04/just-say-no-to-swapping.html">set Linux's swappiness to 0</a>.<br /><br />Yet another possibility is Linux's write cache becomes temporarily too full, thus stalling all IO in the process until it clears; in this case perhaps tuning some of Linux's <a href="http://www.westnet.com/~gsmith/content/linux-pdflush.htm">pdflush tunables</a> could help, although I'd much rather find a Lucene-only solution so this problem can be fixed without users having to tweak such advanced OS tunables, even swappiness.<br /><br />Fortunately, we have an active Google Summer of Code student, Varun Thacker, working on enabling <tt>Directory</tt> implementations to pass appropriate flags to the OS when opening files for merging (<a href="https://issues.apache.org/jira/browse/LUCENE-2793">LUCENE-2793</a> and <a href="https://issues.apache.org/jira/browse/LUCENE-2795">LUCENE-2795</a>). From past testing I know that passing O_DIRECT <a href="http://blog.mikemccandless.com/2010/06/lucene-and-fadvisemadvise.html">can prevent merges from evicting hot pages</a>, so it's possible this will fix our slow reopen time as well since it bypasses the write cache.<br /><br />Finally, it's always possible other OSs do a better job managing the buffer cache, and wouldn't see such reopen delays during large merges.<br /><br />This issue is still a mystery, as there are many possibilities, but we'll eventually get to the bottom of it. It could be we should simply add our own IO throttling, so we can control net MB/sec read and written by merging activity. This would make a nice addition to Lucene!<br /><br />Except for the slowdown during merging, the performance of NRT is impressive. Most applications will have a required indexing rate far below 1 MB/sec per shard, and for most applications reopening once per second is fast enough.<br /><br />While there are exciting ideas to bring true real-time search to Lucene, by directly searching <tt>IndexWriter</tt>'s RAM buffer as <a href="http://vimeo.com/16063395">Michael Busch has implemented at Twitter</a> with some cool <a href="http://engineering.twitter.com/2010/10/twitters-new-search-architecture.html">custom extensions to Lucene</a>, I doubt even the most demanding social apps actually truly need better performance than we see today with NRT.<br /><br /><b><tt>NIOFSDirectory</tt> vs <tt>MMapDirectory</tt></b><br /><br />Out of curiosity, I ran the exact same test as above, but this time with <tt>NIOFSDirectory</tt> instead of <tt>MMapDirectory</tt>:<br /><br /><a href="http://people.apache.org/~mikemccand/NRTNIOFS.html" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img border="0" style="cursor:pointer; cursor:hand;width: 600px; height: 364px;" src="http://3.bp.blogspot.com/-sKXoqkywx9U/Te9HMoW7HFI/AAAAAAAAAHs/rNjMNnZugyk/s1600/NRTNIOFS.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5615785542671866962" /></a><br /><br />There are some interesting differences. The search QPS is substantially slower -- starting at 107 QPS vs 151, though part of this could easily be from getting different compilation out of hotspot. For some reason <tt>TermQuery</tt>, in particular, has <a href="http://people.apache.org/~mikemccand/lucenebench/Term.html">high variance</a> from one JVM instance to another.<br /><br />The mean reopen time is slower: 67.7 milliseconds vs 57.0, and the reopen time seems more affected by the number of segments in the index (this is the saw-tooth pattern in the graph, matching when minor merges occur). The takeaway message seems clear: on Linux, use <tt>MMapDirectory</tt> not <tt>NIOFSDirectory</tt>!<br /><br /><b>Optimizing your NRT turnaround time</b><br /><br />My test was just one datapoint, at a fixed fast reopen period (once per second) and at a high indexing rate (1 MB/sec plain text). You should test specifically for your use-case what reopen rate works best. Generally, the more frequently you reopen the faster the turnaround time will be, since fewer changes need to be applied; however, frequent reopening will reduce the maximum indexing rate.<br /><br />Most apps have relatively low required indexing rates compared to what Lucene can handle and can thus pick a reopen rate to suit the application's turnaround time requirements.<br /><br />There are also some simple steps you can take to reduce the turnaround time:<ul><li> Store the index on a fast IO system, ideally a modern SSD.<br /><br /> <li> Install a merged segment warmer (see <tt>IndexWriter.setMergedSegmentWarmer</tt>). This warmer is invoked by <tt>IndexWriter</tt> to warm up a newly merged segment without blocking the reopen of a new NRT reader. If your application uses Lucene's <tt>FieldCache</tt> or has its own caches, this is important as otherwise that warming cost will be spent on the first query to hit the new reader.<br /><br /> <li> Use only as many indexing threads as needed to achieve your required indexing rate; often 1 thread suffices. The fewer threads used for indexing, the faster the flushing, and the less merging (on trunk).<br /><br /> <li> If you are using Lucene's trunk, and your changes include deleting or updating prior documents, then use the <tt>Pulsing</tt> codec for your <tt>id</tt> field since this <a href="http://blog.mikemccandless.com/2010/06/lucenes-pulsingcodec-on-primary-key.html">gives faster lookup performance</a> which will make your reopen faster.<br /><br /> <li> Use the new <tt>NRTCachingDirectory</tt>, which buffers small segments in RAM to take load off the IO system (<a href="https://issues.apache.org/jira/browse/LUCENE-3092">LUCENE-3092</a>).<br /><br /> <li> Pass <tt>false</tt> for <tt>applyDeletes</tt> when opening an NRT reader, if your application can tolerate seeing deleted doccs from the returned reader.<br /><br /> <li> While it's not clear that thread priorities actually work correctly (see <a href="http://www.youtube.com/watch?v=uL2D3qzHtqY">this Google Tech Talk</a>), you should still set your thread priorities properly: the thread reopening your readers should be highest; next should be your indexing threads; and finally lowest should be all searching threads. If the machine becomes saturated, ideally only the search threads should take the hit.<br /></ul><br />Happy near-real-time searching!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6323037927906542466?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com17tag:blogger.com,1999:blog-8623074010562846957.post-90473096066365042782011-05-21T08:49:00.002-04:002011-05-21T09:00:49.799-04:00The invisible Lucene bug fixed pointIt turns out, <a href="http://www.atlassian.com/software/jira/">the Jira issue tracking system</a>, which we make heavy use of here at <a href="http://apache.org">Apache</a>, uses <a href="http://lucene.apache.org">Lucene</a> under the hood for searching and browsing issues. This is wonderful since it means Lucene developers are <a href="http://en.wikipedia.org/wiki/Eating_your_own_dog_food">eating their own dog food</a> whenever they use Jira.<br /><br /><a href="http://www.atlassian.com">Atlassian</a> has opened up some doozy bugs over time, including one of the earliest bug numbers I've ever worked on, <a href="https://issues.apache.org/jira/browse/LUCENE-140">LUCENE-140</a>. They sent me a t-shirt for fixing that one (thank you!).<br /><br />Now, imagine this: what if there were a sneaky bug in Lucene, say a certain text fragment that causes an exception during indexing. A user <a href="https://issues.apache.org/jira/browse/LUCENE">opens an issue</a> to report this, including the problematic text fragment, yet, because Jira uses Lucene, it hits an exception while indexing that fragment and causes this one bug to be un-searchable and un-viewable when browsing! An invisible bug fixed point.<br /><br />It's somewhat mind bending to think about, Lucene recursing on itself through Jira, yet it's theoretically possible! Maybe we have a few of invisible bug fixed points lurking already and nobody knows...<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-9047309606636504278?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-75273787705600924832011-05-07T14:58:00.010-04:002011-05-09T08:51:50.420-04:00265% indexing speedup with Lucene's concurrent flushing<a href="http://blog.mikemccandless.com/2011/04/catching-slowdowns-in-lucene.html">A week ago</a>, I described the <a href="http://people.apache.org/~mikemccand/lucenebench/">nightly benchmarks</a> we use to catch any unexpected slowdowns in Lucene's performance. Back then the graphs were rather boring (a good thing), but, not anymore! Have a look at the <a href="http://people.apache.org/~mikemccand/lucenebench/indexing.html">stunning jumps in Lucene's indexing rate</a>:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://people.apache.org/~mikemccand/lucenebench/indexing.html"><img style="cursor:pointer; cursor:hand;width: 400px; height: 200px;" src="http://3.bp.blogspot.com/-Se4IoeNW-Cc/Tcet-DxtBfI/AAAAAAAAAHU/IK29w-AV1ag/s400/ConcurrentFlushing.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5604639542963144178" /></a><br /><br />(Click through the image to see details about what changed on dates <b>A</b>, <b>B</b>, <b>C</b> and <b>D</b>).<br /><br />Previously we were around 102 GB of plain text per hour, and now it's about 270 GB/hour. That's a 265% jump! Lucene now indexes all of Wikipedia's <a href="http://en.wikipedia.org/wiki/Wikipedia:Database_download">23.2 GB (English) export</a> in 5 minutes and 10 seconds.<br /><br />How did this happen? <a href="https://issues.apache.org/jira/browse/LUCENE-3023">Concurrent flushing</a>.<br /><br />That new feature, having lived on a branch for quite some time, undergoing many fun iterations, was finally merged back to trunk about a week ago.<br /><br />Before concurrent flushing, whenever <tt>IndexWriter</tt> needed to flush a new segment, it would stop all indexing threads and hijack one thread to perform the rather compute intensive flush. This was a nasty bottleneck on computers with highly concurrent hardware; flushing was inherently single threaded. I <a href="http://blog.mikemccandless.com/2010/09/lucenes-indexing-is-fast.html">previously described the problem here</a>. <br /><br />But with concurrent flushing, each thread freely flushes its own segment even while other threads continue indexing. No more bottleneck!<br /><br />Note that there are two separate jumps in the graph. The first jump, the day concurrent flushing landed (labelled as <b>B</b> on the graph), shows the improvement while using only 6 threads and 512 MB RAM buffer during indexing. Those settings resulted in the fastest indexing rate before concurrent flushing.<br /><br />The second jump (labelled as <b>D</b> on the graph) happened when I increased the indexing threads to 20 and dropped the RAM buffer to 350 MB, giving the fastest indexing rate after concurrent flushing.<br /><br />One nice side effect of concurrent flushing is that you can now use RAM buffers well over 2.1 GB, as long as you use multiple threads. Curiously, I found that larger RAM buffers slow down overall indexing rate. This might be because of the discontinuity when closing <tt>IndexWriter</tt>, when we must wait for all the RAM buffers to be written to disk. It would be better to measure steady state indexing rate, while indexing an effectively infinite content source, and ignoring the startup and ending transients; I suspect if I measured that instead, we'd see gains from larger RAM buffers, but this is just speculation at this point.<br /><br />There were some <b>very</b> challenging changes required to make concurrent flushing work, especially around how <tt>IndexWriter</tt> handles buffered deletes. Simon Willnauer does a great job describing these changes <a href="http://blog.jteam.nl/2011/05/03/lucene-indexing-gains-concurrency/">here</a> and <a href="http://blog.jteam.nl/2011/04/01/gimme-all-resources-you-have-i-can-use-them/">here</a>. Concurrency is tricky!<br /><br />Remember this change only helps you if you have concurrent hardware, you use enough threads for indexing and there's no other bottleneck (for example, in the content source that provides the documents). Also, if your IO system can't keep up then it will bottleneck your CPU concurrency. The nightly benchmark runs on a computer with 12 real (24 with hyperthreading) cores and a fast (OCZ Vertex 3) solid-state disk. Finally, this feature is not yet released: it was committed to Lucene's trunk, which will eventually be released as 4.0.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7527378770560092483?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com1tag:blogger.com,1999:blog-8623074010562846957.post-84182091921714484742011-04-29T14:46:00.005-04:002011-05-01T12:29:20.575-04:00Catching slowdowns in LuceneLucene has <a href="http://blog.mikemccandless.com/2011/03/your-test-cases-should-sometimes-fail.html">great randomized tests</a> to catch functional failures, but when we accidentally commit a performance regression (we slow down indexing or searching), nothing catches us!<br /><br />This is scary, because we want things to get only faster with time.<br /><br />So, when there's a core change that we think may impact performance, we run before/after tests to verify. But this is ad-hoc and error-proned: we could easily forget to do this, or fail to anticipate that a code change might have a performance impact.<br /><br />Even when we do test performance of a change, the slowdown could be relatively small, easily hiding within the unfortunately often substantial noise of our tests. Over time we might accumulate many such small, unmeasurable slowdowns, suffering the fate of the <a href="http://en.wikipedia.org/wiki/Boiling_frog">boiling frog</a>. We do also run performance tests before releasing, but it's better to catch them sooner: solving slowdowns just before releasing is.... dangerous.<br /><br />To address this problem, I've created a <a href="http://code.google.com/a/apache-extras.org/p/luceneutil/source/browse/nightlyBench.py">script</a> that runs standard benchmarks on Lucene's trunk (to be 4.0), nightly. It indexes all of <a href="http://en.wikipedia.org/wiki/Wikipedia:Database_download">Wikipedia's English XML export</a>, three times (with different settings and document sizes), runs a near-real-time (NRT) turnaround time test for 30 minutes, and finally a diverse set of hard queries.<br /><br />This has been running for a few weeks now, and the results are <a href="http://people.apache.org/~mikemccand/lucenebench">accessible to anyone</a>.<br /><br />It's wonderful to see that <a href="http://people.apache.org/~mikemccand/lucenebench/indexing.html">Lucene's indexing throughput</a> is already a bit faster (~98 GB plain text per hour) than when <a href="http://blog.mikemccandless.com/2010/09/lucenes-indexing-is-fast.html">I last measured</a>!<br /><br />Near-real-time reopen latency <a href="http://people.apache.org/~mikemccand/lucenebench/nrt.html">is here</a>; the test measures how long it takes (on average, after discarding outliers) to open a new NRT reader. It's quite intensive, indexing around 1 MB plain text per second as updates (delete+addDocument), and reopening once per second, on the full previously built Wikipedia index.<br /><br />To put this in perspective, that's almost twice <a href="http://www.twitter.com">Twitter's</a> recent peak indexing rate <a href="http://blog.twitter.com/2011/02/superbowl.html">during the 2011 Superbowl</a> (4,064 Tweets/second), although Twitter's use-case is harder because the documents are much smaller, and presumably there's additional indexed metadata beyond just the text of the Tweet. Twitter has actually implemented some cool changes to Lucene to enable real-time searching without reopening readers; Michael Busch describes them <a href="http://engineering.twitter.com/2010/10/twitters-new-search-architecture.html">here</a> and <a href="http://www.lucidimagination.com/events/revolution2010/video-Realtime-Search-With-Lucene-presented-by-Michael-Busch-of-Twitter">here</a>. Some day I hope these will be folded into Lucene!<br /><br />Finally, we test all sorts of queries: <tt>PhraseQuery</tt> (<a href="http://people.apache.org/~mikemccand/lucenebench/Phrase.html">exact</a> and <a href="http://people.apache.org/~mikemccand/lucenebench/SloppyPhrase.html">sloppy</a>), <tt>FuzzyQuery</tt> (edit distance <a href="http://people.apache.org/~mikemccand/lucenebench/Fuzzy1.html">1</a> and <a href="http://people.apache.org/~mikemccand/lucenebench/Fuzzy2.html">2</a>), <a href="http://people.apache.org/~mikemccand/lucenebench/AndHighHigh.html">four</a> <a href="http://people.apache.org/~mikemccand/lucenebench/AndHighMed.html">variants</a> <a href="http://people.apache.org/~mikemccand/lucenebench/OrHighHigh.html">of</a> <a href="http://people.apache.org/~mikemccand/lucenebench/OrHighMed.html"><tt>BooleanQuery</tt></a>, <a href="http://people.apache.org/~mikemccand/lucenebench/IntNRQ.html"><tt>NumericRangeQuery</tt></a>, <a href="http://people.apache.org/~mikemccand/lucenebench/Prefix3.html"><tt>PrefixQuery</tt></a>, <a href="http://people.apache.org/~mikemccand/lucenebench/Wildcard.html"><tt>WildcardQuery</tt></a>, <a href="http://people.apache.org/~mikemccand/lucenebench/SpanNear.html"><tt>SpanNearQuery</tt></a>, and of course <a href="http://people.apache.org/~mikemccand/lucenebench/Term.html"><tt>TermQuery</tt></a>. In addition we test the <a href="http://people.apache.org/~mikemccand/lucenebench/Respell.html">automaton spell checker</a>, and <a href="http://people.apache.org/~mikemccand/lucenebench/PKLookup.html">primary-key lookup</a>.<br /><br />A few days ago, I switched all tests to the very fast 240 GB <a href="http://www.ocztechnology.com/ocz-vertex-3-sata-iii-2-5-ssd.html">OCZ Vertex 3</a> (previously it was a traditional spinning-magnets hard drive). It looks like indexing throughput gained a bit of performance (~102 GB plain text per hour), the search performance was unaffected (expected, because for this test all postings easily fit in available RAM), but the NRT turnaround time saw a drastic reduction in the noise to near-zero. NRT is very IO intensive so it makes sense having a fast IO system improves its turnaround time; I need to dig further into this.<br /><br />Unfortunately, performance results are inherently noisy. For example you can see the large noise (the error band is +/- one standard deviation) in the <a href="http://people.apache.org/~mikemccand/lucenebench/Term.html"><tt>TermQuery</tt> results</a>; other queries seem to have less noise for some reason.<br /><br />So far the graphs are rather boring: nice and flat. This is a good thing!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8418209192171448474?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-74702783197579352222011-04-24T09:05:00.003-04:002011-04-24T11:21:26.706-04:00Just say no to swapping!Imagine you love to cook; it's an intense hobby of yours. Over time, you've accumulated many <a href="http://en.wikipedia.org/wiki/Spice">fun spices</a>, but your pantry is too small, so, you rent an off-site storage facility, and move the less frequently used spice racks there. Problem solved!<br /><br />Suddenly you decide to cook this great new recipe. You head to the pantry to retrieve your <a href="http://en.wikipedia.org/wiki/Saffron">Saffron</a>, but it's not there! It was moved out to the storage facility and must now be retrieved (this is a <a href="http://en.wikipedia.org/wiki/Page_fault">hard page fault</a>).<br /><br />No problem -- your neighbor volunteers to go fetch it for you. Unfortunately, the facility is ~2,900 miles away, all the way across the US, so it takes your friend 6 days to retrieve it!<br /><br />This assumes you normally take 7 seconds to retrieve a spice from the pantry; that your data was in main memory (~100 nanoseconds access time), not in the <a href="http://en.wikipedia.org/wiki/CPU_cache">CPU's caches</a> (which'd be maybe 10 nanoseconds); that your swap file is on a fast (say, <a href="http://en.wikipedia.org/wiki/Western_Digital_Raptor">WD Raptor</a>) spinning-magnets hard drive with 5 millisecond average access time; and that your neighbor drives non-stop at 60 mph to the facility and back.<br /><br />Even worse, your neighbor drives a motorcycle, and so he can only retrieve one spice rack at a time. So, after waiting 6 days for the Saffron to come back, when you next go to the pantry to get some <a href="http://en.wikipedia.org/wiki/Paprika">Paprika</a>, it's also "swapped out" and you must wait another 6 days! It's possible that first spice rack also happened to have the Paprika but it's also likely it did not; that depends on your <a href="http://en.wikipedia.org/wiki/Locality_of_reference">spice locality</a>. Also, with each trip, your neighbor must pick a spice rack to move out to the facility, so that the returned spice rack has a place to go (it is a "swap", after all), so the Paprika could have just been swapped out!<br /><br />Sadly, it might easily be many weeks until you succeed in cooking your dish.<br /><br />Maybe in the olden days, when memory itself was a <a href="http://en.wikipedia.org/wiki/Magnetic-core_memory">core of little magnets</a>, swapping cost wasn't so extreme, but these days, as memory access time has improved drastically while hard drive access time hasn't budged, the disparity is now unacceptable. Swapping has become a <a href="http://www.joelonsoftware.com/articles/LeakyAbstractions.html">badly leaking abstraction</a>. When a typical process (say, your e-mail reader) has to "swap back in" after not being used for a while, it can hit 100s of such page faults, before finishing redrawing its window. It's an awful experience, though it has the fun side effect of letting you see, in slow motion, just what precise steps your email reader goes through when redrawing its window.<br /><br />Swapping is especially disastrous with JVM processes. See, the JVM generally won't do a <a href="http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)">full GC cycle</a> until it has run out of its allowed heap, so most of your heap is likely occupied by not-yet-collected garbage. Since these pages aren't being touched (because they are garbage and thus unreferenced), the OS happily swaps them out. When GC finally runs, you have a ridiculous swap storm, pulling in all these pages only to then discover that they are in fact filled with garbage and should be discarded; this can easily make your GC cycle take many minutes!<br /><br />It'd be better if the JVM could work more closely with the OS so that GC would somehow run on-demand whenever the OS wants to start swapping so that, at least, we never swap out garbage. Until then, make sure you don't set your JVM's heap size too large!<br /><br /><br /><b>Just use an <a href="http://en.wikipedia.org/wiki/Solid-state_drive">SSD</a>...</b><br /><br />These days, many machines ship with <a href="http://en.wikipedia.org/wiki/Solid-state_drive">solid state disks</a>, which are an astounding (though still costly) improvement over spinning magnets; once you've used an SSD you can never go back; it's just one of life's many one-way doors.<br /><br />You might be tempted to declare that this problem is solved, since SSDs are so blazingly fast, right? Indeed, they are orders of magnitudes faster than spinning magnets, but they are still 2-3 orders of magnitude slower than main memory or CPU cache. The typical SSD might have 50 microsends access time, which equates to ~58 total miles of driving at 60 mph. Certainly a huge improvement, but still unacceptable if you want to cook your dish on time!<br /><br /><br /><b>Just add RAM...</b><br /><br />Another common workaround is to put lots of RAM in your machine, but this can easily back-fire: operating systems will happily swap out memory pages in favor of caching IO pages, so if you have any processes accessing lots of bytes (say, mencoder encoding a 50 GB bluray movie, maybe a virus checker or backup program, or even Lucene searching against a large index or doing a large merge), the OS will swap your pages out. This then means that the more RAM you have, the more swapping you get, and the problem only gets worse!<br /><br />Fortunately, some OS's let you control this behavior: on Linux, you can <a href="http://kerneltrap.org/node/3000">tune swappiness down to 0</a> (most Linux distros default this to a highish number); Windows also has a checkbox, under My Computer -> Properties -> Advanced -> Performance Settings -> Advanced -> Memory Usage, that lets you favor Programs or System Cache, that's likely doing something similar.<br /><br />There are <a href="http://linux.die.net/man/2/madvise">low-level</a> <a href="http://linux.die.net/man/2/fadvise">IO flags</a> that these programs are supposed to use so that the OS knows not to cache the pages they access, but sometimes the processes fail to use them or cannot use them (for example, they are <a href="http://blog.mikemccandless.com/2010/06/lucene-and-fadvisemadvise.html">not yet exposed to Java</a>), and even if they do, sometimes the OS <a href="http://blog.mikemccandless.com/2010/06/lucene-and-fadvisemadvise.html">ignores them</a>!<br /><br /><br /><b>When swapping is OK</b><br /><br />If your computer never runs any interactive processes, ie, a process where a human is blocked (waiting) on the other end for something to happen, and only runs batch processes which tend to be active at different times, then swapping can be an overall win since it allows that process which is active to make nearly-full use of the available RAM. Net/net, over time, this will give greater overall throughput for the batch processes on the machine.<br /><br />But, remember that the server running your web-site is an interactive process; if your server processes (web/app server, database, search server, etc.) are stuck swapping, your site has for all intents and purposes become unusable to your users.<br /><br /><br /><b>This is a fixable problem</b><br /><br />Most processes have known data structures that consume substantial RAM, and in many cases these processes could easily discard and later regenerate their data structures in much less time than even a single page fault. Caches can simply be pruned or discarded since they will self-regenerate over time.<br /><br />These data structures should never be swapped out, since regeneration is far cheaper. Somehow the OS should ask each RAM-intensive and least-recently-accessed process to discard its data structures to free up RAM, instead of swapping out the pages occupied by the data structure. Of course, this would require a tighter interaction between the OS and processes than exists today; Java's <a href="http://download.oracle.com/javase/1.4.2/docs/api/java/lang/ref/SoftReference.html"><tt>SoftReference</tt></a> is close, except this only works within a single JVM, and does not interact with the OS.<br /><br /><br /><b>What can you do?</b><br /><br />Until this problem is solved for real, the simplest workaround is to disable swapping entirely, and stuff as much RAM as you can into the machine. RAM is cheap, memory modules are dense, and modern motherboards accept many modules. This is what I do.<br /><br />Of course, with this approach, when you run out of RAM stuff will start failing. If the software is well written, it'll fail gracefully: your browser will tell you it cannot open a new window or visit a new page. If it's poorly written it will simply crash, thus quickly freeing up RAM and hopefully not losing any data or corrupting any files in the process. Linux takes the <a href="http://linux-mm.org/OOM_Killer">simple draconian approach of picking a memory hogging process and SIGKILL'ing it</a>.<br /><br />If you don't want to disable swapping you should at least tell the OS not to swap pages out for IO caching.<br /><br />Just say no to swapping!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7470278319757935222?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com4tag:blogger.com,1999:blog-8623074010562846957.post-1167624243304334522011-03-31T06:32:00.002-04:002011-03-31T06:49:03.642-04:00A login-wall is nearly as bad as a pay-wall!<a href="http://www.businessinsider.com/exclusive-qa-quora-may-be-turning-down-billion-dollar-offers-but-its-still-losing-to-this-guy-2011-2">Much</a> has been <a href="http://www.techfounder.net/2011/02/01/my-take-on-quora-vs-stackoverflow-or-substance-vs-social/">said</a> and <a href="http://meta.stackoverflow.com/questions/44618/what-can-we-learn-from-quora">asked</a> about <a href="http://socialcompare.com/en/comparison/compare-question-answer-sites-quora-vs-yahoo-answers-vs-stackoverflow-vs-ted-conversations">the differences</a> between <a href="http://stackoverflow.com">Stack Overflow</a> and <a href="http://quora.com">Quora</a>.<br /><br />And, while there are deep and interesting differences, such as how Stack Overflow makes <a href="http://stackoverflow.com/faq">reputation tracking</a> and <a href="http://meta.stackoverflow.com/questions/17853/how-do-badges-work">badges</a> explicit, in my opinion, one simple difference is the most important of all: Quora's login-wall.<br /><br />See, you cannot do anything with Quora until you've registered, while with Stack Overflow you can do almost everything without registering. They are polar opposites!<br /><br />Like everyone else, I have too much curiosity and too little time. I try to keep up on <a href="http://news.ycombinator.com">Hacker News</a> (sorry <a href="http://digg.com">Digg</a> and <a href="http://reddit.com">Reddit</a>): I click through to the cool stuff, and then move on. You have one precious first page impression to rope me in, so don't spend that impression with a login-wall!<br /><br />I mean, sure, I'm still going to go link up my <a href="http://facebook.com">Facebook</a> account so I can login to Quora and see the questions, answers, conversations. (And, yes, Facebook seems to be winning at the "universal ID" game, even though I like <a href="http://openid.net">OpenID</a> better.) Still, for each persistent user like me, you've lost 9 non-persistent ones with that dreaded login-wall.<br /><br />Remember: if you are are a new cool Web site, gaining value from the <a href="http://en.wikipedia.org/wiki/Network_effect">network effect</a> (as all social sites do), trying to eek out just a tiny slice of all these fickle users jumping around out here, don't put up a login-wall! It's just about <a href="http://www.techdirt.com/articles/20090707/0207585464.shtml">as bad as a paywall</a>. Let brand new users do as much as possible with your site, and make that very first page impression count.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-116762424330433452?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-90165389417322189502011-03-26T08:44:00.003-04:002011-03-26T12:49:57.317-04:00Your test cases should sometimes fail!I'm an avid subscriber of the delightful weekly (sometimes) Python-URL! email, highlighting the past week's interesting discussions across the numerous <a href="http://mail.python.org/mailman/listinfo">Python lists</a>. Each summary starts with the best quote from the week; here's <a href="http://groups.google.com/group/comp.lang.python/browse_thread/thread/a5c7bd62047263e0/036e2be279cb78f9?lnk=raot&fwc=2">last week's quote</a>:<blockquote>"So far as I know, that actually just means that the test suite is insufficient." - Peter Seebach, when an application passes all its tests.</blockquote>I wholeheartedly agree: if your build always passes its tests, that means your tests are not tough enough! Ideally the tests should stay ahead of the software, constantly pulling you forwards to improve its quality. If the tests keep passing, write new ones that fail! Or make existing ones evil-er.<br /><br />You'll be glad to know that Lucene/Solr's tests do sometimes fail, as you can see in the <a href="http://jenkins-ci.org/content/hudsons-future"><del>Hudson</del></a> Jenkins <a href="https://hudson.apache.org/hudson/job/Lucene-Solr-tests-only-trunk">automated trunk builds</a>.<br /><br /><br /><b>Randomized testing</b><br /><br />Our test infrastructure has gotten much better, just over the past 6 months or so, through heavy use of randomization.<br /><br />When a test needs a <tt>Directory</tt> instance, but doesn't care which, it uses the <tt>newDirectory</tt> method. This method picks one of Lucene's <tt>Directory</tt> implementations (<tt>RAMDirectory</tt>, <tt>NIOFSDirectory</tt>, <tt>MMapDirectory</tt>, etc.) and then wraps it with <tt>MockDirectoryWrapper</tt>, a nice little class that does all sorts of fun things like: occasionally calling <tt>Thread.yield</tt>; preventing still-open files from being overwritten or deleted (acts-like-Windows); refusing to write to the same file twice (verifying Lucene is in fact write-once); breaking up a single <tt>writeBytes</tt> into multiple calls; optionally throwing <tt>IOException</tt> on disk full, or simply throwing exceptions at random times; simulating an OS/hardware crash by randomly corrupting un-<tt>sync</tt>'d files in devilish ways; etc. We pick a timezone and locale.<br /><br />To randomize indexing, we create a <tt>IndexWriterConfig</tt>, tweaking all sorts of settings, and use <tt>RandomIndexWriter</tt> (like <tt>IndexWriter</tt>, except it sometimes optimizes, commits, yields, etc.). The <tt>newField</tt> method enables or disables stored fields and term vectors. We create random codecs, per field, by combining a terms dictionary with a random terms index and postings implementations. <tt>MockAnalyzer</tt> injects payloads into its tokens.<br /><br />Sometimes we use the <tt>PreFlex</tt> codec, to writes all indices in the 3.x format (so that we test index backwards compatibility), and sometimes the nifty <a href="http://blog.mikemccandless.com/2010/10/lucenes-simpletext-codec.html">SimpleText codec</a>. We have exotic methods for creating random yet somewhat realistic full Unicode strings. When creating an <tt>IndexSearcher</tt>, we might use threads (pass an <tt>ExecutorService</tt>), or not. We catch tests that leave threads running, or that cause <a href="http://lucene.apache.org/java/3_0_3/api/core/org/apache/lucene/util/FieldCacheSanityChecker.Insanity.html">insanity</a> in the <tt>FieldCache</tt> (for example by loading both parent and sub readers).<br /><br /><br /><b>Reproducibility</b><br /><br />To ensure a failure is reproducible, we save the random seeds and on a failure print out a nice line like this: <blockquote><tt><nobr>NOTE: reproduce with: ant test</nobr> <nobr>-Dtestcase=TestFieldCacheTermsFilter</nobr> <nobr>-Dtestmethod=testMissingTerms</nobr> <nobr>-Dtests.seed=-1046382732738729184:5855929314778232889</nobr></tt></blockquote> This fixes the seed so that the test runs deterministically. Sometimes, horribly, we have bugs in this seed logic, thus causing tests to <b>not</b> run deterministically and we scramble to fix those bugs first!<br /><br />If you happen to hit a test failure, please send that precious line to the dev list! This is like the <a href="http://setiathome.berkeley.edu">Search for Extraterrestrial Intelligence (SETI)</a>: there are some number of random seeds out there (hopefully, not too many!), that will lead to a failure, and if your computer is lucky enough to discover one of these golden seeds, please share the discovery!<br /><br />The merging of Lucene and Solr's development was also a big step forward for test coverage, since every change in Lucene is now tested against all of Solr's test cases as well.<br /><br />Tests accept a multiplier to crank things up, causing them to use more test documents or iterations, run for longer time, etc. We now have perpetual jobs on Jenkins, for both 3.x and trunk, launching every 15 minutes with multiplier 5. We know quickly when someone breaks the build!<br /><br />This added test coverage has already caught a number of sneaky bugs (including a <a href="https://issues.apache.org/jira/browse/LUCENE-2593">rare index corruption case on disk-full</a> and a <a href="https://issues.apache.org/jira/browse/LUCENE-2627">chunking bug in <tt>MMapDirectory</tt></a>) that we otherwise would not have discovered for some time.<br /><br />The test infrastructure itself is so useful that it's now been <a href="https://issues.apache.org/jira/browse/LUCENE-2609">factored out as a standalone JAR</a> so apps using Lucene can tap into it to create their own fun randomized tests.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-9016538941732218950?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-55727354106315061512011-03-24T09:16:00.011-04:002011-03-26T06:05:05.358-04:00Lucene's FuzzyQuery is 100 times faster in 4.0There are many exciting improvements in Lucene's eventual 4.0 (trunk) release, but the awesome speedup to <tt>FuzzyQuery</tt> really stands out, not only from its incredible gains but also because of the amazing behind-the-scenes story of how it all came to be.<br /><br /><tt>FuzzyQuery</tt> matches terms "close" to a specified base term: you specify an allowed maximum <a href="http://en.wikipedia.org/wiki/Levenshtein_distance">edit distance</a>, and any terms within that edit distance from the base term (and, then, the docs containing those terms) are matched.<br /><br />The <tt>QueryParser</tt> syntax is <tt>term~</tt> or <tt>term~N</tt>, where <tt>N</tt> is the maximum allowed number of edits (for older releases <tt>N</tt> was a confusing float between <tt>0.0</tt> and <tt>1.0</tt>, which translates to an equivalent max edit distance through a tricky formula).<br /><br /><tt>FuzzyQuery</tt> is great for matching proper names: I can search for <tt>mcandless~1</tt> and it will match <tt>mccandless</tt> (insert <tt>c</tt>), <tt>mcandles</tt> (remove <tt>s</tt>), <tt>mkandless</tt> (replace <tt>c</tt> with <tt>k</tt>) and a great many other "close" terms. With max edit distance 2 you can have up to 2 insertions, deletions or substitutions. The score for each match is based on the edit distance of that term; so an exact match is scored highest; edit distance 1, lower; etc.<br /><br />Prior to 4.0, <tt>FuzzyQuery</tt> took the simple yet horribly costly brute force approach: it visits every single unique term in the index, computes the edit distance for it, and accepts the term (and its documents) if the edit distance is low enough.<br /><br /><br /><b>The journey begins</b><br /><br />The long journey began when <a href="http://rcmuir.wordpress.com/">Robert Muir</a> had the idea of pre-building a <a href="http://en.wikipedia.org/wiki/Levenshtein_automaton">Levenshtein Automaton</a>, a deterministic automaton (DFA) that accepts only the terms within edit distance <tt>N</tt>. Doing this, up front, and then intersecting that automaton with the terms in the index, should give a massive speedup, he reasoned.<br /><br />At first he built a simple prototype, explicitly unioning the separate DFAs that allow for up to <tt>N</tt> insertions, deletions and substitutions. But, unfortunately, just building that DFA (let alone then intersecting it with the terms in the index), was too slow.<br /><br />Fortunately, after some Googling, he discovered <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652">a paper</a>, by Klaus Schulz and Stoyan Mihov (now famous among the Lucene/Solr committers!) detailing an efficient algorithm for building the Levenshtein Automaton from a given base term and max edit distance. All he had to do is code it up! It's just software after all. Somehow, he roped <a href="http://www.lucidimagination.com/blog/author/markmiller">Mark Miller</a>, another Lucene/Solr committer, into helping him do this.<br /><br />Unfortunately, the paper was nearly unintelligible! It's 67 pages, filled with all sorts of equations, Greek symbols, definitions, propositions, lemmas, proofs. It uses scary concepts like Subsumption Triangles, along with beautiful yet still unintelligible diagrams. Really the paper may as well have been written in Latin.<br /><br />Much coffee and beer was consumed, sometimes simultaneously. Many hours were spent on IRC, staying up all night, with Mark and Robert carrying on long conversations, which none of the rest of us could understand, trying desperately to decode the paper and turn it into Java code. Weeks went by like this and they actually had made some good initial progress, managing to loosely crack the paper to the point where they had a test implementation of the <tt>N=1</tt> case, and it seemed to work. But generalizing that to the <tt>N=2</tt> case was... daunting.<br /><br /><br /><b>The breakthrough</b><br /><br />Then, finally, a breakthrough! Robert found, after even more Googling, an existence proof, in an unexpected place: an open-source package, <a href="http://sites.google.com/site/rrettesite/moman">Moman</a>, under the generous <a href="http://en.wikipedia.org/wiki/MIT_License">MIT license</a>. The author, <a href="http://www.linkedin.com/pub/jean-philippe-barrette-lapierre/5/21/ab3">Jean-Phillipe Barrette-LaPierre</a>, had somehow, incredibly, magically, quietly, implemented the algorithm from this paper. And this was apparently a random side project for him, unrelated to his day job. So now we knew it was possible (and we all have deep admiration for Jean-Phillipe!).<br /><br />We decided to simply re-use Moman's implementation to accomplish our goals. But, it turns out, its source code is all <a href="http://www.python.org">Python</a> (my favorite programming language)! And, nearly as hairy as the paper itself. Nevertheless, we pushed on.<br /><br />Not really understanding the Python code, and also neither the paper, we desperately tried to write our own Python code to tap into the various functions embedded in Moman's code, to auto-generate Java code containing the necessary tables for each max edit distance case (<tt>N=1</tt>, <tt>N=2</tt>, etc.). We had to guess what each Python function did, by its name, trying to roughly match this up to the spooky terminology in the paper.<br /><br />The result was <a href="https://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/createLevAutomata.py">createLevAutomata.py</a>: it auto-generates crazy looking Java code (see <a href="https://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev2ParametricDescription.java">Lev2ParametricDescription.java</a>, and scroll to the cryptic packed tables at the bottom), which in turn is used by <a href="https://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java">further Java code</a> to create the Levenshtein automaton per-query. We only generate the <tt>N=1</tt> and <tt>N=2</tt> cases (the <tt>N>=3</tt> cases aren't really practical, at least not yet).<br /><br /><br /><b>The last bug...</b><br /><br />Realize, now, what a crazy position we were in. We wrote our own scary Python code, tapping into various functions in the Moman package, to auto-generate unreadable Java code with big tables of numbers, which is then used to generate Levenshtein automata from the base term and <tt>N</tt>. We went through many iterations with this crazy chain of Python and Java code that we barely understood, slowly iterating to get the bugs out.<br /><br />After fixing many problems, we still had one persistent bug which we just couldn't understand, let alone fix. We struggled for several days, assuming the bug was in our crazy Python/Java chain. Finally, we considered the possibility that the bug was in Moman, and indeed Robert managed to reduce the problem to a tiny Python-only case showing where Moman failed to match the right terms. Robert sent this example to Jean-Phillipe, who quickly confirmed the bug and posted <a href="http://groups.google.com/group/moman/browse_thread/thread/16c09d659242c142">a patch</a> the next day. We applied his patch and suddenly everything was working perfectly!<br /><br />Fortunately, while this fast <tt>FuzzyQuery</tt> was unbelievably hairy to implement, testing it well is relatively easy since we can validate it against the brute-force enumeration from <tt>3.0</tt>. We have several tests verifying the different layers executed by the full <tt>FuzzyQuery</tt>. The tests are exhaustive in that they test all structurally different cases possible in the Levenshtein construction, using a binary (only characters <tt>0</tt> and <tt>1</tt>) terms.<br /><br />Beyond just solving this nearly impossible task of efficiently compiling a term to a Levenshtein Automaton, we had many other parts to fill in. For example, Robert separately created a general <tt>AutomatonQuery</tt>, re-using infrastructure from the open-source <a href="http://www.brics.dk/automaton/">Brics</a> automaton package, to enable fast intersection of an automaton against all terms and documents in the index. This query is now used to handle <tt>WildcardQuery</tt>, <tt>RegexpQuery</tt>, and <tt>FuzzyQuery</tt>. It's also useful for custom cases, too; for example it's used by <a href="http://lucene.apache.org/solr/">Solr</a> to reverse wildcard queries. <a href="http://www.slideshare.net/otisg/finite-state-queries-in-lucene">These slides from Robert</a> describe <tt>AutomatonQuery</tt>, and its fun possible use case, in more detail.<br /><br />Separately, we had an impedance mismatch: these automatons speak full unicode (<tt>UTF32</tt>) characters, yet Lucene's terms are stored in <tt>UTF8</tt> bytes, so we had to create a <tt>UTF32 -> UTF8</tt> automaton converter, which by itself was also very hairy! That converter translates any <tt>UTF32</tt> automaton into an equivalent <tt>UTF8</tt> Levenshtein automaton, which can be directly intersected against the terms in the index.<br /><br />So, today, when you run a <tt>FuzzyQuery</tt> in 4.0, it efficiently seeks and scans only those regions of the term space which may have matches, guided by the Levenshtein automaton. This, coupled with ongoing performance improvements to seeking and scanning terms, as well as other major improvements like <a href="https://issues.apache.org/jira/browse/LUCENE-2690">performing MultiTermQuery rewrites per-segment</a>, has given us the astounding overall gains in <tt>FuzzyQuery</tt>.<br /><br />Thanks to these enormous performance improvements, Robert has created an entirely <a href="https://issues.apache.org/jira/browse/LUCENE-2507">new automaton spell checker</a> that uses this same algorithm to find candidate terms for respelling. This is just like <tt>FuzzyQuery</tt>, except it doesn't visit the matching documents. This is a big improvement over the <a href="http://lucene.apache.org/java/3_0_1/api/contrib-spellchecker/index.html">existing spellchecker</a> as it does not require a separate spellchecker index be maintained.<br /><br />This whole exciting experience is a great example of why open-source development works so well. Here we have diverse committers from Lucene/Solr, bringing together their various unusual strengths (automatons, Unicode, Python, etc.) to bear on an insanely hard challenge, leveraging other potent open-source packages including Moman and Brics, iterating with the authors of these packages to resolve bugs. No single person involved in this really understands all of the parts; it's truly a team effort.<br /><br />And now you know what's going on under the hood when you see incredible speedups with <tt>FuzzyQuery</tt> in 4.0!<br /><br />[For the not-faint-of-heart, you can browse <a href="https://issues.apache.org/jira/browse/LUCENE-1606">LUCENE-1606</a> to see parts of this story unfolding through Jira]<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5572735410631506151?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com35tag:blogger.com,1999:blog-8623074010562846957.post-24639372994277839762011-03-11T15:25:00.004-05:002011-03-30T13:46:58.775-04:00Hack on Lucene this summer!Are you a student? Looking to do some fun coding this summer? Then join us for the 2011 <a href="http://wiki.apache.org/lucene-java/SummerOfCode2011">Google Summer of Code</a>!<br /><br />The application deadline is in <a href="http://www.google-melange.com/document/show/gsoc_program/google/gsoc2011/faqs#timeline">less than a month</a>! Lucene has these <a href="https://issues.apache.org/jira/secure/IssueNavigator.jspa?reset=true&jqlQuery=labels+%3D+lucene-gsoc-11">initial<br />potential projects</a> identified, but you can also pick your own; just be sure to discuss with the community first (send an email to <a href="mailto:dev@lucene.apache.org">dev@lucene.apache.org</a>).<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2463937299427783976?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-25152213509874744932011-02-12T11:35:00.007-05:002011-02-12T12:45:29.647-05:00So many iciclesIt's that cold time of year again -- that's right, <a href="http://en.wikipedia.org/wiki/Winter">winter</a>! We have lots of snow, freezing temperatures, and... incredible <a href="http://en.wikipedia.org/wiki/Icicle">icicles</a> hanging off houses:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/-eFTmeUabVB0/TVa3Lr5R7KI/AAAAAAAAAFs/sj43J-rVTCg/s1600/5.jpg"><img style="cursor:pointer; cursor:hand;width: 600px; height: 389px;" src="http://4.bp.blogspot.com/-eFTmeUabVB0/TVa3Lr5R7KI/AAAAAAAAAFs/sj43J-rVTCg/s1600/5.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5572843000306986146" /></a><br /><br />Conditions have to be just right for these icicles to form. First, you need lots of snow accumulated on roofs. Second, you need below-freezing temperatures for many days in a row. Finally, of course, you need a house that loses lots of heat through its attic/roof.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/-i_9o4ifSbzE/TVa4J2HQ7KI/AAAAAAAAAF0/ZPTv77JSeHg/s1600/3.jpg"><img style="cursor:pointer; cursor:hand;width: 600px; height: 387;" src="http://4.bp.blogspot.com/-i_9o4ifSbzE/TVa4J2HQ7KI/AAAAAAAAAF0/ZPTv77JSeHg/s1600/3.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5572844068201884834" /></a><br /><br />These icicles are an easy way to spot houses that waste heat, something that's otherwise not normally easy to detect! In the winter, here in New England, such houses stand out very clearly.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/-YJddixPZam8/TVa4dnPl4qI/AAAAAAAAAF8/8qqSQLib7ic/s1600/1.jpg"><img style="cursor:pointer; cursor:hand;width: 548px; height: 600px;" src="http://4.bp.blogspot.com/-YJddixPZam8/TVa4dnPl4qI/AAAAAAAAAF8/8qqSQLib7ic/s1600/1.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5572844407807664802" /></a><br /><br />Of course, roof snow does also melt for legitimate reasons. For example, when the temperature outside moves above freezing, the snow will melt. However, the resulting water simply falls off the roof. It's only when ambient temperature is below freezing, yet the snow is still being melted (from waste heat leaking through the roof) that you get immense icicles. The water dribbles down the roof, under the snow, and upon hitting the roof's edge / gutter overhang, which is not wasting heat, it freezes.<br /><br />Given enough snow, wasted heat, below freezing temperatures, and time, you'll get amazing icicles. I can understand that older homes will have poorer insulation and thus waste heat: standards were more lax back then, and we generally were not as environmentally conscious as we are today. But, when I see massive icicles on new construction, it's disappointing:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/-FmmZRIgxR_M/TVa4n6XBi3I/AAAAAAAAAGE/LwbKkyYgGsM/s1600/2.jpg"><img style="cursor:pointer; cursor:hand;width: 504px; height: 600px;" src="http://1.bp.blogspot.com/-FmmZRIgxR_M/TVa4n6XBi3I/AAAAAAAAAGE/LwbKkyYgGsM/s1600/2.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5572844584737803122" /></a><br /><br />These icicles are very firmly attached to the roof/gutter, since Mother Nature carefully froze them there one drop at a time. However, as pretty as they are, these so-called <a href="http://en.wikipedia.org/wiki/Ice_dam">ice dams</a> can do massive damage. There are all sorts of products and services out there to try to make them go away. But the best solution, of course, is to simply prevent them from developing in the first place, by addressing the root cause: stop wasting heat. You can add insulation to your attic and/or turn down the thermostat.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2515221350987474493?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-76192297870961708902011-02-11T18:46:00.002-05:002011-02-12T10:52:11.642-05:00Visualizing Lucene's segment mergesIf you've ever wondered how Lucene picks segments to merge during indexing, it looks something like this:<br /><br /><iframe title="YouTube video player" width="560" height="349" src="http://www.youtube.com/embed/YW0bOvLp72E?rel=0" frameborder="0" allowfullscreen></iframe><br /><br />That video displays segment merges while indexing the entire <a href="http://en.wikipedia.org/wiki/Wikipedia:Database_download">Wikipedia (English) export</a> (29 GB plain text), played back at ~8X real-time.<br /><br />Each segment is a bar, whose height is the size (in MB) of the segment (log-scale). Segments on the left are largest; as new segments are flushed, they appear on the right. Segments being merged are colored the same color and, once the merge finishes, are removed and replaced with the new (larger) segment. You can see the nice logarithmic staircase pattern that merging creates.<br /><br />By default, using <tt>ConcurrentMergeScheduler</tt>, Lucene executes each merge in a separate thread, allowing multiple merges to run at once without blocking ongoing indexing. The bigger the merge the longer it takes to finish.<br /><br />One simple metric you can use to measure overall merge cost is to divide the total number of bytes read/written for all merging by the final byte size of an index; smaller values are better. This is analogous to the <a href="http://en.wikipedia.org/wiki/Write_amplification">write amplification</a> measure that solid-state disks use, in that your app has written X MB but because of merging and deleted documents overhead, Lucene had to internally read and write some multiple of X. You can think of this write amplification as a tax on your indexing; you don't pay this tax up front, when the document is first indexed, but only later as you continue to add documents to the index. The video shows the total size of the index as well as net bytes merged, so it's easy to compute write amplification for the above run: 6.19 (final index size was 10.87 GB and net bytes copied during merging was 67.30 GB).<br /><br />Proper merge selection is actually a tricky problem, in general, because we must carefully balance not burning CPU/IO (due to inefficient merge choices), while also not allowing too many segments to accumulate in the index, as this slows down search performance. To minimize merge cost, you ideally would merge only equal-sized segments, and merge a larger number of segments at a time.<br /><br />In fact, from the viewpoint of the <tt>MergePolicy</tt>, this is really a game against a sneaky opponent who randomly makes sudden changes to the index, such as flushing new segments or applying new deletions. If the opponent is well behaved, it'll add equal sized, large segments, which are easy to merge well, as was the case in the above video; but that's a really easy game, like playing tic-tack-toe against a 3 year old.<br /><br />This opponent is more like playing a game of chess:<br /><br /><iframe title="YouTube video player" width="640" height="390" src="http://www.youtube.com/embed/ojcpvIY3QgA?rel=0" frameborder="0" allowfullscreen></iframe><br /><br />No more nice looking staircase! This test shows the more challenging near-real-time use case, which calls <tt>updateDocument</tt> (= delete + add) at a high rate and frequently opens a new reader (creating a new segment each time). The dark gray band on top of each segment shows the proportion of deletions in that segment. When you delete a document in Lucene, the bytes consumed by that document are not reclaimed until the segment is merged, and you can see old segments being eroded as new segments are appended to the index. Unfortunately, Lucene's current default <tt>LogByteSizeMergePolicy</tt> struggles to pick good merges against this opponent, often merging irregularly sized segments.<br /><br />The big issue with <tt>LogByteSizeMergePolicy</tt> is that it must pick adjacent segments for merging. However, we recently <a href="https://issues.apache.org/jira/browse/LUCENE-1076">relaxed this longstanding limitation</a>, and I'm working on a new merge policy, <tt>TieredMergePolicy</tt> (currently a patch on <a href="https://issues.apache.org/jira/browse/LUCENE-854">LUCENE-854</a>) to take advantage of this. <tt>TieredMergePolicy</tt> also fixes some other limitations of <tt>LogByteSizeMergePolicy</tt>, such as merge cascading that results in occasionally "inadvertently optimizing" the index as well as the overly coarse control it offers over the maximum segment size.<br /><br /><tt>TieredMergePolicy</tt> first computes the allowed "budget" of how many segments should be in the index, by counting how many steps the "perfect logarithmic staircase" would require given total index size, minimum segment size (floored), <tt>mergeAtOnce</tt>, and a new configuration <tt>maxSegmentsPerTier</tt> that lets you set the allowed width (number of segments) of each stair in the staircase. This is nice because it decouples how many segments to merge at a time from how wide the staircase can be.<br /><br />Whenever the index is over-budget, it selects the best merge. Potential merges are scored with a combination of skew (basically how "equally sized" the segments being merged are), total size (smaller merges are favored), and how many deleted documents will be reclaimed. It also tries to merge to the exact maximum segment size (default 5GB).<br /><br />Here's the same difficult near-real-time test, this time using <tt>TieredMergePolicy</tt> instead:<br /><br /><iframe title="YouTube video player" width="640" height="390" src="http://www.youtube.com/embed/YOklKW9LJNY?rel=0" frameborder="0" allowfullscreen></iframe><br /><br />Note how the segments are now sorted by size, since <tt>TieredMergePolicy</tt> is allowed to merge non-adjacent segments. For the above difficult run, the write amplification for Lucene's current default merge policy (<tt>LogByteSizeMergePolicy</tt>) was 14.49 while the new merge policy (<tt>TieredMergePolicy</tt>) was 13.64, a nice improvement, though not as much as I was expecting. I suspect this is because <tt>TieredMergePolicy</tt> works hard to hit the max segment size (5 GB), resulting in 6 maximum sized segments while <tt>LogByteSizeMergePolicy</tt> had only 3. These numbers are much higher than the 6.19 write amplification from the "easy" merging, since that merging was about as efficient as we can hope for.<br /><br />While <tt>TieredMergePolicy</tt> is a good improvement over <tt>LogByteSizeMergePolicy</tt>, it's still theoretically possible to do even better! In particular, <tt>TieredMergePolicy</tt> is greedy in its decision making: it only looks statically at the index, as it exists right now, and always chooses what looks like the best merge, not taking into account how this merge will affect future merges nor what further changes the opponent is likely to make to the index. This is good, but it's not guaranteed to produce the optimal merge sequence. For any series of changes made by the opponent there is necessarily a corresponding perfect sequence of merges, that minimizes net merge cost while obeying the budget. If instead the merge policy used a search with some lookahead, such as the <a href="http://en.wikipedia.org/wiki/Minimax">Minimax algorithm</a>, it could do a better job setting up more efficient future merges. I suspect this theoretical gain is likely small in practice; but if there are any game theorists out there reading this now, I'd love to be proven wrong!<br /><br />I generated these movies with <a href="http://code.google.com/a/apache-extras.org/p/luceneutil/source/browse/mergeViz.py">this simple Python script</a>. It parses the <tt>infoStream</tt> output from <tt>IndexWriter</tt>, renders one frame at a time, saved as a PNG file in the local file system, using the <a href="http://www.pythonware.com/products/pil">Python Imaging Library</a>, and finally encodes all frames into a video using <a href="http://www.pythonware.com/products/pil/">MEncoder</a> with the <a href="http://www.videolan.org/developers/x264.html">X264</a> codec.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7619229787096170890?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com20tag:blogger.com,1999:blog-8623074010562846957.post-85836466360491860132011-01-08T06:42:00.002-05:002011-01-08T07:12:41.957-05:00Finite State Transducers, Part 2In my <a href="http://chbits.blogspot.com/2010/12/using-finite-state-transducers-in.html">last post</a>, I described a <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698">cool incremental algorithm for building an FST</a> from pre-sorted input/output pairs, and how we're folding it into Lucene.<br /><br />Progress! The patch on <a href="https://issues.apache.org/jira/browse/LUCENE-2792">LUCENE-2792</a> is now committed to Lucene's trunk (eventually 4.0), so that we now use an FST to hold all terms in RAM for the <a href="http://chbits.blogspot.com/2010/10/lucenes-simpletext-codec.html">SimpleText</a> codec.<br /><br />This was a great step forward, and it added the raw low-level infrastructure for building and using FSTs. But, it's really just a toy usage, since the SimpleText codec is not for production use.<br /><br />I'm happy to report even more progress: we finally have a "real" usage for FSTs in Lucene! With <a href="https://issues.apache.org/jira/browse/LUCENE-2843">LUCENE-2843</a> (now committed), we use an FST to hold the terms index in RAM.<br /><br />Many operations in Lucene require looking up metadata for a requested term. This information includes the number of documents containing the term, file pointers into postings files that actually store the docIDs and positions, etc. Because there could be many unique terms, all this term metadata resides on-disk in the terms dictionary file (<tt>_X.tis</tt>).<br /><br />Looking up a term is then a two-step process. First, we consult the terms index, which resides entirely in RAM, to map the requested term to a file pointer in the terms dictionary file. Second, we scan the terms in the on-disk terms dictionary file starting from that file pointer, to look for an exact match.<br /><br />Certain queries, such as <tt>TermQuery</tt>, need only one exact term lookup. Others, such as <tt>FuzzyQuery</tt> or the new, very cool <a href="https://issues.apache.org/jira/browse/LUCENE-2507">automaton spellchecker</a>, which does not require a separate spellchecker index, perform many term lookups (potentially millions).<br /><br />Before <a href="https://issues.apache.org/jira/browse/LUCENE-2843">LUCENE-2843</a>, in trunk, the terms index used packed <tt>byte[]</tt> and <tt>int[]</tt> arrays. In fact, this was already a <a href="http://chbits.blogspot.com/2010/07/lucenes-ram-usage-for-searching.html">huge improvement over the terms index in 3.0</a>, but is still more wasteful than an FST since each term was stored in fully expanded form, while the FST shares common prefixes and suffixes. Getting this working also required adding separate <tt>seekFloor</tt> and <tt>seekCeil</tt> methods to the <tt>FSTEnum</tt> classes (like a <tt>SortedMap<T></tt>).<br /><br />To test this, I indexed the first 10 million 1KB documents derived from <a href="http://en.wikipedia.org/wiki/Wikipedia:Database_download">Wikipedia's English database download</a>. The resulting RAM required for the FST was ~38% - 52% smaller (larger segments see more gains, as the FST "scales up" well). Not only is the RAM required much lower, but term lookups are also faster: the <tt>FuzzyQuery</tt> <tt>united~2</tt> was ~22% faster.<br /><br />This is very much win/win, so we've made this terms index the default for all core codecs (the terms dictionary and terms index are pluggable, so its easy for other codecs to use this as well).<br /><br />There are many other ways we can use FSTs in Lucene, and we've only just scratched the surface here. In fact, FSTs offers such a sizable RAM reduction that I think for many, but not all, apps it'd be realistic to avoid the two-step term lookup process entirely and simply hold the entire terms dictionary in RAM. This should make term lookup intensive queries potentially much faster, though we'd likely have to rework them to use different algorithms optimized for iterating directly through the terms as an FST.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8583646636049186013?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-60160180464564278622010-12-03T11:40:00.009-05:002010-12-07T13:36:58.112-05:00Using Finite State Transducers in Lucene<a href="http://en.wikipedia.org/wiki/Finite_state_transducer">FSTs</a> are finite-state machines that map a term (byte sequence) to an arbitrary output. They also look cool:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://2.bp.blogspot.com/_4pUbN9gxhUI/TPk21wErb9I/AAAAAAAAAFM/dhPcsyo3KV4/s1600/FSTExample.png"><img style="cursor:pointer; cursor:hand;" src="http://2.bp.blogspot.com/_4pUbN9gxhUI/TPk21wErb9I/AAAAAAAAAFM/dhPcsyo3KV4/s400/FSTExample.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5546524713148968914" /></a><br /><br />That FST maps the sorted words <i>mop</i>, <i>moth</i>, <i>pop</i>, <i>star</i>, <i>stop</i> and <i>top</i> to their ordinal number (0, 1, 2, ...). As you traverse the arcs, you sum up the outputs, so <i>stop</i> hits 3 on the <b>s</b> and 1 on the <b>o</b>, so its output ordinal is 4. The outputs can be arbitrary numbers or byte sequences, or combinations, etc. -- it's pluggable.<br /><br />Essentially, an FST is a SortedMap<ByteSequence,SomeOutput>, if the arcs are in sorted order. With the right representation, it requires far less RAM than other SortedMap implementations, but has a higher CPU cost during lookup. The low memory footprint is vital for Lucene since an index can easily have many millions (sometimes, billions!) of unique terms.<br /><br />There's a <a href="http://www.cs.nyu.edu/~mohri/pub/fla.pdf">great deal of theory</a> behind FSTs. They generally support the same operations as <a href="http://en.wikipedia.org/wiki/Finite-state_machine">FSMs</a> (determinize, minimize, union, intersect, etc.). You can also compose them, where the outputs of one FST are intersected with the inputs of the next, resulting in a new FST.<br /><br />There are some nice general-purpose FST toolkits (<a href="http://www.openfst.org/">OpenFst</a> looks great) that support all these operations, but for Lucene I decided to implement <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698">this neat algorithm</a> which incrementally builds up the minimal unweighted FST from pre-sorted inputs. This is a perfect fit for Lucene since we already store all our terms in sorted (unicode) order.<br /><br />The resulting implementation (currently a patch on <a href="https://issues.apache.org/jira/browse/LUCENE-2792">LUCENE-2792</a>) is fast and memory efficient: it builds the 9.8 million terms in a 10 million Wikipedia index in ~8 seconds (on a fast computer), requiring less than 256 MB heap. The resulting FST is 69 MB. It can also build a <a href="http://en.wikipedia.org/wiki/Trie">prefix trie</a>, pruning by how many terms come through each node, with even less memory.<br /><br />Note that because <a href="http://en.wikipedia.org/wiki/Commutativity">addition is commutative</a>, an FST with numeric outputs is not guaranteed to be minimal in my implementation; perhaps if I could generalize the algorithm to a weighted FST instead, which also stores a weight on each arc, that would yield the minimal FST. But I don't expect this will be a problem in practice for Lucene.<br /><br />In the patch I modified the <a href="http://chbits.blogspot.com/2010/10/lucenes-simpletext-codec.html">SimpleText</a> codec, which was loading all terms into a TreeMap mapping the BytesRef term to an int docFreq and long filePointer, to use an FST instead, and all tests pass!<br /><br />There are lots of other potential places in Lucene where we could use FSTs, since we often need map the index terms to "something". For example, the terms index maps to a long file position; the field cache maps to ordinals; the terms dictionary maps to codec-specific metadata, etc. We also have multi-term queries (eg Prefix, Wildcard, Fuzzy, Regexp) that need to test a large number of terms, that could work directly via intersection with the FST instead (many apps could easily fit their entire terms dict in RAM as an FST since the format is so compact). The FST could be used for a key/value store. Lots of fun things to try!<br /><br />Many thanks to <a href="http://www.cs.put.poznan.pl/dweiss/">Dawid Weiss</a> for helping me iterate on this.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6016018046456427862?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-78920889294162429232010-11-03T13:41:00.003-04:002010-11-03T14:07:04.432-04:00Big Fat FiascoI just watched <a href="http://www.fathead-movie.com/index.php/2010/10/28/video-of-the-big-fat-fiasco-speech/">this talk by Tom Naughton</a>, describing the mis-steps and bad science over the years that have tricked us all into believing we should avoid fat and cholesterol in our diet when in fact we should be doing the exact opposite!<br /><br />Tom is an excellent speaker (he's a comedian!), mixing in humor in what is at heart a very sad topic. He details the science that should have led us to conclude that excessive carbs and sugar consumption are in fact the root cause behind heart disease, diabetes and obesity, not fat and cholesterol as we've been incessantly told over the years.<br /><br />He shows how the "Fat Lazy Slob Theory" (also called "calories in minus calories out") so frequently put forth to explain weight gain is in fact wrong, and that instead the root cause is the biochemistry in your body driving you to eat when your blood sugar is too high.<br /><br />Tom's <a href="http://www.amazon.com/dp/B001NRY6R2?tag=fatheadmoviec-20&camp=14573&creative=327641&linkCode=as1&creativeASIN=B001NRY6R2&adid=1V3CT0XHH4P2RPBKRGZF&">documentary movie Fat Head</a>, which is getting great reviews on Amazon, delves into these same topics. I haven't watched it yet but I plan to.<br /><br />So enjoy your butter, cheese, whole milk, eggs (with yolk!!) and cut back on sugars and carbs. And don't drink soda!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7892088929416242923?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-74302106502744329642010-10-25T16:38:00.002-04:002010-10-25T16:53:50.099-04:00Our medical system is a house of cardsI just came across this <a href="http://www.theatlantic.com/magazine/archive/2010/11/lies-damned-lies-and-medical-science/8269/2/">great article</a> about meta-researcher Dr. John Ioannidis. Here's the summary:<br /><br /><i>Much of what medical researchers conclude in their studies is misleading, exaggerated, or flat-out wrong. So why are doctors—to a striking extent—still drawing upon misinformation in their everyday practice? Dr. John Ioannidis has spent his career challenging his peers by exposing their bad science.</i><br /><br />The gist is that modern medical research is deeply flawed and biased such that the "conclusions" that you and I eventually read in the news headlines are often false. I especially love his advice for us all:<br /><br /> <i>Ioannidis suggests a simple approach: ignore them all</i><br /><br />This is in fact my approach! I have a simple rule: if it tastes good it's good for you. So I eat plenty of fat, salt, sugar, cholesterol, carbs, etc. I love eggs and cheese and I always avoid low-fat or low-cholesterol foods. I get lots of sun and never use sun screen. I drink coffee and beer, daily. I drink lots of water. I get daily exercise, running and walking. And I avoid hand sanitizers like Purell (I believe commonplace dirt/germs are in fact natural and good for you). I strongly believe humans do not need pills to stay healthy. I don't take a daily vitamin. And I'm very healthy!<br /><br />This <a href="http://discovermagazine.com/2005/nov/dialogue-abramson">short interview</a> between Discover Magazine and Harvard clinician John Abramson echoes the same core problem. Here's a choice quote:<br /><br /><i>When you look at the highest quality medical studies, the odds that a study will favor the use of a new drug are 5.3 times higher for commercially funded studies than for noncommercially funded studies.</i><br /><br />Unfortunately, the medical world has a deep, deep conflict of interest: healthy people do not generate profits. Capitalism is a horrible match to health care.<br /><br />So, next time your doctor prescribes a fancy new cool-sounding powerful drug like Alevia or Omosia or Nanotomopia or whatever, try to remember that our medical system is really built on a house of cards. Your doctor, let alone you, cannot possibly differentiate what's true from what's false. Don't trust that large triple-blind random controlled trial that supposedly validated this cool new drug. You are the guinea pig! And it's only when these drugs cause all sorts of problems once they are really tested on the population at large that their true colors are revealed.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7430210650274432964?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-92084912858849103802010-10-17T14:22:00.003-04:002010-10-25T16:55:10.202-04:00Pics from BBQ after Lucene RevolutionI finally pulled the pics off my camera from last week's BBQ after Lucene Revolution in Boston, where much fun was had! See them <a href="http://picasaweb.google.com/mikemccand/BBQLuceneRevolutionOct2010">here</a>. It was awesome to finally meet everyone!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-9208491285884910380?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-28525736462724255372010-10-09T14:20:00.003-04:002010-10-10T14:41:18.379-04:00Fun with flexible indexingThe <a href="http://lucenerevolution.com">Lucene Revolution</a> conference just wrapped up yesterday. It was well attended (~300 or so people). It was great fun to hear about all the diverse ways that Lucene and Solr are being used in the real world.<br /><br />I gave a talk about flexible indexing, coming in the next major release of Lucene (4.0). Slides are <a href="http://www.box.net/shared/mqhoyz5jv7">here</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2852573646272425537?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-55565221288747204132010-10-05T19:27:00.003-04:002010-10-05T19:36:39.929-04:00Lucene's SimpleText codecInspired by <a href="http://www.lucidimagination.com/search/document/b68846e383824653/how_to_export_lucene_index_to_a_simple_text_file#b68846e383824653">this question</a> on the Lucene user's list, I created a new codec in Lucene called the SimpleText codec. The best ideas come from the user's lists!<br /><br />This is of course only available in Lucene's current trunk, to be eventually released as the next major release (4.0). Flexible indexing makes is easy to swap in different codecs to do the actual writing and reading of postings data to/from the index, and we have several fun codecs already available and more on the way...<br /><br />Unlike all other codecs, which save the postings data in compact binary files, this codec writes all postings to a single human-readable text file, like this:<br /><pre><br />field contents<br /> term file<br /> doc 0<br /> pos 5<br /> term is<br /> doc 0<br /> pos 1<br /> term second<br /> doc 0<br /> pos 3<br /> term test<br /> doc 0<br /> pos 4<br /> term the<br /> doc 0<br /> pos 2<br /> term this<br /> doc 0<br /> pos 0<br />END<br /></pre><br /><br />The codec is read/write, and fully functional. All of Lucene's unit tests pass (slowly) with this codec (which, by the way, is an awesome way to test your own codecs).<br /><br />Note that the performance of SimpleText is quite poor, as expected! For example, there is no terms index for fast seeking to a specific term, no skipping data for fast seeking within a posting list, some operations require linear scanning, etc. So don't use this one in production!<br /><br />But it should be useful for transparency, debugging, learning, teaching or anyone who is simply just curious about what exactly Lucene stores in its inverted index.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5556522128874720413?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com1tag:blogger.com,1999:blog-8623074010562846957.post-40300872954206768232010-09-28T15:07:00.009-04:002010-09-29T05:53:21.546-04:00Track your home's live electricity usage with PythonModern electric meters (the one attached to the outside of your house) emit an IR flash for each watt-hour consumed, through the port on the top of the meter. It turns out, it's easy to detect this flash, decode it into "live" power usage, and make cool charts like this:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_4pUbN9gxhUI/TKI9kH3HX_I/AAAAAAAAAB4/dEEWeYlh_cI/s1600/Elec.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 215px;" src="http://4.bp.blogspot.com/_4pUbN9gxhUI/TKI9kH3HX_I/AAAAAAAAAB4/dEEWeYlh_cI/s400/Elec.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5522043783904452594" /></a><br />That's live KW on the Y axis and time on the X axis.<br /><br />The flash, at least for my meter, appears to have high temporal accuracy, meaning it flashes precisely as you cross 1.000 WH. This is great, since it enables accurate, real-time power usage. For example, when I turn on the lights in my home office, I quickly see the power jump by ~65 watts, and then drop again when I turn the lights off.<br /><br />This is a fun way to track down which appliances or crazy computers or parasitic drains are using up so much electricity in your house!<br /><br />I've gone through several designs for this over the years. My last attempt was destroyed when <a href="http://chbits.blogspot.com/2010/06/our-house-was-hit-by-lightning.html">lightning hit my house</a> (there's always a silver lining!), so, I decided to try something new this time and I'm very happy with the approach since it's much simpler, and, moves the pulse detection into Python.<br /><br />I use a trivial analog circuit to detect the IR pulse, consisting of two 100K resistors in series and an IR photodiode in parallel with one of the resistors. Make sure you get the polarity right on the photodiode otherwise it won't work! Mount the photodiode on your power meter, aligned so that it "sees" each IR pulse. I also added a small (0.01 uF) ceramic capacitor in parallel with the same resistor, to suppress transient EM fields otherwise picked up by the relatively long wires out to my meter.<br /><br />Finally, I use this <a href="http://www.amazon.com/Syba-SD-CM-UAUD-Adapter-C-Media-Chipset/dp/B001MSS6CS/ref=sr_1_1?s=electronics&ie=UTF8&qid=1284509194&sr=1-1">simple USB audio adapter</a> to move the problem into the digital domain, connecting to the ends of the two series resistors to the mic input to use it for the A/D conversion. This USB audio adapter drives the mic input with ~4.0V bias voltage, which is great since otherwise you'd need an external source.<br /><br />When there's no pulse, the photo-diode acts roughly like an open switch, meaning there is a fixed 200K resistive load on the mic input. When a pulse happens (mine seem to last for ~10 msec), the photo-diode acts roughly like a closed switch, suddenly dropping the series resistance to 100K. This drop causes a very detectible pulse (strongly negative then strongly positive) on the mic input's voltage, I suspect because there's a capacitor behind the bias voltage (but: I am no analog circuit engineer, so this is speculation!).<br /><br />You can plug this USB audio adapter into any computer; I use a <a href="http://en.wikipedia.org/wiki/SheevaPlug">Sheeva plug computer</a> (delightful device, very low power -- I have three!). I record the digital samples (<a href="http://linux.die.net/man/1/arecord">arecord</a> works well, at a 2 Khz rate) and decode the samples in Python to detect a pulse whenever the value drops below -1000. You can easily compute the live KW based on the time between two adjacent pulses, push this into a database, and build graphs on top of this using <a href="http://code.google.com/apis/visualization/documentation/gallery.html">Google's visualization APIs</a> (I use <a href="http://danvk.org/dygraphs">dygraphs</a>).<br /><br />My last approach didn't have nearly the temporal accuracy (ie, it smoothed heavily across time), which masks interesting things. For example, now I can tell the difference between a resistive load (the coffee maker, oven, crockpot) and an inductive load (refrigerator compressor, vacuum cleaner) because the inductive load has a huge spike in the beginning, as the motor consumes lots of power trying to spin up.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4030087295420676823?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-32295322511658633802010-09-17T05:35:00.009-04:002010-10-25T16:55:25.600-04:00Lucene's indexing is fast!<div><br /><a href="http://wikipedia.org/">Wikipedia</a> periodically exports all of the content on their site, providing a nice corpus for performance testing. I downloaded <a href="http://download.wikimedia.org/enwiki/20100904/pages-articles.xml.bz2">their most recent English XML export</a>: it uncompresses to a healthy 21 GB of plain text! Then I fully indexed this with Lucene's current trunk (to be 4.0): it took 13 minutes and 9 seconds, or 95.8 GB/hour -- not bad!<br /><br />Here are the details: I first pre-process the XML file into a single-line file, whereby each doc's title, date, and body are written to a single line, and then index from this file, so that I measure "pure" indexing cost. Note that a real app would likely have a higher document creation cost here, perhaps having to pull documents from a remote database or from separate files, run filters to extract text from PDFs or MS Office docs, etc. I use Lucene's <tt>contrib/benchmark</tt> package to do the indexing; here's the alg I used:<br /><pre><br />analyzer=org.apache.lucene.analysis.standard.StandardAnalyzer<br /><br />content.source = org.apache.lucene.benchmark.byTask.feeds.LineDocSource<br />docs.file = /lucene/enwiki-20100904-pages-articles.txt<br /><br />doc.stored = true<br />doc.term.vector = false<br />doc.tokenized = false<br />doc.body.stored = false<br />doc.body.tokenized = true<br /><br />log.step.AddDoc=10000<br /><br />directory=FSDirectory<br />compound=false<br />ram.flush.mb = 256<br /><br />work.dir=/lucene/indices/enwiki<br /><br />content.source.forever = false<br /><br />CreateIndex<br /><br />{ "BuildIndex"<br />[ { "AddDocs" AddDoc > : * ] : 6<br />- CloseIndex<br />}<br /><br />RepSumByPrefRound BuildIndex</pre><br />There is no field truncation taking place, since this is now disabled by default -- every token in every Wikipedia article is being indexed. I tokenize the body field, and don't store it, and don't tokenize the title and date fields, but do store them. I use StandardAnalyzer, and I include the time to close the index, which means IndexWriter waits for any running background merges to complete. The index only has 4 fields -- title, date, body, and docid.<br /><br />I've done a few things to speed up the indexing:<ul><li> Increase IndexWriter's RAM buffer from the default 16 MB to 256 MB<br /></li><li> Run with 6 threads<br /></li><li> Disable compound file format<br /></li><li> Reuse document/field instances (<tt>contrib/benchmark</tt> does this by default)</li></ul>Lucene's wiki <a href="http://wiki.apache.org/lucene-java/ImproveIndexingSpeed">describes</a> additional steps you can take to speed up indexing.<br /><br />Both the source lines file and index are on an Intel X25-M SSD, and I'm running it on a modern machine, with dual Xeon X5680s, overclocked to 4.0 Ghz, with 12 GB RAM, running Fedora Linux. Java is <tt>64bit 1.6.0_21-b06</tt>, and I run as <tt>java -server -Xmx2g -Xms2g</tt>. I could certainly give it more RAM, but it's not really needed. The resulting index is 6.9 GB.<br /><br />Out of curiosity, I made a small change to <tt>contrib/benchmark</tt>, to print the ingest rate over time. It looks like this (over a 100-second window):<div><br /></div><a border=0 onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_4pUbN9gxhUI/TJM9bDK2zaI/AAAAAAAAABw/vClPjJBoYYs/s1600/IngestRate.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 240px;" src="http://4.bp.blogspot.com/_4pUbN9gxhUI/TJM9bDK2zaI/AAAAAAAAABw/vClPjJBoYYs/s400/IngestRate.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5517821503375592866" /></a><br /><br />Note that a large part (slightly over half!) of the time, the ingest rate is 0; this is not good! This happens because the flushing process, which writes a new segment when the RAM buffer is full, is single-threaded, and, blocks all indexing while it's running. This is a known issue, and is actively being addressed under <a href="https://issues.apache.org/jira/browse/LUCENE-2324">LUCENE-2324</a>.<br /><br />Flushing is CPU intensive -- the decode and reencode of the great many vInts is costly. Computers usually have big write caches these days, so the IO shouldn't be a bottleneck. With <a href="https://issues.apache.org/jira/browse/LUCENE-2324">LUCENE-2324</a>, each indexing thread state will flush its own segment, privately, which will allow us to make full use of CPU concurrency, IO concurrency as well as concurrency across CPUs and the IO system. Once this is fixed, Lucene should be able to make full use of the hardware, ie fully saturate either concurrent CPU or concurrent IO such that whichever is the bottleneck in your context gates your ingest rate. Then maybe we can double this already fast ingest rate!<br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3229532251165863380?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-79373208048726300572010-09-16T10:29:00.002-04:002010-09-16T10:32:45.274-04:00Proper localization is important!Sometimes it's <a href="http://gizmodo.com/382026/a-cellphones-missing-dot-kills-two-people-puts-three-more-in-jail">really important</a> to get localization right!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7937320804872630057?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-15917115369753872362010-09-13T14:11:00.005-04:002010-09-13T14:52:20.853-04:00Fast search filters using flexA filter in Lucene is a bit set that restricts the search space for any query; you pass it into IndexSearcher's search method. It's effective for a number of use cases, such as document security, index partitions, facet drill-down, etc.<br /><br />To apply a filter, Lucene must compute the intersection of the documents matching the query against the documents allowed by the filter. Today, we do that <a href="https://svn.apache.org/repos/asf/lucene/dev/branches/branch_3x/lucene/src/java/org/apache/lucene/search/IndexSearcher.java">in IndexSearcher</a> like this:<br /><pre><br /> while (true) {<br /> if (scorerDoc == filterDoc) {<br /> // Check if scorer has exhausted, only before collecting.<br /> if (scorerDoc == DocIdSetIterator.NO_MORE_DOCS) {<br /> break;<br /> }<br /> collector.collect(scorerDoc);<br /> filterDoc = filterIter.nextDoc();<br /> scorerDoc = scorer.advance(filterDoc);<br /> } else if (scorerDoc > filterDoc) {<br /> filterDoc = filterIter.advance(scorerDoc);<br /> } else {<br /> scorerDoc = scorer.advance(filterDoc);<br /> }<br /> }<br /></pre><br />We call this the "leapfrog approach": the query and the filter take turns trying to advance to each other's next matching document, often jumping past the target document. When both land on the same document, it's collected.<br /><br />Unfortunately, for various reasons this implementation is inefficient (these are spelled out more in <a href="https://issues.apache.org/jira/browse/LUCENE-1536">LUCENE-1536</a>):<ol><li> The advance method for most queries is costly.<br /></li><li> The advance method for most filters is usually cheap.<br /></li><li> If the number of documents matching the query is far higher than<br />the number matching the filter, or vice versa, it's better to drive<br />the matching by whichever is more restrictive.<br /></li><li> If the filter supports fast random access, and is not super<br />sparse, it's better to apply it during postings enumeration, like<br />deleted docs.<br /></li><li> Query scorers don't have a random access API, only .advance(),<br />which does unecessary extra work .next()'ing to the next matching<br />document.</li></ol>To fix this correctly, Lucene really needs an optimization stage, much like a modern database, which looks at the type and structure of the query and filter, as well as estimates of how many documents will match, and then picks an appropriate execution path. Likely this will be coupled with source code specilization/generation (<a href="https://issues.apache.org/jira/browse/LUCENE-1594">LUCENE-1594</a>) to write dedicated java code to execute the chosen path. Some day we'll get to that point!<br /><br />Until then, there in a simple way to get a large speedup in many cases, addressing the 4th issue above. Prior to flexible indexing, when you obtained the postings enumeration for documents matching a given term, Lucene would silently filter out deleted documents. With flexible indexing, the API now allows you to pass in a bit set marking the documents to skip. Normally you'd pass in the IndexReader's deleted docs. But, with a simple subclass of FilterIndexReader, it's possible to use any filter as the documents to skip.<br /><br />To test this, I created a simple class, CachedFilterIndexReader (I'll attach it to <a href="https://issues.apache.org/jira/browse/LUCENE-1536">LUCENE-1536</a>). You pass it an existing IndexReader, plus a Filter, and it creates an IndexReader that filters out both deleted documents and documents that don't match the provided filter. Basically, it compiles the IndexReader's deleted docs (if any), and the negation of the incoming filter, into a single cached bit set, and then passes that bit set as the skipDocs whenever postings are requested. You can then create an IndexSearcher from this reader, and all searches against it will be filtered according to the filter you provided.<br /><br />This is just a prototype, and has certain limitations, eg it doesn't implement reopen, it's slow to build up its cached filter, etc.<br /><br />Still, it works very well! I tested it on a 10M Wikipedia index, with a random filter accepting 50% of the documents:<br /><br /><table><tbody><tr><td align="left">Query</td><td align="left">QPS Default</td><td align="left">QPS Flex</td><td>% change</td></tr><tr><td>united~0.7</td><td>19.95</td><td>19.25</td><td><span style="color:red;">-3.5%</span></td></tr><tr><td>un*d</td><td>43.19</td><td>52.21</td><td><span style="color:green;">20.9%</span></td></tr><tr><td>unit*</td><td>21.53</td><td>30.52</td><td><span style="color:green;">41.8%</span></td></tr><tr><td>"united states"</td><td>6.12</td><td>8.74</td><td><span style="color:green;">42.9%</span></td></tr><tr><td>+united +states</td><td>9.68</td><td>14.23</td><td><span style="color:green;">47.0%</span></td></tr><tr><td>united states</td><td>7.71</td><td>14.56</td><td><span style="color:green;">88.9%</span></td></tr><tr><td>states</td><td>15.73</td><td>36.05</td><td><span style="color:green;">129.2%</span></td></tr></tbody></table><br />I'm not sure why the fuzzy query got a bit slower, but the speedups on the other queries are awesome. However, this approach is actually slower if the filter is very sparse. To test this, I ran just the TermQuery ("states"), against different filter densities:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_4pUbN9gxhUI/TI5r3_yhKaI/AAAAAAAAABo/A2Vwa0olPxg/s1600/TermQuerySpeedup.png"><img border=0 style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 240px;" src="http://1.bp.blogspot.com/_4pUbN9gxhUI/TI5r3_yhKaI/AAAAAAAAABo/A2Vwa0olPxg/s400/TermQuerySpeedup.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5516465203335735714" /></a><br />The cutover, for TermQuery at least, is somewhere around 1.1%, meaning if the filter accepts more than 1.1% of the index, it's best to use the CachedFilterIndexReader class; otherwise it's best to use Lucene's current implementation.<br /><br />Thanks to this new flex API, until we can fix Lucene to properly optimize for filter and query intersection, this class gives you a viable, fully external, means of massive speedups for non-sparse filters!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-1591711536975387236?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-62738165596647593102010-08-24T08:11:00.002-04:002010-08-24T08:17:59.206-04:00Here comes another bubble<a href="http://www.youtube.com/watch?v=I6IQ_FOCE6I">Hilarious</a>. It's a spoof of Billy Joel's catchy <a href="http://en.wikipedia.org/wiki/We_Didn't_Start_the_Fire">We Didn't Start the Fire</a>. Scary that this was posted more than two and a half years ago!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6273816559664759310?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-54952406119727631702010-08-07T08:22:00.000-04:002010-08-07T08:23:14.913-04:00Do babies really sleep?Those of you with kids have undoubtedly discovered that sometimes they sleep with their eyes half open.<br /><br />The first time it happens it's somewhat alarming, but, then, you get used to it and realize it's "normal". It probably just means their eyelids haven't quite closed yet.<br /><br />Well, my one-year-old did this, yesterday, so I seized the opportunity to do an experiment!! I wanted to test just how asleep she was, so, I smiled like crazy, made funny faces, scrunched my nose, stuck my tongue out, at her half open eye.<br /><br />And get this: she laughed! In her sleep. I repeated the test 3 times and each time she laughed. Yet, she was most definitely "asleep" -- the eyelid eventually closed and she didn't wake up for another hour.<br /><br />I guess enough of the brain remains active to process what the eye is seeing even when the rest of the brain is sleeping? Wild!<br /><br />Before you think I'm being unfair, she also conducts sleep experiments on us! Last weekend the whole family went camping. It was bed time and, as usual, we were all exhausted except our one-year-old. There was enough low light so she could see, so, as we were all dropping off one by one, she took turns running back and forth and pulling hard on our chins to wake us up again! Probably, from her perspective, this was like a horror movie, where her family is one by one dropping into comas and it's her job to prevent the disaster!<br /><br />Kids are great fun!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5495240611972763170?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-44079211554465366162010-08-04T10:27:00.002-04:002010-08-04T10:30:31.156-04:00Java developers are not consenting adults<a href="http://steve-yegge.blogspot.com/2010/07/wikileaks-to-leak-5000-open-source-java.html">Hilarious</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4407921155446536616?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-62984784173506916372010-08-02T18:12:00.004-04:002010-08-02T20:40:50.508-04:00Lucene performance with the PForDelta codecToday, to encode the postings (docs, freqs, positions) in the index, Lucene uses a variable byte format where each integer is individually encoded as 1-5 bytes.<br /><br />While this is wonderfully simple, it requires an if statement on every byte during decode, which is very costly since the CPU cannot easily <a href="http://en.wikipedia.org/wiki/Branch_predictor">predict the branch outcome</a>.<br /><br />To reduce the number of branches per int decode, you must switch to decoding groups of ints at once. <a href="http://www2008.org/papers/pdf/p387-zhangA.pdf">This paper</a> describes a few such encoders (PForDelta, Rice Coding, Simple9, Simple16). <a href="">Chapter 6 (Index Compression)</a> of <a href="http://www.ir.uwaterloo.ca/book">Information Retrieval: Implementing and Evaluating Search Engines</a> goes into great detail on these and others, including an <a href="http://www.ir.uwaterloo.ca/book/addenda-06-index-compression.html">addenda</a> showing results for <a href="http://research.google.com/people/jeff/WSDM09-keynote.pdf">Google's Group VarInt</a> encoder.<br /><br />The IntBlock codec is designed to make it easy to experiment with these sorts of different int encoders. It does the "hard part" of enabling Lucene to operate on a set of ints at once, which is somewhat tricky as the seek points (in the terms dict and the skipping lists) must now encode both the file-pointer where the block starts as well as the index (starting int) into the block.<br /><br />There is already a low-level initial implementation Frame-of-reference (FOR) and Patched frame-of-reference (PFOR), on <a href="https://issues.apache.org/jira/browse/LUCENE-1410">LUCENE-1410</a>, as well as Simple9/16 on <a href="https://issues.apache.org/jira/browse/LUCENE-2189">LUCENE-2189</a>, thanks to Paul Elschot and Renaud Delbru.<br /><br />FOR is a simple encoding: it takes each fixed block of ints, ands stores them all as packed ints, where each value gets N bits, set by the maximum int in the block. So say our block size is 8, and we have these ints:<br /><pre><br /> 1 7 3 5 6 2 2 5<br /></pre><br />we'd only need 3 bits per value. But, FOR has a clear weakness: if you have a single big int mixed in with a bunch of small ones, then you waste bits. For example if we have these ints:<br /><pre><br /> 1 7 3 5 293 2 2 5<br /></pre><br />then FOR must use 9 bits for all values (because of 293), despite the fact that the other values only needed 3 bits each. How much this hurts in practice remains to be seen.<br /><br />PFOR fixes this by marking such large numbers as exceptions, which are then "patched" after the initial decode. So for the above example, we would still use 3 bits per-value, but we'd mark that the 293 value was an "exception" and it would be separately encoded at the end (with more bits), and then "patched" back in at decode time. <a href="http://www2008.org/papers/pdf/p387-zhangA.pdf">The above paper</a> has the details.<br /><br />Note that block-based codecs are not always a good fit, since in order to access even one int within the block, they [typically] must decode the full block. This can be a high cost if you frequently need to decode just an int or two, such as with a primary key field. <a href="http://chbits.blogspot.com/2010/06/lucenes-pulsingcodec-on-primary-key.html">Pulsing codec</a> is a better fit for such fields.<br /><br />During testing, I found a few silly performance problems in the IntBlock codec, which I've hacked around for now (I'll post my patch on <a href="https://issues.apache.org/jira/browse/LUCENE-1410">LUCENE-1410</a>); the hacks are nowhere near committable, but are functioning correctly (identical search results for the queries I'm testing). I also made some more minor optimizations to the FOR/PFOR implementation. I'd like to get the IntBlock codec to the point where anyone can easily tie in a fixed or variable block size int encoding algorithm and run their own tests.<br /><br />I indexed the first 10 million Wikipedia ~1KB sized docs. The resulting index sizes were:<br /><br /><table><tr><td><b>Codec</b></td><td><b>Size</b></td><td><b>% Change</b></td></tr><tr><td>Standard</td><td>3.50 GB</td><td> </td></tr><tr><td>FOR</td><td>3.96 GB</td><td>13.3% bigger</td></tr><tr><td>PFOR</td><td>3.87 GB</td><td>11.1% bigger</td></tr></table><br />The size increase of both FOR and PFOR are fairly low. PFOR is smaller than FOR, as expected, but it's surprising that it's only a little bit lower. Though, this is a function of where you draw the line for the exception cases and will be corpus dependent. Still, I'm encouraged by how little additional space FOR requires over the Standard codec.<br /><br />I ran a set of queries and measured the best time (of 40 runs) for each, across 4 threads. Here are the results for FOR:<br /><br /><table><tr><td align=left><b>Query</b></td><td align=left><b>QPS Standard</b></td><td align=left><b>QPS FOR</b></td><td><b>% Change</b></td></tr><tr><td>united~0.6</td><td>5.59</td><td>5.08</td><td><font color=red>-9.0%</font></td><tr><td>"united states"</td><td>11.46</td><td>11.22</td><td><font color=red>-2.1%</font></td><tr><td>united~0.7</td><td>18.33</td><td>19.23</td><td><font color=green>4.9%</font></td><tr><td>united states</td><td>15.53</td><td>18.66</td><td><font color=green>20.1%</font></td><tr><td>uni*d</td><td>34.25</td><td>43.37</td><td><font color=green>26.6%</font></td><tr><td>unit*</td><td>31.27</td><td>41.07</td><td><font color=green>31.3%</font></td><tr><td>states</td><td>55.72</td><td>75.82</td><td><font color=green>36.1%</font></td><tr><td>+united +states</td><td>15.17</td><td>21.43</td><td><font color=green>41.2%</font></td></table><br />and for PFOR:<br /><br /><table><tr><td align=left><b>Query</b></td><td align=left><b>QPS Standard</b></td><td align=left><b>QPS PFOR</b></td><td><b>% Change</b></td></tr><tr><td>united~0.6</td><td>5.59</td><td>5.02</td><td><font color=red>-10.1%</font></td><tr><td>"united states"</td><td>11.46</td><td>10.88</td><td><font color=red>-5.1%</font></td><tr><td>united~0.7</td><td>18.33</td><td>19.00</td><td><font color=green>3.7%</font></td><tr><td>united states</td><td>15.53</td><td>18.11</td><td><font color=green>16.6%</font></td><tr><td>uni*d</td><td>34.25</td><td>43.71</td><td><font color=green>27.6%</font></td><tr><td>states</td><td>55.72</td><td>71.39</td><td><font color=green>28.1%</font></td><tr><td>unit*</td><td>31.27</td><td>41.42</td><td><font color=green>32.5%</font></td><tr><td>+united +states</td><td>15.17</td><td>21.25</td><td><font color=green>40.1%</font></td></table><br />They both show good gains for most queries; FOR has a slight edge since it doesn't have to decode exceptions. The united~0.6 (max edit distance = 2) is slower, likely because a good number of the 519 terms it expands to have low frequency, and so the overhead of a full block decode is hurting performance. The PhraseQuery also got a little slower, probably because it uses non-block skipping during searching. The AND query, curiously, got faster; I think this is because I modified its scoring to first try seeking within the block of decoded ints. Likely a hybrid codec for Lucene, using FOR or FFOR for high frequency terms, Standard for medium frequency, and Pulsing for very low frequency, would perform best overall.<br /><br />I ran one additional test, this time using FOR on MMapDirectory (instead of NIOFSDirectory used above), passing an IntBuffer from the mapped pages directly to the FOR decoder:<br /><br /><table><tr><td><b>Query</b></td><td><b>QPS Standard</b></td><td><b>QPS FOR</b></td><td><b>% Change</b></td></tr><tr><td>united~0.6</td><td>6.00</td><td>5.28</td><td><font color=red>-12.1%</font></td><tr><td>united~0.7</td><td>18.48</td><td>20.53</td><td><font color=green>11.1%</font></td><tr><td>"united states"</td><td>10.47</td><td>11.70</td><td><font color=green>11.8%</font></td><tr><td>united states</td><td>15.21</td><td>20.25</td><td><font color=green>33.2%</font></td><tr><td>uni*d</td><td>33.16</td><td>47.59</td><td><font color=green>43.5%</font></td><tr><td>unit*</td><td>29.71</td><td>45.14</td><td><font color=green>51.9%</font></td><tr><td>+united +states</td><td>15.14</td><td>23.65</td><td><font color=green>56.2%</font></td><tr><td>states</td><td>52.30</td><td>88.66</td><td><font color=green>69.5%</font></td></table><br />The results are generally even better for two reasons. First, for some reason the Standard codec slows down a bit with MMapDirectory. Second, the FOR codec speeds up substantially, because I'm able (hacked up though) do a no-copy decode with MMapDirectory.<br /><br /><b>Remember</b> that these results are very preliminary, based on a patch with many non-committable hacks (eg deleted docs are ignored!), that doesn't pass all Lucene's unit tests, etc. There are also still further optimizations to explore, and lots of work remains. So it's not clear where the final numbers will be, but these initial results are very encouraging!<br /><br />If you have any other algorithms to try for encoding ints, pleaes pipe up! It's very easy to have Lucene generate a few billion ints for you to encode/decode if you want to run standalone tests.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6298478417350691637?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com4tag:blogger.com,1999:blog-8623074010562846957.post-13803069874476318382010-07-14T05:17:00.004-04:002010-07-14T05:44:55.058-04:00Moving readVInt to CBy far the hottest spot in Lucene during searching is the method (DataInput.readVInt) that decodes Lucene's variable-length integer representation (vInt). This method is called an insane number of times, while iterating the postings lists (docs, freqs, positions), during query execution.<br /><br />This representation is not CPU friendly: for every single byte read, the CPU hits a hard-to-predict if statement (testing the high bit). Alternative block-based formats do a good job reducing branches while decoding, such as <a href="http://cis.poly.edu/cs912/indexcomp.pdf">these encodings</a> (PFOR-DELTA is currently an experimental codec attached as a patch on <a href="https://issues.apache.org/jira/browse/LUCENE-1410">LUCENE-1410</a>) or Google's <a href="http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/people/jeff/WSDM09-keynote.pdf">Group Varint</a>.<br /><br />Anyway, I decided to test whether porting readVInt to C would gives us a performance boost. I had known the overhead of JNI was highish in the past, but I was hoping in modern JREs this had been improved.<br /><br />Unfortunately, it wasn't: I see a ~10%-~40% slowdown, depending on the query. Likely hotspot's inability to inline native methods is also a factor here. Perhaps, if/when we switch to a block-based codec, we'll see a gain with a native implementation, since the amortized overhead of invoking JNI will be lower.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-1380306987447631838?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-88307061491562024692010-07-13T16:56:00.004-04:002010-07-13T17:25:37.344-04:00Apple censorship, againIt's sickening that Apple thinks it's OK to <a href="http://www.tuaw.com/2010/07/12/apple-drops-consumer-reports-discussion-threads-down-memory-hole/">censor (remove) posts from their forums</a>. It's <a href="http://www.tomshardware.com/reviews/apple-display-update,1747.html">not the first time they've done this</a>, either.<br /><br />I consider it entrapment -- Apple hosts these forums, as the obvious place where we all can go to discuss any issues we have. As with any forum, there's a natural implicit assumption of non-interference, much like I expect my ISP not to block my visits to random web-sites or my email provider to block certain emails or the local coffee shop to disallow discussions about certain topics.<br /><br />But then, suddenly, Apple acts like China: they censor that which they disagree with.<br /><br />C'mon Apple!<br /><br />You should be above such draconian behavior. If you disagree with what's being said, play fair! Come out and discuss the topic, explain your viewpoint, convince us.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8830706149156202469?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-82907559287503614502010-07-11T08:17:00.002-04:002010-10-25T16:55:41.105-04:00Beware statins<a href="http://www.thincs.org/melchior1.htm">Statins -- Miracle drug or tragedy?</a><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8290755928750361450?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-22424601775742740562010-07-10T11:34:00.002-04:002010-07-10T11:40:23.505-04:00What motivates us<a href="http://www.youtube.com/watch?v=u6XAPnuFjJc">Great video</a>, from Daniel Pink, animated by <a href="http://www.thersa.org">RSA</a>, summarizing <a href="http://www.amazon.com/Drive-Surprising-Truth-About-Motivates/dp/1594488843">his book</a> digging into what motivates people to do things. I find it very accurate about myself, and I expect especially people working in open-source projects will resonate strongly with the surprising findings.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2242460177574274056?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-76677582082442727632010-07-10T11:18:00.002-04:002010-07-10T11:21:21.784-04:00Encoding videos for Apple iPad/iPod, using mencoderAfter much searching, poking, iterating, I found a magical mencoder command-line that encodes videos in the right format for the <a href="http://www.apple.com/ipad">ipad</a>. Debugging this is hard because, if you get something wrong, iTunes simply silently fails to open the video file, giving no specific feedback as to what's wrong. I felt like a monkey on a typewriter...<br /><br />So here are the options, broken by group. Set the output format to MP4:<br /><pre><br /> -of lavf -lavfopts format=mp4<br /></pre><br />Scale the video to width 1280, height to match the aspect ratio (if your source video is low resolution, eg DVD, leave this off; you can also crop (-vf crop=W:H:X:Y; run mplayer -vf cropdetect,scale to have it guess the crop for you), or de-interlance (I like -vf pp=lb), or any other video filter):<br /><pre><br /> -vf scale=1280:-3<br /></pre><br />Use x264 codec for video, with a zillion options (tweak that crf=XX if you want higher quality; lower values of XX give higher quality, but take more space):<br /><pre><br /> -ovc x264 -x264encopts crf=28:vbv_maxrate=1500:nocabac:global_header:frameref=3:threads=auto:bframes=0:subq=6:mixed-refs=0:weightb=0:8x8dct=1:me=umh:partitions=all:qp_step=4:qcomp=0.7:trellis=1:direct_pred=auto<br /></pre><br />Use faac codec for audio:<br /><pre><br /> -oac faac -faacopts br=160:mpeg=4:object=2:raw -channels 2 -srate 48000<br /></pre><br />I'm sure many other command-line combinations would work; this was just the first combo I found that works.<br /><br />If you need to encode for the <a href="http://www.apple.com/ipodtouch/">iPod Touch</a>, just change the -vf scale=1280:-3 to -vf scale=640:-3 (at least this works for recent iPod Touch models).<br /><br />You can also use the nifty <a href="http://mp4v2.googlecode.com/svn/doc/1.9.0/ToolGuide.html">mp4art</a> tool to insert cover art after the encode finishes; this lets you set the image for the movie when browsing on the iPad/iPod or in iTunes, which is vital if young kids will be launching the movies! I use PNG images, which work fine.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7667758208244272763?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com4tag:blogger.com,1999:blog-8623074010562846957.post-65148839125572031532010-07-09T16:16:00.003-04:002010-07-09T16:36:57.409-04:00Old Orchard BeachWe spent the past half week in Old Orchard Beach, Maine (US), in the <a href="http://www.tripadvisor.com/Hotel_Review-g40792-d125883-Reviews-Crest_Motel-Old_Orchard_Beach_Maine.html">Crest Motel</a>. It's a great place! The rooms are clean, the beach is right outside, and it's a short walk to <a href="http://www.palaceplayland.com/">Palace Playland</a>. They have an indoor pool & hot tub, and I'm happy to report that they do not <a href="http://chbits.blogspot.com/2009/10/discrimination-against-kids.html">discriminate against kids</a>. The whole area is very family friendly, and the kids had a blast!<br /><br />But what I loved most was... while we were staying there, they happened to be installing Solar hot water panels! At first we saw random holes drilled in the floor and ceiling, which made all of us very curious. Then the next day these were filled in with insulated pipes. Finally, this morning, we saw the solar panels themselves, being carried up and installed on the roof. The location is excellent -- they have a large roof, and no tall trees anywhere nearby. It looked like a high capacity installation, maybe ~250 square feet. They expect to fully generate all hot water in the summer, and also a sizable portion of the (air) heat in the winter.<br /><br />I have a small (600W nominal, off-grid) solar electric installation in my house, self-installed. In the summer, it easily offsets the electricity used by our home theater. I involved the kids all throughout the installation, to teach them how important it is to find renewable sources for everything. And whenever they or their friends watch movies, I remind them that it's all powered by sunshine electricity, which of course leads to a great curious discussion and more teachable moments.<br /><br />So I took this chance to (again) hammer home this vital lesson. And, I'm very happy to see that others are adopting Solar energy!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6514883912557203153?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-56097179163417059052010-07-09T15:57:00.004-04:002010-07-09T16:03:48.911-04:00Communism vs capitialism/democracyWhile we in the "free" world like to believe our capitalistic, democratic way is better than the tight-fisted communist approach in, say, China, the situation is not really so clear cut.<br /><br />The Chinese government has full control to make changes to nearly everything in the country. Yes, sometimes this power is used to awful ends, such as <a href="http://en.wikipedia.org/wiki/Human_rights_in_the_People's_Republic_of_China">human rights violations</a> and the <a href="http://en.wikipedia.org/wiki/Internet_censorship_in_the_People's_Republic_of_China">great firewall of China</a>.<br /><br />But then, this same unilateral power can lead to great progress, overnight. For example, <a href="http://news.bbc.co.uk/2/hi/business/10551140.stm">China plans to add a 5% tax on oil and gas consumption</a> (plus other "raw materials"). The US, in contrast, has for a very long time offered <a href="http://www.nytimes.com/2010/07/04/business/04bptax.html">massive tax breaks</a> to the oil companies (this is why the price of our gasoline is horribly low compared to nearly every other country, encouraging us to buy massive, awfully fuel inefficient cars and trucks).<br /><br />Another example: a few years back, China suddenly required that <a href="http://english.people.com.cn/200612/19/eng20061219_334047.html">all cell phone chargers adopt the same standard</a>, so that when people buy new phones the do not need a new charger, thus eliminating a big source of electronics waste. In contrast, in the US with our "new every 2", we have to throw away our chargers every time we upgrade since they rarely interoperate.<br /><br />A third example is <a href="http://en.wikipedia.org/wiki/Fuel_economy_in_automobiles">fuel economy standards</a>: China has for a long time had far more stringent requirements than the US.<br /><br />In contrast, accomplishing these excellent improvements in the US is nearly impossible: each small change requires a tremendous battle through our congress, many members of which are <a href="http://www.crewsmostcorrupt.org">rather blatantly corrupt</a>, accepting all sorts of creative bribes (campaign contributions) from corporations, to buy their vote. And corporate influence got even stronger thanks the recent <a href="http://en.wikipedia.org/wiki/Citizens_United_v._Federal_Election_Commission">Supreme Court landmark decision</a> giving corporations much more freedom to influence elections. Finally, congress members, especially these days, seem to vote almost always along party lines rather than what's actually best for our country's future.<br /><br />Don't get me wrong: net/net I'm quite happy I live in the US, given all the tradeoffs. But, still, we can and should do better, and copying some of China's recent changes would be a great start.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5609717916341705905?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-75696427045841306532010-07-05T14:48:00.003-04:002010-07-05T15:10:29.315-04:00A better grassThis <a href="http://www.pearlspremium.com/">Pearl's premium grass</a> looks awesome: mow only once per month; extremely drought tolerant (seldom or never water); thrives without chemicals. It's the polar opposite of <a href="http://chbits.blogspot.com/2009/08/life-support-grass.html">life-support grass</a>, that's the gold standard in today's yards.<br /><br />Maybe, once our yard is in really bad shape, I'll try this seed, mixed with clover. I want our yard to have zero environmental cost, zero <a href="http://en.wikipedia.org/wiki/Carbon_footprint">carbon footprint</a>. We currently have just that: we haven't watered our lawn in 2 years; no fertilizer, pesticides; no dethatching, mechanical aeration; very rarely raked, mowed; etc., except, it's slowly dying, and weeds are moving in, because we inherited prior life-support grass.<br /><br />I'd also like near-zero effort on our part (we don't want to hire a lawn care service because we feel that sets a bad example for our kids), and of course to have decent curb appeal. Surely this is not too much to expect?<br /><br />I wish there were more companies/people developing environmentally free/friendly alternatives to the standard life-support grass. I'd do a bake-off with these alternatives on different spots in our challenging yard!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7569642704584130653?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com2tag:blogger.com,1999:blog-8623074010562846957.post-48808059766126182282010-07-05T09:37:00.002-04:002010-07-05T09:42:05.297-04:00Ethernet lightning protectionI'm going to try using this <a href="http://www.amazon.com/APC-ProtectNet-100BT-Ethernet-Protector/dp/B00006BBGX">APC ethernet surge suppressor</a> to protect the important devices (desktop, laptop, filer, backups, FIOS) attached to our ethernet network.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4880805976612618228?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-54848959943306104642010-07-05T08:59:00.003-04:002010-07-05T15:07:40.384-04:00Lucene's RAM usage for searchingFor fast searching, Lucene loads certain data structures entirely into RAM:<br /><ul><br /> <li> The terms dict index requires substantial RAM per indexed term (by default, every 128th unique term), and is loaded when IndexReader is created. This can be a very large amount of RAM for indexes that have an unusually high number of unique terms; to reduce this, you can pass a terms index divisor when opening the reader. For example, passing 2, which loads only every other indexed term, halves the RAM required. But, in tradeoff, seeking to a given term, which is required once for every TermQuery, will become slower as Lucene must do twice as much scanning (on average) to find the term.<br /><br /> <li> Field cache, which is used under-the-hood when you sort by a field, takes some amount of per-document RAM depending on the field type (String is by far the worst). This is loaded the first time you sort on that field.<br /><br /> <li> Norms, which encode the a-priori document boost computed at indexing time, including length normalization and any boosting the app does, consume 1 byte per field X document used for searching. For example, if your app searches 3 different fields, such as body, title and abstract, then that requires 3 bytes of RAM, per document. These are loaded on-demand the first time that field is searched.<br /><br /> <li> Deletions, if present, consume 1 bit per doc, created during IndexReader construction.<br /></ul><br />Warming a reader is necessary because of the data structures that are initialized lazily (norms, FieldCache). It's also useful to pre-populate the OS's IO cache with those pages that cover the frequent terms you're searching on.<br /><br />With flexible indexing, available in Lucene's trunk (4.0-dev), we've made great progress on reducing the RAM required for both the terms dict index and the String index field cache (<a href="https://issues.apache.org/jira/browse/LUCENE-2380?focusedCommentId=12871342&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#action_12871342">some details here</a>). We have substantially reduced the number of objects created for these RAM resident data structures, and switched to representing all character data as UTF8, not java's char, which halves the RAM required when the character data is simple ascii.<br /><br />So, I ran a quick check against a real index, created from the first 5 million documents from the <a href="http://en.wikipedia.org/wiki/Wikipedia_database">Wikipedia database export</a>. The index has a single segment with no deletions. I initialize a searcher, and then load norms for the body field, and populate the FieldCache for sorting by the title field, using JRE 1.6, 64bit:<br /><ul><br /> <li> 3.1-dev requires 674 MB of RAM<br /><br /> <li> 4.0-dev requires 179 MB of RAM<br /></ul><br />That's a 73% reduction on RAM required!<br /><br />However, there seems to be <a href="https://issues.apache.org/jira/browse/LUCENE-2504">some performance loss when sorting by a String field</a>, which we are still tracking down.<br /><br />Note that modern OSs will happily swap out RAM from a process, in order to increase the IO cache. This is rather silly: Lucene loads these specific structures into RAM because we know we will need to randomly access them, a great many times. Other structures, like the postings data, we know we will sweep sequentially once per search, so it's less important that these structures be in RAM. When the OS swaps our RAM out in favor of IO cache, it's reversing this careful separation!<br /><br />This will of course cause disastrous search latency for Lucene, since many page faults may be incurred on running a given search. On Linux, you can fix this by <a href="http://kerneltrap.org/node/3000">tuning swappiness down to 0</a>, which I try to do on every Linux computer I touch (most Linux distros default this to a highish number). Windows also has a checkbox, under My Computer -> Properties -> Advanced -> Performance Settings -> Advanced -> Memory Usage, that lets you favor Programs or System Cache, that's likely doing something similar.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5484895994330610464?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-43662380261037335782010-07-03T10:39:00.000-04:002010-07-03T10:40:09.422-04:00Java vs .NET<a href="http://www.youtube.com/watch?v=8EOQvgdyVBY">Hilarious</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4366238026103733578?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-57388741792455728732010-06-30T05:54:00.003-04:002010-07-05T05:46:57.041-04:00Our house was hit by lightningBelieve it or not, our house was struck by lightning! It happened a few days ago, as a cold front swept over, bringing with it some intense but short-lived thunderstorms.<br /><br />I was working on my computer when I heard a loud POP sound of a spark, behind me, in the utility closet. At the same time my computer went blank, and there was insanely loud thunder clap. My poor son was on the toilet at the time and told me he was so startled that he jumped high in the air and almost fell in! Fortunately, none of us were hurt. <br /><br />The strike destroyed our central 16-port gigabit ethernet switch, 3 out of 4 LAN ports on my <a href="http://www22.verizon.com/Residential/aboutFiOS/Overview.htm?CMP=DMC-CVS_ZZ_ZZ_E_TV_N_X001">FIOS</a> NAT box, a couple power supplies and one netcam. It also fried the device I use to read the electrical (charging, inverting) data from the solar panels in my back yard, but the solar panels themselves, including the thick copper ground wires designed to "guide" lightning into the ground and away from the house, were all fine, as well as the charger, inverter and batteries. My <a href="http://en.wikipedia.org/wiki/1-Wire">1-Wire network</a>, which I use to measure various indoor & outdoor temperatures, is also still dead. My wife's computer immediately shut down and rebooted, several times (spooky), but apparently unharmed. My computer seemed to lose both ethernet ports, but then after much rebooting and testing plug-in ethernet cards, they came back to life.<br /><br />A large tree branch in our neighbor's yard fell down; the neighbors across the street called the fire department; yet another neighbor saw bright sparks in his basement and also lost a bunch of electronics.<br /><br />Almost certainly this was not a direct strike for us; otherwise things would have been vaporized instead of simply dead. Instead, the sudden immense electro-magnetic field created at the direct strike radiates outward, creating the local equivalent of an <a href="http://en.wikipedia.org/wiki/Electromagnetic_pulse">EMP bomb</a>. This EMF then induces high voltage and current in any wires it crosses; the closer you are to the direct strike, and the longer your wires are, the more damaing the induced voltage and current is. In my case, apparently, the extensive network of ethernet wires in my house cause most of the damage. This is a good reason to use WiFi!<br /><br />I will now buy myself <a href="http://www.google.com/products?q=ethernet+lightning++protection&hl=en&aq=f">something</a> to try to prevent this from happening again.<br /><br />Lightning is crazy stuff. The <a href="http://en.wikipedia.org/wiki/Lightning#Leader_formation_and_the_return_stroke">process the lightning goes through in seeking the path through which it will dump insane amounts of current</a> is fascinating. National Geographic has a <a href="http://news.nationalgeographic.com/news/2004/06/0623_040623_lightningfacts.html">great facts page</a>; for example, talking on your land-line telephone is the leading cause of lightning injuries inside the home. I suspect we may have been hit by <a href="http://news.nationalgeographic.com/news/2004/06/0623_040623_lightningfacts_2.html">positive lightning</a>, because we seemed to be hit, out of the blue, well before the storm itself seemed to arrive.<br /><br />Lightning strikes are apparently rather common; in just my immediate family this has now happened twice to me, and once each to my brother, father and grandparents!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5738874179245572873?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-1367810169592639122010-06-29T05:21:00.001-04:002010-07-05T15:08:00.167-04:00Lucene in Action 2nd Edition is done!Lucene in Action, 2nd Edition, is finally done: the eBook is <a href="http://manning.com/hatcher3">available now</a>, and the print book should be released on July 8th!<br /><br />The source code that goes along with the book is <a href="http://manning.com/hatcher3/LIAsourcecode.zip">freely available</a> and free to use (<a href="http://www.apache.org/licenses/LICENSE-2.0.html">Apache Sofware License 2.0</a>), and there are two free chapters (<a href="http://manning.com/hatcher3/Sample-1.pdf">Chapter 1</a>, and <a href="http://manning.com/hatcher3/Sample-3.pdf">Chapter 3</a>). There is also a free green paper excerpted from the book, <a href="http://manning.com/free/green_HotBackupsLucene.html">Hot Backups with Lucene</a>, as well as the <a href="http://www.code972.com/blog/2010/06/lucene-in-action-free-chapter-coupon-code/">section describing CLucene</a>, the C/C++ port of Lucene.<br /><br />Writing is the best way to learn something -- because of this book I've learned all sorts of nooks and crannies in Lucene that I otherwise would not have explored for quite some time.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-136781016959263912?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com5tag:blogger.com,1999:blog-8623074010562846957.post-74868029310492036152010-06-21T11:48:00.002-04:002010-06-21T11:58:46.949-04:00Beware String.substring's memory usageI'm trying to build up a test index for testing Lucene's sort performance, to track down a <a href="https://issues.apache.org/jira/browse/LUCENE-2504">regression in String sorting performance between 3.x and 4.0</a>, apparently from our <a href="https://issues.apache.org/jira/browse/LUCENE-2380">packed ints cutover</a>.<br /><br />To do this, I want to use the unique title values from <a href="http://en.wikipedia.org/wiki/Wikipedia_database">Wikipedia's full database export</a>.<br /><br />So I made a simple task in Lucene's contrib/benchmark framework to hold onto the first 1M titles it hits. Titles tend to be small, say maybe average worst case 100 characters per document, so worst case RAM would be ~200 MB or so, right?<br /><br />Wrong!<br /><br />It turns out, in Java, when you call String's substring method, the resulting String returned to you keeps a reference to the original String, so the original String can never be GC'd if you hold onto the substring. Java can do this "optimization" because Strings are immutable.<br /><br />For me, this "optimization" is a disaster: the title is obtained by getting the substring of a large string (derived from a line-doc file) that holds the full body text as well! Instead of ~200 characters per unique title I was looking at ~25K characters! Ugh.<br /><br />Fortunately, the workaround is simple -- use the String constructor that takes another String. This forces a private copy.<br /><br />I imagine for many cases this "optimization" is very worthwhile. If you have a large original string, and pull many substrings from it, and then discard all of those substrings and the original string, you should see nice gains from this "optimization".<br /><br />There is a <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4513622">longstanding bug opened</a> for this; likely it will never be fixed. Really, GC should be empowered to discard the original string and keep only the substring. Or perhaps substring should have some heuristics as to when it's dangerous to keep the reference to the original String.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7486802931049203615?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com1tag:blogger.com,1999:blog-8623074010562846957.post-12920427462382174352010-06-20T09:10:00.002-04:002010-06-20T09:35:26.227-04:00Geek DadWe've had this great family ritual, for a few years now: at the start of every summer we pitch a tent in our back yard! We leave it there all summer, and the kids have great fun, with neighbors and friends, playing in it, hiding from the rain, etc.<br /><br />We also pick a few nights to sleep in the tent, which feels almost as real as camping, yet you have the delightful freedom of taking a short walk back to the house if you forgot something.<br /><br />So, last night we slept in the tent. But, this year I brought our new <a href="http://www.apple.com/ipad/">iPad</a> with us. The kids took turns playing a few games; one of their favorites is <a href="http://itunes.apple.com/us/app/gomi-hd/id370888255?mt=8">Gomi HD</a>, a game I also love for its not-so-subtle message that we humans are screwing up the planet and it's up to the kids to fix it. Then we watched <a href="http://en.wikipedia.org/wiki/Shrek_2">Shrek 2</a>, which I had previously encoded for the iPad (using <a href="http://handbrake.fr/">Handbrake</a>). Finally, the kids, one by one, fell asleep.<br /><br />Then, in the middle of the night, I woke up and heard rain hitting the tent. I was worried that it could turn into a big storm (in past years our tent has been literally flattened by passing thunderstorms, once when we were inside!), so, I turned on the iPad and loaded the local <a href="http://www.wunderground.com/radar/radblast.asp?zoommode=pan&prevzoom=zoom&num=6&frame=0&delay=15&scale=1.000&noclutter=0&ID=BOX&type=N0R&showstorms=0&lat=42.44557953&lon=-71.23622131&label=Lexington,%20MA&map.x=400&map.y=240&scale=1.000¢erx=400¢ery=240&showlabels=1&rainsnow=0&lightning=0&lerror=20&num_stns_min=2&num_stns_max=9999&avg_off=9999&smooth=0">NexRAD radar</a>, and confirmed that in fact it was just a small passing cell: phew!<br /><br />Finally, I woke up, and was ready to get up, so I used the iPad again, this time to start the coffee maker. I have a simple Web server, written in Python, that exposes an HTML interface to variance lights and appliances controlled via <a href="http://www.insteon.net/">Insteon</a>, including the coffee maker. It's vital that I minimize the time from when I first stand up in the morning to when I consume my coffee!<br /><br />Yes, I'm a geek Dad.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-1292042746238217435?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-21193116542800073052010-06-14T18:15:00.004-04:002010-06-14T18:34:17.082-04:00Lucene and fadvise/madviseWhile indexing, Lucene periodically merges multiple segments in the index into a single larger segment. This keeps the number of segments relatively contained (important for search performance), and also reclaims disk space for any deleted docs on those segments.<br /><br />However, it has a well known problem: the merging process evicts pages from the OS's buffer cache. The eviction is ~2X the size of the merge, or ~3X if you are using compound file.<br /><br />If the machine is dedicated to indexing, this usually isn't a problem; but on a machine that's also searching, this can be catastrophic as it "unwarms" your warmed reader. Users will suddenly experience long delays when searching. And because a large merge can take hours, this can mean hours of suddenly poor search performance.<br /><br />So why hasn't this known issue been fixed yet? Because Java, unfortunately, does not expose access to the low-level APIs (<a href="http://www.opengroup.org/onlinepubs/009695399/functions/posix_fadvise.html">posix_fadvise</a>, <a href="http://www.opengroup.org/onlinepubs/000095399/functions/posix_madvise.html">posix_madvise</a>) that would let us fix this. It's not even clear whether <a href="http://java.sun.com/developer/technicalArticles/javase/nio/">NIO.2</a> (in Java 7) <a href="http://markmail.org/message/jvwv3ne2se3gjeee">will expose these</a>.<br /><br />On the Lucene dev list we've long assumed that these OS-level functions should fix the issue, if only we could access them.<br /><br />So I decided to make a quick and dirty test to confirm this, using a small JNI extension.<br /><br />I created a big-ish (~7.7G) multi-segment Wikipedia index, and then ran a set of ~2900 queries against this index, over and over, letting it warm up the buffer cache. Looking at /proc/meminfo (on Linux) I can see that the queries require ~1.4GB of hot RAM in the buffer cache (this is a CentOS Linux box with 3G RAM; the index is on a "normal" SATA hard drive). Finally, in a separate JRE, I opened an IndexWriter and called optimize on the index.<br /><br />I ran this on trunk (4.0-dev), first, and confirmed that after a short while, the search performance indeed plummets (by a factor of ~35), as expected. RAM is much faster than hard drives!<br /><br />Next, I modified Lucene to call posix_fadvise with the <tt>NOREUSE</tt> flag; from the man page, this flag looks perfect:<br /><br /><em>Specifies that the application expects to access the specified data once and then not reuse it thereafter.</em><br /><br />I re-ran the test and.... nothing changed! Exactly the same slowdown. So I did some digging, and found Linux's <a href="http://lxr.free-electrons.com/source/mm/fadvise.c">source code for posix_fadvise</a>. If you look closely you'll see that the NOREUSE is a no-op! Ugh.<br /><br />This is really quite awful. Besides Lucene, I can imagine a number of other apps that really should use this flag. For example, when mencoder slowly reads a 50 GB bluray movie, and writes a 5 GB H.264 file, you don't want any of those bytes to pollute your buffer cache. Same thing for rsync, backup programs, software up-to-date checkers, desktop search tools, etc. Of all the flags, this one seems like the most important to get right! It's possible other OSs do the right thing; I haven't tested.<br /><br />So what to do?<br /><br />One approach is to forcefully free the pages, using the DONTNEED flag. This will drop the specified pages from the buffer cache. But there's a serious problem: the search process is using certain pages in these files! So you must only drop those pages that the merge process, alone, had pulled in. You can use the <a href="http://www.kernel.org/doc/man-pages/online/pages/man2/mincore.2.html">mincore</a> function, to query for those pages that are already cached, so you know which ones not to drop. A <a href="http://insights.oetiker.ch/linux/fadvise">neat patch for rsync</a> took exactly this approach. The problem with this is mincore provides only a snapshot, so you'd have to call it many times while merging to try to minimize discarding pages that had been recently cached for searching.<br /><br />We should not have to resort to such silly hacks!<br /><br />Another approach is to switch to memory-mapped IO, using Lucene's MMapDirectory, and then use madvise. The SEQUENTIAL option looks promising from the man page:<br /><br /><em>Expect page references in sequential order. (Hence, pages in the given range can be aggressively read ahead, and may be freed soon after they are accessed.)</em><br /><br />Looking through the linux sources it look like the SEQUENTIAL option is at least not a no-op; that setting has some influence over how pages are evicted.<br /><br />So I tested that, but, alas, the search performance still plummets. No go!<br /><br />Yet another approach is to bypass all OS caching entirely, only when merging, by using the Linux-specific O_DIRECT flag. Merge performance will definitely take a hit, since the OS is no longer doing readahead nor write caching, and every single IO request must hit the disk while you wait, but for many apps this could be a good tradeoff.<br /><br />So I created a prototype Directory implementation, a variant of DirectNIOFSDirectory (currently a patch on <a href="https://issues.apache.org/jira/browse/LUCENE-2056">LUCENE-2056</a>), that opened all files (input and output) with O_DIRECT (using jni). It's a little messy because all IO must be "aligned" by certain rules (I followed the rules for 2.6.* kernels).<br /><br />Finally, this solution worked great! Search performance was unchanged all through the optimize call, including building the CFS at the end. Third time's a charm!<br /><br />However, the optimize call slowed down from 1336 to 1680 seconds (26% slower). This could likely be reduced by further increasing the buffer sizess (I used 1 MB buffer for each IndexInput and IndexOutput, which is already large), or possibly creating our own readahead / write cache scheme.<br /><br />We <em>really</em> should not have to resort to such silly hacks!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2119311654280007305?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com13tag:blogger.com,1999:blog-8623074010562846957.post-28347919225070324812010-06-06T11:58:00.010-04:002010-06-06T13:54:30.979-04:00Finding the lead in your houseIt's known that <a href="http://www.cnn.com/2010/HEALTH/05/13/lead.poisoning.landrigan/index.html">exposure to lead</a>, even in tiny amounts, causes loss of intelligence and other nasty problems in children.<br /><br />We have now phased out lead paint, leaded gasoline, and <a href="http://en.wikipedia.org/wiki/Restriction_of_Hazardous_Substances_Directive">lead (and other dangerous elements) in electronics</a>. But, surprisingly, it was only relatively recently (2008) with the passage of <a href="http://en.wikipedia.org/wiki/Consumer_Product_Safety_Improvement_Act">Consumer Product Safety Improvement Act</a> that we finally set limits on the amount of lead in consumer items, particularly kids toys. As of June 2010, the legal limit for lead in kid's toys is 300 ppm (parts per million) and will drop to 100 ppm by August 2011. The legal limit for cadmium in paint on kid's toys is 75 ppm.<br /><br />Our house is filled with all sorts of toys, many of which we've picked up as hand-me-downs from various sources. I've long wondered whether these toys have lead, cadmium, etc...<br /><br />So, I decided to test them myself, using an <a href="http://www.niton.com/Niton-Analyzers-Products/xl3/xl3t.aspx?sflang=en">XRF analyzer</a>. This amazing handheld device emits a small directed xray beam out the front, causing elements to <a href="http://en.wikipedia.org/wiki/X-ray_fluorescence">fluoresce</a> with specific spectral signatures. The device detects the strength of these signatures and reports back to you the breakdown of elements in the sample, either in parts per million (ppm) or in percentage (1% = 10,000 ppm!).<br /><br />In addition to <a href="http://en.wikipedia.org/wiki/Lead">lead</a>, the device reliably detects other elements like <a href="http://en.wikipedia.org/wiki/Cadmium">cadmium</a>, <a href="http://en.wikipedia.org/wiki/Bromine">bromine</a> (used in <a href="http://en.wikipedia.org/wiki/Brominated_flame_retardant">brominated flame retardants</a>), <a href="http://en.wikipedia.org/wiki/Chlorine">chlorine</a>, <a href="http://en.wikipedia.org/wiki/Arsenic">arsenic</a>, <a href="http://en.wikipedia.org/wiki/Mercury_(element)">mercury</a>, <a href="http://en.wikipedia.org/wiki/Tin">tin</a>, <a href="http://en.wikipedia.org/wiki/Antimony">antimony</a>, <a href="http://en.wikipedia.org/wiki/Chromium">chromium</a>, and many others!<br /><br />There are some limitations. For example, all of the door knobs in my house tested high (1-2%) for lead, however, it turns out they are nickel plated but the XRF analyzer was seeing through this layer to the lead beneath. Likely this lead would never transfer to our hands, unless the nickel wears through.<br /><br />Another limitation is that the device detects elements, not their molecular form. For example, certain forms of <a href="http://en.wikipedia.org/wiki/Chromium">chromium</a>, like hexavalent chromium, are toxic, while other forms, like trivalent chromium, is useful and necessary in the human body.<br /><br />Finally, just because a material contains a given element doesn't mean that element would ever find its way into a child's body. For example, lead bound in plastic is likely difficult to dislodge.<br /><br />For all these reasons, just because the analyzer detects certain elements in a given item, does not mean the item could cause harm. Think of the analyzer as a simple fact-finder: it reports the raw elements it sees. What action you then choose to take is your decision. However, the <a href="http://en.wikipedia.org/wiki/Precautionary_principle">precautionary principle</a> applies here: if an item does have measurable amounts of lead or cadmium, why risk exposing your family to it?<br /><br />While the devices are still insanely expensive, they have come down in price enough to make rental just barely within reach for the end consumer. I rented mine (a <a href="http://www.niton.com/Niton-Analyzers-Products/xl3/xl3t.aspx?sflang=en">Niton XL3T</a>) for a few hundred dollars a day from from <a href="http://www.ashtead-technology.com/">Ashtead Technology</a>, and split the cost with a neighbor (she tested by night and I tested by day!).<br /><br />So I walked around my house, testing everything, and the results were a real eye-opener! A number of ordinary looking things had lead, sometimes at levels far higher than the 300 ppm legal limit, plus other possibly harmful elements:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_4pUbN9gxhUI/TAvXFTVMZQI/AAAAAAAAAAc/4Aweqn3JOMQ/s1600/lead1.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 225px;" src="http://3.bp.blogspot.com/_4pUbN9gxhUI/TAvXFTVMZQI/AAAAAAAAAAc/4Aweqn3JOMQ/s400/lead1.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5479709857714824450" /></a><br /><br />The green rain coat has 6,537 ppm lead; the handle on the lacrosse stick has 14,700 ppm lead; the basketball has 3,320 ppm lead and 322 ppm arsenic; the lunchbox has 677 ppm lead; the doctor's bag has 2,511 ppm antimony and 55 ppm arsenic. Many smaller toys also have lead:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_4pUbN9gxhUI/TAvXrmRowzI/AAAAAAAAAAk/Ch72RG8XcJU/s1600/lead3.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 397px; height: 317px;" src="http://4.bp.blogspot.com/_4pUbN9gxhUI/TAvXrmRowzI/AAAAAAAAAAk/Ch72RG8XcJU/s400/lead3.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5479710515635209010" /></a><br /><br />The red measuring spoon has 1,651 ppm lead; the blue dinosaur has 767 ppm lead and 91 ppm cadmium; the red car has 860 ppm lead; the red plate has 3,268 ppm lead; the blue train has 271 ppm lead; the little green ABC has 1,015 ppm lead. The three legos were surprising, having between 1,245 and 2,427 ppm lead -- they are not actually legos; they are a copycat brand (Mega Bloks). All of our "real" legos tested fine.<br /><br />Other toys have high cadmium:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_4pUbN9gxhUI/TAvZR7hozJI/AAAAAAAAAAs/MdQWFuCXLuo/s1600/lead2.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 342px; height: 205px;" src="http://1.bp.blogspot.com/_4pUbN9gxhUI/TAvZR7hozJI/AAAAAAAAAAs/MdQWFuCXLuo/s400/lead2.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5479712273686121618" /></a><br /><br />The little slinky has 527 ppm cadmium and 1,365 ppm lead; the salt shaker has 22,634 ppm cadmium; the ice cream scoop has 1,188 ppm cadmium. Here were a bunch of other small toys that had varying amounts of lead:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_4pUbN9gxhUI/TAvZosEkGII/AAAAAAAAAA0/x0NNgXCE9CU/s1600/lead4.jpg"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 306px;" src="http://4.bp.blogspot.com/_4pUbN9gxhUI/TAvZosEkGII/AAAAAAAAAA0/x0NNgXCE9CU/s400/lead4.jpg" border="0" alt=""id="BLOGGER_PHOTO_ID_5479712664674637954" /></a><br /><br />Small toys are especially spooky since babies are more likely to put them in their mouth. These pictures show only about 1/3rd of the things I found with lead! Here are some other surprising discoveries:<br /><ul><br /><li> Old Christmas ornaments often have very high lead. I had one silver ball that had ~1% arsenic, ~20% lead. Worse, it was well worn, which means the arsenic and lead had rubbed of onto people's hands, over the years.<br /><br /><li> Car keys have lead (~6,700 ppm for my 2 keys)! Don't let your babies play with them.<br /><br /><li> Nearly every wire has high lead content in the insulation; christmas lights had especially high lead.<br /><br /><li> The soft (usually black) plastic/rubber kids bike handles, and also tricycles, are often very high in lead.<br /><br /><li> An old recliner had 29,500 ppm lead on the foot rest and 20,000 ppm lead on the arm rests.<br /><br /><li> Our door knobs, cabinet knobs, faucets, and spouts, had ~1-2% lead.<br /><br /><li> We had a jar of kid's vitamins. The vitamins tested OK, but the jar (it was a dark brown tint) had 140 ppm lead.<br /><br /><li> One of our garden hoses had 5,255 ppm lead; not great because we had used this hose to water the plants in our edible garden.<br /><br /><li> Our waffle iron had 1,143 ppm lead on the cooking surface (likely, though, this was the metal under the teflon).<br /><br /><li> My supposedly lead-free solder (was not cheap!!) in fact contains 0.5% lead.<br /></ul><br /><br />Here are some "rough" patterns:<br /><ul><br /><li> The older the toy, the more likely it is to have high lead, cadmium, etc.<br /><br /><li> Newer things that are "burnable" (fleece, bedding, futons, mattresses, beds, plush chairs, etc.) often have very high (10s of thousands ppm) levels of bromine.<br /><br /><li> Colors like yellow, orange, red often have lead in their pigment.<br /><br /><li> Beware glasses that have paint on them! We had one glass that was 8% lead -- 266 times the legal limit. Colored glass (where the color is embedded into the glass) are also more likely to be leaded.<br /></ul><br /><br />I'm not the only consumer playing with XRf analyzers: a recent recall of 12M Shrek glasses by McDonald's was initiated by at least two people who <a href="http://www.npr.org/templates/story/story.php?storyId=127474049&ps=cprs">discovered high levels of cadmium in the paint on the glass using XRF analyzers</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2834791922507032481?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-59927789594580226402010-06-05T14:53:00.007-04:002010-10-04T13:59:04.628-04:00Lucene's PulsingCodec on "Primary Key" FieldsFlexible indexing in <a href="http://lucene.apache.org">Lucene</a> (now available on trunk, which will eventually be the next major release, 4.0) enables apps to use custom codecs to write/read the postings (fields, terms, docs, positions, payloads).<br /><br />By default, Lucene uses the <em>StandardCodec</em>, which writes and reads in nearly the same format as the current stable branch (3.x). Details for a given term are stored in terms dictionary files, while the docs and positions where that term occurs are stored in separate files.<br /><br />But there is an experimental codec, <em>PulsingCodec</em>, which implements the <em>pulsing</em> optimization described in a <a href="http://www.jopedersen.com/Publications/cutting90optimizations.pdf">paper by Doug Cutting and Jan Pedersen</a>. The idea is to inline the docs/positions/payloads data into the terms dictionary for low frequency terms, so that you save 1 disk seek when retrieving document(s) for that term.<br /><br />The <tt>PulsingCodec</tt> wraps another fallback <tt>Codec</tt> that you provide; this allows the pulsing to be dynamic, per term. For each term, if its frequency (the number of documents that it appears in) is below a threshold (default 1) that you provide, then that term's postings are inlined into the terms dictionary; otherwise, the term is forwarded (<em>pulsed</em>) to the wrapped codec. This means <tt>PulsingCodec</tt> should be helpful for ordinary text fields which obey <a href="http://en.wikipedia.org/wiki/Zipf's_law">Zipf's Law</a>, as many terms will be rare-ish.<br /><br /><tt>PulsingCodec</tt> should really shine on "primary key" fields, where each term occurs in exactly one document, and batch lookups (for example because the app performs deletes, updates and/or lookups) are common.<br /><br />I created a simple performance test to confirm this.<br /><br />The test first creates an optimized index with 10M docs, where each doc has a single field with a randomly generated unique term, and then performs term -> doc lookup for N (parameter) random terms. It's a self-contained test (source code is <a href="http://www.codeupload.com/572">here</a>).<br /><br />It's important to flush your OS's IO cache before running the test; otherwise you can't measure the reduced number of seeks. On recent Linux kernels, just run <em>echo 1 > /proc/sys/vm/drop_caches</em>. That said, in a real production usage, the IO cache will typically (legitimately) help you, and pulsing should make more efficient use of the IO cache since the postings data is contiguously stored.<br /><br />To measure the speedup from using <tt>PulsingCodec</tt> on a primary key field, as well as the impact of the OS's IO cache, I ran the <a href="http://www.codeupload.com/572">above test</a> on an increasing number of random term lookups (always flushing the the OS's IO cache first):<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_4pUbN9gxhUI/TAqnyf2_49I/AAAAAAAAAAU/yXDf6by8VUY/s1600/PulsingSpeedup.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 209px;" src="http://1.bp.blogspot.com/_4pUbN9gxhUI/TAqnyf2_49I/AAAAAAAAAAU/yXDf6by8VUY/s400/PulsingSpeedup.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5479376382637106130" /></a><br /><br />The results are compelling! When performing a small number of term lookups relative to the total number of terms on a cold OS IO cache, which is likely the more common case in a real application, pulsing shows a ~45-50% speedup, as expected, since it requires 1/2 the seeks.<br /><br />As the number of random term lookups increases, <tt>PulsingCodec</tt>'s gains decrease, because more and more of the lookups are hitting the OS's IO cache and thus avoiding the seek (the machine I ran the test on had plenty of RAM to cache the entire index). It's interesting that <tt>PulsingCodec</tt> still shows ~15% gain once the lookups are mostly cached; likely this is because <tt>PulsingCodec</tt> saves the deref cost of finding the postings in the <tt>frq</tt> file.<br /><br />Pulsing also makes the index a bit smaller (211 MB vs 231 MB), because it saves one vLong pointer per term. For the test, the index with pulsing had a 0 byte <tt>frq</tt> file since all postings were inlined into the terms dict. There is no <tt>prx</tt> file because I index the field with <tt>setOmitTermFreqAndPositions(true)</tt>.<br /><br />Note that the <a href="http://www.codeupload.com/572">test case</a> simply uses PulsingCodec for all fields; if you'd like per-field control you should use the <tt>PerFieldCodecWrapper</tt>. However, because <tt>PulsingCodec</tt> is dynamic (per term), it is likely a good default for all fields.<br /><br />Another way to speed up primary key lookups through Lucene is to store your index on a solid-state disk, where seeks are much less costly than they are on spinning magnets (though, still several orders of magnitude more costly than RAM). Or better yet, do both!<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5992778959458022640?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com1tag:blogger.com,1999:blog-8623074010562846957.post-1221721393047266082010-05-14T08:28:00.002-04:002010-05-14T10:56:21.855-04:00Cancer and chemicalsThe <a href="http://deainfo.nci.nih.gov/advisory/pcp/pcp.htm">President's Cancer panel</a> yesterday released their <a href="http://deainfo.nci.nih.gov/advisory/pcp/pcp08-09rpt/PCP_Report_08-09_508.pdf">2008-2009 annual report</a>. It's a long (240 page) report, and what's amazing is that these are mainstream scientists who are now calling for precautionary reduction of our exposure to all sorts of chemicals we are now routinely exposed to.<br /><br />It has some sobering facts about cancer, such as:<br /><br /><em>Approximately 41% of Americans will be diagnosed with cancer at some point in their lives, and 21% will die from it.</em><br /><br />And:<br /><br /><em>The incidence of some cancers, including some most common among children, is increasing for unexplained reasons.</em><br /><br />This <a href="http://www.nytimes.com/2010/05/06/opinion/06kristof.html?src=me&ref=homepage">this op-ed</a> pulls out some great highlights from the report. For example, here's a depressing one:<br /><br /> <em>Noting that 300 contaminants have been detected in umbilical cord blood of newborn babies, the study warns that: "to a disturbing extent, babies are born 'pre-polluted.' "</em><br /><br />And then there's this quote:<br /><br /> <em>The report blames weak laws, lax enforcement and fragmented authority, as well as the existing regulatory presumption that chemicals are safe unless strong evidence emerges to the contrary.</em><br /><br />Congress is now attempting to address this, with the <a href="http://chbits.blogspot.com/2010/04/safe-chemicals-act.html">Safe Chemicals Act</a>.<br /><br />Here is a quote specifically about <a href="http://chbits.blogspot.com/2009/08/on-bottled-water.html">Bisphenol A</a>:<br /><br /> <em>Studies of BPA have raised alarm bells for decades, and the evidence is still complex and open to debate. That's life: In the real world, regulatory decisions usually must be made with ambiguous and conflicting data. The panel's point is that we should be prudent in such situations, rather than recklessly approving chemicals of uncertain effect.</em><br /><br />This is an important point: during the time of uncertainty, when we don't know that a given chemical is dangerous nor do we know that it is safe, we should err on the side of caution, treating the chemical as guilty until proven innocent. I discovered that there is a name for this approach: the <a href="http://en.wikipedia.org/wiki/Precautionary_principle">precautionary principle</a>, and this is of course the core change to the Safe Chemicals Act.<br /><br />Here's yet another quote, this time from a <a href="http://www.cnn.com/2010/HEALTH/05/13/lead.poisoning.landrigan/index.html">brief article</a> about one of the scientists who discovered lead exposure, even in tiny amounts, is very dangerous for kids:<br /><br /><em>We've been very careless in simply presuming that chemicals are innocent until proven guilty," says Dr. Phillip Landrigan.</em><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-122172139304726608?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-56803668547070461332010-05-13T11:14:00.002-04:002010-05-13T11:35:02.293-04:00Plants and animals use quantum mechanics?<a href="http://en.wikipedia.org/wiki/Quantum_mechanics">Quantum mechanics</a>, which Einstein once referred to as "spooky action at a distance", is a set of laws that govern how tiny (atomic & sub-atomic) things interact with one another. The laws are very different from classical physics, and really quite surprising, but nevertheless appear to be true (there's been much experimental validation).<br /><br />Using quantum mechanics, it's possible to build a quantum computer, and indeed many research labs and at least one <a href="http://en.wikipedia.org/wiki/D-Wave_Systems">startup</a>, have built simple ones. Quantum computers can do some amazing things, such as <a href="http://en.wikipedia.org/wiki/Shor's_algorithm">factoring integers very quickly</a>, something classical computers can only do very slowly as the number gets bigger (as best we know, so far).<br /><br />Most recently, a simplistic quantum computer was used to <a href="http://www.popsci.com/science/article/2010-05/single-molecule-computes-thousands-times-faster-your-pc">compute a discrete fourier transform using a single iodine molecule</a>. Someday quantum computers will be all over the place...<br /><br />But, isn't it possible that plants and animals have evolved to take advantage of quantum mechanics? Indeed there is evidence that we have! <br /><br />The process of photosynthesis looks to be <a href="http://www.nanowerk.com/news/newsid=16218.php">based on quantum entanglement</a>.<br /><br />And, one leading theory about how animals can smell so well is based on <a href="http://www.scientificamerican.com/article.cfm?id=is-sense-of-smell-powered">quantum vibrations</a>. Luca Turin, who created this theory, has a good quote in that article:<br /><br /><em>Most people would probably feel that if it can be done at all, evolution has managed to make use of it.</em><br /><br />And this makes sense - evolution is relentless at trying to find good ways to create plants and animals. Since quantum mechanics is real, evolution should have tapped into it.<br /><br />This is also the reason I would expect <a href="http://en.wikipedia.org/wiki/Lamarckism">Lamarckian inheritance</a> to in fact be true. Any animal that can alter the traits of its offspring based on experiences in its own lifetime would clearly have a big advantage, so, evolution really should have found a way.<br /><br />In fact, it sort of did, in a non-biological manner: language. We can pass on all sorts of life lessons to our kids, through language, and we get to stand on the shoulders of past giants, as we take for granted the knowledge created by the generations before us, passed on through language.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5680366854707046133?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-75232569147920194342010-05-03T06:50:00.002-04:002010-05-03T06:53:07.608-04:00Lots of problems these days...I try to keep my kids roughly informed about what's going on in the world; I think it's important they grow up with at least a basic world view.<br /><br />Last night, my 7 year old son observed "you know there are alot of problems right now", and he's right! He then rattled off the <a href="http://www.youtube.com/watch?v=f1ztg0wUqKY">Iceland volcano eruption</a>, the <a href="http://www.boston.com/news/local/massachusetts/articles/2010/05/02/a_catastrophic_rupture_hits_regions_water_system">ruptured water main in our state</a>, forcing us to boil water before drinking it, and the disastrous <a href="http://en.wikipedia.org/wiki/Deepwater_Horizon_drilling_rig_explosion">oil rig explosion and subsequent and ongoing oil geyser</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7523256914792019434?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-30840273203522699342010-05-03T06:35:00.003-04:002010-05-03T06:44:02.981-04:00Concord bans sale of bottled waterFabulous! The town of Concord, MA has <a href="http://www.boston.com/lifestyle/green/articles/2010/05/01/concord_fires_first_shot_in_water_battle/">banned the sale of bottled water</a> because of the wretched environmental impact these bottles have.<br /><br />The environmental cost of such trash is stunning. We know this fills up our landfills, but have you heard of the <a href="http://en.wikipedia.org/wiki/Great_Pacific_Garbage_Patch">Great Pacific Garbage Patch</a>? This is one of 5 spots in the oceans where garbage collects and kills marine life.<br /><br />Of course you really shouldn't <a href="http://chbits.blogspot.com/2009/08/on-bottled-water.html">drink bottled water in the first place</a>.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3084027320352269934?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-42353506272722079932010-05-02T09:30:00.003-04:002010-05-02T09:32:53.197-04:00Your ideas and your nameI love this quote:<br /><br /><em>Your ideas will go further if you don't insist on going with them.</em><br /><br />It's very true (note that I didn't tell you who said it)!<br /><br />I find it especially applies to healthy open source projects. In Apache, the individuals (contributors, committers) who work on a given project are fleeting, transient. We will come and go. Our names are not attached to the code we commit.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4235350627272207993?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-4408599929989423192010-05-02T09:09:00.002-04:002010-05-02T09:25:03.155-04:00Sinister search engine de-optimizationThere's a <a href="http://www.washingtonpost.com/wp-dyn/content/article/2010/05/01/AR2010050103051.html">large recall going on right now</a> for many popular over-the-counter infant's and children's medicines, such as <a href="http://www.mcneilproductrecall.com/page.jhtml?id=/include/new_recall.inc">Motrin</a>, <a href="http://www.mcneilproductrecall.com/page.jhtml?id=/include/new_recall.inc">Tylenol</a>, and <a href="http://www.mcneilproductrecall.com/page.jhtml?id=/include/new_recall.inc">Zyrtec</a>.<br /><br />But if you look at the <a href="http://www.mcneilproductrecall.com/page.jhtml?id=/include/new_recall.inc">recall details page</a>, posted by the company that manufactures these medicines (McNeil), you'll see that the table is actually a single JPEG image instead of an HTML table. If you don't believe me, try searching in your browser for the words you see in that table!<br /><br />At first I thought "how strange -- why would they use an image instead of a normal HTML table?". But then a more sinister plot came to mind: perhaps they want to make it as hard as possible for future web searches to find this page. After all, they must now be in major damage control mode. It's the exact opposite problem of the more common <a href="http://en.wikipedia.org/wiki/Search_engine_optimization">search engine optimization</a>.<br /><br />Hiding text into a JPEG image to avoid searches finding you is a rather nasty practice, in my opinion (hmm, I see there's even <a href="http://www.hidetext.net">this service</a> to help you do it!). Google could prevent such sneakiness by running <a href="http://en.wikipedia.org/wiki/Optical_character_recognition">OCR</a> on the image (perhaps they do this already -- anyone know?), but then I suppose the war would escalate and we'd start seeing barely readable tables like this that look like the dreaded <a href="http://en.wikipedia.org/wiki/CAPTCHA">Captcha tests</a>. To workaround such companies, if we all link to this page with some real text (as I've done above) then Google will still find it!<br /><br />It's also possible there's a more reasonable explanation for this maybe the good old saying "<em>never attribute to malice that which can be adequately explained by something else</em>" somehow applies?<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-440859992998942319?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-71039597247864477342010-04-18T19:34:00.002-04:002010-04-18T19:40:32.542-04:00Safe Chemicals ActFinally, there's been a bill introduced to congress, called the Safe Chemicals Act, to better regulate the chemicals we all are exposed to in day to day products.<br /><br />The current law (from 1976) is ancient, and assumes any chemical is safe until proven otherwise -- innocent until proven guilty -- a dangerously lax approach which has resulted in the potentially dangerous chemicals we all have heard about, such as bisphenol A in certain plastics, brominated flame retardents, numerous phthalates released by vinyl (this causes that awful new shower curtain smell), etc.<br /><br />There are 80,000 chemicals in use today and the EPA has only required testing for 200 of them. There are surely additional dangerous chemicals lurking, undetected.<br /><br />Refreshingly, the new bill takes the opposite approach, the same I approach I take with my family: a chemical is guilty until proven innocent! This is why I use no pesticides on my <a href="http://chbits.blogspot.com/2009/08/life-support-grass.html">life support grass</a>.<br /><br />If this bill becomes law, manufacturers must prove a chemical is safe before they can use it in their products. The burden of proof moves to the manufacturers. <a href="http://www.time.com/time/health/article/0,8599,1982489,00.html">Here</a>'s a good writeup of the bill.<br /><br />Lobbyists will undoubtedly fight this bill tooth and nail... so we need to push our congressional representatives!! You can use <a href="http://bit.ly/bluzJt">this site</a> to do so.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7103959724786447734?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-16797418340935396732010-03-08T06:22:00.002-05:002010-03-08T06:31:51.305-05:00Disagreements are healthy!Another great quote, this time from Henry Ford:<br /><br /><span style="font-style:italic;">If two people always agree, one if them is unnecessary.</span><br /><br />The quote applies very well to open source development -- what makes open source so strong is that such wildly diverse people, with different backgrounds, ideas, approaches, languages, IDEs, interests, itches, sleeping habits, coffee addictions, etc., come together and work on the same problems.<br /><br />And lots of disagreement ensues.<br /><br />As long as the resulting discussions are driven by technical merit and not personal attacks (ie, <a href="http://theapacheway.com">The Apache Way</a>), and consensus is eventually reached, then the disagreements are very powerful.<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-1679741834093539673?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-78332125056715824792010-02-25T08:31:00.002-05:002010-02-25T10:13:19.974-05:00Serenity, courage and wisdom<div>I love this quote:</div><div><br /></div><div> <i>Strive for the serenity to accept the things you cannot change;</div><div> courage to change the things you can; and wisdom to know the</div><div> difference.</i></div><div><br /></div><div>It's the opening to the Serenity Prayer (from the Bible), but I've taken the liberty of replacing <i>God grant</i> with <i>strive for</i>.</div><div><br /></div><div>The idiom "pick your battles" means the same thing as the 3rd goal.</div><div><br /></div><div>This great quote from <a href="http://elise.com/quotes/quotes/shawquotes.htm">George Bernard Shaw</a> relates closely to the 2nd goal:</div><div><br /></div><div><i>The reasonable man adapts himself to the conditions that surround him...</div><div> The unreasonable man adapts surrounding conditions to himself...</div><div> Therefore, all progress depends on the unreasonable man</i></div><div><br /></div><div>Think about these goals. You'll likely find that each goal is distinct, very important, and somewhat surprisingly often applies in your day to day life.</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7833212505671582479?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-61655320489664855522010-02-04T10:25:00.001-05:002010-02-04T10:30:23.357-05:00Why do people vote against their own interests?<div>I found <a href="http://news.bbc.co.uk/2/hi/americas/8474611.stm">this article</a> very interesting.</div><div><br /></div><div>The first thing that struck me is its detached tone -- sort of like the curious look a child gives when looking inside a cage at an exotic animal. Probably this was written by someone who lives in Great Brittain, looking over the Atlantic ocean with mild curiosity at how crazy the US health care situation is.</div><div><br /></div><div>The second thing that struck me is that the observation is very true. A huge majority of the population in this country would benefit from health care reform, including the public option. Those who cannot afford health insurance now, those with pre-existing conditions, etc.</div><div><br /></div><div>Yet, many people who stand to benefit angrily fight reform. It's just plain weird. Here are two quotes from the article:</div><div><ul><li>Why are so many American voters enraged by attempts to change a horribly inefficient system that leaves them with premiums they often cannot afford?<br /><br /></li><li>In Texas, where barely two-thirds of the population have full health insurance and over a fifth of all children have no cover at all, opposition to the legislation is currently running at 87%.</li></ul></div><div>Finally, the two books referenced by the article certainly look relevant, roughly concluding that the average American doesn't really make decisions based on facts. (This also means "trial by a jury of your peers" is not a very comforting approach.) While I haven't read these books, I have come to the same depressing conclusion.</div><div><br /></div><div>A democracy is only as effective as its population is at making rational decisions.</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-6165532048966485552?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-81736036759817639672010-02-04T08:17:00.001-05:002010-02-04T08:20:19.288-05:00Why not create a public bank?<div>Why don't we have a public bank already? I mean a bank run by the federal government that competes with private banks, keeping them honest.</div><div><br /></div><div>Let's recap what's happened in the past few years. First, the financial world collapsed (the risky sub-prime loans, CDOs, etc.). So, the federal gov't was forced to loan insane amounts of taxpayer's (and our children's future) money to the banks, just to barely keep them afloat. By and large, that worked: the banks have survived and recovered.</div><div><br /></div><div>Yet, today they still pay out insane bonuses to their top employees, still fly around in private jets, throw lavish parties, travel to exotic places, etc. They are not extending the loans to small businesses that are required for our economy to really recover. And they are now spending lots of money, fighting the legislation that would regulate things to prevent a future collapse from happening again. In short, they have not changed.</div><div><br /></div><div>Something has gone terribly wrong!</div><div><br /></div><div>See, these banks don't contribute directly to economic progress. They don't build houses, invent new products, grow food, create more fuel efficient cars, etc. Really they are just the "lubrication" to enable all the real progress in our economy. They are not suposed to make tons of money, yet they do. And they most certainly shouldn't be given the power to hold our economy hostage, as they are today.</div><div><br /></div><div>So why not create a public bank, run by the federal government, that would extend legitimate loans with reasonable terms, today? This would put a strong competitive pressure on the existing banks to lend, as the public bank would otherwise take customers away. It would be a much more direct way to stimulate the economy, than the "give lots of money to the banks and hope they loan it out instead of paying themselves fat bonuses" approach that is clearly not working very well today.</div><div><br /></div><div>It could be a temporary creation, only around until the private banks start behaving well again. Or it could remain indefinitely, keeping the banks honest over time.</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8173603675981763967?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-88717638111781264442009-12-11T06:10:00.002-05:002009-12-11T06:23:01.311-05:00Harmony is stuck in my head!<div><div><div>I often get songs stuck in my head, but I've noticed a curious thing: I'm especially proned to getting songs with a <a href="http://en.wikipedia.org/wiki/Harmony">harmony</a> stuck in my head. It's a puzzle and my brain won't stoup until it's teased apart the primary melody and harmony. Literally it just keeps playing over and over, even as I type this.</div><div><br /></div><div><a href="http://www.youtube.com/watch?v=meT2eqgDjiM">This is the song stuck in my head right now</a>. It's a great rendition of Michael Jackson's beat it. I especially love the Xylophone -- it's partially <a href="http://en.wikipedia.org/wiki/Syncopation">syncopated</a> (plays, sometimes, on the off beat). The harmony starts at 1:14. Warning: it's addictive -- your brain, too, may not stop until it's figured out the harmony!</div><div><br /></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8871763811178126444?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-54554444489136279352009-11-09T08:23:00.003-05:002009-11-09T08:33:13.778-05:00Direct DemocracyI think <a href="http://www.NaturalNews.com/027439_Congress_democracy_America.html">this is a great idea</a>, to allow the US population to vote, directly, on whether a bill should become law, instead of the indirect process we now use, trusting our congresspeople to vote on our behalf.<div><br /></div><div>Everyone in the US knows how lobbyists, hired by corporations or other groups with lots of money, sway how our congresspeople vote by simply bribing them. It's a disgusting situation, yet, somehow we all complacently accept it as normal. I'm sure our founding fathers had no idea this would happen nor how much technology would advance.</div><div><br /></div><div>Congress does other things, of course, like holding public hearings on important topics, etc., so I don't think it'll really be as simple as outright abolishing it.</div><div><br /></div><div>Unfortunately it seems very unlikely that the US will ever switch to a direct democracy. But I for one would sure love to see it.</div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5455444448913627935?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com3tag:blogger.com,1999:blog-8623074010562846957.post-79774291607305593482009-10-24T07:28:00.003-04:002009-10-24T07:45:35.608-04:00Discrimination against kids<div>A few weeks back we went camping with the kids; it was great fun! I did tons of camping as a kid and I've been eagerly looking forward to our kids being old enough to go. They finally are.</div><div><br /></div><div>My wife found a rather luxurious campground: it had indoor pools, jacuzzi, outdoor pools, places to buy food, drinks, firewood, etc. It was generally very kid friendly -- lots of activities for kids, play room, etc. We were quite spoiled and we loved it.</div><div><br /></div><div>However, there was a strict rule that kids are not allowed in the jacuzzi nor the sauna. When we pulled out inflatable pool toys, we were politely informed that they, too, are not allowed.</div><div><br /></div><div>Now, don't get me wrong: these rules are common these days. Many places with pools and jacuzzis and saunas will have the same rules. These rules didn't exist when I was a kid, but now they are commonplace and accepted as normal. My kids just accepted them, in stride, as kids will do.</div><div><br /></div><div>But I am bothered: this is quite simply discrimination against kids.</div><div><br /></div><div>I understand why the rules are there. Thanks to our overly litigious society, if kids get hurt in the pool or overheat in the jacuzzi, the parents sue the campground rather than accept their own negligence. And unfortunately, they often win, or, settle out of court. This is not unlike McDonalds being sued for making coffee that's too hot.</div><div><br /></div><div>At the same time, we also have become a "safety above all" society, for better or worse. We must wear helmets when we bike, elbow pads and knee pads when we get on our roller blades, seat belts and car seats when we go driving, life preservers if we get anywhere near water. Kids barely venture out into their front yard, let alone out around the neighborhood, for the [overblown] fear that something bad could happen. Examples abound.</div><div><br /></div><div>As a parent I fully appreciate the dangers of water. In fact water is a terrifying combination: it is at once incredibly fun yet also deadly. To a child who can't yet swim, a pool is literally a potential death trap, and it's the parent's job to keep their kids safe.</div><div><br /></div><div>Thus, the insurance costs go up, likely by quite a bit, if the campground allows such "unsafe" activities, and so they choose to discriminate against kids and save some money.</div><div><br /></div><div>There was a time when slavery was common place, but that certainly didn't make it right. Just because kid discrimination has now become widely accepted does not make it right. If you encounter discrimination against your kids when you travel, please write up a review making this clear so future families can plan accordingly.</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-7977429160730559348?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-56615700595681083462009-09-30T07:45:00.001-04:002009-09-30T07:50:37.332-04:00A better grass?<div><div><div><div>I came across this article about a <a href="http://www.boston.com/business/articles/2009/07/04/wayland_man_has_developed_seeds_that_produce_a_greener_grass/">newly developed grass</a> that does not require the normal intense life-support we all have come to assume is "normal".</div><div><br /></div><div>You don't have to water it (after the initial seeding), nor apply pesticides nor fertilizer. And it only requires mowing once per month instead of the typical once per week schedule for life-support grass. It was designed to simply survive, naturally, in our challenging northeast climate.</div><div><br /></div><div>I've always felt that such a grass must exist, but that the existing grass seed companies would not be interested in pursuing it. See, if the grass simply takes care of itself, we all will buy much less grass seed over time. The lawn care service industry will see much less business, mowing our lawns monthly instead of weekly. Manufacturers of pesticides and fertilizers and lawn care equipment will see less demand, etc. It's quite clearly not in the interest of the lawn care industry to pursue nor allow such innovation.</div><div><br /></div><div>I sure hope this grass is successful, but the pessimist in me expects that in a few years time, either this company will have been sued out of existence, or the rights to this grass will have been purchased for a princely sum, and then promptly shelved, by one of the big established players in the grass seed industry.</div><div><br /></div><div>For better or worse, capitalism favors waste in mature markets.</div><div><br /></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5661570059568108346?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-27666515013490021672009-09-24T07:57:00.002-04:002009-09-24T08:03:12.059-04:00<div><div><div><div><div><div>Today, on my morning run, I saw a student walking, late for the bus. The bus saw her walking, way down the road and so stopped and waited for probably two minutes or so for her to catch up and get on. </div><div><br /></div><div>This might seem like only reasonable behavior, on the bus driver's part. S/he was being nice, right?</div><div><br /></div><div>As crazy as it sounds, while it was a nice thing to do, I don't think the bus should have stopped. Here's why.</div><div><br /></div><div>It sends the message that one student's inability to be on time is allowed to cut into the time the rest of the students get at school. The needs of the one outweigh the needs of the many (thank you <a href="http://www.imdb.com/title/tt0084726/quotes">Spock</a>). It's only two minutes, but if this happens a few times on the route, day in and day out, that adds up to net/net less time at school for all the kids.</div><div><br /></div><div>The rest of the students, who made the bus on time, probably having rushed through their morning at home to do so, pay the price for those students who can't make the bus on time. They will conclude that they, too, can be a bit late and the bus will wait. Why bother rushing to be on time? Rather than being taught that they should try hard to make the bus on time, to take responsibility for not making others wait, they are taught the reverse.</div><div><br /></div><div>Finally, seeing the bigger picture, this teaches kids that the world will stop and wait for them. Make up for their faults. Be forgiving. That you need not try very hard for things because the rest of the world will compensate. You need not take responsibility. It ties right into the dangerous sense of entitlement that many kids seem to have now. For better or worse, the world simply is not like that once you grow up.</div><div><br /></div><div>She should have simply missed the bus and learned a good lesson.</div><div><br /></div></div></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-2766651501349002167?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-80120403562295794922009-09-05T17:09:00.003-04:002009-09-05T20:19:09.953-04:00Fun questionsHere are two fun questions I've [temporarily] stumped my kids on:<div><ul><li>How can gravity make something go up?</li><li>How can the moon get you wet?</li></ul></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8012040356229579492?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-30061244729030890152009-09-01T07:51:00.002-04:002009-09-01T08:19:10.131-04:00Spell correction<div>Spell correction is a challenging feature for search engines. Unfortunately, it's also crucial: mis-spelling is rampant when users run searches. In part this is because we all can't remember how to spell, and that's no wonder: the number of English words today is <a href="http://www.youtube.com/watch?v=pMcfrLYDm2U">5X what it was in Shakespeare's time</a>! But it's also because we are simply in a hurry, or, lazy, and make many typos.</div><div><br /></div><div>I rely on <a href="http://aspell.net/">aspell</a> when I'm using <a href="http://www.gnu.org/software/emacs">emacs</a>. Modern web browsers and word processors check the spelling of all text you enter. Web-side search engines have excellent spell correction; in fact, I no longer bother to correct my typos when entering a search. I've often wondered whether such "crutches" of our modern world are in fact weakening our minds and perhaps causing our language to further evolve? For example, I wonder how Microsoft Word's often wrong (in my experience) grammar checker has crimped "modern" writing.</div><div><br /></div><div>My Chemistry teacher in high school refused to allow us to use calculators during our tests, for fear that we would lose our ability to do math with only basic tools (paper, pencil, brain, hands). My Physics teacher did the opposite, for the reverse fear that the distraction of doing basic math would take precious time and thought away from actually thinking about how to solve the problems. Who's right?</div><div><br /></div><div>Google clearly sets the gold standard for respelling, that any search engine is now required to live up to. If you don't match that high bar, users are automatically disappointed. And you really don't want to disappoint your users: it's nearly impossible to get them to try out your new application, and, they often don't give second chances.</div><div><br /></div><div>For most approaches to spell correction, the more data you throw at them the better they perform. If you have lots of queries coming in, you can use that as your sole source. Google of course has tons of queries to tap into. If you are less fortunate, you can use your index/documents as your source. Both of these approaches assume most people know how to spell well! The assumption seems to hold, for now, but I have to wonder, as we all lean on this crutch and become worse at spelling with time, won't this eventually undermine Google's approach? No worries; Google will adapt. This is not unlike investing in index funds: that approach only works well if relatively few people do it.</div><div><br /></div><div>Lucene's <a href="http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/search/spell/SpellChecker.html">basic spellchecker package</a>, under contrib, which requires you to provide a Dictionary of "known words", allows you to derive these words from your search index. It has some limitations: it can only do context-free correction (one word at once, independent of all other words in the query); it doesn't take word frequency in the index into account when deriving the index (so if a typo gets into your index, which can easily happen, you could end up suggesting that typo!); etc. But it does provide a pluggable distance measure for picking the best candidate. It's a good start.</div><div><br /></div><div>One particularly sneaky feature to get right is spell correction in the context of entitlements; <a href="http://lucene.markmail.org/search/?q=java-user#query:java-user%20order%3Adate-backward+page:1+mid:tsthwag5byzbo6v3+state:results">my post this morning on Lucene's user list</a> raises this problem in a real use case (single index to search multiple user's emails). Entitlements means restricting access for certain users to certain documents. For example, you could have a large search index containing all documents from your large intranet, but because of security on the intranet, only certain users are allowed to access certain documents.</div><div><br /></div><div>Lucene makes it easy to implement entitlements during searching, by using static (based solely on what's indexed) or dynamic (based on some "live" external source at search time) filtering.</div><div><br /></div><div>However, properly doing spell correction in the presence of entitlements is dangerous. If you build a global lexicon based on your index, that lexicon can easily "bleed" entitlements when there are terms that only occur in documents from one entitlement class. This might be acceptable for context-free spell correction, but if your spell correction has context (can suggest whole phrases at a time) you could easily bleed a very dangerous phrase (eg, "Bob was fired") by accident.</div><div><br /></div><div>So, you might choose to splinter your spell correction dictionary by user class, but that could result in far too little data per user class. I'm not sure how to solve it, well; it's a challenging problem.</div><div><br /></div><div>I hope I haven't mis-spelled any words here!</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3006124472903089015?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-55685792368678647852009-08-28T10:36:00.002-04:002009-08-28T13:28:02.636-04:00The best way to learn is to teach<div><div><div>They say the best way to learn something is to teach it. Well, I say writing a book sure counts as teaching because writing the <a href="http://www.manning.com/hatcher3/">2nd edition of Lucene in Action</a> sure has taught me all sorts of juicy details about Lucene, far more than I would have learned on my own.</div><div><br /></div><div>I can also say that writing a book about an active open-source project is very demanding. I try to keep the manuscript current, as changes are happening to Lucene, but then more than once I've been burned by keeping it just a little too current, only to see that the community up and changed its mind on something I had already folded into the book's manuscript and source code!</div><div><br /></div><div>Finally, as Lucene is getting <a href="http://lucene.markmail.org/message/a4fw4icbwdmnkqfg">very close to releasing 2.9</a> I'm now scrambling to fix the loooong tail of little things all throughout the book. Even once I finish that, it's several more months for a deep technical review, Manning's production process, etc. I'm looking forward to finishing!</div><div><br /></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5568579236867864785?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-91594529482087595242009-08-23T09:05:00.002-04:002009-08-23T09:09:16.873-04:00A kid's mind<div>I just love how kids think. It's so carefree and unrestrained by all the silly "limitations" we adults have learned with time.</div><div><br /></div><div>Here's an example: we just finished a vacation with cousins (my kids' cousins). They were all in the car yesterday, eagerly discussing Halloween and who's going to wear what costume. But then they all realized and lamented that in fact they would not be together for Halloween. So, immediately, my son said "Dad, can we fly to California for Halloween?".</div><div><br /></div><div>It just tickled me pink! See, we live in Boston, MA, so flying to California is easily a 9 hr affair, one way, "door to door". Not to mention, expensive! But my son's thinking of course wasn't restrained by such silly things.</div><div><br /></div><div>As adults the idea would never be allowed to cross our mind. Somewhere, deep in our brains, is a group of neurons that quickly and mercilessly kills off such thoughts before we can even think them. But there's no such limitation, yet, with a kid's mind.</div><div><br /></div><div>If you spend even a small amount of time with any child, you'll see many examples of this unrestrained thinking, and it's delightfully refreshing. We all should strive not to grow up. It's easily the best thing you could do for yourself!</div><div><br /></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-9159452948208759524?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-44422273585628941522009-08-23T08:34:00.004-04:002009-08-28T07:55:21.928-04:00On bottled water<div><div><div><div><div><div><div><div><div>The bottled water industry is truly silly.</div><div><br /></div><div>It's an enormous money-maker, a $20B industry in the US alone. You're buying a product that's hundreds of times more expensive than tap water. Yet, often the bottled water simply comes from a municipal source anyway. Furthermore, it's easily less safe than your tap water. See, the EPA has tougher regulations for tap water than the FDA has for bottled water. For example, the FDA allows some contamination of <a href="http://en.wikipedia.org/wiki/Escherichia_coli">E Coli</a>, and does not require testing for known parasites such as <a href="http://en.wikipedia.org/wiki/Cryptosporidiosis">Cryptosporidium</a> or <a href="http://en.wikipedia.org/wiki/Giardia_lamblia">Giardia Lamblia</a>. Likely your bottled water does not contain <a href="http://en.wikipedia.org/wiki/Fluoride">Fluoride</a> as well.</div><div><br /></div><div>Not to mention the insane consumption of oil required to schlepp around all this bottled water and then again to discard the empty plastic bottles. You should of course recycle them, but precious few of us actually do and so they fill up landfill, a "gift" from us to our future generations. Or perhaps your empty bottles end up in the <a href="http://en.wikipedia.org/wiki/Great_Pacific_Garbage_Patch">Great Pacific Garbage Patch</a>.</div><div><br /></div><div>And as if all of this weren't already reason enough to avoid bottled water, there is the curious problem of the chemicals in plastic, such as <a href="http://en.wikipedia.org/wiki/Bisphenol_A">Bisphenol A</a> (BPA), leaching into the water over time. Previously, it was believed that these chemicals didn't easily leach unless the plastic was hot (this is why you're not suposed to put plastic containers in the microwave or dishwasher).</div><div><br /></div><div>However, <a href="http://focus.hms.harvard.edu/2009/061909/research_briefs.shtml">this delightful study</a> showed that simply drinking bottled water increased BPA in urine by 2/3rds. Perhaps bottled water should include a clear "bottled on" date so you can at least roughly gauge how much BPA you're about to drink.</div><div><br /></div><div>Plastic is clearly an incredibly useful material, and I'm sure we'll eventually sort out the problems of the various chemicals that leach from it. In the meantime, I simply play it safe by avoiding plastic touching our food/drink, when practical. For example, we only put glass ware in the microwave, and when we need to carry water on-the-go, we always use a <a href="http://www.kleankanteen.com/">Klean Kanteen</a>. In fact we now have many Klean Kanteens: in the car, in the stroller, next to the kid's beds and in our home offices, on the dining room table, etc.</div><div><br /></div></div></div></div></div></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4442227358562894152?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-30835453208363665822009-08-22T07:13:00.004-04:002009-08-22T07:32:14.911-04:00Hurricane Bill is coming!<div><div><div>I find myself, this quiet Saturday morning, in Falmouth MA, staring down the barrel of <a href="http://www.weather.com/newscenter/hurricanecentral/2009/bill.html">Hurricane Bill</a>! Seriously, it's headed straight for us, having gained strength last night.</div><div><br /></div><div>Yet, we're planning to go happily to the beach this morning, anyway. Why play chicken with a hurricane? Because the computer models at the <a href="http://www.nws.noaa.gov/">National Weather Service</a> insist that Bill will take a turn northward, sometime very soon, and not in fact touch Cape Cod at all (though it is projected to make landfall in Nova Scotia Sunday PM).</div><div><br /></div><div>We place alot of confidence in our computer models these days, and I sure hope they're right.</div><div><br /></div><div>I was in Falmouth for <a href="http://www.geocities.com/hurricanene/hurricanebob.htm">Hurricane Bob</a> in 1991 and it was stunning. Have you ever tried to stand up when 100 mph sustained winds are blowing at you? It's quite an experience, and the resulting damage was unreal.</div><div><br /></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3083545320836366582?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-80009310304906590072009-08-13T19:35:00.003-04:002009-08-13T19:39:57.220-04:00Anticipation is half the funI've found that for most people, but especially kids, the anticipation leading up to something is a sizable part of the fun. If you have an exciting vacation coming up, take every chance to remind your kids that it's coming, what the plans are, etc. If you don't, they've missed out on half the fun!<div><br /></div><div>I'm also convinced that this is why so many people can go to the Disney parks. The lines are amazingly long, and the actual rides amazingly short. It's the anticipation of going on a ride that keeps you happy.</div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8000931030490659007?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-37573918337344311782009-08-04T12:38:00.002-04:002009-08-04T13:29:06.840-04:00Life support grass<div><div>Seriously, could we possibly have picked a worse plant for our yards than "grass", even if we tried?</div><div><br /></div><div>I mean the stuff is so sickly, it has no prayer of living on its own in our local climate. It requires massive amounts of life support just to barely eek out an existence.</div><div><br /></div><div>I'll admit, with all the life support, the stuff can be truly beautiful. But the price we pay to reach that beauty is ridiculous.</div><div><br /></div><div>We dump hundreds of gallons of water on the stuff, every night, using sprinkler systems now built standard into the ground for new homes. This of course leaches all nutrients from the soil. Worse, grass is nitrogen-leaching: it removes nitrogen from the soil. So we must dump on loads of fertilizer to put it back.</div><div><br /></div><div>Being on such luxurious life support, the grass grows like it's in a jungle, and so we are forced to mow it, at least once per week. While leaving those clippings in place would make great natural fertilizer (after all, this is where all the fertilizer went!), it's not pretty so we truck the clippings away and dump them somewhere else.</div><div><br /></div><div>Of course, lots of other plants thrive, too, even better than grass. We like to call them "weeds", since they are not grass. And so we must dump toxins over the yard to kill them. We dump separate toxins to kill all sorts of bugs. Sometimes, from too much water, a fungus develops, so we dump something else on to kill that.</div><div><br /></div><div>All this stuff we dump on the yard likely endangers our kids, us, and our pets, but somehow we don't seem to care. It also kills off the worms that'd naturally aerate the soil, and so we must do our own forced mechanical aeration. It messes up the pH balance, so we dump yet more stuff on (lime, sulphur) to fix that.</div><div><br /></div><div>In fall, when the leaves drop on the weak grass, we must quickly rake or blow them off, because the grass dies off quickly if it's left covered by leaves.</div><div><br /></div><div>After winter, which the grass barely survives, some of it has died off and turned brown. This is fully natural, and that dead grass would normally serve as nature's fertilizer, yet we don't like the color, so we dethatch and reseed.</div><div><br /></div><div>These practices don't end with grass, of course. We truck in loads of mulch, the lipstick of modern lawn care, each year. We spray all sorts of toxins on the trees, the bushes, etc. Terminex shows up, spraying all sorts of other toxins. People with blowers show up and blow every last little thing off the asphault of your driveway.</div><div><br /></div><div>This whole ritual is now commonplace. It's assumed, accepted and expected practice. If you don't subscribe the life-support grass movement, people think something is wrong with you. How did we get ourselves into such a mess?</div><div><br /></div><div>Can't we, instead, find a plant that has no trouble surviving in our natural climate, with zero life support? Why did we all fall in love with this sickly life support grass, anyway?</div><div><br /></div><div>For example, crabgrass thrives. It's very hardy, grows with no additional watering, takes care of seeding by itself while grass never succeeds in seeding itself (presumably it's been selected and bred <b>not</b> to). Clover is another example, and has the advantage of being nitrogen fixing (the exact opposite of grass): it extracts nitrogren from the air and puts it back into the soil. This is why it's such a dark green even without fertilizer.</div><div><br /></div><div>Surely we can do better.</div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-3757391833734431178?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-4333265317937796192009-07-27T06:25:00.002-04:002009-07-27T06:36:45.717-04:00ZFS and ECC RAM<div><div><div><div><div><div><div>I started <a href="http://opensolaris.org/jive/thread.jspa?threadID=108609">this thread</a> over on the ZFS discuss list.</div><div><br /></div><div>My question dug into why the ZFS bigwigs alway so strongly recommend ECC RAM. Was it simply for the added security of preventing a few corrupted files (because non-ECC RAM will likely flip a few bits in the lifetime of your computer)?</div><div><br /></div><div>Or... was there something more spooky going on such that something catastrophic (losing an entire RAID-Z pool) is possible if your RAM has a bit error at a particularly bad time?</div><div><br /></div><div>This is important to know, because when spec'ing out a new server, you need the facts in order to make proper cost/benefit tradeoffs. This decision should be no different from whether I should get the latest and greatest hard drive (risky, since it has no track record), or an known-good older generation drive that has less capacity and performance but has a good record. If non-ECC RAM means I risk losing the pool then I'll fork out the extra $$$!</div><div><br /></div><div>It's great to see that ZFS has such a vibrant community that my simple question received so many answers. In this day and age the health of the community behind the software you are using is more important than the health of the software itself! <a href="http://lucene.apache.org">Lucene</a> also has a great community, though, I'm biased!</div><div><br /></div><div>My thread also indicates one of the challenges with open-source: sometimes you can't get a "definitive" answer to questions like this. Many people chimed in with "opinions", on both sides, but if I tally up the votes, and take into account the number of posts (rough measure of "authority") behind each vote, more people say "a bit error will just corrupt files/directories" than "a bit error can lose the pool".</div><div><br /></div><div>The dicussion also pointed out <a href="http://bugs.opensolaris.org/bugdatabase/view_bug.do?bug_id=6667683">this very-important issue</a>, which is to create a way to rollback ZFS to a prior known good state. It's the closest ZFS will get to providing something like fsck, I think. Sort of spooky ZFS doesn't already have that. I hope by the time I need it, if ever, this issue is done!</div><div><br /></div></div></div></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-433326531793779619?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-83375448694063143782009-07-18T06:08:00.003-04:002009-07-18T10:14:36.889-04:00WDTLER and WDIDLE3<div><div><div><div><div>Western Digital states that the <a href="http://www.wdc.com/en/products/products.asp?driveid=576">Caviar GP drives</a> are not recommended for RAID arrays, and that instead you should get their <a href="http://www.wdc.com/en/products/products.asp?driveid=610">enterprise RE-4 drive</a>. But there's a $100 price difference between the two right now! (<a href="http://www.newegg.com/Product/Product.aspx?Item=N82E16822136344">$230</a> vs <a href="http://www.newegg.com/Product/Product.aspx?Item=N82E16822136365">$330</a> at Newegg). So I decided to risk it and build my RAIDZ array with the GP drives. Check back in a couple of years to see if I have any regrets!</div><div><br /></div><div>In building the array I discovered two very important fixes I needed to make to the drives, in order to make them behave more like the RE-4 drives.</div><div><br /></div><div>First was to enable <a href="http://en.wikipedia.org/wiki/Time-Limited_Error_Recovery">Time-Limited Error Recovery</a>. This tells the drive to NOT make ridiculous efforts to recover a sector that it's having trouble reading, and to instead quickly report back an error that the sector could not be read. See, if the drive takes too long to answer a read request, the RAID level will assume it has gone kaput and boot it from the array. By enabling TLER, you prevent this from happening, thus letting the RAID level handle the error. Use the <a href="http://shifteightgeneration.com/content/wdtler-fix-tler-setting-wd-desktop-hard-drives">WDTLER</a> utility to do this.</div><div><br /></div><div>Second, the GP drives have a feature called Intellipark, which parks the drives heads (moves them off the platters) so as to reduce air resistance drag on the motor that spins the platter (every little power saving counts!). You can hear it clearly when it kicks in: it makes a slight clicking sound when parking. When you need to use the drive again, there's a clear delay and new clicking sound while the disk head unparks.</div><div><br /></div><div>While nice in theory, it's unfortunately rather frustrating in practice. See, modern OS's use write caching to gather up a bunch of writes in RAM, and only actually write to the hard drives in bulk, every 10-30 seconds. The GP's idle timer is 8 seconds by default (a rather poorly chosen default). As a result the drive incessantly parks and unparks as random services write a few bytes here and there. Eventually, too many such cycles (I've read in forums that 300,000 is the spec'd limit) will cause wear & tear and increase the chance of failure. <a href="http://kerneltrap.org/mailarchive/linux-kernel/2008/4/9/1386304">This thread</a> on the Linux Kernel mailing list gives some details. While this is a problem even in non-RAID settings, it's exacerbated by RAID because now you have N drives that park/unpark, in sequence.</div><div><br /></div><div>Fortunately, there's another utility called <a href="http://forums.storagereview.net/index.php?showtopic=27269">WDIDLE3</a> that lets you increase the time (to a max of 25.5 seconds, which I don't think is enough), or to disable the timer entirely, which is what I did.</div><div><br /></div><div>If you don't run Windows and thus cannot directly run these EXEs, one simple workaround is to slipstream them into the <a href="http://www.ultimatebootcd.com/">Ultimate Boot CD</a> as <a href="http://shifteightgeneration.com/content/wdtler-fix-tler-setting-wd-desktop-hard-drives">described here</a>. Those instructions are for WDTLER specifically, but simply slip in WDIDLE3 at the same time. Keep the resulting CD accessible since you'll likely need to run it again if you have to replace any drives in your array!</div><div><br /></div><div>As best I can tell, Western Digital does not officially support these utilities, so use them at your own risk. They both worked fine for me, on OpenSolaris, but your mileage may vary!</div><div><br /></div></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-8337544869406314378?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com7tag:blogger.com,1999:blog-8623074010562846957.post-57998401385850765262009-07-18T05:48:00.004-04:002009-07-29T06:34:29.810-04:00Newegg vs Amazon<div><div>I'm using 6 of the <a href="http://www.wdc.com/en/products/products.asp?driveid=576">2 TB Western Digital Caviar GP</a> drives in my new build, in a <a href="http://blogs.sun.com/bonwick/entry/raid_z">RAID-Z array</a>. Despite reading horror stories online, eg the many users seeing drives die quickly in the <a href="http://www.newegg.com/Product/ProductReview.aspx?Item=N82E16822136344">customer reviews at Newegg</a>, mine are working great despite the sizable stress tests I've been running.</div><div><br /></div><div>Except: one of my drives keeps reallocating sectors. I see this in its SMART diagnostics (5 sectors as of 2 weeks ago, 14 reallocated as of yesterday). This isn't normal (eg, the other 5 drives have 0 reallocated sectors), so I'll be keeping an eye on it and at some point might ask WD for a warranty replacement. I wonder if there's an accepted "policy" on how many reallocated sectors is too many? This reminds of the numerous "how many dead pixels are too many" discussions for new LCD monitors.</div><div><br /></div><div>Of course, I don't lose any data because of this; ZFS's RAIDZ simply corrects the error for me. </div><div><br /></div><div>I bought 3 of the drives from <a href="http://www.newegg.com/">Newegg</a> and 3 from <a href="http://www.amazon.com/">Amazon</a>. If I were more patient I would have spread them out over time as well. In general you should buy your drives across space and time, to minimize the chance of "correlated failures". If you buy all your drives from the same place, it's likely they were manufactured in the same "batch" which means any manufacturing defect in the production of that batch would make it more likely that you'd lose 2 or more drives at once, thus destroying all your data.</div><div><br /></div><div>Newegg, it turns out, does a poor job shipping hard drives. They simply wrap them in bubble wrap and tape it up, sometimes packing 2 drives together inside the bubble wrap. What they don't realize is, because of rough handling from UPS, those bubbles pop, one by one I imagine, during transit, such that by the time I receive it, there is zero protection (no bubbles left) along at least one edge of the hard drives. It's rather shocking because Newegg is otherwise excellent. I've read several posts in the user comments noting exactly what I just said, yet Newegg hasn't improved. It's a bad sign when a company stops listening to its customers.</div><div><br /></div><div>In contrast, Amazon (whose price matched Newegg's) packed each drive into it's own dedicated foam packing and box. Fabulous!</div><div><br /></div><div>[<b>EDIT Jul 28, 2009</b>: I just received one more drive from Amazon, and they unfortunately have taken a turn for the worse! They now ship in a similar fashion to Newegg, wrapping the drive in minimal bubble wrap which pops during transit. They also take the wasteful step of "box within a box", which I don't think adds much protection to the drive. This drive will be my "hot spare", so if/once it get swapped into the array, I'll try to remember to watch for reallocated sectors and any other problems. Sigh.]</div><div><br /></div><div>The one drive I see failing was in fact one from Newegg (I kept track of the serial numbers); it's entirely possible Newegg's poor shipping and the rough handling from UPS led to this drive's failure.</div><div><br /></div><div>Losing one drive in a RAID array is quite terrifying because until you get the new drive <a href="http://blogs.sun.com/bonwick/entry/smokin_mirrors">resilvered</a>, you're running with no safety margin! If you lose another drive, you've lost all your data. RAIDZ is not a replacement for good backups. It's best to have a spare drive on hand; you can even install it and notify ZFS to keep the drive as a hot spare, meaning if any drive drops out of the array, ZFS will immediately start the resilvering process to bring the new drive in. Or you could create a RAIDZ2 array, which has two drives worth of redundancy, but then you've "lost" 2 drives worth of storage!</div><div><br /></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-5799840138585076526?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-45276840108898426742009-07-17T11:02:00.006-04:002009-08-15T11:45:59.134-04:00OpenSolaris challenges<div><div><div><div><div><div><div>Whenever I encounter someone who's overly ecstatic about some new technology or gizmo or something, I quickly say "tell me what's wrong with it". If they can't think of anything, then I can't trust their opinion.</div><div><br /></div><div>Nothing is perfect. There are always tradeoffs to be made. Only once you are properly informed with the facts, clearly seeing the goods and the bads, minus all the hype, can you finally make a good decision.</div><div><br /></div><div>If you are passionate about something, and you use it day in and day out, then you ought to have a big list of the things that bother you most about it. Next time you see someone loving their <a href="http://www.apple.com/iphone/">iPhone</a>, try asking them what's wrong with it.</div><div><br /></div><div>Unfortunately, hype, "popular opinion", "conventional wisdom", "everybody's doing it", etc. drive so many decisions these days. Not long ago, when you bought a house, everyone pushed you to choose these newfangled mortgages like ARMs, interest only loans, etc., instead of the boring old-fashioned 30 year fixed rate mortgage. <a href="http://en.wikipedia.org/wiki/Alan_Greenspan">Alan Greenspan</a> was giving speech after speech praising the "innovation" in the financial services industry. Look where that got us!</div><div><br /></div><div>I came across this quote recently: "If you find yourself in the majority then it's time to switch sides". I've been realizing lately how true that is.</div><div><br /></div><div>So in this spirit of presenting a balanced picture, here are some of the challenges I've hit with <a href="http://opensolaris.org/">OpenSolaris</a>:</div></div></div><div><ul><li>It took practically an Act of God to switch from a dynamically (DHCP assigned) IP address to a static one. I ran the nice GUI administration tool, made the change, and at first all seemed good. But then on my next reboot, appparently a bunch of services failed to start. After much futzing, it was only when I uninstalled <a href="http://www.virtualbox.org/">VirtualBox</a> that things finally worked (I think VirtualBox's virtual adapter somehow conflicted). I now have a static IP!</li></ul></div><div><ul><li>There is apparently no SMART support for SATA drives, which is stunning. These days, as drives become more and more complex, we need access to their diagnostics. I rely on SMART to monitor the health, temperatures, remapped sectors, etc. of my drives.</li></ul></div><div><ul><li>The <a href="http://owfs.org/">1-wire File System</a> has not been ported to OpenSolaris. I have a network of 1-wire devices in my house to monitor temperatures, eg, outdoors, in the kid's bedroom, the attic, etc. I'm still working on this one... there seem to be some problems talking to libusb. I may end up simply running a tiny Linux PC (the <a href="http://www.fit-pc2.com/wiki/index.php?title=Main_Page">Fit PC 2</a> looks cute) instead, for such random services.</li></ul></div><div><br /></div><div><br /></div></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-4527684010889842674?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0tag:blogger.com,1999:blog-8623074010562846957.post-91992229533995846312009-07-14T16:13:00.001-04:002009-07-17T11:23:09.678-04:00Sun's ZFS filesystem<div><div><div><div><div><div><div><div><div>I've been test driving Sun's (now Oracle's!) <a href="http://opensolaris.org/os/">OpenSolaris</a> (2009.06) and <a href="http://opensolaris.org/os/community/zfs/">ZFS</a> filesystem as my home filer and general development machine.</div><div><br /></div><div>I'm impressed!</div><div><br /></div><div>ZFS provides some incredible features. For example, taking a snapshot of your entire filesystem is wicked fast. This gives you a "point in time" copy of all files that you can keep around for as long as you want. It's very space efficient because only when a file is changed does the snapshot actually consume disk space (preserving the old copy).</div><div><br /></div><div>From the snapshot, which is read-only, you can then make a clone that's read-write. This effectively lets you fork your filesystem, which is amazing. Sun builds on this by providing "boot environments", which let you clone your world, boot to it, do all kinds of reckless things, and if you don't like the results, switch back to your current safe world again, no harm done. I used to leave my home filers pretty much untouched once I started using them for fear of screwing something up. Now with boot environments I can freely experiment away.</div><div><br /></div><div>I have a great many Lucene source code checkouts, to try out ideas, apply patches, etc., and by using ZFS's cloning I can now create a new checkout and apply a patch in only a few seconds. And it's very space efficient because only the changed files in the new checkout consume disk space. Since I'm using an <a href="http://www.anandtech.com/cpuchipsets/intel/showdoc.aspx?i=3403">Intel X25 SSD</a> as my primary storage, space efficiency is important. The machine uses Intel's Core i7 920 CPU, which has fabulous concurrency and can run the Lucene unit tests 3X faster than my old machine. This all nets out to wonderful productivity gains.</div><div><br /></div><div>ZFS also nicely decouples the raw storage device (the "pool"), from filesystems that pull from that storage. For the secondary storage I set up a <a href="http://blogs.sun.com/bonwick/entry/raid_z">RAID-Z</a> pool (like raid5, but fixes the "write hole" problem) using 6 of the <a href="http://www.amazon.com/Western-Digital-Caviar-Green-WD20EADS/dp/B001RB1TIS">Western Digital Green Caviar 2TB</a> drives. Be sure to use the <a href="http://en.wikipedia.org/wiki/Time-Limited_Error_Recovery">WDTLER utility</a> if you use these drives in a RAID array. This gives me 9TB usable space to play with; from here I've created many filesystems that all share the pool.</div><div><br /></div><div>Performance is excellent: copying a 1TB directory on the RAID-Z pool to another directory on the same pool averages 100 MB/sec.</div><div><br /></div><div>I also just <a href="http://www.theregister.co.uk/2009/07/13/zfs_deduplication/">read this morning</a> that ZFS will add de-duping at the block level, thus making it even more space efficient.</div><div><br /></div><div>ZFS can provide these features because it has a write-once core: no block is ever overwritten (unless it was already freed). Lucene has the same core approach: no file is ever overwritten in the index. Lucene's transactional semantics derive directly from this as well (though Lucene can't "fork" an index... maybe someday!).</div><div><br /></div><div>Bye bye Linux, hello Solaris! I only hope this innovation continues now that Oracle has acquired Sun.</div><div><br /></div></div></div></div></div></div></div></div></div><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/8623074010562846957-9199222953399584631?l=blog.mikemccandless.com' alt='' /></div>Mike McCandlesshttp://www.blogger.com/profile/04277432937861334672noreply@blogger.com0