Categories
数据库

Druid存储结构

Apache Druid是一款优秀的OLAP引擎,众所周知数据存储格式对一款存储系统来说是最核心的组件,Druid的数据格式是自定义的,以此保证了在海量数据下的亚秒级查询。本文深入分析Druid V1版本数据存储格式,包括索引结构和数据在磁盘中的存储方式。在阅读本文之前希望您对Druid和数据存储有简单了解。

Druid的存储方式是列式的,每个列为一个逻辑文件,列与列之间的数据格式是相对独立的。与传统OLAP系统一样,Druid的列分为维度与度量两种,其中维度列因为需要被检检索,所以设计了索引,维度列的数据格式也是Druid数据结构的核心;相对的度量列只需要存储行值就可以。为了方便阐述数据格式,本文以一个广告效果分析作为例子进行分析,图1中是样例数据,请一定注意它是聚合后的数据,而不是原始数据。

维度数据结构

上文提到维度是Druid存储结构的核心,并且各个维度是相对独立存储的,所以我们可以通过分析单个维度的数据结构,来窥探Druid的存储结构。图2展示了“city”维度和两个度量的逻辑存储结构,整体上Druid维度的索引包含三部分:字典、编码后的维度值、倒排索引,接下来详细分析这三部分。

字典

字典是将列的所有值去重,然后按照字典顺序排序的值组成的数组,虽然字典中只存储了排序后的维度值,但是它还隐含了另一个信息,那就是每个维度值的编码值,编码值就等于数组的下标。字典的设计目的有两个:一是维度值可以使用编码后的整数表示,而不是实际的值,编码值一般可以节约存储空间;二是编码后的整数是定长的,磁盘中定长存储可以省去定位单个值的offset length等索引信息的开销,最终还是能节省存储空间。

图3展示了Druid字典的逻辑结构和物理结构,Druid字典采用了线性的数组结构。因为字典中的值是不定长的,所以物理结构中有一段index部分,其中记录了每个值的offset;data部分每个值的头部记录了该值的长度。这样的设计才能定位到任意一个行的值。

编码后的维度值

Druid是一个预聚合的方案,但是其聚合不是按照一个维度的group-by聚合,而是按照所有维度的group-by聚合,对于图1中的数据已经是按照聚合过了。可以看出对于单一维度而言,编码过后的维度值依然可能重复,所以每个维度的行信息不能用字典代替,而需要额外存储。

编码后的维度值都是一个个的整数。为了保证单一值在磁盘中能快速定位,在整个维度范围内这些整数需要是定长的,因为定长元素组成的数组可以通过计算直接定位到某一个元素。同时为了节约存储空间这些整数不一定需要用4个字节表示,它的长度取决于该维度在单一数据文件内的唯一值的数量,Druid采用了采用了变长整数编码的方式,具体如下:

1 – 2^8-1 => 1 byte
2^8 - 2^16-1 => 2 bytes
2^16 - 2^24-1 => 3 bytes
2^24 - 2^32-1 => 4 bytes
2^32 - 2^40-1 => 5 bytes
...

以图1中“city”维度为例,它包含唯一值3个,所以每个值用1个字节表示。

图4展示了编码后维度值的逻辑结构和物理结构,在逻辑上整个维度是一个线性的结构,但是在物理存储上数据结构中包含了offset索引和元素length部分,这很明显是存储非定长数据的。原来Druid将整个线性结构首先划分成了一个个分组,每个分组大小不超过64KB,而分组又进行了压缩,压缩后的分组已经是非定长的了,所以站在整个数据结构的角度,需要按照非定长数据的格式进行存储。

将整个整数数组进行分组压缩的设计思路,其背后的考量点主要是:一是对于磁盘存储压缩是有必要的,因为能减小空间占用和传输消耗;二是分组也是有必要的,因为绝大多数读取数据的场景不会涉及到所有的分组,而是部分分组,分组后一次查询只涉及到了少数分组,对于查询速度的提升有极大帮助。

倒排索引

最后是倒排索引部分,对于字典中的每个元素,Druid都会生成一个Bitmap,其中1表示该bit下标对应的行的值是对应字典元素的值,反之不是。

Bitmap数据是基于聚合后的数据的,所以它的长度和原始数据的行数是没有关系的。从图5中“Beijing”对应的Bitmap可以看出,它基于图1中的聚合后的数据,而不是原始数据,所以Bitmap的长度是4。

