本文主要介绍 clickhouse 的基础用法

安装

下面以 Debain/Ubuntu系统为例，安装方式

1
2
3
4
5
6
7
8
9
10
11

sudo apt-get install -y apt-transport-https ca-certificates dirmngr
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 8919F6BD2B48D754

echo "deb https://packages.clickhouse.com/deb stable main" | sudo tee \
    /etc/apt/sources.list.d/clickhouse.list
sudo apt-get update

sudo apt-get install -y clickhouse-server clickhouse-client

sudo service clickhouse-server start
clickhouse-client # or "clickhouse-client --password" if you've set up a password.

创建表

• MergeTree类型

  以下是一个记录用户访问日志的表

  1 2 3 4 5 6 7 8 9 10

  CREATE TABLE IF NOT EXISTS visit_log ( user_id UInt32, url String, count UInt8, created_at DateTime ) Engine = MergeTree PARTITION BY toYYYYMMDD(created_at) -- 按照日期分区 ORDER BY created_at -- 按照时间排序 TTL created_at + toIntervalDay(180) -- 指定180天自动删除过期数据 SETTINGS index_granularity = 8192 -- 设置索引颗粒度

• 创建视图

  以下视图是为了按小时统计url的访问次数

  1 2 3 4 5 6 7 8 9 10 11 12 13

  CREATE MATERIALIZED VIEW url_stat ENGINE = AggregatingMergeTree() ORDER BY (hour_time, url) TTL hour_time + toIntervalDay(1) AS SELECT url, toStartOfHour(created_at) AS hour_time, --格式化为小时 sumState(count) AS visit_count_state, -- 统计总和 minState(created_at) AS first_time_state, -- 记录最早访问时间 maxState(created_at) AS last_time_state -- 记录最晚访问时间 FROM visit_log WHERE count>0 GROUP BY hour_time,url

  more >>

什么是clickhouse

ClickHouse是一个用于联机分析(OLAP)的列式数据库管理系统(DBMS)。列式数据库更适合于OLAP场景(对于大多数查询而言，处理速度至少提高了100倍)

特性

• 海量数据：每秒几亿行的吞吐能力
• 数据压缩：支持以更小的磁盘存储更多的数据
• 并行处理：ClickHouse会使用服务器上一切可用的资源，从而以最自然的方式并行处理大型查询
• 分布式集群：支持多分片存储，查询可以并行地在所有分片上进行处理

想要了解更多，请查看：https://clickhouse.com/docs/zh/introduction/distinctive-features

适用场景

• 适合海量数据存储，大批量数据快速插入

  写入到MergeTree表中时，写入速度大约为50到200MB/s

• 适合查询频率较低，查询数据庞大

  一个不太复杂的查询在单个服务器上大约能够以2-10GB／s（未压缩）的速度进行处理（对于简单的查询，速度可以达到30GB／s）
  在相同的情况下，ClickHouse可以在单个服务器上每秒处理数百个查询（在最佳的情况下最多可以处理数千个）。但是由于这不适用于分析型场景。因此我们建议每秒最多查询100次。

定义

Redis 的 Listpack 是一种专门用于实现底层的 list 数据结构的紧凑型二进制数据格式，通过优化内存占用和 CPU 执行效率等方面来提高列表操作的性能和吞吐量。通常情况下，Listpack 会在 Redis 的列表操作中与 Quicklist 和 Ziplist 进行混合组合使用。

Listpack 的设计主要有以下几个方面的考虑：

• 物理上受限。一次仅能访问固定大小的内存块，因此需要有效地优化内存占用。
• 高效归档。缓慢和大量访问时需要很快地进行归档和截断，因此需要有效地支持对跨越多块或长时间未被访问的元素的删除和收缩操作。
• 具有随机访问特性。允许针对需要随机访问的元素（如非常大的列表）使用块缓存、预取依赖等高级缓存算法以支持快速随机访问功能而不会影响整体性能。

