翻译整理自 https://bduvenhage.me/performance/2019/04/22/size-of-hash-table.html

其实文章写得通俗易懂没必要翻译。感谢原作者的分享

1. std::unoredered_set的实现

std::unorederd_set 是hash set实现的，这个容器通过桶 bucket来维护元素，当插入一个元素，先计算hash计算出桶索引bucket index，然后元素加入到桶中。桶典型由链表来维护

unoredered_set会记录每个桶的负载因子(load factor) 也就是平均每个桶放几个元素，默认是1，如果负载因子超过了默认值，那就需要扩容2倍，即让负载因子降低成原来的一半。负载因子低，每个桶的元素少，这样桶的链表就短，维护链表的开销旧地。

2. 堆分配表现

测试数据条件

32位无符号整形，插入2000万数据，代码见参考链接，编译使用clang10 O3 (xcode release)

上图，每次大幅度跳跃都是 调整负载因子的场景。作者想用valgrind massif工具来分析 std::unordered_set的内存占用，但是valgrind不支持macos，所以作者写了个alloctor来调用默认的alloctor，只是记录次数

上图，随机插入数据，每次负载因子达到上限，都会重新调整桶数量，使负载因子降低到上限的一半

增加桶的个数需要重新分配内存，调整元素的位置，上图展示了每次重整耗费的时间

保存两千万个32位无符号数据需要657M内存，细节如下

每个桶的元素结构基本上是这样的

struct BucketItem
{
    size_t hash_;
    uint32_t item_; 
    //4 bytes of padding lay here.
    BucketItem *next_;
};

数据size=24为什么两个数据是相等的？

3. 总结 && 参考链接

博客地址 https://bduvenhage.me/performance/2019/04/22/size-of-hash-table.html

作者的代码 https://github.com/bduvenhage/Bits-O-Cpp/blob/master/containers/main_hash_table.cpp

主要是依靠modern-package-template这个工具。非常方便，推荐给大家

按照readme一步一步来就可以了

以我这个包 https://github.com/wanghenshui/fake_redis_command为例子

首先安装

pip install modern-package-template

然后创建一个包项目

paster create -t modern_package helloworld

然后项目就搞好了，按照生成文件夹里的hacking一步一步搞就行了，当然最后

python setup.py install

就可以安装了。后面还有上传到pip仓库的操作。很简单，但是我网络不行传不上去。

要注意的只有setup.py文件的写法

目录结构不重要，重要的是setup.py文件要写好

以我的包为例，目录结构是

fake_redis_command/
├── HACKING.txt
├── MANIFEST.in
├── NEWS.txt
├── README.rst
├── bootstrap.py
├── build
├── dist
│   ├── fake_redis_command-0.1-py3.6.egg
│   └── fake_redis_command-0.1.tar.gz
├── examples
│   └── random_command.py
├── setup.py
└── src
    ├── fake_redis_command
    │   └── `__init__`.py
    └── fake_redis_command.egg-info
        ├── PKG-INFO
        ├── SOURCES.txt
        ├── dependency_links.txt
        ├── entry_points.txt
        ├── not-zip-safe
        ├── requires.txt
        └── top_level.txt

大部分都是和包不相关的，主要setup.py文件要写对，比如我的文件只有src/fake_redis_command/下一个文件，还是__init__.py文件，所以setup.py文件里写的

    packages=find_packages('src'),
    package_dir = {'': 'src'},include_package_data=True,

使用就可以直接用

from fake_redis_command import redis_command

因为我的redis_command实现在__init__.py文件, 最简单。但是项目复杂一些，不可能放在同一个文件，来看看redis-py的setup.py文件 https://github.com/andymccurdy/redis-py/blob/master/setup.py

packages=['redis'],

redis的目录也很简单，就一层redis目录，没有我那层src嵌套（模板生成的我也不想）

写的很简单，说明其他定义在redis目录下的__init__.py文件里，但是目录下有很多文件，那肯定就是只导出了。

