tonglin0325的个人主页

存储底层数据结构对比

tonglin0325

该文章对比了常用的一些存储底层所使用的数据结构。

1.B+树#

MySQL，MongoDB的索引使用的就是B+树

B+树在多读少写（相对而言）的情境下比较有优势。

B+树的主要优点：

  • 1.结构比较扁平，高度低（一般不超过4层），随机寻道次数少；
  • 2.数据存储密度大，且都位于叶子节点，查询稳定，遍历方便；
  • 3.叶子节点形成有序链表，范围查询转化为顺序读，效率高。相对而言B树必须通过中序遍历才能支持范围查询。

B+树的缺点：

  • 1.如果写入的数据比较离散，那么寻找写入位置时，子节点有很大可能性不会在内存中，最终会产生大量的随机写，性能下降。
  • 2.如果B+树已经运行了很长时间，写入了很多数据，随着叶子节点分裂，其对应的块会不再顺序存储，而变得分散。这时执行范围查询也会变成随机读，效率降低了。

参考：从B+树到LSM树，及LSM树在HBase中的应用

2.LSM树(Log-structured Merge-Tree/日志结构的合并树)#

RocksDB，HBase，Cassandra，Kudu底层使用的是LSM树

LSM树的优点：

  • 1.LSM树由于数据按顺序存储，因此可以有效地执行区间查询（从最小值到最大值扫描所有的键），并且由于磁盘是顺序写入的（以顺序方式写入紧凑的SSTable文件，而不必重写树中的多个页），所以LSM-Tree可以支持非常高的写入吞吐量。

LSM树的缺点：

  • 1.压缩过程中有时会干扰正在进行的读写操作。即使存储引擎尝试增量地执行压缩，并且不影响并发访问，但由于磁盘的并发资源有限，所以当磁盘执行昂贵的压缩操作时，很容易发生读写请求等待的情况。而B-tree的响应延迟则更具确定性。

参考：LSM树由来、设计思想以及应用到HBase的索引 和 数据密集型应用系统设计第3章

3.跳表#

Redis底层使用的是SkipTable

Mysql的索引为什么使用B+树而不使用跳表?#

B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息，所以扇出很高。三层左右就可以存储2kw左右的数据(知道结论就行，想知道原因可以看之前的文章)。也就是说查询一次数据，如果这些数据页都在磁盘里，那么最多需要查询三次磁盘IO。

跳表是链表结构，一条数据一个结点，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，也即是查一次数据会经历24次磁盘IO。

因此存放同样量级的数据，B+树的高度比跳表的要少，如果放在mysql数据库上来说，就是磁盘IO次数更少，因此B+树查询更快。

而针对写操作，B+树需要拆分合并索引数据页，跳表则独立插入，并根据随机函数确定层数，没有旋转和维持平衡的开销，因此跳表的写入性能会比B+树要好。

redis为什么使用跳表而不使用B+树或二叉树呢?#

redis支持多种数据结构，里面有个有序集合，也叫ZSET。内部实现就是跳表。那为什么要用跳表而不用B+树等结构呢?

大家知道，redis 是纯纯的内存数据库。

进行读写数据都是操作内存，跟磁盘没啥关系，因此也不存在磁盘IO了，所以层高就不再是跳表的劣势了。

并且前面也提到B+树是有一系列合并拆分操作的，换成红黑树或者其他AVL树的话也是各种旋转，目的也是为了保持树的平衡。

而跳表插入数据时，只需要随机一下，就知道自己要不要往上加索引，根本不用考虑前后结点的感受，也就少了旋转平衡的开销。

因此，redis选了跳表，而不是B+树。

参考：MySQL的索引为什么使用B+树而不使用跳表？

ElasticSearch学习笔记——插件开发

tonglin0325

参考

1
2
3
4
5
6
https://dzone.com/articles/elasticsearch5-how-to-build-a-plugin-and-add-a-lis
https://github.com/chrisshayan/es-changes-feed-plugin
https://blog.csdn.net/qq_16164711/article/details/87872383
https://blog.gaiaproject.club/es-develop-plugin/
https://blog.51cto.com/13755625/2117995

