原文:https://stackoverflow.com/a/17504505

中英对照:

  • Segment tree 线段树
  • Interval tree 区间树
  • Range tree 范围树
  • Binary indexed tree 二叉索引树

主要用于解决的问题:

  • Segment tree 存储区间,查询哪些区间包含给定的点
  • Interval tree 存储区间,查询哪些区间与给定区间相交,也支持点查询(Segment tree)
  • Range tree 存储点,查询哪些点落在了给定区间
  • Binary indexed tree 存储每个索引的项目数,查询索引 m 和 n 之间有多少个项目

性能(k 是结果数):

  • Segment tree O(n logn) 预处理时间,O(k+logn) 查询,O(n logn) 空间
  • Interval tree O(n logn) 预处理时间,O(k+logn) 查询,O(n) 空间
  • Range tree O(n logn) 预处理时间,O(k+logn) 查询,O(n) 空间
  • Binary indexed tree O(n logn) 预处理时间,O(logn) 查询,O(n) 空间

因工作需要,学习了原本十分抗拒的 perl 语言,不过整体看下来后发现 perl 也有其自身的特点与优势,看来每个语言都不可小觑。

由于时间比较急,所以在网上找了一篇速读文章学习,教程很棒,读完后对各种奇葩语法有了一定的认识,链接如下:

https://qntm.org/perl_cn

下面是一些小笔记:

获取数组长度,前面的 scalar 表示在 scalar 上下文中求 @array 的值,此时即为求数组长度

1
scalar @array

获取数组最大有效索引

1
$#array

引用(可以理解为指针)

1
2
@array = (1,2,3,4)
$array_ref = \@array

匿名结构(也是引用)

1
2
$array_ref = [1,2,3,4] # 与上一个 array_ref 一样,都是一个包含四个 scalar 的 array 的引用,但引用的对象不同
$hash_ref = {1 => 2, 3 => 4} # hash_ref 是一个包含两个键值对的 hash 的引用

引用取值

1
2
$array_ref -> [0] # 获取第一个 scalar 1
$hash_ref -> {1} # 获取 1 对应的值 2

解引用

1
2
@{ $array_ref } # 等价于 @$array_ref
%{ $hash_ref } # 等价于 %$hash_ref

阅读全文 »

使用 brew cask 安装的 macvim,版本为:8.1.2234,161

macvim 图形界面中文显示成问号,但在终端下面却可以正常显示,网上搜了很久都在说编码问题,其实不是,正解如下:

  1. 打开 macvim GUI
  2. 点击菜单栏-Preferences
  3. 点击 Advanced
  4. 取消选中 Use Core Text renderer 选项
  5. 重启 macvim GUI

最近在使用 clickhouse(下面简称 CH) 的 materialized view(下面简称为 MV)功能,类似其他数据库的物化视图,触发器之类的功能,不过遇到了几点坑,有的通过升级 CH 版本解决了,有的可以在写 sql 的时候小心避免。

先列一下我个人总结出来的使用要点,不想继续看的可以尝试依据这些要点看能否解决自己的问题:

  1. 在创建 MV 表时,一定要使用 TO 关键字为 MV 表指定存储位置
  2. 在创建 MV 表时如果用到了多表联查,不能为连接表指定别名,如果多个连接表中存在同名字段,在连接表的查询语句中使用 AS 将字段名区分开
  3. 在创建 MV 表时如果用到了多表联查,只有当第一个查询的表有数据插入时,这个 MV 才会被触发
  4. 在创建 MV 表时如果用到了子查询,且子查询会回查 SRC 表,那么这个子查询会回查整个 SRC 表,并不是只有新插入的那部分数据
  5. 在创建 MV 表时不要使用 POPULATE 关键字,而是在 MV 表建好之后将数据手动导入 MV 表

先看看官方的创建 MV 的语句:

1
CREATE MATERIALIZED VIEW [IF NOT EXISTS] [db.]table_name [TO[db.]name] [ENGINE = engine] [POPULATE] AS SELECT ...

具体的介绍可以阅读官方文档:https://clickhouse.yandex/docs/en/query_language/create/#create-view

值得一提的虽然官方提供了中文文档,但中文文档内容更新不及时,较英文文档有缺失的部分,还是建议阅读英文的。

我使用 MV 的场景是:

1
SRC -> MV1 -> MV2
阅读全文 »

zookeeper 崩溃恢复过程中两个关键性问题

Q1:leader 提交事务 A 后崩溃,follower 没有收到提交事务 A 的消息,再次选举 leader 时如何确保事务 A 被应用?

A1:既然 leader 已经在本地提交了事务 A,那么说明事务 A 肯定已经经过了多数 follower 的确认,即多数 follower 上都有事务 A 的记录,leader 崩溃后,重新选举出的新 leader 肯定包含未提交的事务 A,因为事务 A 的事务 ID 最大,新 leader 会继续提交事务 A。