Druid的反向索引采用的是Bitmap的方案,因为字典中每个元素对应的Bitmap的长度都是一样的,所以物理存储上可以采用定长的方式?其实不是的,出于节省存储空间的考虑,Druid将每个Bitmap进行了压缩,一般Bitmap数据结构的压缩比例是比较大的,所以压缩的是有必要的。因为压缩后数据长度不相同了,所以存储上需要按照非定长数据进行存储。

数组

Druid是支持数组数据类型维度的,对于数组数据类型Druid如何存储呢?整体上数组的存储方式还是字典、编码后的维度值、倒排索引三个部分。其中字典和倒排索引部分是跟单值类型的维度的存储方式没有任何区别。

但是在编码后的维度值部分是有区别的,对于单值维度这部分的逻辑结构是一个线性列表(这里暂时不考虑分组),但是对于数组类型的维度,它其实是一个二层的层次结构,外层是一个非定长的线性列表,线性列表的每个元素也就是内层,是一个定长的线性列表。对于整个数据结构来说,在物理结构上依然可以进行分组和压缩。

存储结构小结

对于物理结构来说其元素是否定长,对其存储方式起到决定作用,图6总结了定长和非定长的存储模式,请注意这里没有考虑分组和压缩。

Druid对线性非定长存储结构有这大量的应用,它遵循图6的总结,只是在元数据部分稍有不同,现总结如下:

version:占用 1byte
allowReverseLookup:1byte ,是否允许反向查找,指根据Value反查index, 用于Dictionary字典查找
numBytesUsed :4bytes ,所占字节数
numElements:4bytes,元素的总数量

如何使用

最后简单分析下Druid在查询中如何使用到以上数据结构,为了聚焦问题,假设查询只命中了一个数据文件,这样可以忽略多个数据文件的结果合并等问题。我们以下面简单查询为例:

select city, sum(click_cnt) from table_t where category=0 or category=1 group by city

图8展示了查询流程,其中第1.6步用到了字典结构,第3步用到了倒排索引数据结构,第4部用到了编码后的维度值数据结构。

版权声明:文章为作者辛勤劳动的成果,转载请注明作者与出处。

7,935 replies on “Druid存储结构”

It’s a shame you don’t have a donate button! I’d
without a doubt donate to this fantastic blog! I guess for now i’ll
settle for bookmarking and adding your RSS feed to my Google account.
I look forward to new updates and will talk about this blog with
my Facebook group. Talk soon!

What’s Going down i am new to this, I stumbled upon this I have found
It positively helpful and it has aided me out loads.
I am hoping to contribute & aid different users like its helped me.

Good job.

Plastic, Reconstructive, and Aesthetic Surgery treat congenital and acquired aesthetic, shape, and functional disorders. Specialist plastic surgeons meet the requirements of the branch. Cosmetic surgery in Turkey includes plastic, Reconstructive, and Aesthetic Surgical operations.
if there’s anything else that you need you can write me.
thanks in advance for your services

best cosmetic surgery turkey
Plastic, Reconstructive, and Aesthetic Surgery treat congenital and acquired aesthetic, shape, and functional disorders. Specialist plastic surgeons meet the requirements of the branch. Cosmetic surgery in Turkey includes plastic, Reconstructive, and Aesthetic Surgical operations.
if there’s anything else that you need you can write me.
thanks in advance for your services.

Controlo de pragas – um servico completo e de qualidade, realizado com profissionais qualificados e de forma planeada.

Premium Protect e um servico premium que lhe oferece a capacidade de proteger a sua propriedade ou estabelecimento contra pragas.

Plastic, Reconstructive, and Aesthetic Surgery treat congenital and acquired aesthetic, shape, and functional disorders. Specialist plastic surgeons meet the requirements of the branch. Cosmetic surgery in Turkey includes plastic, Reconstructive, and Aesthetic Surgical operations.
if there’s anything else that you need you can write me.
thanks in advance for your services

온라인 카지노 가입 상담 전문 컨설팅

