Felix021

　　前几天讨论遇到一个涉及区间覆盖的数据统计，发现很适合使用线段树来解决，于是重新回顾了一下这个好几年前学过的东西，凭着残存的理解，好了好久才勉强写了出来，感觉自己确实是没有搞算法的天赋，在边界处理的时候磕磕碰碰的，需要改好几次才能写对，不够干净利落。

　　不过能从繁杂的业务中抽出来写写纯粹的数据结构和算法，有点回到学校的状态，感觉也蛮不错。

　　以前在学校折腾算法的时候，从yyt同学的分享的ppt学到了这个数据结构，印象比较深的是，ppt上说，对于一个长度是 x 的线段，使用数组（元素 i 的左右节点分别是 2*i 和 2*i+1 ）来记录的话，需要大小约为 3*x 的数组，但是在实际做题的时候却发现越界了，后来仔细去挖这个地方，才发现，其实应该是找到一个 y = 2^n 满足 2^(n-1) < x <= 2^n，所需的数组长度为 2y 。

　　这次是先写了一个C++的class（偷懒用的struct），配合一些c-style的函数，让python用ctypes载入使用。然后兴起写了个Python的版本对比，跑了个简单的case，发现性能居然相差200+倍，做了一些改进，才领悟到，对于python来说，其实用数组建树比起直接用对象指针关联建树并没有太大优势，而用对象建树的好处是，如果不是极端情况，可以lazy load左右子树（当然，数组也可以lazy initialization子节点，但不能减少内存占用）。改起来也不难，于是就验证了一下，效果相当好，甚至比C++还快（因为测试case太简单，几乎没有展开子树），此外这种方式节点的数量可以减少到2 * x - 1（但是相应地每个节点需要增加指针）。

　　另外遇到一个问题是迭代，Python的迭代器如果使用Generator语法(yield)，写起来和用起来都特别自然，可是到C++就完全不一样了，形式上想要达到类似的效果比较累，保存和还原现场比较辛苦（不过这个case还好），试着实现了一个版本，但是需要遍历所有的节点感觉不太好，后来还是改成了偷懒的写法（直接生成整个结果集，在结果集上迭代）。

　　最后，不成熟的小代码放在了这里：https://github.com/felix021/mycodes/tree/master/segtree

[update] 到数据集上实际跑了一下，C++版还是跑赢了几倍的速度，这还是没有做lazy init的情况，回头抽空再写个版本验证一下吧~

　　我司CTO和技术总监都是腾讯系的，所以我们一开始就选用腾讯云的服务。他们家的云数据库提供了可视化的运维操作页面和自动备份的能力，降低了DB运维的门槛。同时云数据库还支持高可用架构，对数据的安全性和服务的可靠性更有保障。另外有的云数据库厂商还提供了诸如数据库审计、慢查询分析、数据回档等能力，大大减轻了数据库运维和DBA的工作量。

　　其实我们就没有专门的DBA，都是开发自己上去折腾，通过把数据库的可靠性外包给云端，确实极大地降低了我们的工作量，这一点还是挺爽的。但是在具体的使用过程中，发现还是有些地方不够满意，比如MySQL最高版只有5.6，没法用上5.7.8+新增的JSON字段；建立数据库自带的只读从库门槛较高（要最高版本）；binlog的备份不方便；数据库授权上的坑（没有FILE和SHUTDOWN，不能grant all on *.*）等。

　　记得以前对比过阿里云和UCloud的云主机磁盘IO（那时候腾讯云好像才刚起步呢），这么久过去了，再来比比看，他们的云数据库怎么样。墙内目前就只有这三家还算比较能入眼吧，网易和百度的就先跳过，都没听说谁家在用。另外那个不要脸的X云就算了，期权都能黑下来的公司，估计也活不了多久。

　　这次除了对比性能，顺便再看看价格。

　　在测试开始之前先打个预防针：以下的测试可能比较粗糙，并不是针对实际业务进行的，所以结果仅供参考；而且实际的业务往往并不是以性能为唯一考量标准，公司的一整套业务需要多项云服务的支撑，最基础的主机、数据库、NoSQL、对象存储、负载均衡等服务这几家都比较完善了，但是在增值、附加服务上各有优劣、亮点，实际选型还是应该根据业务特点仔细考量。