Es的插件主要有如下几种类型，参考

1
2
https://github.com/elastic/elasticsearch/tree/master/server/src/main/java/org/elasticsearch/plugins

全文 >>

HBase学习笔记——rowkey

tonglin0325

1.Airbnb rowkey设计案例

在Airbnb的rowkey设计案例中，使用了hash法避免了写入热点问题，其中

Event_key标识了一条日志的唯一性，用于将来自Kafka的日志数据进行去重；

Shard_id是将Event_key进行hash（可以参考es的路由哈希算法Hashing.murmur3_128）之后，对Shard_num进行取余后的结果，Shard_num感觉应该是当前hbase表region server的总数，由于airbnb在hbase中存储的是实时日志数据，并开启了Hbase的TTL，所以当前hbase表中的数据总量应该是可预测的，即region server数量不会无限增加

Shard_key应该就是当前业务的region_start_keys+shard_id，比如当前业务分配的前缀为00000，同时规划了100个table regions给这个业务，即00-99，那么Shard_key的范围就是0000000-0000099

rowkey就是Shard_key.Event_key，比如0000000.air_events.canaryevent.016230-a3db-434e

参考：

Reliable and Scalable Data Ingestion at Airbnb

Apache HBase at Airbnb

Airbnb软件工程师丁辰 - Airbnb的Streaming ETL

2.rowkey设计原则

1.rowkey长度原则：rowkey是一个二进制码流，可以是任意字符串，最大长度

全文 >>

Hive学习笔记——fetch

tonglin0325

在美团点评的文章中，介绍了HiveSQL转化为MapReduce的过程

1
2
3
4
5
6
7
1、Antlr定义SQL的语法规则，完成SQL词法，语法解析，将SQL转化为抽象语法树AST Tree
2、遍历AST Tree，抽象出查询的基本组成单元QueryBlock
3、遍历QueryBlock，翻译为执行操作树OperatorTree
4、逻辑层优化器进行OperatorTree变换，合并不必要的ReduceSinkOperator，减少shuffle数据量
5、遍历OperatorTree，翻译为MapReduce任务
6、物理层优化器进行MapReduce任务的变换，生成最终的执行计划

参考：Hive SQL的编译过程

但是不是所有的SQL都有必要转换为MR来执行，比如

1
2
select * from xx.xx limit 1

Hive只需要直接读取文件，并传输到控制台即可

全文 >>

ElasticSearch学习笔记——ik分词添加词库

tonglin0325

前置条件是安装ik分词，请参考

Elasticsearch学习笔记——分词

1.在ik分词的config下添加词库文件

1
2
3
~/software/apache/elasticsearch-6.2.4/config/analysis-ik$ ls | grep mydic.dic
mydic.dic

内容为

1
2
我给祖国献石油

2.配置词库路径，编辑IKAnalyzer.cfg.xml配置文件，添加新增的词库

3.重启es

4.测试

data.json

1
2
3
4
5
{
        "analyzer":"ik_max_word",
        "text": "我给祖国献石油"
}

添加之后的ik分词结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
curl -H 'Content-Type: application/json' http://localhost:9200/_analyze?pretty=true -d@data.json
{
  "tokens" : [
    {
      "token" : "我",
      "start_offset" : 0,
      "end_offset" : 1,
      "type" : "CN_CHAR",
      "position" : 0
    },
    {
      "token" : "给",
      "start_offset" : 1,
      "end_offset" : 2,
      "type" : "CN_CHAR",
      "position" : 1
    },
    {
      "token" : "祖国",
      "start_offset" : 2,
      "end_offset" : 4,
      "type" : "CN_WORD",
      "position" : 2
    },
    {
      "token" : "献",
      "start_offset" : 4,
      "end_offset" : 5,
      "type" : "CN_CHAR",
      "position" : 3
    },
    {
      "token" : "石油",
      "start_offset" : 5,
      "end_offset" : 7,
      "type" : "CN_WORD",
      "position" : 4
    }
  ]
}

