Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How should you build a high-performance column store for the 2020s?

lemire.me

Post reply on HN
Print view View original

11–20 of 73 posts

Re: How should you build a high-performance column store for the 2020s?

#11

Post by dustingetz »

SamReidHughes wrote: post #9
dustingetz wrote: post #8

Datastore of 2020s will be designed around an immutable log because it permits both strong consistency and horizontal scaling (like git). Once you're both distributed and consistent, the problems today's stores are architected around, go away. Your distributed queries can index the immutable log however they like. column-oriented, row-oriented, documents, time-oriented, graphs, immutability means you can do all of it…

You can't just say "immutable log" and then be done. You certainly don't want to have just one immutable log, because then unrelated operations, for example to different parts of a key space, have to "see" each other. If you go the route of Datomic, your writes can't outpace the one CPU that processes them. (Correct me if I'm wrong, I'm just reading its documentation.) Git, with a DAG history, is just eventual consis…

In RDBMS, when you shard, read shards and write shards are in lock-step, which is the whole problem with sharding. In Datomic (and in git), by sharding writes, it doesn't really impact reads.

This is interesting, because consider a large system like Facebook. Transactions naturally fall within certain boundaries. You never transact to Events, Photos, and Instagram all at once - from the write side, they don't have to share the same single-writer process delivering ACID.

You do however, on the read side, need to have fluid queries across them all, as if they were one database. RDBMS can't do that, but Datomic can, and Git can too - consider submodules. Immutability is what makes it possible to shard like this without sacrificing query expressiveness, strong consistency or ACID (like every other distributed system that isn't accumulate only)

Re: How should you build a high-performance column store for the 2020s?

#12

Post by spinco »

lima wrote: post #5

Yandex's recently open sourced ClickHouse[1] column store does some of these. It heavily relies on compression, data locality and SIMD instructions and supports external dictionaries for lookup. [1]: https://clickhouse.yandex/

HN discussion on ClickHouse from a few years ago: https://news.ycombinator.com/item?id=11908254

Re: How should you build a high-performance column store for the 2020s?

#13

Post by gopalv »

(man, I'd love to go work on this for three years, without worrying about a "customer" or "backwards compatability")

> That is, if you have N distinct values, you can store them using ceil(log(N)/log(2)) bits

Ideally you don't need to do ceil, if you had an low number like 5 items, then it looks like you need 3 bits to store it, but you can store it in 2.4 bits (just pack 10 values into 24 bits instead of 30).

Getting distinct and repeated values by tearing apart data so that you can use these algorithms is something which I could use some papers to refer to.

For instance, here's[1] what we're trying to do with Double encoding loops, but it still suffers from the problems of a car moving from 0.3 -> 0.2 location.

[1] - http://bit.ly/2zt70iL

Re: How should you build a high-performance column store for the 2020s?

#15

Post by mej10 »

dustingetz wrote: post #11
SamReidHughes wrote: post #9

Earlier quoted context omitted.

You can't just say "immutable log" and then be done. You certainly don't want to have just one immutable log, because then unrelated operations, for example to different parts of a key space, have to "see" each other. If you go the route of Datomic, your writes can't outpace the one CPU that processes them. (Correct me if I'm wrong, I'm just reading its documentation.) Git, with a DAG history, is just eventual consis…

In RDBMS, when you shard, read shards and write shards are in lock-step, which is the whole problem with sharding. In Datomic (and in git), by sharding writes, it doesn't really impact reads. This is interesting, because consider a large system like Facebook. Transactions naturally fall within certain boundaries. You never transact to Events, Photos, and Instagram all at once - from the write side, they don't have to…

I was under the impression, based on its docs, that Datomic only supports processing transactions serially through a single transactor.

Re: How should you build a high-performance column store for the 2020s?

#16

Post by posnet »

xoogler_thr wrote: post #2

This already exists, in Google BigQuery. Uses darn near every trick in the book, and some that aren’t in the book. Source: shipped it.

[Edit]: Why was the above comment flagged?

How much of big queries performance do you think stems from Capacitor versus the rest of the system. For example if you switched it out with parquet, but kept everything else (Colossus, Dremel, Background reordering, metadata stored in Spanner etc) would it still be 10/30/50% worse or would it be an order of magnitude worse.

Re: How should you build a high-performance column store for the 2020s?

#17

Post by posnet »

misterHN wrote: post #6

put data in text files, ASCII printable characters, one data point per line put data files in directory name data files after columns use ".data" filename extension for data files write a tool to create index files (append ".index" to the name of the input text file) that map record number to byte offset in data file If data files are all Each index file is a packed array of 32 bit integers Write a tool to create len…

This sounds almost identical to the datastore honeycomb.io built and describe in the talk https://www.youtube.com/watch?v=tr2KcekX2kk

Re: How should you build a high-performance column store for the 2020s?

#18

Post by posnet »

lima wrote: post #5

Yandex's recently open sourced ClickHouse[1] column store does some of these. It heavily relies on compression, data locality and SIMD instructions and supports external dictionaries for lookup. [1]: https://clickhouse.yandex/

I am always impressed with clickhouse, especially when it holds up against massive data processing systems, but running on a laptop http://tech.marksblogg.com/benchmarks.html

Re: How should you build a high-performance column store for the 2020s?

#19

Post by SamReidHughes »

mej10 wrote: post #15
dustingetz wrote: post #11

Earlier quoted context omitted.

In RDBMS, when you shard, read shards and write shards are in lock-step, which is the whole problem with sharding. In Datomic (and in git), by sharding writes, it doesn't really impact reads. This is interesting, because consider a large system like Facebook. Transactions naturally fall within certain boundaries. You never transact to Events, Photos, and Instagram all at once - from the write side, they don't have to…

I was under the impression, based on its docs, that Datomic only supports processing transactions serially through a single transactor.

Not surprisingly, it also says it's not designed for high throughput write workloads, the topic of this blog post.

Re: How should you build a high-performance column store for the 2020s?

#20

Post by oaijdsfoaijsf »

posnet wrote: post #16
xoogler_thr wrote: post #2

This already exists, in Google BigQuery. Uses darn near every trick in the book, and some that aren’t in the book. Source: shipped it.

[Edit]: Why was the above comment flagged? How much of big queries performance do you think stems from Capacitor versus the rest of the system. For example if you switched it out with parquet, but kept everything else (Colossus, Dremel, Background reordering, metadata stored in Spanner etc) would it still be 10/30/50% worse or would it be an order of magnitude worse.

It would have to depend on the dataset, right?

For anyone who doesn't know what Capacitor is: https://cloud.google.com/blog/big-data/2016/04/inside-capaci...

Post reply on HN