性能

　　首先最重要的，是云数据库的读写性能。我在规划实例的配置时，主要考虑下面2点：首先，云数据库要使用SSD硬盘，这样能够保证数据库服务器的IO能够尽量的快。其次，云数据库的内存要尽可能大，这样有尽可能多的数据能够被缓存，提高读写速度。

　　因此我选择的数据库配置如下：硬盘300GB SSD，内存8GB左右。由于每个云平台提供的配置都不相同（腾讯云的内存和磁盘比例是限定的，UCloud的内存没有8G等等），我在三个云平台上分别申请了如下配置的云数据库进行性能测试：



　　由于实际情况下，云数据库一般是通过云服务器进行访问的，因此我在这3个平台分别申请了配置差不多的云主机，在上面运行性能测试。我申请的云主机的操作系统都是64位CentOS 6.5，具体的配置如下：



　　现在比较流行的测试数据库工具是sysbench，为了和实际使用的情况吻合，我对sysbench做了参数上的修改。

　　一般来说，读操作要远远高于写操作，并且有很多操作是需要范围查找和排序的，所以我在测试中提高了读操作的比例，特别是提高了范围查找和排序的比重。

　　同时，对于写操作，稍微提高了update操作的比例。最终运行的测试中，每一个事务的读操作和写操作的比例是6:1左右。为了模拟项目启动之后的场景，我的sysbench测试集的数据量是总共20张表，每张表200万行数据，开启32个线程，并行向DB发送事务请求，共运行30分钟。下面是我观察到的结果：



　　把这个测试结果做成图表是这个结果：



　　这个性能测试结果大大出乎我的意料，虽然UCloud的DB界面看上去和阿里云和腾讯云相比比较朴实，产品介绍中也介绍的相对简单，但是，性能上的优势让我吃惊。说实话，自己测试之前，我没想到UCloud有如此大幅领先的性能。从测试结果分析，UCloud比阿里云高了422%，比腾讯云高了297%。而且，这还是在UCloud云数据库的内存不如其它2家大的情况下的结果（UCloud：6G内存，阿里云和腾讯云：8G内存）。
这个数据让我对UCloud的SSD云数据库性能十分动心，要知道，这个是我没有做过任何调优，开箱即用的配置，完全符合我对于云数据库“快速部署，性能满意”的期望。
 
　　以下是测试结果的截图，从上到下分别是UCloud的UDB，阿里云RDS和腾讯CDB：

UCloud的UDB↓



阿里云RDS↓



腾讯云CDB↓

价格

　　看过了性能之后，我又顺便分析了一下价格，貌似阿里云和UCloud的价格是线性关系的。阿里云根据内存，CPU和磁盘定价，而UCloud根据内存和磁盘定价，CPU免费。腾讯云的配置只有几档，每一档根据内存和磁盘来定价，内存和磁盘的排列是固定的，不是简单的线性关系。因此，我计算出了阿里云和UCloud的价格因素的计算常数，然后以腾讯云的配置为基础，分别推算了3个厂商在同等条件下的价格，可以得到三个厂商的定价趋势图如下：



　　其中，腾讯云的价格是最便宜的，只是磁盘和内存的比例是固定的；UCloud的价格比腾讯云略贵，而阿里云比其它两家要高出40%左右的价钱。这可能是因为阿里云主备架构的关系；不过，我发现UCloud的普通版UDB和高可用版UDB几乎是一个价钱，也就是说，如果考虑主备架构的高可用版云数据库，UCloud的高可用版实例的价格比阿里云要低40%。仔细看了下，貌似UCloud的高可用数据库最近在进行促销，所以才会这么划算，也就是说趁活动期间购买的话可以省一大笔钱。可惜我们用的是腾讯云……

总结

　　阿里云的文档非常全，而且详细。很多信息都可以通过文档来获取。而且它的MySQL在线管理工具很强大，就是建立DB的时候比较麻烦，还是要去界面上申请建立DB，价格较贵。

