[ https://issues.apache.org/jira/browse/HBASE-4218?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Phabricator updated HBASE-4218: ------------------------------- Attachment: D447.24.patch mbautin updated the revision "[jira] [HBASE-4218] HFile data block encoding framework and delta encoding implementation". Reviewers: JIRA, tedyu, stack, nspiegelberg, Kannan Addressing Ted's comments and removing two .rej files that somehow got into the patch. REVISION DETAIL https://reviews.facebook.net/D447 AFFECTED FILES src/main/java/org/apache/hadoop/hbase/HColumnDescriptor.java src/main/java/org/apache/hadoop/hbase/HConstants.java src/main/java/org/apache/hadoop/hbase/KeyValue.java src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java src/main/java/org/apache/hadoop/hbase/io/encoding/CompressionState.java src/main/java/org/apache/hadoop/hbase/io/encoding/CopyKeyDataBlockEncoder.java src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoding.java src/main/java/org/apache/hadoop/hbase/io/encoding/DiffKeyDeltaEncoder.java src/main/java/org/apache/hadoop/hbase/io/encoding/EncodedDataBlock.java src/main/java/org/apache/hadoop/hbase/io/encoding/EncoderBufferTooSmallException.java src/main/java/org/apache/hadoop/hbase/io/encoding/FastDiffDeltaEncoder.java src/main/java/org/apache/hadoop/hbase/io/encoding/PrefixKeyDeltaEncoder.java src/main/java/org/apache/hadoop/hbase/io/hfile/AbstractHFileReader.java src/main/java/org/apache/hadoop/hbase/io/hfile/AbstractHFileWriter.java src/main/java/org/apache/hadoop/hbase/io/hfile/BlockCacheKey.java src/main/java/org/apache/hadoop/hbase/io/hfile/BlockType.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFile.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlock.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileDataBlockEncoder.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileDataBlockEncoderImpl.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFilePrettyPrinter.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileReaderV1.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileReaderV2.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterV1.java src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterV2.java src/main/java/org/apache/hadoop/hbase/io/hfile/LruBlockCache.java src/main/java/org/apache/hadoop/hbase/io/hfile/NoOpDataBlockEncoder.java src/main/java/org/apache/hadoop/hbase/mapreduce/LoadIncrementalHFiles.java src/main/java/org/apache/hadoop/hbase/regionserver/CompactSplitThread.java src/main/java/org/apache/hadoop/hbase/regionserver/HRegion.java src/main/java/org/apache/hadoop/hbase/regionserver/MemStore.java src/main/java/org/apache/hadoop/hbase/regionserver/Store.java src/main/java/org/apache/hadoop/hbase/regionserver/StoreFile.java src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java src/main/java/org/apache/hadoop/hbase/regionserver/StoreScanner.java src/main/java/org/apache/hadoop/hbase/regionserver/metrics/SchemaConfigured.java src/main/java/org/apache/hadoop/hbase/util/ByteBufferUtils.java src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java src/main/ruby/hbase/admin.rb src/test/java/org/apache/hadoop/hbase/BROKE_TODO_FIX_TestAcidGuarantees.java src/test/java/org/apache/hadoop/hbase/HBaseTestCase.java src/test/java/org/apache/hadoop/hbase/HBaseTestingUtility.java src/test/java/org/apache/hadoop/hbase/HFilePerformanceEvaluation.java src/test/java/org/apache/hadoop/hbase/TestAcidGuarantees.java src/test/java/org/apache/hadoop/hbase/client/TestAdmin.java src/test/java/org/apache/hadoop/hbase/client/TestFromClientSide.java src/test/java/org/apache/hadoop/hbase/io/TestHalfStoreFileReader.java src/test/java/org/apache/hadoop/hbase/io/TestHeapSize.java src/test/java/org/apache/hadoop/hbase/io/encoding/RedundantKVGenerator.java src/test/java/org/apache/hadoop/hbase/io/encoding/TestBufferedDataBlockEncoder.java src/test/java/org/apache/hadoop/hbase/io/encoding/TestChangingEncoding.java src/test/java/org/apache/hadoop/hbase/io/encoding/TestDataBlockEncoders.java src/test/java/org/apache/hadoop/hbase/io/encoding/TestEncodedSeekers.java src/test/java/org/apache/hadoop/hbase/io/encoding/TestLoadAndSwitchEncodeOnDisk.java src/test/java/org/apache/hadoop/hbase/io/encoding/TestUpgradeFromHFileV1ToEncoding.java src/test/java/org/apache/hadoop/hbase/io/hfile/CacheTestUtils.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestCacheOnWrite.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFile.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileBlock.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileBlockIndex.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileDataBlockEncoder.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFilePerformance.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileSeek.java src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileWriterV2.java src/test/java/org/apache/hadoop/hbase/mapreduce/TestImportExport.java src/test/java/org/apache/hadoop/hbase/regionserver/CreateRandomStoreFile.java src/test/java/org/apache/hadoop/hbase/regionserver/DataBlockEncodingTool.java src/test/java/org/apache/hadoop/hbase/regionserver/EncodedSeekPerformanceTest.java src/test/java/org/apache/hadoop/hbase/regionserver/HFileReadWriteTest.java src/test/java/org/apache/hadoop/hbase/regionserver/TestCompactSelection.java src/test/java/org/apache/hadoop/hbase/regionserver/TestCompaction.java src/test/java/org/apache/hadoop/hbase/regionserver/TestCompoundBloomFilter.java src/test/java/org/apache/hadoop/hbase/regionserver/TestFSErrorsExposed.java src/test/java/org/apache/hadoop/hbase/regionserver/TestMultiColumnScanner.java src/test/java/org/apache/hadoop/hbase/regionserver/TestScanWithBloomError.java src/test/java/org/apache/hadoop/hbase/regionserver/TestSeekOptimizations.java src/test/java/org/apache/hadoop/hbase/regionserver/TestStoreFile.java src/test/java/org/apache/hadoop/hbase/regionserver/wal/TestLogRolling.java src/test/java/org/apache/hadoop/hbase/regionserver/wal/TestWALReplay.java src/test/java/org/apache/hadoop/hbase/util/LoadTestKVGenerator.java src/test/java/org/apache/hadoop/hbase/util/LoadTestTool.java src/test/java/org/apache/hadoop/hbase/util/MultiThreadedReader.java src/test/java/org/apache/hadoop/hbase/util/MultiThreadedWriter.java src/test/java/org/apache/hadoop/hbase/util/RestartMetaTest.java src/test/java/org/apache/hadoop/hbase/util/TestByteBufferUtils.java src/test/java/org/apache/hadoop/hbase/util/TestLoadTestKVGenerator.java src/test/java/org/apache/hadoop/hbase/util/TestMiniClusterLoadEncoded.java src/test/java/org/apache/hadoop/hbase/util/TestMiniClusterLoadParallel.java src/test/java/org/apache/hadoop/hbase/util/TestMiniClusterLoadSequential.java > Data Block Encoding of KeyValues (aka delta encoding / prefix compression) > --------------------------------------------------------------------------- > > Key: HBASE-4218 > URL: https://issues.apache.org/jira/browse/HBASE-4218 > Project: HBase > Issue Type: Improvement > Components: io > Affects Versions: 0.94.0 > Reporter: Jacek Migdal > Assignee: Mikhail Bautin > Labels: compression > Fix For: 0.94.0 > > Attachments: 0001-Delta-encoding-fixed-encoded-scanners.patch, > 0001-Delta-encoding.patch, 4218-2012-01-14.txt, 4218-v16.txt, 4218.txt, > D447.1.patch, D447.10.patch, D447.11.patch, D447.12.patch, D447.13.patch, > D447.14.patch, D447.15.patch, D447.16.patch, D447.17.patch, D447.18.patch, > D447.19.patch, D447.2.patch, D447.20.patch, D447.21.patch, D447.22.patch, > D447.23.patch, D447.24.patch, D447.3.patch, D447.4.patch, D447.5.patch, > D447.6.patch, D447.7.patch, D447.8.patch, D447.9.patch, > Data-block-encoding-2011-12-23.patch, > Delta-encoding.patch-2011-12-22_11_52_07.patch, > Delta-encoding.patch-2012-01-05_15_16_43.patch, > Delta-encoding.patch-2012-01-05_16_31_44.patch, > Delta-encoding.patch-2012-01-05_16_31_44_copy.patch, > Delta-encoding.patch-2012-01-05_18_50_47.patch, > Delta-encoding.patch-2012-01-07_14_12_48.patch, > Delta-encoding.patch-2012-01-13_12_20_07.patch, > Delta_encoding_with_memstore_TS.patch, open-source.diff > > > A compression for keys. Keys are sorted in HFile and they are usually very > similar. Because of that, it is possible to design better compression than > general purpose algorithms, > It is an additional step designed to be used in memory. It aims to save > memory in cache as well as speeding seeks within HFileBlocks. It should > improve performance a lot, if key lengths are larger than value lengths. For > example, it makes a lot of sense to use it when value is a counter. > Initial tests on real data (key length = ~ 90 bytes , value length = 8 bytes) > shows that I could achieve decent level of compression: > key compression ratio: 92% > total compression ratio: 85% > LZO on the same data: 85% > LZO after delta encoding: 91% > While having much better performance (20-80% faster decompression ratio than > LZO). Moreover, it should allow far more efficient seeking which should > improve performance a bit. > It seems that a simple compression algorithms are good enough. Most of the > savings are due to prefix compression, int128 encoding, timestamp diffs and > bitfields to avoid duplication. That way, comparisons of compressed data can > be much faster than a byte comparator (thanks to prefix compression and > bitfields). > In order to implement it in HBase two important changes in design will be > needed: > -solidify interface to HFileBlock / HFileReader Scanner to provide seeking > and iterating; access to uncompressed buffer in HFileBlock will have bad > performance > -extend comparators to support comparison assuming that N first bytes are > equal (or some fields are equal) > Link to a discussion about something similar: > http://search-hadoop.com/m/5aqGXJEnaD1/hbase+windows&subj=Re+prefix+compression -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa For more information on JIRA, see: http://www.atlassian.com/software/jira