온라인 카지노를 처음 접하신 분들은 카지노 게임 플레이를 즐기고 싶은데 어디서 어떻게 해야 되는지 많은 고민이 될 것 입니다. 고민의 종류로는 카지노 게임을 플레이 후 환급 처리에 관한 문제, 온라인 카지노는 어떠한 방식으로 이용하는지 대한 문제, 온라인 카지노를 이용 시 나에게 오는 피해는 없을지 많은 것을 생각하게 됩니다. 따라서 어떻게 해야 좋은 선택 인지를 많이 고민합니다. 본사와 상담 후 카지노 사이트 가입을 추천 드리고 있습니다.
온라인 카지노를 이용 함으로써 나에게 오는 악 영향은 없을지 왜 많은 사람들은 온라인 카지노를 플레이 하는지, 온라인 카지노를 믿을 수 있는지 모든 것을 본사에서 상담하여 드리고 있습니다.

본사에서 안내해드리는 카지노사이트 는 모두 100% 검증이 되었고 안전한 곳만을 안내하여 드리고 있습니다.

카지노사이트
온라인 카지노 가입 상담 전문 컨설팅

온라인 카지노를 처음 접하신 분들은 카지노 게임 플레이를 즐기고 싶은데 어디서 어떻게 해야 되는지 많은 고민이 될 것 입니다. 고민의 종류로는 카지노 게임을 플레이 후 환급 처리에 관한 문제, 온라인 카지노는 어떠한 방식으로 이용하는지 대한 문제, 온라인 카지노를 이용 시 나에게 오는 피해는 없을지 많은 것을 생각하게 됩니다. 따라서 어떻게 해야 좋은 선택 인지를 많이 고민합니다. 본사와 상담 후 카지노 사이트 가입을 추천 드리고 있습니다.
온라인 카지노를 이용 함으로써 나에게 오는 악 영향은 없을지 왜 많은 사람들은 온라인 카지노를 플레이 하는지, 온라인 카지노를 믿을 수 있는지 모든 것을 본사에서 상담하여 드리고 있습니다.

본사에서 안내해드리는 카지노사이트 는 모두 100% 검증이 되었고 안전한 곳만을 안내하여 드리고 있습니다.

Slot Gacor
Rajabet168 : Situs Slot 4D 303 Slot Gacor Hari Ini Terbaru

Rajabet168 adalah situs slot 4d terbaru yang terkemuka diantara 303 slot dengan memiliki beragam info slot gacor hari ini selalu 24 jam online non stop.Lebih dari 500 permainan slot 4d & mpo terbaik di Indonesia bisa kamu mainkan di sini.

cosmetic surgery turkey
Plastic, Reconstructive, and Aesthetic Surgery treat congenital and acquired aesthetic, shape, and functional disorders. Specialist plastic surgeons meet the requirements of the branch. Cosmetic surgery in Turkey includes plastic, Reconstructive, and Aesthetic Surgical operations.
if there’s anything else that you need you can write me.
thanks in advance for your services.

Plastic, Reconstructive, and Aesthetic Surgery treat congenital and acquired aesthetic, shape, and functional disorders. Specialist plastic surgeons meet the requirements of the branch. Cosmetic surgery in Turkey includes plastic, Reconstructive, and Aesthetic Surgical operations.
if there’s anything else that you need you can write me.
thanks in advance for your services.

Slot 4d
Rajabet168 : Situs Slot 4D 303 Slot Gacor Hari Ini Terbaru

Rajabet168 adalah situs slot 4d terbaru yang terkemuka diantara 303 slot dengan memiliki beragam info slot gacor hari ini selalu 24 jam online non stop.Lebih dari 500 permainan slot 4d & mpo terbaik di Indonesia bisa kamu mainkan di sini.

cosmetic surgery Istanbul
Plastic, Reconstructive, and Aesthetic Surgery treat congenital and acquired aesthetic, shape, and functional disorders. Specialist plastic surgeons meet the requirements of the branch. Cosmetic surgery in Turkey includes plastic, Reconstructive, and Aesthetic Surgical operations.
if there’s anything else that you need you can write me.
thanks in advance for your services.

Hunting in South Africa
Are you ready for the best South Africa Hunting Safari?

I can honestly say that I have hunted all over this beautiful continent and people might differ from me but there is no other place in the world where you will be treated and hunt the amount of animals in a short period of time.

And I know there is a lot of debate on hunting in High Fenced areas but let me tell you something from one thing I’ve experience and still deal with every day. No matter if you hunt in Masai Land in Tanzania or in Luangwa Valley in Zambia of in Tsholotsho in Zimbabwe.

If you would like to know more about African Safari and Photo. We are excited to discuss a custom hunting package just for you.