　　腾讯云虽然没有阿里云的RDS做的那么完善，也还算易用。他们使用PHPMyAdmin来管理数据库，对于熟练这套工具的开发人员可能比较容易上手。价格较便宜。

　　UCloud云数据库测出的TPS和QPS性能远高于业内平均水平。而且产品易用性好，价格适中。

　　综上所述，性价比最高的云数据库是UCloud的UDB。

　　额外再提一句，对于名列在程序员最讨厌两件事之一的“写文档”，在查看3个厂商的DB产品介绍时，感觉阿里云和腾讯云的产品介绍做的很好，里面有各种解决方案的架构，非常贴心。而且云数据库和云主机自建DB的区别也讲得很直观；而UCloud的UDB介绍比较简单，还需要进一步提高。

　　以上。本文仅代表个人观点，如有意见和建议，欢迎探讨。

(懒得看细节的同学直接拉到末尾下载带有shadowsocks的镜像)


TP-Link很久没给我的路由器更新固件了，而且它运行一段时间以后就需要重启才能保证wifi正常，这对于家里有基于Wifi的智能设备来说是不能忍的，所以只能折腾了，上OpenWRT吧。

记得09年的时候折腾路由器，WL520GU，刷上了DD-WRT，然后再交叉编译弄了个锐捷的客户端，这样就可以把校园网分享出来用。心血来潮到珞珈山水去翻了一下，当年发的帖子竟然还在Linux版置顶……

回归正题，1041n的OpenWRT页面在这里： https://wiki.openwrt.org/toh/tp-link/tl-wr1041n

虽然可以从 这里 下载预编译好的镜像，但是不折腾一下感觉不带感，所以参考官方的教程，自定义镜像。

1. 下载 Image Generator

当年玩WL520gu的时候，好辛苦，先得用openwrt的buildroot脚本创建一个交叉编译环境，那个脚本特别不适合中国国情，用wget慢慢下载国外的源……等得我都快崩溃了，于是拉出它的下载连接直接用迅雷下好放进去再启动。现在可好，直接就有现成的环境直接下载，一分钟就搞定了。

具体参考这个页面：https://wiki.openwrt.org/doc/howto/obtain.firmware.generate

正好1041n是ar71xx架构的，照做就好了。

2. 生成image

可惜1041n只有4M的flash，否则我一定把php和python都打进去，这样还能跑起个shadowsocks server。

最后权衡了下，是这么生成的：

    make image PROFILE=TLWR1041 PACKAGES='luci luci-i18n-base-zh-cn luci-i18n-firewall-zh-cn libev libpolarssl curl'

之所以把 libev 也打进去，主要是想之后可以用shadowsocks-libev，但是编译了一下发现可执行文件竟然 1M+，strip以后也还有两三百KB，还是算了。

如果不用curl的话，可以把libpolarssl和curl去掉，不过好像也没什么其他特别有用的了（或者是pptp？）。curl我是用来请求DnsPod的，这样可以及时把家里的IP刷到某个域名上去。

如果没什么错的话，生成的 image 就是这个了：

    bin/ar71xx/openwrt-15.05.1-ar71xx-generic-tl-wr1041n-v2-squashfs-factory.bin

3. 升级配置

tp不校验固件，所以直接通过路由器管理页面升级就行了。

升级了以后  telnet 192.168.1.1 登上去，用 passwd 修改root密码，然后就可以ssh登录，或者访问luci  http://192.168.1.1

image里面带了中文语言包，登录以后可以在 System -> Language 里面修改成简体中文。

配置PPPoE：打开  网络->接口，点击 WAN 接口的修改，看着配就好了。就那么点东西。

剩下的就是瞎折腾了

4. 创建用户

没什么卵用，弄着玩，这样就可以用另一个用户登录路由器，而且还是通过publickey authentication。





==== UPDATE ====


还是花了一个晚上折腾了shadowsocks

1 安装SDK

参考：https://wiki.openwrt.org/doc/howto/obtain.firmware.sdk

下载SDK： https://downloads.openwrt.org/chaos_calmer/15.05.1/ar71xx/generic/OpenWrt-SDK-15.05.1-ar71xx-generic_gcc-4.8-linaro_uClibc-0.9.33.2.Linux-x86_64.tar.bz2