Listpack 将列表中所有字符串类型的值编码成一种紧凑的、不可变的字节数组并按顺序连接起来，同时还维护了一份总长度、最后一个元素的偏移量、已使用字节数和尾部空白（tail free）区域的首地址等元数据信息。为了优化内存使用和分配，Listpack 还使用了一种连续型内存结构，其中每个块包含至多 64 个字节并允许使用支持延迟分配的技术。

1

总之，Redis 的 Listpack 是一种紧凑、高效、可扩展的二进制格式，通过设计精巧的开销管理和随机访问功能来提高 Redis 列表操作性能和灵活性。

什么是QuickList

Redis 中的 Quicklist 是一种高效存储小块二进制数据的数据结构，是由两个有序列表组成的双向链表，其中每个节点可以包含多个小块数据。Quicklist 通常用于处理缓存、队列和列表等场景，相比于单纯使用链表或数组存储小块数据，在内存占用、遍历速度和插入/删除操作上都具有更优秀的性能。

原理

Quicklist 内部实现细节如下：

• 双向链表结构：quicklist 由多个有序列表组成，列表是通过双向指针连接起来的双向链表。
• 节点大小限制：每个 quicklist 节点最大为 4KB。
• 压缩与不压缩：当 quicklist 中的所有小块数据（也称为 blob）平均较小且数量众多时，会启用自动压缩机制，并将多个小块数据合并为较大的块以节约空间和加快遍历速度；而当数据块较大或数量不足时，压缩机制失效，节点中的 - blob 仍然保持原样（不压缩）。
• 按插入顺序存储：Quicklist 内的元素是按照添加时间排序的，最新的小块数据始终排在链表的最前面。
• ziplist 数据结构：在 Quicklist 节点中存储小块数据使用的是 ziplist 数据结构，这是一种紧凑高效的连续内存布局，可以减少内存分配和指针跳转的脆弱性。
• 多层级索引：quicklist 中还有一个多层级索引，可以根据 blob 的下标位置快速定位到对应节点的列表，并减少遍历操作的次数。

定义

Redis中的Ziplist是一种压缩列表（compact list）数据结构，用于代替双端链表、哈希表等常规数据结构。它可以在内存占用较小的情况下支持随机访问，适合存储长度小且元素数量少的列表。

Ziplist将多个节点连续存储在一个紧凑的可重复利用的内存区域中，相比于双端链表、哈希表之类的数据结构，它节省了大量的内存分配和管理开销。并且，在元素个数较少的情况下，它可以更快地处理命令请求，其中包括插入、删除和遍历操作。

classDiagram
    ZipList .. Entry
    class ZipList{
        -[]byte data
        -int count
        -int tailIndex
        +Insert(entry)
        +Get(index)
    }
    class Entry {
        -int prevLen
        -[]byte data
        -Encoding encoding
        +Byte()
    }

特点

• Ziplist的内存分布连续，高效利用了cache line，可以减少内存碎片和操作次数。
• 可以通过偏移量快速计算每个节点的位置，并进行快速的定位和修改。这使得Ziplist的遍历与查找操作非常高效，时间复杂度为O(1)。
• Ziplist本身就具有压缩性，节点数量较少时，可以极大地节约内存空间。如果列表已经达到了一定大小或者需要频繁更新，则Redis会自动将其转换成基于双端链表或者散列表的数据结构。

实现

我们今天来介绍下红黑树，根据此文快速掌握红黑树这种数据结构的原理与实现

什么是红黑树

红黑树是一种常用的自平衡二叉搜索树，与 AVL 树、Treap 等数据结构相比，其插入和删除操作的时间复杂度更优秀，而且难度较低。它能够在任何情况下保持平衡，因此在高效的查找、插入、删除等操作中得到广泛应用。

特性

• 每个节点要么是红色，要么是黑色；
• 根节点是黑色的；
• 所有叶子节点（即空节点）都是黑色的；
• 如果一个节点是红色的，则它的两个子节点都是黑色的；也就是说不能出现连续的红节点；
• 从任意一个节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束条件确保了红黑树在插入和删除结点时始终保持平衡，即每个结点到叶子结点的路径长度都是大致相同的，从而保证了红黑树的查找、插入和删除操作的时间复杂度为O(logn)。另外，由于红黑树内部所有的插入、删除操作都需要保证其满足着上述特点，所以相比于其他平衡树（如AVL树），红黑树的实现难度较低，而且性能表现更为稳定，因此应用广泛。