Q2:leader 在还未将事务 B 广播到集群中时崩溃,在重新选举 leader 并在旧 leader 恢复正常后如何处理事务 B?

A2:事务 B 将会被删除,不会被提交。leader 在接收到一个请求,并将其转化为事务 B 后崩溃,此时还没有将事务 B 广播到集群中,即此事务只存在于 leader 机器上,经过新一轮的 leader 选举后,旧 leader 恢复正常并加入集群,此时会发现事务 B 的事务 ID 所使用的 epoch 号与新 leader 的对不上,那么事务 B 就会被删除。

应用场景

把握好 zookeeper 的主要特性就可以将其应用在多种多样的场景下。主要特性如下:

  • 节点
    • 树结构
    • 持久节点
    • 持久顺序节点
    • 临时节点
    • 临时顺序节点
    • 节点只能被注册一次
  • watcher

在《从 Paxos 到 Zookeeper》一书中提到的应用场景以及我认为场景所应用到的主要特性如下:

阅读全文 »

公司有线网是电信的,访问境外的服务器会间歇性得无法访问,但有一个无线网是移动的,用手机测试发现一直没什么问题,所以搞了个无线网卡连无线网。

但电脑的数据默认只走有线网,只有关了有线网才能用无线网,但是公司内部的服务只能通过有线网访问,所以就尝试了以下方案:

  • 192.168.1.0/24 网段走有线网,其他走无线网
  • 只在访问境外服务器的时候走无线网

经过测试确定这两个方案都能满足我的需求,但是由于无线不如有限稳定,所以最后确定使用第二种方案。

调整路由的工具使用 ip 命令的子命令 route,除了路由子命令还有很多其他网络相关的功能,具体可以查看 ip 命令的 man 手册。

linux 下当连接无线网和有线网之后使用 ip route,可以简写为 ip r 可以列出当前所有的路由规则:

1
2
3
4
5
6
default via 192.168.1.1 dev enp2s0 proto static metric 100
default via 192.168.1.1 dev wlx200db012a6be proto dhcp metric 600
172.17.0.0/16 dev docker0 proto kernel scope link src 172.17.0.1 linkdown
192.168.1.0/24 dev enp2s0 proto kernel scope link src 192.168.1.208 metric 100
192.168.1.0/24 dev wlx200db012a6be proto kernel scope link src 192.168.1.74 metric 600
192.168.252.0/24 dev xdroid0 proto kernel scope link src 192.168.252.1

其中 enp2s0 是有线网相关的路由,wlx200db012a6be 是无线网相关的路由,此外还有 docker 和 xdroid 相关的,后面这两个不用管,没有安装这两个程序的机器也不会有这两种路由。

从上面的路由规则可以看到 enp2s0 相关的 metric 值为 100 而 wlx200db012a6be 相关的 metric 值为 600,这就表示 enp2s0 相关的路由规则比 wlx200db012a6be 相关的路由规则优先级高。在相同的条件下,如相同的 prefix(IP 地址段)时系统将优先使用 enp2s0。

例如以下这两条规则,就表示访问 192.168.1.* 就会走 enp2s0:

1
2
192.168.1.0/24 dev enp2s0 proto kernel scope link src 192.168.1.208 metric 100
192.168.1.0/24 dev wlx200db012a6be proto kernel scope link src 192.168.1.74 metric 600

此外要注意调整路由规则需要 root 权限。

阅读全文 »

klib 的项目地址:https://github.com/attractivechaos/klib/

klib 官方文档:http://attractivechaos.github.io/klib/

总的来说整个 klib 库小巧且功能强大,各种实现之间没有依赖,大多只需要 include 头文件即可使用,目前已经使用过的有 khash 和 klist,这里先说我个人在使用 khash 的过程中遇到的问题和使用过程中需要注意的点。

上面的 klib 官方文档链接中有不少入门的小例子,但也只是简单的使用方法,很多接口并没有提及,不过也有可能作者没有及时更新文档中的例子。

在使用过程中要时刻谨记 khash 中给出的接口都是宏,这也意味着在调试的时候很不方便,如果搞不懂一个接口的意思或者想知道这个接口都做了什么,最好还是看一下 khash.h 中的实现。

就我个人来说,最想提出要注意的一点是 内存释放,在过去一段时间内,我手上依赖 klib 的程序一直都有内存泄漏,不过我始终没有找到原因,直到昨天我才终于定位到是 khash 相关的数据没有被彻底释放。导致这一问题出现的重要原因也在于我接手这个项目时,khash 相关的释放代码已经大量存在了,以至于先入为主,令我以为正确的释放操作就应该就那样,昨天定位到这个问题后我仔细分析了一下 khash 的源码,发现一直以来程序里关于销毁释放内存的操作,一直都是错误的。下面只会使用正确的方法(至少目前我认为是正确的:)),以免误导了其他人。