$ tar jxf Openwrt-SDK*

$ mv Openwrt-SDK* sdk

$ cd sdk

2 编译

$ git clone https://github.com/shadowsocks/openwrt-feeds.git package/feeds

$ git clone https://github.com/shadowsocks/shadowsocks-libev.git package/shadowsocks-libev
# 注@20180524，最新版本会出现编译错误，和libsodium貌似不兼容，建议用 v2.4.7

$ make menuconfig #选中 network 下的 shadowsocks-libev-polarssl

$ make package/shadowsocks-libev/compile V=99

编译好的文件位于：./build_dir/target-mips_34kc_uClibc-0.9.33.2/shadowsocks-libev-polarssl/shadowsocks-libev-2.4.7/ipkg-install/usr/bin/

3 腾出空间(回到Image Builder)

对于4M flash的image来说，openwrt给的空间实在太小了，所以只好打起现有package的主意。翻了一下，ipv6似乎占了比较大的空间，考虑到国内确实用不上ipv6，所以就拿它开刀吧。

参考前面 https://wiki.openwrt.org/doc/howto/obtain.firmware.generate 的 Remove useless files from firmware

修改 Makefile，添加 FILES_REMOVE 选项，并在 files_remove 文件中添加：


4 加入shadowsocks

$ mkdir -p files/etc/init.d files/usr/bin

$ cp /path/to/ss-server /path/to/ss-local files/usr/bin

$ cp /path/to/shadowsocks-libev/openwrt/files/shadowsocks.json files/etc/ss-server

$ cp /path/to/shadowsocks-libev/openwrt/files/shadowsocks.init files/etc/init.d/ss-server #修改配置文件路径为 /etc/ss-server，去掉 -b 0.0.0.0

$ cp /path/to/shadowsocks-libev/openwrt/files/shadowsocks.json files/etc/ss-local

$ cp /path/to/shadowsocks-libev/openwrt/files/shadowsocks.init files/etc/init.d/ss-local #修改配置文件路径为 /etc/ss-local