再看https://github.com/andymccurdy/redis-py/blob/master/redis/init.py

果不其然，把所有的类和异常都暴露出来了。这样import redis就能直接用了。

说的十分粗糙，但是临时用一下造一个粗糙的轮子包够用了。

这是翻译整理

一张图概括改动点

Scan Resistant Cache

这个概念我不知道怎么翻译，总之就是一个能够抗住Scan动作污染的cache

yugabytedb针对rocksdb lru cache的缺陷，做了个优化 https://github.com/YugaByte/yugabyte-db/commit/0c6a3f018ac90724ac1106ff248c051afbdd6979

作者也说了，这个实现和mysql/hbase类似，是2Q

我的疑问

• 为啥rocksdb不加上？找到了一个commit，没看出来加在哪里了 https://github.com/facebook/rocksdb/commit/6e78fe3c8d35fa1c0836af4501e0f272bc363bab
• 实现Scan Resistant cache需要做什么？2Q ARC都是怎么抵消影响的？

Block-based Splitting of Bloom/Index Data

rocksdb的sst文件包含元数据，比如index和bloom filter。作者观点这个数据是没有必要的，可以砍掉了，毕竟都在内存里 修改在这里https://github.com/YugaByte/yugabyte-db/commit/147312863b104d2d4b2f267cbb6b4fc95f35f3a8

Multiple Instances of RocksDB Per Node

多rocksdb实例。这个很常见，作者列出来几个设计优势

• 集群节点的负载均衡 节点failover 添加节点都变的非常简单，可以直接搬迁sst文件。
• 删掉表直接删掉rocksdb实例
• 可以对一个表做不同的存储策略，压缩开关？压缩算法自定义？编码自定义（前缀etc）
• 可以对一个表做不通的布隆过滤侧率，不同主键，不同桶数etc
• 。。。还有一个和yogabyte db业务相关，没看懂，没翻译 Allows DocDB to track min/max values for each clustered column in the primary key of a table (another enhancement to RocksDB) and store that in the corresponding SSTable file as metadata. This enables YugabyteDB to optimize range predicate queries like by minimizing the number of SSTable files that need to be looked up:

但是这种用法工程实践上的坑需要注意

全局block cache

writebuffer memtable wal大小限制

过大重启重放日志会很痛苦，这里yugabyte db做了改进，尽可能的刷数据 https://github.com/YugaByte/yugabyte-db/commit/faed8f0cd55e25f2e72c39fffa72c27c5f84fca3

针对不同规模的compaction做分类，不同的队列来做

改进在这里https://github.com/YugaByte/yugabyte-db/commit/dde2ecd5ddf4b01879e32f033e0a80e37e18341a

• 事实上有观点认为应该把linux调度算法搬到这里。rocksdb的compaction策略粗糙，而两个队列算是个粗糙调度

Smart Load Balancing Across Multiple Disks 这个没看懂

DocDB supports a just-a-bunch-of-disks (JBOD) setup of multiple SSDs and doesn’t require a hardware or software RAID. The RocksDB instances for various tablets are balanced across the available SSDs uniformly, on a per-table basis to ensure that each SSD has a similar number of tablets from each table and is taking uniform type of load. Other types of load balancing in DocDB are also done on a per-table basis, be it:

• Balancing of tablet replicas across nodes
• Balancing of leader/followers of Raft groups across nodes
• Balancing of Raft logs across SSDs on a node

附加改动

用raft替代rocksdb的wal

mvcc

用的混合逻辑时钟

