精华内容
下载资源
问答
  • 原文出处:https://bohutang.me/2020/06/05/clickhouse-and-friends-development/一次偶然的机会,和ClickHouse团队做...

    原文出处:https://bohutang.me/2020/06/05/clickhouse-and-friends-development/

    一次偶然的机会,和ClickHouse团队做了一次线下沟通,Alexey提到ClickHouse的设计哲学:

    1. The product must solve actual problem

    2. And do it better than others

    用工程思维解决商业问题的典范啊!

    对用户来说,他们关心的不是什么天花乱坠、上天入地的高科技,只是需要一个能很好解决自己问题的方案,这在开源社区是非常难得的,靠实力“野蛮式”生长。

    于是,我对这个散发着伏特加味道的利器充满了好奇,并参与到ClickHouse的社区中一探究竟,第一感觉是开放、友好、战斗力强(AK47 vs CK16, ClickHouse 2016年开源)。

    本文先从编译和测试入手,再到如何为社区贡献Patch,希望对那些想参与CK社区的同学有所帮助。

    如何本地编译和测试ClickHouse?

    源码获取

    1
    
    git clone --recursive https://github.com/ClickHouse/ClickHouse
    

    编译准备

    1
    2
    3
    4
    5
    6
    7
    
    sudo apt install build-essential
    sudo apt-get install software-properties-common
    sudo apt-add-repository ppa:ubuntu-toolchain-r/test
    sudo apt-get update
    
    sudo apt-get install gcc-9 g++-9 git python ninja-build
    sudo snap install cmake
    

    开始编译

    1
    2
    3
    4
    5
    6
    7
    
    cd ClickHouse
    mkdir build
    cd build
    export CC=gcc-9
    export CXX=g++-9
    cmake ..
    ninja
    

    测试方法

    ClickHouse的测试在官方development/tests(https://github.com/ClickHouse/ClickHouse/blob/master/docs/en/development/tests.md)文档里有详细的介绍,这里列举3个常用的测试模式:

    1. Functional Tests

    功能测试,主要用于ClickHouse内部功能测试,方式:输入一个sql文件,输出一个result,类似MySQL里的mtr,测试集合(https://github.com/ClickHouse/ClickHouse/tree/master/tests/queries)

    1
    2
    
    cd tests
    ./clickhouse-test -c "../build/programs/clickhouse-client" 00001_select_1
    

    2. Integration Tests

    集成测试,主要用于涉及第三方服务的测试,比如MySQL/Postgres/MongoDB等,以容器化方式编排调度(pytest)运行,测试集合

    由于涉及模块较多,集成测试环境的搭建有一定的难度,建议使用官方的docker镜像。比如要跑test_mysql_protocol下的集成测试集:

    1
    2
    3
    
    cd tests/integration
    docker pull yandex/clickhouse-integration-tests-runner
    ./runner --binary /your/ClickHouse/build/programs/clickhouse  --bridge-binary /your/ClickHouse/build/programs/clickhouse-odbc-bridge --configs-dir /your/ClickHouse/programs/server/ 'test_mysql_protocol/test.py::test_java_client -ss -vv'
    

    3. Unit Tests

    单元测试,主要用于代码模块的测试,测试集在各个模块的tests目录,比如: Core/tests(https://github.com/ClickHouse/ClickHouse/tree/master/src/Core/tests)

    如果大家想了解某个模块是如何工作的,强烈建议去翻翻该模块的tests目录,比如想了解processor的工作机制,跟踪调试 Processors/tests/(https://github.com/ClickHouse/ClickHouse/tree/master/src/Core/tests) 即可。

    如何给ClickHouse社区提Patch?

    1. fork

    首先在自己的github上fork一份ClickHouse代码,比如 https://github.com/BohuTANG/ClickHouse

    2. clone到本地

    1
    2
    
    git clone --recursive https://github.com/BohuTANG/ClickHouse
    git checkout -B mysql_replica(branch名字)
    

    3. 创建新的分支

    1
    
    git checkout -B mysql_replica(branch名字)
    

    4. 功能开发

    开发者可以提交一个Draft Pull Request到官方,github会显示这个Pull Request处于Draft状态,官方是无法Merge的

    5. can be testd标签

    等待Upstream打[can be tested]标签,一旦被标记CI狂魔们就强势开跑,跑一轮大概需要几十个小时。
    协助开发者发现一些代码Style、编译以及测试等错误,这样开发者就可以在自己的分支不停的迭代、修正。

    如果只是修改typo,这个标签Upstream通常不会添加。

    6. 开发完毕

    开发完成,测试OK,把Draft提升为正式Pull Request,等待Upstraem Review。

    7. Merge到Master

    如果Upstream通过,你的代码会被Merge到Master,恭喜你成为ClickHouse贡献者

    8. 注意事项

    ClickHouse Upstream迭代非常快,一定要多关注master分支进度,尽量保持自己的分支代码与master同步。否则Upstream Docker更新,自己的test可能就过不了。

    建议把 doc/development(https://github.com/ClickHouse/ClickHouse/tree/master/docs/en/development) 读一遍。

    全文完。

    Enjoy ClickHouse :)

    叶老师的「MySQL核心优化」大课已升级到MySQL 8.0,扫码开启MySQL 8.0修行之旅吧

    展开全文
  • 上篇的存储引擎技术进化与MergeTree介绍了存储算法的演进。存储引擎是一个数据库的底盘,一定要稳动力澎湃。接下来我们将一起来探索下 ClickHouse MergeTree 列...

    上篇的 存储引擎技术进化与MergeTree 介绍了存储算法的演进。

    存储引擎是一个数据库的底盘,一定要稳和动力澎湃。

    接下来我们将一起来探索下 ClickHouse MergeTree 列式存储引擎,解构下这台“跑车”最重要的部件。

    所有的存储引擎,无论精良与粗制滥造,最终都是要把数据回写到磁盘,来满足存储和索引目的。

    磁盘文件的构造可以说是算法的物理体现,我们甚至可以通过这些存储结构反推出其算法实现。

    所以,要想深入了解一个存储引擎,最好的入手点是它的磁盘存储结构,然后再反观它的读、写机制就会有一种水到渠成的感觉。

    如果这个分析顺序搞反了,会有一种生硬的感觉,网上大部分教程都是这种“生硬”式教学,本文将直击灵魂从最底层谈起,彻底搞明白4个问题:

    1. MergeTree 有哪些文件?

    2. MergeTree 数据如何分布?

    3. MergeTree 索引如何组织?

    4. MergeTree 如何利用索引加速?

    话不多说,上表:

    CREATE TABLE default.mt
    (
        `a` Int32,
        `b` Int32,
        `c` Int32,
        INDEX `idx_c` (c) TYPE minmax GRANULARITY 1
    )
    ENGINE = MergeTree
    PARTITION BY a 
    ORDER BY b
    SETTINGS index_granularity=3
    

    造点数据:

    insert into default.mt(a,b,c) values(1,1,1);
    insert into default.mt(a,b,c) values(5,2,2),(5,3,3);
    insert into default.mt(a,b,c) values(3,10,4),(3,9,5),(3,8,6),(3,7,7),(3,6,8),(3,5,9),(3,4,10);
    

    磁盘文件

    ls ckdatas/data/default/mt/
    1_4_4_0  3_6_6_0  5_5_5_0  detached  format_version.txt
    

    可以看到,生成了 3 个数据目录,每个目录在 ClickHouse 里称作一个分区(part),目录名的前缀正是我们写入时字段 a 的值: 1,3,5,因为表分区是这样定位的:PARTITION BY a

    现在我们看看 a=3 分区:

    ls ckdatas/data/default/mt/3_6_6_0/
    a.bin  a.mrk2  b.bin  b.mrk2  c.bin  checksums.txt  c.mrk2  columns.txt  count.txt  minmax_a.idx  partition.dat  primary.idx  skp_idx_idx_c.idx  skp_idx_idx_c.mrk2
    
    • *.bin 是列数据文件,按主键排序(ORDER BY),这里是按照字段 b 进行排序

    • *.mrk2 mark 文件,目的是快速定位 bin 文件数据位置

    • minmax_a.idx 分区键 min-max 索引文件,目的是加速分区键 a 查找

    • primay.idx 主键索引文件,目的是加速主键 b 查找

    • skp_idx_idx_c.* 字段 c 索引文件,目的是加速 c 的查找

    在磁盘上,MergeTree 只有一种物理排序,就是 ORDER BY 的主键序,其他文件(比如 .mrk/.idx)是一种逻辑加速,围绕仅有的一份物理排序,要解决的问题是:

    在以字段 b 物理排序上,如何实现字段 a、字段 c 的快速查找?

    MergeTree 引擎概括起来很简单:整个数据集通过分区字段被划分为多个物理分区,每个分区內又通过逻辑文件围绕仅有的一种物理排序进行加速查找。

    存储结构

    数据文件

    对于单个物理分区內的存储结构,首先要明确一点,MergeTree 的数据只有一份:*.bin。

    a.bin 是字段 a 的数据,b.bin 是字段 b 的数据,c.bin 是字段 c 的数据,也就是大家熟悉的列存储。

    各个 bin 文件以 b.bin排序对齐(b 是排序键),如图:

    这样会有一个比较严重的问题:如果 *.bin 文件较大,即使读取一行数据,也要加载整个 bin 文件,浪费了大量的 IO,没法忍。

    granule

    高、黑科技来了,ClickHouse MergeTree 把 bin 文件根据颗粒度(GRANULARITY)划分为多个颗粒(granule),每个 granule 单独压缩存储。

    SETTINGS index_granularity=3 表示每 3 行数据为一个 granule,分区目前只有 7 条数据,所以被划分成 3 个 granule(三个色块):

    为方便读取某个 granule,使用 *.mrk 文件记录每个 granule 的 offset,每个 granule 的 header 里会记录一些元信息,用于读取解析:

    这样,我们就可以根据 mark 文件,直接定位到想要的 granule,然后对这个单独的 granule 进行读取、校验。

    目前,我们还有缺少一种映射:每个 mark 与字段值之间的对应,哪些值区间落在 mark0,哪些落在 mark1 ...?

    有了这个映射,就可以实现最小化读取 granule 来加速查询:

    1. 根据查询条件确定需要哪些 mark

    2. 根据 mark 读取相应的 granule

    存储排序

    在了解 MergeTree 索引机制之前,需要明白以下两点:

    1. 只有一份全量数据,存储在 *.bin 文件

    2. *.bin 按照 ORDER BY 字段降序存储


    稀疏索引

    因为数据只有一份且只有一种物理排序,MergeTree在索引设计上选择了简单、高效的稀疏索引模式。

    什么是稀疏索引呢?就是从已经排序的全量数据里,间隔性的选取一些点,并记录这些点属于哪个 mark。

    1. primary index

    主键索引,可通过[PRIMARY KEY expr]指定,默认是 ORDER BY 字段值。

    注意 ClickHouse primary index 跟 MySQL primary key 不是一个概念。

    在稀疏点的选择上,取每个 granule 最小值:

    2. skipping index

    普通索引。

    INDEXidx_c(c) TYPE minmax GRANULARITY 1 针对字段 c 创建一个 minmax 模式索引。

    GRANULARITY 是稀疏点选择上的 granule 颗粒度,GRANULARITY 1 表示每 1 个 granule 选取一个:

    如果定义为GRANULARITY 2 ,则 2 个 granule 选取一个:

    3. partition minmax index

    针对分区键,MergeTree 还会创建一个 min/max 索引,来加速分区选择。

    4. 全景图

    查询优化

    现在熟悉了 MergeTree 的存储结构,我们通过几个查询来体验下。

    1. 分区键查询

    语句:

    select * from default.mt where a=3
    

    查询会直接根据 a=3 定位到单个分区:

    <Debug> InterpreterSelectQuery: MergeTreeWhereOptimizer: condition "a = 3" moved to PREWHERE
    <Debug> default.mt (SelectExecutor): Key condition: unknown
    <Debug> default.mt (SelectExecutor): MinMax index condition: (column 0 in [3, 3])
    <Debug> default.mt (SelectExecutor): Selected 1 parts by a, 1 parts by key, 3 marks by primary key, 3 marks to read from 1 ranges
    ┌─a─┬──b─┬──c─┐
    │ 3 │  4 │ 10 │
    │ 3 │  5 │  9 │
    │ 3 │  6 │  8 │
    │ 3 │  7 │  7 │
    │ 3 │  8 │  6 │
    │ 3 │  9 │  5 │
    │ 3 │ 10 │  4 │
    └───┴────┴────┘
    

    2. 主键索引查询

    语句:

    select * from default.mt where b=5
    

    查询会先从 3 个分区读取 prmary.idx,然后定位到只有一个分区符合条件,找到要读取的 mark:

    <Debug> default.mt (SelectExecutor): Key condition: (column 0 in [5, 5])
    <Debug> default.mt (SelectExecutor): MinMax index condition: unknown
    <Debug> default.mt (SelectExecutor): Selected 3 parts by a, 1 parts by key, 1 marks by primary key, 1 marks to read from 1 ranges
    ┌─a─┬─b─┬─c─┐
    │ 3 │ 5 │ 9 │
    └───┴───┴───┘
    

    3. 索引查询

    语句:

    select * from default.mt where b=5
    

    查询会先从 3 个分区读取 prmary.idx 和 skp_idx_idx_c.idx 进行 granule 过滤(没用的 drop 掉),然后定位到只有 3_x_x_x 分区的一个 granule 符合条件:

    <Debug> InterpreterSelectQuery: MergeTreeWhereOptimizer: condition "c = 5" moved to PREWHERE
    <Debug> default.mt (SelectExecutor): Key condition: unknown
    <Debug> default.mt (SelectExecutor): MinMax index condition: unknown
    <Debug> default.mt (SelectExecutor): Index `idx_c` has dropped 1 / 1 granules.
    <Debug> default.mt (SelectExecutor): Index `idx_c` has dropped 1 / 1 granules.
    <Debug> default.mt (SelectExecutor): Index `idx_c` has dropped 2 / 3 granules.
    <Debug> default.mt (SelectExecutor): Selected 3 parts by a, 1 parts by key, 5 marks by primary key, 1 marks to read from 1 ranges
    ┌─a─┬─b─┬─c─┐
    │ 3 │ 9 │ 5 │
    └───┴───┴───┘
    

    总结

    本文从磁盘存储结构入手,分析 ClickHouse MergeTree 的存储、索引设计。

    只有了解了这些底层机制,我们才好对自己的 SQL 和表结构进行优化,使其执行更加高效。

    ClickHouse MergeTree 设计简单、高效,它首要解决的问题是:在一种物理排序上,如何实现快速查找。

    针对这个问题,ClickHouse使用稀疏索引来解决。

    在官方 roadmap 上,列举了一个有意思的索引方向:Z-Order Indexing,目的是把多个维度编码到一维存储,当我们给出多维度条件的时候,可以快速定位到这个条件点集的空间位置,目前 ClickHouse 针对这个索引设计暂无进展。

    延伸阅读

    全文完。

    Enjoy ClickHouse :)

    叶老师的「MySQL核心优化」大课已升级到MySQL 8.0,扫码开启MySQL 8.0修行之旅吧

    展开全文
  • 原文出处:https://bohutang.me/2020/06/11/clickhouse-and-friends-processor/本文谈下 ClickHouse 核心科技:处理器...

    原文出处:https://bohutang.me/2020/06/11/clickhouse-and-friends-processor/

    本文谈下 ClickHouse 核心科技:处理器 Processor 和有向无环调度器 DAG Scheduler。

    这些概念并不是 ClickHouse 首创,感兴趣的同学可以关注下 materialize的 timely-dataflow,虎哥用golang 也写过一个原型。

    拼的是实现细节,正是这些模块的精良设计,才有了 ClickHous e整体的高性能。

    Pipeline问题

    在传统数据库系统中,一个 Query 处理流程大体是:

    其中在Plan阶段,往往会增加一个 Pipeline 组装(一个 transformer 代表一次数据处理):

    所有 transformer 被编排成一个流水线(pipeline),然后交给 executor 串行式执行,每执行一个 transformer 数据集就会被加工并输出,一直到下游的 sinker。可以看到,这种模型的优点是简单,缺点是性能低,无法发挥 CPU 的并行能力,通常叫火山模型(volcano-style),对于 OLTP 低延迟来说足够,对于计算密集的 OLAP 来说是远远不够的,CPU 不到 100% 就是犯罪!

    对于上面的例子,如果 transformer1 和 transformer2 没有交集,那么它们就可以并行处理:

    这样就涉及到一些比较灵魂的问题:

    1. 如何实现 transformer 的灵活编排?

    2. 如何实现 transformer 间的数据同步?

    3. 如何实现 transformer 间的并行调度?

    Processor 和 DAG Scheduler

    1. Transformer 编排

    ClickHouse 实现了一系列基础 transformer 模块,见 src/Processors/Transforms,比如:

    • FilterTransform -- WHERE 条件过滤

    • SortingTransform -- ORDER BY 排序

    • LimitByTransform -- LIMIT 裁剪

    当我们执行:

    SELECT * FROM t1 WHERE id=1 ORDER BY time DESC LIMIT 10
    

    对于 ClickHouse 的 QueryPipeline 来说,它会按照以下方式进行编排组装:

    QueryPipeline::addSimpleTransform(Source)
    QueryPipeline::addSimpleTransform(FilterTransform)
    QueryPipeline::addSimpleTransform(SortingTransform)
    QueryPipeline::addSimpleTransform(LimitByTransform)
    QueryPipeline::addSimpleTransform(Sinker)
    

    这样就实现了 Transformer 的编排,但是执行时数据如何进行同步呢?

    2. Transformer 数据同步

    当 QueryPipeline 进行 transformer 编排时,我们还需要进行更加底层的 DAG 连通构建。

    connect(Source.OutPort, FilterTransform.InPort)
    connect(FilterTransform.OutPort, SortingTransform.InPort)
    connect(SortingTransform.OutPort, LimitByTransform.InPort)
    connect(LimitByTransform.OutPort, Sinker.InPort)
    

    这样就实现了数据的流向关系,一个 transformer 的 OutPort 对接另外一个的 InPort,就像我们现实中的水管管道一样,接口有 3 通甚至多通。

    3. Transformer 执行调度

    现在管道组装起来了,那么管道内的水如何进行处理和给压流动呢?

    ClickHouse 定义了一套 transform 状态,processor 根据这些状态来实现调度。

        enum class Status
        {
            NeedData  // 等待数据流进入
            PortFull, // 管道流出端阻塞
            Finished, // 完成状态,退出
            Ready,    // 切换到 work 函数,进行逻辑处理
            Async,    // 切换到 schedule 函数,进行异步处理
            Wait,     // 等待异步处理
            ExpandPipeline,      // Pipeline 需要裂变
        };
    

    当 source 生成数据后,它的状态会设置为 PortFull,意思是等着流入其他 transformer 的 InPort,processor 会开始调度 FilterTransformer(NeedData) 的 Prepare,进行 PullData,然后它的状态设置为 Ready,等待 processor 调度 Work 方法进行数据Filter处理,大家就这样靠状态让 processor 去感知,来调度和做状态迁移,直到 Finished 状态。

    这里值得一提的是 ExpandPipeline 状态,它会根据 transformer 的实现,可以把一个 transformer 裂变出更多个 transformer 并行执行,达到一个爆炸效果。

    Example

    SELECT number + 1 FROM t1;
    

    为了更加深入理解 ClickHouse 的 processor 和 scheduler 机制,我们来一个原生态的 example:

    1. 一个 Source:{0,1,2,3,4}

    2. AdderTransformer 对每个数字做加1操作

    3. 一个 Sinker,输出结果

    1. Source

    class MySource : public ISource
    {
    public:
        String getName() const override { return "MySource"; }
    
        MySource(UInt64 end_)
            : ISource(Block({ColumnWithTypeAndName{ColumnUInt64::create(), std::make_shared<DataTypeUInt64>(), "number"}})), end(end_)
        {
        }
    
    private:
        UInt64 end;
        bool done = false;
    
        Chunk generate() override
        {
            if (done)
            {
                return Chunk();
            }
            MutableColumns columns;
            columns.emplace_back(ColumnUInt64::create());
            for (auto i = 0U; i < end; i++)
                columns[0]->insert(i);
    
            done = true;
            return Chunk(std::move(columns), end);
        }
    };
    

    2. MyAddTransform

    class MyAddTransformer : public IProcessor
    {
    public:
        String getName() const override { return "MyAddTransformer"; }
    
        MyAddTransformer()
            : IProcessor(
                {Block({ColumnWithTypeAndName{ColumnUInt64::create(), std::make_shared<DataTypeUInt64>(), "number"}})},
                {Block({ColumnWithTypeAndName{ColumnUInt64::create(), std::make_shared<DataTypeUInt64>(), "number"}})})
            , input(inputs.front())
            , output(outputs.front())
        {
        }
    
        Status prepare() override
        {
            if (output.isFinished())
            {
                input.close();
                return Status::Finished;
            }
    
            if (!output.canPush())
            {
                input.setNotNeeded();
                return Status::PortFull;
            }
    
            if (has_process_data)
            {
                output.push(std::move(current_chunk));
                has_process_data = false;
            }
    
            if (input.isFinished())
            {
                output.finish();
                return Status::Finished;
            }
    
            if (!input.hasData())
            {
                input.setNeeded();
                return Status::NeedData;
            }
            current_chunk = input.pull(false);
            return Status::Ready;
        }
    
        void work() override
        {
            auto num_rows = current_chunk.getNumRows();
            auto result_columns = current_chunk.cloneEmptyColumns();
            auto columns = current_chunk.detachColumns();
            for (auto i = 0U; i < num_rows; i++)
            {
                auto val = columns[0]->getUInt(i);
                result_columns[0]->insert(val+1);
            }
            current_chunk.setColumns(std::move(result_columns), num_rows);
            has_process_data = true;
        }
    
        InputPort & getInputPort() { return input; }
        OutputPort & getOutputPort() { return output; }
    
    protected:
        bool has_input = false;
        bool has_process_data = false;
        Chunk current_chunk;
        InputPort & input;
        OutputPort & output;
    };
    
    

    3. MySink

    class MySink : public ISink
    {
    public:
        String getName() const override { return "MySinker"; }
    
        MySink() : ISink(Block({ColumnWithTypeAndName{ColumnUInt64::create(), std::make_shared<DataTypeUInt64>(), "number"}})) { }
    
    private:
        WriteBufferFromFileDescriptor out{STDOUT_FILENO};
        FormatSettings settings;
    
        void consume(Chunk chunk) override
        {
            size_t rows = chunk.getNumRows();
            size_t columns = chunk.getNumColumns();
    
            for (size_t row_num = 0; row_num < rows; ++row_num)
            {
                writeString("prefix-", out);
                for (size_t column_num = 0; column_num < columns; ++column_num)
                {
                    if (column_num != 0)
                        writeChar('\t', out);
                    getPort()
                        .getHeader()
                        .getByPosition(column_num)
                        .type->serializeAsText(*chunk.getColumns()[column_num], row_num, out, settings);
                }
                writeChar('\n', out);
            }
    
            out.next();
        }
    };
    

    4. DAG Scheduler

    int main(int, char **)
    {
        auto source0 = std::make_shared<MySource>(5);
        auto add0 = std::make_shared<MyAddTransformer>();
        auto sinker0 = std::make_shared<MySink>();
    
        /// Connect.
        connect(source0->getPort(), add0->getInputPort());
        connect(add0->getOutputPort(), sinker0->getPort());
    
        std::vector<ProcessorPtr> processors = {source0, add0, sinker0};
        PipelineExecutor executor(processors);
        executor.execute(1);
    }
    

    总结

    从开发者角度看还是比较复杂,状态迁移还需要开发者自己控制,不过 upstream 已经做了大量的基础工作,比如对 source的封装 ISource,对 sink 的封装 ISink,还有一个基础的 ISimpleTransform,让开发者在上层使用 processor 时更加容易,可以积木式搭建出自己想要的 pipeline。

    ClickHouse 的 transformer 数据单元是 Chunk,transformer 对上游 OutPort 流过来的 Chunk 进行加工,然后输出给下游的 InPort,图连通式的流水线并行工作,让 CPU 尽量满负荷工作。

    当一个 SQL 被解析成 AST 后,ClickHouse 根据 AST 构建 Query Plan,然后根据 QueryPlan 构建出 pipeline,最后由 processor 负责调度和执行。目前,ClickHouse 新版本已经默认开启 QueryPipeline,同时这块代码也在不停的迭代。

    文内链接

    延伸阅读

    全文完。

    Enjoy ClickHouse :)

    叶老师的「MySQL核心优化」大课已升级到MySQL 8.0,扫码开启MySQL 8.0修行之旅吧

    展开全文
  • ClickHouse和他朋友们(2)MySQL ProtocolRead调用栈 ClickHouse和他朋友们(1)编译、开发、测试 全文完。 Enjoy ClickHouse :) 叶老师的「MySQL核心优化」大课已升级到MySQL 8.0,扫码开启MySQL 8.0修行之...

    21 世纪的第二个 10 年,虎哥已经在存储引擎一线奋战近 10 年,由于强大的兴趣驱动,这么多年来几乎不放过 arXiv 上与存储相关的每一篇 paper。尤其是看到带有 draft 的 paper 时,有一种乞丐听到“叮当”响时的愉悦。看paper这玩意就像鉴宝,多数是“赝品”,需要你有“鉴真”的本领,否则今天是张三的算法超越xx,明儿又是王二的硬件提升了yy,让你永远跟不上节奏zz,湮灭在这些没有营养的技术垃圾中,浪费大好青春。

    言归正传,接下来的3篇,跟 ClickHouse 的 MergeTree 引擎有关: 上篇介绍存储引擎的技术演进史,从"远古"的 B-tree 出发推演到目前主流的技术架构。 中篇会从存储结构介绍 MergeTree 原理,对 ClickHouse MergeTree 有一个深入的认识,如何合理设计来进行科学加速。 下篇会从MergeTree代码出发,看看 ClickHouse MergeTree 如何实现读、写。

    本文为上篇,先来个热身,相信本篇大部分内容对大家来说都比较陌生,很少人写过。

    地位

    存储引擎(事务型)在一个数据库(DBMS)中的地位如何呢?

    MySQL 的商业成功可以说大部分来自于 InnoDB 引擎,Oracle 收购 InnoDB 比 MySQL 早好几年呢!20年前,能亲手撸一套 ARIES (Algorithms for Recovery and Isolation Exploiting Semantics) 规范引擎,实力还是相当震撼的,相信 Oracle 收购的不仅是 InnoDB 这个引擎,更重要的是人, InnoDB 作者在哪里,在干什么?!Fork 出来的 MariaDB 这么多年一直找不到自己的灵魂,在 Server 层磨磨蹭蹭可谓是江河日下,只能四处收购碰碰运气,当年 TokuDB 战斗过的 commit 依在,但这些已经是历史了。另,WiredTiger 被 MongoDB 收购并使用,对整个生态所起的作用也是无可估量的,这些发动机引擎对于一辆汽车是非常重要的。

    有人问道,都已经 2020 年了,开发一个存储引擎还这么难吗?不难,但是造出来的未必有 RocksDB 好用?!如大家所见,很多的分布式存储引擎都是基于 RocksDB 研发,可谓短期内还算明智的选择。从工程角度来看,一个 ACID 引擎要打磨的东西非常之多,到处充斥着人力、钱力、耐心的消耗,一种可能是写到一半就停滞了(如 nessDB),还有一种可能是写着写着发现跟xx很像,沃茨法克。当然,这里并不是鼓励大家都去基于 RocksDB 去构建自己的产品,而是要根据自己的情况去做选择。

    B-tree

    首先要尊称一声大爷,这个大爷年方 50,目前支撑着数据库产业的半壁江山。

    50 年来不变而且人们还没有改变它的意向,这个大爷厉害的很!鉴定一个算法的优劣,有一个学派叫 IO复杂度分析,简单推演真假便知。下面就用此法分析下 B-tree(traditional b-tree) 的 IO 复杂度,对读、写 IO 一目了然,真正明白读为什么快,写为什么慢,如何优化。为了可以愉快的阅读,本文不会做任何公式推导,复杂度分析怎么可能没有公式呢!

    读IO分析

    这里有一个 3-level 的 B-tree,每个方块代表一个 page,数字代表 page ID。

    上图 B-tree 结构是内存的一个表现形式,如果我们要读取的记录在 leaf-8上,read-path 如蓝色箭头所示: root-9 --> branch-6 --> leaf-8

    下图是 B-tree 在磁盘上的存储形式,meta page 是起点:

    这样读取的随机 IO (假设内存里没有 page 缓存且 page 存储是随机的)总数就是(蓝色箭头):

    1(meta-10)IO + 1(root-9)IO + 1(branch-6)IO + 1(leaf-8)IO = 4次 IO,这里忽略一直缓存的 meta 和 root,就是 2 次随机 IO。如果磁盘 seek 是 1ms,读取延迟就是 2ms。

    通过推演就会发现,B-tree 是一种读优化(Read-Optimized)的数据结构,无论 LSM-tree 还是 Fractal-tree 等在读上只能比它慢,因为读放大(Read Amplification)问题。存储引擎算法可谓日新月异,但是大部分都是在跟写优化(Write-Optimized)做斗争,那怕是一个常数项的优化那就是突破,自从 Fractal-tree 突破后再无来者了!

    写IO分析

    现在写一条记录到 leaf-8。

    可以发现,每次写都需要先读取一遍,如上图蓝色路径所示。

    假设这次写入导致 root, branch 都发生了变化,这种 in-place 的更新反映到磁盘上就是:

    基本是 2 次读 IO和写 2 次写 IO+WAL fsync,粗略为 4 次随机 IO。通过分析发现,B-tree 对写操作不太友好,随机 IO 次数较多,而且 in-place 更新必须增加一个 page 级的 WAL 保证失败回滚,简直是要命。

    Write-Optimized B-tree

    说到写优化,在机械盘的年代,大家的方向基本是把随机 IO 转换为顺序 IO,充分发挥磁盘的机械优势,于是出现一种 Append-only B-tree:

    1. 更新生成新的 page(蓝色)

    2. page 回写磁盘时 append only 到文件末尾

    3. 无需 page WAL,数据不 overwrite,有写放大(Write Amplification)问题,需要做空洞重利用机制

    Append-only B-tree 节省了回写时的 2 次随机 IO,转换为常数级(constant)的1次顺序 IO,写性能大幅提升,总结起来就是: 随机变顺序,空间换时间 LSM-tree, Fractal-tree 等写优化算法的核心思想也是这个,只不过其实现机制不同。

    LSM-trees

    随着 LevelDB 的问世,LSM-tree 逐渐被大家所熟知。LSM-tree 更像一种思想,模糊了 B-tree 里 tree 的严肃性,通过文件组织成一个更加松散的 tree。这里不谈一个具体的 LSM-tree 是 Leveled 还是 Size-tiered,只谈大体思想。

    写入

    1. 先写入内存的 C0

    2. 后台线程根据规则(Leveled/Sized)进行 merge,C0 --> C1, C1 --> C2 ... CL

    3. 写入 C0 即可返回,IO 放到后台的 Merge 过程

    4. 每次 Merge 是硬伤,动作大就抖,动作小性能不好,每次 Merge 的数据流向不明确

    5. 写放大问题

    读取

    1. 读取 C0

    2. 读取 C1 .. CL

    3. 合并记录返回

    4. 读放大问题

    Fractal-tree

    终于发展到了“终极”优化(目前最先进的索引算法),Fractal-tree。它是在 Append-only B-tree 的基础上,对每个 branch 节点增加了一个 message buffer 作为缓冲,可以看做是 LSM-tree 和 Append-only B-tree 完美合体。

    相对于 LSM-tree 它的优势非常明显: Merge 更加有序,数据流向非常分明,消除了 Merge 的抖动问题,大家一直寻找的 compaction 防抖方案一直存在的!

    这个高科技目前只有 TokuDB 在使用,这个算法可以开篇新介,这里不做累述,感兴趣的可以参考原型实现 nessDB。

    Cache-oblivious

    这个词对于大部分人都是陌生的,不过别怕。在存储引擎里,有一个数据结构非常非常重要,它负责 page 数据有序性维护,比如在一个 page 里怎么快速定位到我要的记录。在 LevelDB 里使用 skiplist,但大部分引擎使用的是一个有序数组来表示,比如 [1, 2, 3, ... 100],然后使用二分查找。

    大概 10 年前一位内核开发者发表了一篇 <You're Doing It Wrong>,这个小文讲了一个很有意思的事情: 数据的组织形式对性能有很大的影响,因为 CPU有 cache line。

    抛开这篇文章不谈,咱们来看一张“神仙”图:

    这是一个 binary-tree 的 4 种 layout 表示形式,那么哪种 layout 对 CPU cache line 最友好?

    也许你已经猜对了,那就是 van Emde Boas,简称 vEB。因为它的相邻数据“扎堆”存储,point-query 和 range-query 的 cache line 可以最大化共享,skiplist 对 cache line 是非常不友好的,还可以更快!对于 cache oblivious 数据结构,这里有一个简单的原型实现: omt

    B-tree优化魔力象限

    写优化算法从原生的 B-tree 到 Append-only B-tree(代表作 LMDB),又到 LSM-tree(LevelDB/RocksDB 等),最后进化到目前最先进的 Fractal-tree (TokuDB)。这些算法耗费了很多年才在工程上实现并被认可,研发一款存储引擎缺的不是算法而是“鉴宝”的能力,这个“宝”可能已经躺了几十年了。

    其实,"科学家"们已经总结出一个 B-tree 优化魔力象限:

    横坐标是写性能,纵坐标是读性能,B-tree 和 Logging 数据结构分布在曲线的两个极端。B-tree 的读性能非常好,但是写性能差。Logging 的写性能非常好,但是读性能差(想想我们每次写都把数据追加到文件末尾,是不是很快?但是读...)。

    在它们中间有一个优化曲度(Optimal Curve)。在这个曲度上,你可以通过增加/减少一个常数(1-epsilon)来做读和写优化组合,LSM-tree/Fractal-tree 都在这个曲度之上。

    总结

    本文主要讨论事务性引擎的技术演进,其中包含了 IO 复杂度分析,其实这个分析是基于一个 DAM(Disk Access Machine)模型,这里不再展开。这个模型要解决什么问题呢?如果工程中涉及硬件层级关系,比如 Disk / Memory / CPU,数据在Disk,读取(以 block 为单位)到 Memory,查找计算(cache-line)在 CPU, 不同介质间性能差距又非常之大,我们怎么做才能让整体性能更优的问题。和当今的硬件相融合,这个模型也一样适用。

    最后回到 ClickHouse 的 MergeTree 引擎,它只使用了本文中的部分优化,实现也比较简洁、高效,毕竟没有事务,撸起来也没啥心理负担。 随机变顺序,空间换时间, MergeTree 原理,请听下回分解。

    References

    [1] [Cache-Oblivious Data Structures](https://www.cs.au.dk/~gerth/papers/cacheoblivious05.pdf)

    [2] [Data Structures and Algorithms for Big Databases](https://www3.cs.stonybrook.edu/~bender/talks/2013-BenderKuszmaul-xldb-tutorial.pdf)

    [3] [The buffer tree: A new technique for optimal I/O-algorithms](https://link.springer.com/chapter/10.1007%2F3-540-60220-8_74)

    [4] [how the append-only btree works](http://www.bzero.se/ldapd/btree.html) 

    [5] [写优化的数据结构(1):AOF和b-tree之间](https://www.douban.com/note/269741273/)

    [6] [写优化的数据结构(2):buffered tree](https://www.douban.com/note/269744617/)

    [7] [存储引擎数据结构优化(1):cpu bound](https://www.douban.com/note/304123656/)

    [8] [存储引擎数据结构优化(2):io bound](https://www.douban.com/note/304349195/)

    [9] [nessDB](https://github.com/BohuTANG/nessDB)

    [10] [omt](https://github.com/BohuTANG/omt)

    [11] [MergeTree存储结构](https://bohutang.me/2020/06/26/clickhouse-and-friends-merge-tree-disk-layout/)

    [12] [ARIES (Algorithms for Recovery and Isolation Exploiting Semantics)](https://en.wikipedia.org/wiki/Algorithms_for_Recovery_and_Isolation_Exploiting_Semantics)

    [13] [You're Doing It Wrong](https://queue.acm.org/detail.cfm?id=1814327)

    [14] [TokuDB](https://github.com/xelabs/tokudb)

    延伸阅读

    全文完。

    Enjoy ClickHouse :)

    叶老师的「MySQL核心优化」大课已升级到MySQL 8.0,扫码开启MySQL 8.0修行之旅吧

    展开全文
  • 原文出处:https://bohutang.me/2020/07/26/clickhouse-and-friends-mysql-replication/很多人看到标题还以为自己走错了夜...
  • 原文出处:https://bohutang.me/2020/08/31/clickhouse-and-friends-materialized-view/最后更新: 2020-08-31...
  • 原文出处:https://bohutang.me/2020/07/25/clickhouse-and-friends-parser/现实生活中的物品一旦被标记为“纯手工打造”,给人的第一...
  • 原文出处:https://bohutang.me/2020/09/18/clickhouse-and-friends-compute-storage/最后更新: 2020-09-18如果...
  • 原文出处:https://bohutang.me/2020/06/07/clickhouse-and-friends-mysql-protocol-read-stack/作为一个 OLA...
  • 原文出自:https://bohutang.me/2020/08/26/clickhouse-and-friends-mysql-gtid-replication/最后更新: 2020-...
  • 原文出处:https://bohutang.me/2020/09/13/clickhouse-and-friends-replicated-merge-tree/最后更新: 2020-0...
  • 原文出处:https://bohutang.me/2020/08/18/clickhouse-and-friends-merge-tree-wal/最后更新: 2020-09-18数据库...
  • 原文出处:https://bohutang.me/2020/06/08/clickhouse-and-friends-mysql-protocol-write-stack/上篇的MySQ...
  • 这里我使用到了Clickhouse的原生命令行客户端:Clickhouse-client,用于快速导入。 安装clickhouse 1)验证是否支持sse4.2 #clickhouse的server已经client仅支持x86_64,AArch64或PowerPC64LE CPU架构的Linux,...
  • 在揭秘 ClickHouse Group By 之前,先聊聊数据库的性能对比测试问题。在虎哥看来,一个“讲武德”的性能对比测试应该提供什么信息呢?首先要尊重客观事实,在什么场景下,x 比...
  • Hbase、Kudu和ClickHouse全视角对比

    千次阅读 2020-12-08 14:00:00
    点击上方蓝色字体,选择“设为星标”回复”资源“获取更多资源大数据技术与架构点击右侧关注,大数据开发领域最强公众号!大数据真好玩点击右侧关注,大数据真好玩!Hbase、KuduClick...
  • 快速上手 ClickHouse

    2021-10-16 20:28:41
    本篇来自数月前对外分享的文稿整理,并进行了一些扩展。 希望通过简单的方式,来介绍新手如何一步一步上手 ClickHouse,如果你有潜在的数据分析的需求,但是不知道...感谢两年前一位好朋友对我进行的技术选型推荐,使用
  • ClickHouse存储结构及索引详解

    千次阅读 2021-01-15 11:10:08
    (公司同事新出炉的技术文,虽然除了字都认识外其他看不出个所以然,不妨碍我仰望大神) 本文作者:擎创 大飞哥 ClickHouse存储结构及索引详解 环境介绍 本文基于ClickHouse 20.8.5.45版本编写,操作系统使用...
  • 使用Docker安装ClickHouse

    千次阅读 2020-04-10 22:07:24
    使用Docker安装ClickHouse
  • MySQL与Clickhouse是两个完全不一样的数据库,两者均有着自己的优缺点,两者所适合的业务场景也是不一样的,在实际业务中,我们需要根据数据库自身的特性优点选择合适它的业务场景。传统的MySQL数据库虽然很好的支持...
  • 0.ClickHouse 参考资料 : Clickhouse 在腾讯的应用实践 : http://www.yidianzixun.com/article/0NaOwJjF?appid=mibrowser 0.基础概念 0.0.概述 俄罗斯 Yandex 2016 开源 列式存储数据库 DBMS 0.1.应用场景 在线分析...
  • 大数据分析 mysql数据迁移clickhouse 最近项目遇到个问题,就是mysql做数据分析高并发情况下,老是报超时错误,主要原因还是因为mysql进行大批量关联查询太耗时间,于是在网上查询了下资料,决定试一下clickhouse ...
  • 原文出处:https://bohutang.me/3030/12/12/clickhouse-and-friends-mysql-replication-materializemysql...
  • 哈喽,小伙伴,承诺大家的clickhouse专栏系列开始了!博主也是一名入门者,践行者&布道者。希望一方面记录所思所为,另一方面把工作中实践的一些东西拿来分享给广大朋友,以飨读者!才疏学浅,难免有误!还望...
  • 随着物联网 IOT 时代的来临,IOT 设备感知报警存储的数据越来越大,有用的价值数据需要数据分析师去分析。大数据分析成了非常重要的环节。当然近两年开启的开源大潮,为大数据分析工程师提供了十分富余的工具。但...
  • 使用deb安装 按照教程使用 clickhouse-client报错如下 报错 $ clickhouse-client ClickHouse client version 21.3.2.5 (official build). Connecting to localhost:9000 as user default. Code: ...
  • 除此之外,夏水军还为我们分析了ClickHouse的优势与不足之处,不足之处在于ClickHouse不支持事务与多表join,只支持局部的updatedelete,且高并发不足、运维困难等局限。但是其优势也是有目共睹的,包括True ...
  • ClickHouse 正是以不依赖Hadoop 生态、安装维护简单、查询速度快、可以支持SQL等特点在大数据分析领域披荆斩棘越走越远。 ADB (AnalyticDB for MySQL) 分析型数据库MySQL版(AnalyticDB for MySQL),是阿里巴巴...
  • 感兴趣的朋友们可以参考这个教程[6],创建一个空文件,把它格式化成 squashfs,然后 mount 到本地文件系统的某个目录(mount point)里。 待到我们 umount 的时候,曾经加入到 mount point 里的文件,就留在这个“空...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 166
精华内容 66
关键字:

clickhouse和他的朋友们