$ chmod +x files/etc/init.d/*

5 重新生成image

make image PROFILE=TLWR1041 PACKAGES='luci luci-i18n-base-zh-cn luci-i18n-firewall-zh-cn libev libpolarssl curl libpthread -kmod-ip6tables -ip6tables -kmod-ipv6 -kmod-nf-ipt6 -luci-proto-ipv6 -libip6tc' FILES=files/ FILES_REMOVE="files_remove"

升级一下新的rom，然后就可以在路由器上启动shadowsocks的server/client了。

在路由器上启动server，配合surge，就变成一个简易VPN了，效果相当赞。


附1：带有shadowsocks的镜像下载地址为 http://pan.baidu.com/s/1bpl9jK7 密码: 7ugp （貌似不加密码很容易失效）

附2：编译好的shadowsocks

# Linux下的文件锁

Linux下有两种不同的文件锁机制，一种是通过 `flock` 系统调用锁定整个文件，另一种是通过 `fcntl` 系统调用完成更细粒度的记录锁（锁定文件中的一个区间）

## open 系统调用

Linux下，在最初打开一个文件的时候，最终都是落到 `open` 这个系统调用上。

open系统调用 (@./fs/open.c) 里头做了很多事情，跟文件锁有关的主要是分配了一个 `struct file` 对象，并且给该对象的 `struct inode *inode` 和 `struct file_operations *f_op` 成员赋值。

其中 inode 是对应文件系统分配的（比如 ext4 文件系统的分配函数是 fs/ext4/inode.c 中的 `ext4_iget`），其中也包含了一个 `struct file_operations *` 类型的成员 `i_fop`，即针对该文件系统文件操作的函数指针集合。

以上提到的两次 `struct file_operations` 对象包含 `flock` 和 `lock` 两个函数指针，分别用于上述的两种不同锁机制。

内核在内存中只会给一个文件分配一个 `struct inode` 对象，不同进程打开同一个文件时，都会单独分配一个 `struct file` 对象，且 `file->inode` 指向该文件的 inode 对象。其中 `file->f_op` 实际上就是在 open 系统调用过程中，从 `inode->i_fop` 拷贝过来的。(open -> do_sys_open -> do_filp_open -> path_openat -> do_last -> vfs_open -> do_dentry_open: `f->f_op = fops_get(inode->i_fop)`)

## flock 加锁

内核首先根据第一个参数 fd 找到内核中的 `struct file` 对象，判断 `file->f_op->flock` 指针是否有效，如果有效（说明是文件系统指定了加锁机制，例如 fs/fuse/file.c 中指定了 `fuse_file_flock` 函数，而ext2/3/4都没有指定），就调用该指针指向的函数来执行加锁操作；如果不存在，则执行`flock_lock_file_wait` -> `flock_lock_inode` （@ fs/locks.c）。

如果文件系统没有指定加锁机制，那么 `flock_lock_inode` 会尝试给该文件对应的 inode 加文件锁（加锁机制比较琐碎，我没看得太细，大致是获取 `inode->i_flctx->flc_lock` 这个spinlock，然后增删改查 `inode->i_flctx->flc_flock` 这个链表，但是可以看出全是内存操作）。

如果文件系统指定了加锁机制，那么就要具体考察对应的加锁机制是否是持久化在磁盘上了；不过从加锁这个需求本身去考察，大多数情况下应当是期望能够快速完成，除了特殊情况，可以认为只是在内存中操作，并没有持久化到磁盘。

## fcntl 加锁

与 `flock` 类似，区别在于判断的函数指针是 `file->f_op->lock` ，如果不存在的话，则调用 `posix_lock_file` 尝试对该 inode 加记录锁，也是在 `inode->i_flctx` 上面倒腾，不过用的是 `inode->i_flctx->flc_lock` 这个链表，具体操作更复杂一些，还要考虑记录锁区间的交叉等问题。

## 结论

具体情况取决于文件系统是否使用了指定的加锁机制，如果有，要单独分析。

如果没有，所有的锁都是在内存中维护的，如果断电，锁自动失效。这样也比较符合通常的理解。

另外，针对文件的加锁行为一般都是进程执行的，进程退出（包括意外退出）时，exit 系统调用会调用 `exit_files` 函数清理该进程打开的所有文件。

Let's Encrypt项目进入Public Beta已经好久拉，不过因为使用dnspod作为域名的解析服务提供商，该项目官方刚开始的时候并不被支持（总是报错），所以拖了好久，今天才终于搞起来。

用起来还真是超简单:

1. 获取证书

$ git clone https://github.com/letsencrypt/letsencrypt
$ cd letsencrypt
$ ./letsencrypt-auto certonly -w /path/to/www-root felix021.com www.felix021.com

没有什么意外的话，获取到的证书就存在 /etc/letsencrypt/live/felix021.com/ 下面

2. 配置nginx

最简单的就是加上三行：

但是比较推荐的做法是增加一个80端口redirect到https的配置：

然后执行 service nginx reload ，就生效了。

p.s. 对于我使用的bo-blog博客系统，还有一个坑，就是需要在blog设置里面将URL路径的http换成https，否则使用相对路径引用的css等静态文件资源还是会引用到http去（这是多么奇葩的一个特性啊...）

3. 定期更新

该项目提供的整数有效期只有90天，似乎短了点，但是实际上因为提供了命令行自动更新的方式，并不会造成多大困然，反而可以缩短因为证书泄漏而导致的风险期（貌似也提供了revoke功能，不过我没尝试）。因此官方宣称证书的有效期未来可能会进一步缩短。

想要renew证书，最直接的方式就是前面的certonly命令带上完整参数再跑一次。官方还提供了一个更简单的"letsencrypt renew"命令，会读取上次的配置来重新获取证书。

基于此可以写一个简单的renew脚本，放到root的crontab里，每个月跑一次就好拉。记得renew完要service nginx reload就好啦。

不知道为什么这么多年都没遇到啥问题，到了钱厂以后接连遇到3种不同的ssh延迟，觉得有必要记一下了：

1. GSSAPIAuthentication

ssh -vv someserver 可以看到如下类似字样的：


在 ~/.ssh/config（也可以是 /etc/ssh/ssh_config）加上

2. AddressFamily

ssh -vv 在这里卡住的：

加上

3. UseDNS

在server端卡住的（忘了log是啥了），在server的 /etc/ssh/sshd_config 加上



ssh的坑真多，感觉应该抽空整理一个全集，包括之前记录过的 ServerAliveCountMax/ClientAliveCountMax，还有诸如GatewayPorts之类的。

参考：
Fixing SSH login long delay
debug2: ssh_connect: needpriv 0 stuck - Fix.

== 卸载OneDrive ==

C:\windows\syswow64\onedrivesetup.exe /uninstall



== 卸载 Cortana ==



== 禁用Win+S ==



== 从“此电脑”删除垃圾链接（图片、视频等） ==



== 禁用锁屏界面 ==

组策略-》计算机配置-》管理模版-》控制面板-》个性化-》不显示锁屏

p.s. 周年更新以后这个方法失效了，得这么用：

本地安全策略 -> 软件限制策略 -> 新建路径规则， 路径填写“C:\Windows\SystemApps\Microsoft.LockApp_cw5n1h2txyewy”，安全级别“不允许”

== 禁止自动更新 ==

不让我设置禁止自动重启，那只好禁止自动更新了。

services.msc -> windows update -> 禁止

== windows图片查看器 ==



== 图片查看器背景色发黄 ==

显示设置->高级显示设置->显示适配器属性->颜色管理

设备：选择显示器，勾上“使用我对此设备的设置”，“添加(A)..."，选择 “sRGB IEC61966-2.1”，"设置为默认配置"

== 垃圾APP ==

有些右键就卸载掉了（但实际上文件还在），这样删比较干净点。

打开Powershell执行：

Get-AppxPackage -name Microsoft.ZuneMusic | remove-appxpackage
Get-AppxPackage -name Microsoft.XboxApp | remove-appxpackage
Get-AppxPackage -name Microsoft.WindowsMaps | remove-appxpackage
Get-AppxPackage -name Microsoft.BingWeather | remove-appxpackage
Get-AppxPackage -name Microsoft.ZuneVideo | remove-appxpackage
Get-AppxPackage -name Microsoft.BingSports | remove-appxpackage
Get-AppxPackage -name Microsoft.3DBuilder | remove-appxpackage


p.s. 打包下载

好早以前看到过这个项目，不过当时没有测试成功，昨天晚上看了一下，有点眉目了，先记录一点东西。

1. 项目主页：http://usbip.sourceforge.net/ ，但是这里实际上已经没有再维护了，内核模块已经merge到linux kernel（drivers/usb/usbip）。这里有提供经过ReactOS（这个神奇的项目）签名的windows驱动程序（windows下只有client，没有server），但是不知道四年过去了还能不能用……

2. ubuntu默认安装没有相关模块，需要安装 linux-image-extras ，然后 cd /lib/modules/[KERNEL_VER]/kernel/drivers/usb/usbip && sudo insmod *.ko

3. ubuntu源里的usbip包已经是很老的版本，无法利用新的内核模块，会提示“usbipd requires usbip_common_mod.ko and usbip.ko kernel modules”，实际上userspace tool也已经挪到kernel source里了，位于 linux-source/tools/usb/usbip，编译方法可参考该目录下的README文件，类似于：

但是我是直接下载的kernel source，没有安装在系统目录，所以在编译的时候会提示 libsrc/usbip_common.h 找不到 linux/usbip.h ，解决方法很简单，把那一行改为 #include "usbip.h" ，然后把 linux-source/include/uapi/linux/usbip.h 复制到 libsrc 目录，再编译就行了（对，就是这么粗暴简单）。

4. update@2015-12-25：在linux下测试成功。windows的driver废弃太久，已经不能支持新版代码的协议了。

p.s. 还有一个收费的商业项目 usb-over-ethernet ，有free trial版本，但是没尝试过。
p.s. 2. 还有一个开源的项目SPICE，有一个 usbredir 模块 http://www.spice-space.org/page/UsbRedir ，不过好像还不完善。