Join the INDIA’s leading casino brand and enjoy the best of live casino!Play online IPL, Poker, Roulette, Slots,Baccarat and more all legally and securely, right from your phone!

Howdy I am so delighted I found your web site, I really found you by mistake, while I was browsing on Bing for something else, Regardless I am here now and would
just like to say thanks a lot for a marvelous post and a
all round enjoyable blog (I also love the theme/design), I don’t have time to go through it all at the moment but I have
book-marked it and also added your RSS feeds, so when I have time I will
be back to read more, Please do keep up the superb work.

Simply want to say your article is as astounding.
The clearness in your submit is just nice and that i can think you’re a professional in this subject.
Fine along with your permission let me to clutch your RSS feed
to keep up to date with imminent post. Thank you one million and please keep up the
gratifying work.

카지노사이트
온라인 카지노 가입 상담 전문 컨설팅

온라인 카지노를 처음 접하신 분들은 카지노 게임 플레이를 즐기고 싶은데 어디서 어떻게 해야 되는지 많은 고민이 될 것 입니다. 고민의 종류로는 카지노 게임을 플레이 후 환급 처리에 관한 문제, 온라인 카지노는 어떠한 방식으로 이용하는지 대한 문제, 온라인 카지노를 이용 시 나에게 오는 피해는 없을지 많은 것을 생각하게 됩니다. 따라서 어떻게 해야 좋은 선택 인지를 많이 고민합니다. 본사와 상담 후 카지노 사이트 가입을 추천 드리고 있습니다.
온라인 카지노를 이용 함으로써 나에게 오는 악 영향은 없을지 왜 많은 사람들은 온라인 카지노를 플레이 하는지, 온라인 카지노를 믿을 수 있는지 모든 것을 본사에서 상담하여 드리고 있습니다.

카지노사이트
온라인 카지노 가입 상담 전문 컨설팅

온라인 카지노를 처음 접하신 분들은 카지노 게임 플레이를 즐기고 싶은데 어디서 어떻게 해야 되는지 많은 고민이 될 것 입니다. 고민의 종류로는 카지노 게임을 플레이 후 환급 처리에 관한 문제, 온라인 카지노는 어떠한 방식으로 이용하는지 대한 문제, 온라인 카지노를 이용 시 나에게 오는 피해는 없을지 많은 것을 생각하게 됩니다. 따라서 어떻게 해야 좋은 선택 인지를 많이 고민합니다. 본사와 상담 후 카지노 사이트 가입을 추천 드리고 있습니다.
온라인 카지노를 이용 함으로써 나에게 오는 악 영향은 없을지 왜 많은 사람들은 온라인 카지노를 플레이 하는지, 온라인 카지노를 믿을 수 있는지 모든 것을 본사에서 상담하여 드리고 있습니다.

본사에서 안내해드리는 카지노사이트 는 모두 100% 검증이 되었고 안전한 곳만을 안내하여 드리고 있습니다.

카지노사이트
카지노사이트
카지노사이트 정보
카지노사이트 및 온라인카지노 실시간 정보
카지노 사이트 25에서는 다양한 카지노쿠폰 혜택 제공 및 엄격한 검증을 완료한 카지노 사이트 가입, 온라인카지노 가입에 도움을 드리고 있습니다. 검증 카지노 사이트 업체의 실시간 이벤트 혜택 및 변동규정 사항, 최근 카지노 사이트 운영의 크고 작은 이슈를 가장 정확하고 빠르게 제공하고 있으니, 카지노 사이트 25에서 검증이 완료된 안전한 카지노 사이트 정보를 받아보시기 바랍니다. 자세한 상담은 하단 상담링크를 통해 가능합니다. 안전하고 검증된 카지노 사이트 선택은 카지노사이트25에서 시작하시기 바랍니다.

super slot
sabai99 สบาย99
สมัครปั๊บรับเลยโบนัส 50บาท
+ แนะนำเพื่อน เอาไป 50 ฉันได้เพื่อนฉันก็ต้องได้
+ ไปPG 50บาท
มัครปั๊บรับเลยโบนัส 50บาท
สมัครง่ายๆเพียงแค่กรอก (หมายเลขโทรศัพท์) ก็รับโบนัส 50 บาทไปเลย
*หากทำเงื่อนไขการถอนเกมสำเร็จ ก็สามารถทำรายการถอนได้