红黑树的具体实现可以使用旋转操作，向上旋转、向下旋转、左旋等操作来保证树的平衡状态。

实现

classDiagram
class RedBlackTree:::styleClass {
        -root *node // 头节点
        +Put(key int, val any) // 写入数据
        +Get(key int) any // 获取数据
        +Delete(key int) // 删除数据
    }

以下是golang版的红黑树实现代码：

在redis中，利用SkipList实现了如SortedSet这样的数据结构。本文将介绍SkipList算法实现细节

什么是SkipList(跳表)

跳表是一种基于多级索引的数据结构，用于快速查找链表中的数据。它的查询和插入操作都可以在 O(log n) 的时间复杂度内完成。

• 设计思想
  跳表的基本思想是为链表建立多级索引，每层索引包含了下一层索引的部分节点。较高层的索引节点可以直接跨越较低层的多个节点，从而实现了快速查找的功能。

• 适用场景
  因为跳表具有简单、易实现、效率高等优点，所以被广泛应用于各类数据存储系统和搜索算法中。比如Redis的有序集合就是采用SkipList实现的

实现

本文主要介绍栈的概念与实现，以及应用场景

概念

栈 Stack是一种遵循先入后出数据操作规则的线性数据结构。

• 栈顶：栈的最顶部元素
• 栈底：栈的最底部元素
• 入栈：将元素添加到栈顶
• 出栈：删除栈顶元素

应用场景

• 浏览器前进与后退
• 操作的撤销与反撤销

实现

常用操作

本文将初步探索k8s的架构设计。

架构图

组件说明

控制平面组件(ControlPlaneComponents)

主要运行在Master节点，为k8s集群做出全局决策，如资源调度、服务检测、集群事件响应等。

• kube-apiserver
  该组件管理着k8s的开放接口，是k8s集群的前端控制，负责处理内部集群与外部客户端的请求。

• etcd
  该组件为高可用的键值存储数据库，负责存储k8s集群的所有资源配置数据。

• kube-schedule
  该组件负责监听新创建且未指定Node的Pods,并选择某个Node来运行Pod。

调度策略由Pod定义的资源需求、软硬件需求、亲和性、反亲和性、工作负载等因素决定。

• kube-controller-manager
  该组件负责运行控制器进程，包含多个控制器，主要包括：
  • 节点控制器(NodeController): 负责在节点出现故障时进行通知和响应。
  • 任务控制器(JobController): 监测代表一次性任务的Job对象，然后创建Pods来运行任务直至完成。
  • 端点分片控制器(EndpointSliceController): 填充EndpointSlice对象，提供Service与Pod之间的链接。
  • 服务账号控制器(ServiceAccountController): 为新的命名空间创建默认的服务账号。

Node组件

运行在每个worker节点上，负责维护运行Pod以及提供k8s运行环境

• kubelet
  该组件通过各类机制提供给它的PodSpecs，确保描述的容器处理运行状态且健康。

• kube-proxy
  运行在每个节点上的网络代理，负责流量转发，允许集群内部或外部直接与pod进行通信。

• Container Runtime
  k8s支持多种容器运行环境，如containerd,docker等

本文介绍如何实现grpc服务的负载均衡

什么是grpc

gRPC 是一个高性能、开源、通用的 RPC 框架，面向移动和 HTTP/2 设计，是由谷歌发布的首款基于 Protocol Buffers 的 RPC 框架。 gRPC 基于 HTTP/2 标准设计，带来诸如双向流、流控、头部压缩、单 TCP 连接上的多复用请求等特性。

问题

由于grpc底层是通过保持长连接来实现链路复用，避免重复创建连接导致的开销。但是当服务端存在多个实例时，会导致新的请求始终指到某一个实例。

为此我们需要一些特殊的手段来实现负载均衡。

实现方式

我们可以通过客户端负载均衡以及服务端负载均衡两种方式来实现，对比如下：

具体介绍如下：