Hybrid Logical Clock (HLC), the hybrid timestamp assignment algorithm, is a way to assign timestamps in a distributed system such that every pair of “causally connected” events results in an increase of the timestamp value. Please refer to these reports (#1 or #2) for more details.

参考

• 原文 https://blog.yugabyte.com/enhancing-rocksdb-for-speed-scale/
• 这个是arc介绍，效果优于lru http://hcoona.github.io/Paper-Note/arc-one-up-on-lru/
  • 论文原文https://www.usenix.org/conference/fast-03/arc-self-tuning-low-overhead-replacement-cache
  • 据说zfs也用。
• 搜到的一个issue，建议kudu替换他们的cache系统，换成arc或者hbase 2Q，https://issues.apache.org/jira/browse/KUDU-613
• scan resistant cache貌似是个热点问题？搜关键字蹦出好几个论文。不列举了。
• 这里有个2Q的介绍 https://flak.tedunangst.com/post/2Q-buffer-cache-algorithm 值得翻译一下

本文是参考链接的简单总结。概述没有翻译

Strings

主要使用场景

• Session cache 许多网站使用redis Strings来创建session cache，保存html或者网页来加速网站体验。这种数据基本都在内存中，使用redis再好不过，还有类似购物车的数据，临时缓存。
• 队列 处理流量，消息，数据收集，任务管理，数据分发，使用redis 队列（https://www.infoworld.com/article/3230455/how-to-use-redis-for-real-time-metering-applications.html） 可以更好的管理
• 数据采集

Redis Lists

主要使用场景

• 社交网站信息流推送，时间线推送，主页信息推送。
• Rss feeds。和上面一样
• leaderboards

Redis Sets

• 分析商业数据，集合操作。比如统计销量等等
• Ip 流量访问统计
• 文本过滤，关键字屏蔽

Redis Sorted Sets

• QA平台 答案权重排序
• 游戏积分排行榜 https://www.ionos.com/community/hosting/redis/how-to-implement-a-simple-redis-leaderboard/
• 任务调度服务 https://medium.com/@ApsOps/migrating-redis-sorted-sets-without-losing-data-f9e85f6549c5
• redis geo也是zset实现的

Redis Hashes

• 用户档案信息。字段保存
• 用户发帖保存 https://instagram-engineering.com/storing-hundreds-of-millions-of-simple-key-value-pairs-in-redis-1091ae80f74c
• 多租户数据 https://divinglaravel.com/introduction-to-redis-hashes

上面的网址都没看。值得逐个看一眼放到这个帖子里

参考链接

• http://highscalability.com/blog/2019/9/3/top-redis-use-cases-by-core-data-structure-types.html

转自 http://sunisdown.me/ke-kuo-zhan-fu-wu-she-ji-yuan-ze-checklist.html

考虑一下

基本原则

• Expect failures 硬盘可能会坏，网络会不稳定，系统设计的时候是不是能够优雅的处理各种异常？
• Keep things simple 复杂会导致更多的问题，简单的系统更容易正确的运行。去掉不必要的依赖等
• Automate everything 使人都会犯错，把所有能够自动化的都自动化。

整体设计

• 发生故障的时候，系统能否在没有人工干预的情况下自动恢复
• 故障恢复的路径需要经常被测试
• 把各个不同的组件都文档化，而不是每次了解某一个部分都需要看代码
• 是否只提供一个版本给用户（单一版本迭代成本更低
• 多租户，是否需要在没有物理隔离的情况下提供多租户功能
• health check 是否实现了自动且快速的故障检测
• 当你依赖的系统有问题的时候，能否服务降级
• 相同那个的功能，只需要在一个应用里面实现，没有必要实现多次，会增加维护成本。
• 服务需要能够单独运行，而不是必须要依赖于某个其他的服务才可以正常运行。
• 针对少数需要人工干预的情况，需要准备好文档，脚本，测试方案等。
• 保持系统简单的架构，如果是为了优化性能而增加复杂度，则需要这个性能上的改进超过一个数量级，只有几个百分点的改进不值得增加系统复杂成都。
• 所有层级的入口都应该有准入机制，比如 rate limit，防止量过大导致服务不可用
• 能否拆分服务，拆分的是否合理
• 分布式环境下，我们是否了解里面的网络拓扑，这个是否找网络方面专家 review 过
• 是否分析过吞吐量与延迟，是否有对应的扩容方案
• 对于这个服务给数据库/数据服务带来的流量是否有一个明确的理解，是否验证过。
• 是否所有的系统，都是在同一套工具链下完成的，比如相同的 code review，测试环境等
• 版本化，保留之前的版本，测试用例，万一需要回滚呢
• 单点故障是不可接受的

自动化管理

• 所有的服务都需要支持重启
• 所有持久化的数据都需要备份
• 设计上需要支持跨数据中心部署（如果设计是不做，后面要实现就会比较麻烦）
• 部署/配置自动化
• 配置与代码需要一起交付，不要 version A的代码用了 version B 的配置。
• 线上的更改，需要有记录，what，when，whom，which servers ，定时扫描线上版本，以免出现不一致的情况。
• 按照角色来来管理服务，而不是面向服务来管理。
• 系统出现多种故障的时候，服务是否能够正常工作
• 重要的数据不要依赖于本地存储，很容易丢数据。
• 部署过程是否简单？
• chaos monkey 是个好东西

依赖管理

• 能否容忍 latency 比较高的情况
• 服务调用是否有超时机制
• 超时重试是否有限制次数
• 是否有CB 机制
• 是否有快速失败机制
• 依赖的组件是否可靠，验证过？
• 跨服务的监控告警有吗
• 依赖双方要有一直的设计目标
• 模块解耦，依赖的组件挂了，也要能够服务（服务降级）

发布周期与测试

• 是否频繁发布，发布频繁可以减少出错的机会，发布周期太长是很危险的（3个月）
• 是否对用户体验定义了标准，是否有测试这些标准
• 能否回滚到某一个指定版本
• 可以在单节点上部署测试嘛？
• 有压测嘛
• 新版本发布之前的测试（性能，吞吐量，latency）
• 可以使用 production 来测试嘛
• 是否有跟生成环境完全一直的环境，并用相同的数据进行大规模测试
• 有监控系统吗
• 监控系统能明显的看出系统的各种重要指标嘛
• 能否减少误报

硬件选择与标准化

这个老哥在论文里面教了怎么购买硬件，怎么搞机柜。Google 有一本更专业的书来说这个事儿，这里不总结了。

运维与容量规划。

• devops, 谁开发，谁治理。
• 只做软删除，要能够恢复被误删的数据
• 跟踪资源分配
• 一次只做一项更改（排查问题是，一次只对应用做一次更改，方便溯源问题）
• 配置一切，如果可以通过更新配置来完成，而不是更改代码，这样会方便很多

审计，监控与告警

• 监控一切
• 统计有问题但是没有告警的情况，把这个比例降低到0
• 分析数据，理解那些是正常的行为，避免误报。
• 数据是最有价值的资源，帮助我们追溯问题。
• 日志 Level是否可以配置，而不是重启，可配置的日志 Level 可以在需要的时候，输出更详细的日志帮助排问题。
• 所有发现的错误都要及时处理，如果有错误但是没有处理手段，那这个错误就可能会被长期忽略，最终导致灾难发生
• 快速定位线上问题
• 能否镜像一个线上的系统，在镜像系统调试问题

优雅的降级与准入机制

• 是否有 红按钮 机制，支持拒绝不重要的请求
• 准入控制，拒绝部分请求
• 渐入式准入控制，慢慢放开流量，以便系统能够优化恢复

客户沟通计划

• 针对大规模系统不可用，数据丢失或损坏，安全漏洞等，是否制定了沟通计划，想之前腾讯云那种情况，就是缺乏沟通导致的

客户自助

• 客户自行配置可以降低成本，并提高满意度，支持客户自助也相对重要。

也是以后的工作总结与更新

坑与被坑

• 不要说别人做没做到，问你自己做没做到。很容易挖坑
• 合入主动问还缺什么。自己充分验证要留下证据。不要自己合入，自己觉得没问题，但是经不起推敲
• 实际上Pull Request模板能做到上面的覆盖，但是实际上并不是人人都遵守 or 模板要求不全面，导致各种没对齐，当前项目的用例门禁是不全面的。这本来是流水线/门禁的工作，但实际上推到了实际开发的人身上。本质还是没有充分验证。
• 推动别人review，没办法。都忙
• 自己的写法上面不理解不接受怎么办？上面还觉得自己设计的挺好怎么办？
  • 如果自己没有新方案写不出更好的，捏着鼻子忍着
  • 自己写的自认为比原来的好但是不接受 -> 捏着鼻子忍着 or 离职
• pr信息写全面，简单总结改了啥，没人看你补充的用例。把reviewer当智障
• 验证是对自己负责。
• 确认问题是否解决要自己验证一下，不要信别人，不然自己背锅
• 写代码有点追求。别指望别人给你review，事实上根本review功能就是废的，没人真的细看，用例补充是对自己负责，因为别人没义务负责，顶多挑挑格式问题
• 接上条，如果之前代码没写好，大家也没review，后面大概率会被鞭尸。躺平任嘲，记住，写好代码的义务在于自己，不要指望别人真能指出问题
• 完备性，就是边角的用例场景，这种填坑的活真不愿意干。尽量想到吧，想不到没办法。
• 还是代码，对代码可能有错误理解。这个理解一定要反复确认。
• 还是代码。注释文档要齐全。补齐。越齐全越好。自己动过那个功能，没有文档，就把功能的文档补齐。
• 结对编程初衷是好的，但实际上没人真的结对了。大家不过是共同填坑。
• 效率。定好时间线，早点做完再划水，代码真的没多少，想法时间 > 写代码时间 > 划水时间
• 对接，坦然面对别人不鸟你。自己热情别减。都是工作。做好记录反馈就好了。保留证据。
• 还是对接，推不动别人让领导推动。人微言轻啊胖友。

沟通

• 邮件说清楚，做了什么，做了多少，做到了什么程度，不要图省事儿
• 打字说问题，完整说清楚，上下文别省略

喷与被喷

• 定位问题

  • 给上下文相关的信息，简要概述
  • 给自己的简单结论和证据,（现象，日志，回报结果等）给个别误导他人的简单思路，或者跪求帮忙别说话
  • 给他人定位所需的基本信息，别扔一句话跑了等人家反馈

• 敲定一个默认值，敲定一个方案

  • 验证过是最佳的值了吗？问过别人意见没
  • 是不是需要和其他服务搭配调整？
    • 牵一发动全身的配置改动有没有配套的校验工具？你能不能提供一个？
  • 想不到就是你遗漏，你遗漏就可能会挨喷。想的越仔细越好

• 还是敲定一个方案

  • 问过别人意见没？确认过了吗，虽然这是你的小小代码，但还是很容易写出垃圾设计

• 修问题

  • 能从根源搞定，不要用规避方案

缕清几个概念，水一个博客

Ref

• https://stackoverflow.com/questions/212466/what-is-a-bus-error
• https://stackoverflow.com/questions/14897157/what-does-corrupted-double-linked-list-mean

首先，redis的bitmap占用空间是很恐怖的，512M，就算用的很少也是512M

但是使用概率型数据结构，比如hyperloglog，省空间，但是有误差，且只能增不能删

又想要大量标记，又不想有误差，又不想占用大空间，解决方案 roaring bitmap

对稀疏位图进行压缩，减少内存占用并提高效率。比较有代表性的有WAH、EWAH、Concise，以及RoaringBitmap。前三种算法都是基于行程长度编码（Run-length encoding, RLE）做压缩的，而RoaringBitmap算是它们的改进

1. 支持动态修改位图（静态的位图有其它压缩方式）
2. 利用SIMD加速位图操作

32位无符号整数按照高16位分桶，即最多可能有216=65536个桶，论文内称为container。存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中。也就是说，一个RBM就是很多container的集合

• 第一层称之为Chunk，每个Chunk表示该区间取值范围的base(n2^16, 0<= n < 2^16)，如果该取值范围内没有数据则Chunk不会创建
• 第二层称之为Container，会依据数据分布进行创建（Container内的值实际是区间内的offset）

ArrayContainer

当桶内数据的基数不大于4096时，会采用它来存储，其本质上是一个unsigned short类型的有序数组。数组初始长度为4，随着数据的增多会自动扩容（但最大长度就是4096）。另外还维护有一个计数器，用来实时记录基数。

• 当区间内数量少于4096时，数组占用更紧凑；多于4096，则使用位图更经济

BitmapContainer

当桶内数据的基数大于4096时，会采用它来存储，其本质就是上一节讲过的普通位图，用长度固定为1024的unsigned long型数组表示，亦即位图的大小固定为216位（8KB）。它同样有一个计数器。

上图中的第三个container基数远远大于4096，所以要用BitmapContainer存储。

RunContainer

RunContainer在图中并未示出，初始的RBM实现中也没有它，而是在本节开头的第二篇论文中新加入的。它使用可变长度的unsigned short数组存储用行程长度编码（RLE）压缩后的数据。

AAAAAAbbbXXXXXt
6A3b5X1t

由此可见，RunContainer的压缩效果可好可坏。考虑极端情况：如果所有数据都是连续的，那么最终只需要4字节；如果所有数据都不连续（比如全是奇数或全是偶数），那么不仅不会压缩，还会膨胀成原来的两倍大。所以，RBM引入RunContainer是作为其他两种container的折衷方案。

O(logn)的查找性能：

• 首先二分查找key值的高16位是否在分片（chunk）中
• 如果分片存在，则查找分片对应的Container是否存
• • 如果Bitmap Container，查找性能是O(1)
  • 其它两种Container，需要进行二分查找

参考链接

• 论文地址 https://arxiv.org/pdf/1603.06549.pdf
• 官网 http://roaringbitmap.org/，有各种实现 c实现 https://github.com/RoaringBitmap/CRoaring
• redis的bitmap不是这个方案，社区实现了一个module https://github.com/aviggiano/redis-roaring，直接搬croaring
• 图来自 https://blog.bcmeng.com/post/doris-bitmap.html 这篇介绍，doris了解一下，doris和clickhouse啥区别？
  • https://github.com/apache/incubator-doris
  • 他这篇hbase rowkey设计也不错，基本覆盖了书里介绍的内容 https://blog.bcmeng.com/post/hbase-rowkey.html
• 本文内容整理自 https://zhuanlan.zhihu.com/p/39828878和https://www.jianshu.com/p/818ac4e90daf
• sigmod2021有一个新的设计 Tree-Encoded Bitmaps http://db.in.tum.de/~lang/papers/tebs.pdf 值得研究一下，这里留个坑 TODO

我不怎么做算法题，今天才碰到整数划分，结果还是个经典递归/dp题目

参考链接给的是递归解法。

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return equationCount(n,n);
    else if(n==m)
        return 1+equationCount(n,n-1);
    else
        return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
    {
        printf("%d\n",equationCount(n,n));
    }
    return 0;
}

递归和DP是一体两面，比如台阶dp

l = []
l.append(0)
l.append(1)
l.append(2)
n=int(input())
for i in range(3,n+1):
    l.append(l[i-1]+l[i-2])

print(l[n])

判断进程

lsof

netstat -tcp closewait

ref

• https://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html

• https://www.zhihu.com/question/56577396 这个问题讲了整数划分的背景

• https://blog.csdn.net/dst111188/article/details/78554698 递归和DP的关系，空间换时间。核心的转换公式都是一样的。

• http://blackblog.tech/2018/08/24/LeetCodeReview6/ 列了一些leetcode上的DP题目的解法。很有心了

• https://blog.csdn.net/sxhelijian/article/details/8978794

• https://blog.csdn.net/sxhelijian/article/details/8978850 上面这两个链接是c/c++输入模板