khash 里面提供了两种数据结构:hashmap 和 hashset,两种结构的使用方法大致是一样的,可以把 hashset 结构看作是没有值的 hashmap。

demo1

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
// 声明 hashmap 名字和键值的类型
// 这个宏还定义了大量的函数,不过一般都不直接使用那些函数,而是使用通用的接口宏
// 这里声明了一个键值对是 int:int 的 map 类型,注意这里只是声明了一个 类型
// 这个 map 类型的名字是 MAP_int2int,map 的名字后面会经常用到
// 此外,这个宏是对宏 KHASH_INIT 的一个简单封装
// 如果有复杂需求要使用 KHASH_INIT,则需要提供两个 hash 函数,我没有用到就不举例了
// hash 函数的实现可以参考 khash 里已有的来实现
KHASH_MAP_INIT_INT(MAP_int2int, int);

khash_t(MAP_int2int) *map_int2int = kh_init(MAP_int2int); // 使用上面声明的 map 类型声明并初始化一个变量

khiter_t iter = 0; // 访问键、值都需要使用 iter
iter = kh_get(MAP_int2int, map_int2int, 100); // 查看 100 这个键是否在 map 中存在

if (iter == kh_end(map_int2int)) { // 不存在
int ret = 0; // 将 100 这个键放入 map,ret 是一个额外的返回值,用来表示放入操作的结果
iter = kh_put(MAP_int2int, map_int2int, 100, &ret); // 放入成功后返回值 iter 即表示为 100 这个键在 map 中的位置
}
kh_value(map_int2int, iter) = 200; // 使用 iter 来存值,值为 200
/* 至此 map 中就有了 100:200 这一个数据 */

// 遍历 map
for (iter = kh_begin(map_int2int); iter != kh_end(map_int2int); iter++) {
if (!kh_exist(map_int2int, iter)) { // 这里的判断一定要有
continue;
}
do_something_foo(kh_key(map_int2int, iter));
do_something_bar(kh_val(map_int2int, iter));
}
/* khash 里还提供了更便利的遍历宏:kh_foreach 和 kh_foreach_value */

kh_del(MAP_int2int, map_int2int, iter); // 当确定一个 iter 之后,可以移除一个键值对
kh_clear(MAP_int2int, map_int2int); // 清空这个 map 的所有数据

do_something_zzz(map_int2int); // 清空后的 map 还可以继续使用,比如继续往里面存值

kh_destroy(MAP_int2int, map_int2int); // 销毁 map,销毁之后就不能再使用了

demo2

阅读全文 »

在 linux 下补全的配置一般发行版都给默认配了,原本以为在 OSX 下用 brew 装个 bash-completion 包,再在 bashrc 下贴两行配置也就搞定了,没想到不行,OSX 下 bash-completion 包有两个,另一个是 bash-completion@2,这两个包分别对应 bash 的两个版本,具体可以用 brew info bash-completion@2 来看。

而且 bash-completion@2bash-completion 相比还要多一行配置,总之就是需要下面两行配置才行,原因是大多软件包都只提供了旧版本的 completion 文件,新版的没有提供支持,所以下面的第一行就是声明要兼容下旧的补全文件:

1
2
export BASH_COMPLETION_COMPAT_DIR="/usr/local/etc/bash_completion.d"
[[ -r "/usr/local/etc/profile.d/bash_completion.sh" ]] && . "/usr/local/etc/profile.d/bash_completion.sh"

除此之外还有个问题,我自己设置了很多别名 alias,但是这些自定义的别名默认是不支持参数补全的,想要如丝般顺滑就要用另一个项目:https://github.com:cykerway/complete-alias,具体的使用方法就不赘述了,可以去项目里看看怎么配置。

经过实践发现这个项目也不支持旧版的 bash-completion 包,会提示 _completion_loader 找不到的错误,改装 bash-completion@2 就好了。

使用 let’s encrypt 证书颁发机构的免费证书,如果想看官方的文档访问下面的链接,官方文档提供了各种方案来启用 https,我使用是推荐的 Certbot 方案。

https://letsencrypt.org/zh-cn/getting-started/

本文摘自的 Certbot 官网的针对 Ubuntu+Nginx 方案的教程,原文链接如下。

https://certbot.eff.org/lets-encrypt/ubuntuxenial-nginx

如果你的系统不是 Ubuntu 16.04 或者使用的 web 服务不是 nginx 可以去下面的链接重新选择教程。

https://certbot.eff.org

正文开始:

使用 ssh 或任何方法登陆到运行 web 服务的服务器,注意账户需要有 root 权限。

使用下面的命令添加 Certbot PPA 到系统中:

1
2
3
4
5
sudo apt-get update
sudo apt-get install software-properties-common
sudo add-apt-repository universe
sudo add-apt-repository ppa:certbot/certbot
sudo apt-get update

使用如下命令安装 Certbot:

1
sudo apt-get install certbot python-certbot-nginx

阅读全文 »