添加之后的ik分词结果，分词结果的tokens中增加了 “我给祖国献石油”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
curl -H 'Content-Type: application/json' http://localhost:9200/_analyze?pretty=true -d@data.json
{
  "tokens" : [
    {
      "token" : "我给祖国献石油",
      "start_offset" : 0,
      "end_offset" : 7,
      "type" : "CN_WORD",
      "position" : 0
    },
    {
      "token" : "祖国",
      "start_offset" : 2,
      "end_offset" : 4,
      "type" : "CN_WORD",
      "position" : 1
    },
    {
      "token" : "献",
      "start_offset" : 4,
      "end_offset" : 5,
      "type" : "CN_CHAR",
      "position" : 2
    },
    {
      "token" : "石油",
      "start_offset" : 5,
      "end_offset" : 7,
      "type" : "CN_WORD",
      "position" : 3
    }
  ]
}

　　

全文 >>

Flink学习笔记——用户自定义Functions

tonglin0325

Flink支持用户自定义 Functions，方法有2个

Ref

1
2
https://ci.apache.org/projects/flink/flink-docs-release-1.12/zh/dev/user_defined_functions.html

  1. 实现 MapFunction接口
1
2
3
4
5
class MyMapFunction implements MapFunction<String, Integer> {
  public Integer map(String value) { return Integer.parseInt(value); }
};
data.map(new MyMapFunction());

  1. 继承 RichMapFunction
1
2
3
4
class MyMapFunction extends RichMapFunction<String, Integer> {
  public Integer map(String value) { return Integer.parseInt(value); }
};

全文 >>

Flink学习笔记——Execution Mode

tonglin0325

Flink有3中运行模式，分别是STREAMING，BATCH和AUTOMATIC

Ref

1
2
https://ci.apache.org/projects/flink/flink-docs-release-1.12/zh/dev/datastream_execution_mode.html

1.STREAMING运行模式 是DataStream默认的运行模式

2.BATCH运行模式 也可以在DataStream API上运行

3.AUTOMATIC运行模式 是让系统根据source类型自动选择运行模式

可以通过命令行来配置运行模式

1
2
bin/flink run -Dexecution.runtime-mode=BATCH examples/streaming/WordCount.jar

也可以在代码中配置

1
2
3
StreamExecutionEnvironment env = StreamExecutionEnvironment.getExecutionEnvironment();
env.setRuntimeMode(RuntimeExecutionMode.BATCH);

全文 >>

Flink学习笔记——Environment

tonglin0325

Flink有以下几种Environment

  1. 批处理Environment，ExecutionEnvironment
1
2
ExecutionEnvironment env = ExecutionEnvironment.getExecutionEnvironment();

2.流处理Environment，StreamExecutionEnvironment

1
2
StreamExecutionEnvironment env = StreamExecutionEnvironment.getExecutionEnvironment();

  1. 本机Environment，LocalEnvironment
1
2
ExecutionEnvironment env = LocalEnvironment.getExecutionEnvironment();

  1. java集合Environment，CollectionEnvironment
1
2
ExecutionEnvironment env = CollectionEnvironment.getExecutionEnvironment();

Ref

1
2
https://www.yuque.com/cuteximi/base/flink-02?language=en-us

　　

创建Environment的方法

  1. getExecutionEnvironment ，含义就是本地运行就是

    全文 >>

tonglin0325

标签

标签云

AWS Airbnb Android CDH Doris ELK Flink Git Grafana HAProxy HBase Hadoop Hive Hudi InfluxDB JDBC JMeter JVM Java JavaWeb LaTex Linkedin Linux ML ML Infra MPP Maven MySQL Nexus OpenTSDB Paper Play Prometheus Python React Redis RocksDB Scala Solr Spark SpringBoot SpringMVC Thrift YARN antlr arthas avro cassandra clickhouse confluent docker filebeat flume golang google gradle hexo impala jenkins k8s kafka kerberos kudu ldap mac mongo mybatis nginx nlp open-falcon openwrt parquet presto ranger scyllaDB twitter zookeeper 刷题 前端 图存储及计算 多线程 广告系统 开发工具 数据结构 杂谈 正则表达式 算法 系统设计 计算机网络 设计模式

文章归档

最近文章