New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature request: add ability to apply delta or delta-of-delta encoding to numeric columns before compression #838

Open
valyala opened this Issue Jun 1, 2017 · 16 comments

Comments

Projects
None yet
@valyala

valyala commented Jun 1, 2017

Clickhouse fits well for time-series DB from the performance point of view. But the compression ratio for the data stored in such databases may be further improved.

Tables in time-series DBs usually contain numeric values of two types: gauges (cpu usage, memory usage, network bandwidth usage, etc.) and counters (bytes transferred, requests processed, cpu cycles used, etc.).
Gauges are usually oscillate at a certain constant with a certain delta. So they compress well after delta encoding.
Counters are constantly incremented at a certain speed with the acceleration close to zero. So they compress well after delta-of-delta encoding.

It would be great if clickhouse would support delta and delta-of-delta encoding for numeric columns. This may be done via special type hints in CREATE TABLE:

CREATE TABLE t (
    EventDate Date,
    EventTime DateTime,

    -- CPU usage in percents [0..100]. Use delta encoding before compression.
    CPUUsage DeltaCoding(UInt8),

    -- The number of requests processed. Use delta-of-delta encoding before compression.
    RequestsProcessed DeltaDeltaCoding(UInt64),

    -- Random number equally distributed in the range [0...2^32).
    -- Do not use any encoding before compression, since it has no sense.
    RandomNum UInt32
) ENGINE = MergeTree(...)

@ztlpn ztlpn added the feature label Jun 1, 2017

@pavel-odintsov

This comment has been minimized.

pavel-odintsov commented Jun 8, 2017

Agree with it. Would be nice to have such option. I tried to put big number of metrics to CH and compression rate wasn't so cool :(

@Civil

This comment has been minimized.

Contributor

Civil commented Jun 8, 2017

I also agree with that and even more - I think for TSDBs it might worth to implement some customized delta-delta encodings, e.x. how it's done in Prometheus v2 storage.

@valyala

This comment has been minimized.

valyala commented Jun 12, 2017

This would be useful for projects similar to https://github.com/s4z/prom2click , cc'ing @s4z.

@alexey-milovidov

This comment has been minimized.

Member

alexey-milovidov commented Jun 12, 2017

Totally agree.
We should have the ability to specify custom compression codec per column.

@AlekSi

This comment has been minimized.

AlekSi commented Aug 22, 2017

@mattbostock

This comment has been minimized.

mattbostock commented Jan 17, 2018

I'd like to give this a go but I'm new to the project. Would anyone more familiar with it be able to give me some pointers on the implementation, specifically adding a custom compression codec per column?

@alexey-milovidov

This comment has been minimized.

Member

alexey-milovidov commented Jan 18, 2018

Our compression format is quite simple.
Look at CompressedWriteBuffer and CompressedReadBufferBase for reference.

In short, it is the following:

Compressed data is formed of blocks, one after the other. Blocks are completely independent.
Each block is:

/** The compressed block format is as follows:
  *
  * The first 16 bytes are the checksum from all other bytes of the block. Now only CityHash128 is used.
  * In the future, you can provide other checksums, although it will not be possible to make them different in size.
  *
  * The next byte specifies the compression algorithm. Then everything depends on the algorithm.
  *
  * 0x82 - LZ4 or LZ4HC (they have the same format).
  *
  * NOTE: Why is 0x82?
  * Originally only QuickLZ was used. Then LZ4 was added.
  * The high bit is set to distinguish from QuickLZ, and the second bit is set for compatibility,
  *  for the functions qlz_size_compressed, qlz_size_decompressed to work.
  * Although now such compatibility is no longer relevant.
  *
  * 0x90 - ZSTD
  *
  *        Next 4 bytes - the size of the compressed data, taking into account this 8-byte header; 
  *        Next 4 bytes is the size of the uncompressed data.
  *
  * All sizes are little endian.
  */

What we want to change:

  1. Single byte is not enough to identify the compression method, because we want to allow nested algorithms. For example, LZ4 of Delta (two algorithms stacked one after the other). We want to encode arbitary large sequence of compression algorithms; and each algorithm may have parameters that affect compressed format.
    To do this while maintaining backward compatibility, we may reserve a range with continuation bits - that will mean - look at the next byte.

  2. Now we are stuck with single variant of checksum (CityHash128 exactly from CityHash version 1.0.2). Sometimes we want to use different checksums: xxhash for example. We can encode it in the same place as compression method.

  3. As we will add the support of many compression algorithms, it's reasonable to extract switch/case to a separate interface and create a factory.

After we will add this support in block format, we can extend CREATE syntax to allow specifying preferred algorithms. Example: CREATE TABLE t (x UInt32 COMPRESSION LZ4(BLOSC))

But explicit specifying compression method for columns is not the only choice.
For example, we may want to implement the following features:

  • compression of old/cold data with different algo or with higher compression level during merges (we already have this option, look at config.xml, compression section)
  • background re-compression of data during idle times;
  • adapt compression level to data ingestion rate during inserts;
  • choosing somewhat optimal compression method by compressing blocks with slightly different settings;

It's unclear, how we can configure these possible options?

@alexey-milovidov

This comment has been minimized.

Member

alexey-milovidov commented Feb 9, 2018

We decided the following:

For every column in a table it will be possible to specify a list of compression codecs stacked together.
Example:

x UInt64 CODEC(Delta, LZ4(1))
  • it means, that Delta codec will be applied, then LZ4 with parameter 1.

If codec is specified for a column, it will have highest priority over other (global) compression settings.

@Sindbag

This comment has been minimized.

Sindbag commented Feb 18, 2018

I will take that.

@otisg

This comment has been minimized.

otisg commented Feb 26, 2018

On https://clickhouse.yandex/docs/en/roadmap/ I see compression is scheduled for Q2 2018. Does it mean somebody from CH team will start working on better compression then, or can external contributors provide PRs earlier than that? For example, it looks like @Sindbag is saying he is up for doing it?

@Sindbag

This comment has been minimized.

Sindbag commented Feb 26, 2018

@otisg , I am doing it under control of the ClickHouse team, as external employee.

@zhang2014

This comment has been minimized.

Contributor

zhang2014 commented Mar 17, 2018

What is the current state of this issue? I plan to implement it. @alexey-milovidov

@Sindbag

This comment has been minimized.

Sindbag commented Mar 18, 2018

@zhang2014 I am doing the task, plan to pull request soon.

@otisg

This comment has been minimized.

otisg commented Mar 18, 2018

Nice. I know this will vary from situation to situation, but have you done any work to see how savings one could expect from this compression and what the price of that might be in terms of increased CPU usage?

@Sindbag

This comment has been minimized.

Sindbag commented Mar 18, 2018

@otisg well, currently I did not precisely benchmark the performance, but it is planned and, I expect, will be packed with other tests.

@sundy-li

This comment has been minimized.

Contributor

sundy-li commented Apr 23, 2018

@Sindbag Is there any new progress about this feature you can share with us?
For example, will the implementation refer to gorilla and influxdb (delta compression , XOR compression etc )?

This feature could make ClickHouse perform much better on the time-series Data monitor scene. We are really very urgent to see that.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment