On 7/16/11 10:08 PM, Stack wrote: > On Fri, Jul 15, 2011 at 10:06 AM, Claudio Martella > <[email protected]> wrote: >> On 7/15/11 6:24 PM, Stack wrote: >>> How do you figure the N in the below Claudio? >> N is the total amount of pairs in the sequence file. You know that when >> you finish flushing a memstore or compacting files. > So a perfect index? If this is what you mean, won't the index often > be often be close in size to the data size? (And index lives in memory > at the moment; we have yet to make it so unused indices are let go if > unused. And if this is what you mean, you can have a perfect index > now by setting hfile block size < your smallest cell size.
No, you can have collisions, so the index is not perfect (which means you can have buckets for colliding keys and empty unused entries in the hashtable directory). Also, the index stores only offsets, not the keys. So they overhead of the index is sizeof(long) * number of key-value pairs in the file (in the optimal case, the overhead is 16 bytes for each colliding key-value pair as it's managed through a linked-list). For this reason using a load-factor > 1 can actually save memory and increase performance. Inside of the bucket, managed through a linked list, you scan the linked-list seeking to the key-value pair in the data segment and checking for key equality. this can require some seeks for colliding keys (as many as the number of entries in the bucket before the right one), but should not be the average case and can be decreased by increasing the load factor. This strategy is also used by cdb (http://cr.yp.to/cdb.html) and is quite effective in my benchmarks. > >> That is interesting, the principle looks like the same as in HFile >> (blocks and Btree) but I have to understand the difference further. >> > In HFile, the index is for every ~64k blocks or so; one block could > have one entry only while the next block could have hundreds of > entries; either has one entry in index only. So, its not the same as > mapfile. It will write an index entry every 128 (IIRC) entries > whether the entries are 10M each or 10bytes each (So, the indices > could be wildly different in size based off cell size). Thanks, this makes it all clear. >>> IIRC, we have >>> performance evaluation for various file types (You might be interested >>> in this recent posting by Mikhail Bautin of an hfile v2). >> I'd be interested in that, do you have a reference to it? >> > Here is Mikhail's post of an hfile v2 > https://issues.apache.org/jira/browse/HBASE-3857 > > The HFile perf test tool is in code base at > src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFilePerformance.java > (It was used comparing hfile vs tfile vs mapfile and then hfile > tweaks; it may be a little stale). > > Thanks for bringing up this topic Claudio and for taking the time to > do a bit of research. > Thank you very much for all this information. I'll try to implement a prototype in September, I'm pretty busy with deadlines right now. > St.Ack > -- Claudio Martella Free Software & Open Technologies Analyst TIS innovation park Via Siemens 19 | Siemensstr. 19 39100 Bolzano | 39100 Bozen Tel. +39 0471 068 123 Fax +39 0471 068 129 [email protected] http://www.tis.bz.it Short information regarding use of personal data. According to Section 13 of Italian Legislative Decree no. 196 of 30 June 2003, we inform you that we process your personal data in order to fulfil contractual and fiscal obligations and also to send you information regarding our services and events. Your personal data are processed with and without electronic means and by respecting data subjects' rights, fundamental freedoms and dignity, particularly with regard to confidentiality, personal identity and the right to personal data protection. At any time and without formalities you can write an e-mail to [email protected] in order to object the processing of your personal data for the purpose of sending advertising materials and also to exercise the right to access personal data and other rights referred to in Section 7 of Decree 196/2003. The data controller is TIS Techno Innovation Alto Adige, Siemens Street n. 19, Bolzano. You can find the complete information on the web site www.tis.bz.it.
