(译)redis核心数据结构的典型用法

10 Jan 2020 | |

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

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
Read More

(转)可扩展服务设计原则checklist

01 Jan 2020 | |

转自 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 可以在需要的时候，输出更详细的日志帮助排问题。
  • 所有发现的错误都要及时处理，如果有错误但是没有处理手段，那这个错误就可能会被长期忽略，最终导致灾难发生
  • 快速定位线上问题
  • 能否镜像一个线上的系统，在镜像系统调试问题

优雅的降级与准入机制

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

客户沟通计划

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

客户自助

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

2019工作体验简单总结

31 Dec 2019 |

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

坑与被坑

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

沟通

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

喷与被喷

  • 定位问题

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

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

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

  • 还是敲定一个方案

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

  • 修问题

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

roaring bitmap aka RBM

04 Dec 2019 | |

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

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

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

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

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

image-20201214204833017

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
Read More

整数划分

29 Nov 2019 | |

我不怎么做算法题，今天才碰到整数划分，结果还是个经典递归/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

netstat -na awk ‘/^tcp/ {++S[$NF]} END {for(a in S) print a, S[a]}’

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++输入模板

Read More

招人啦

10 Oct 2019

老东家，对我挺好，早知道当初留在那边了，宁做鸡头不做凤尾，平台优势不是你个人优势

Read More

relocation error version GLIBC_PRIVATE not defined in file

24 Sep 2019 | |

拷贝库到某某目录，执行

 export LD_LIBRARY_PATH=$PWD:$LD_LIBRARY_PATH

导入，遇到了一堆类似的错误。做个记录。以后弄清楚

ref

  1. https://lists.debian.org/debian-glibc/2016/03/msg00153.html
  2. https://askubuntu.com/questions/831592/glibc-private-not-defined-in-file-libc-so-6 貌似是resolv库拷贝引发的不兼容
  3. https://unix.stackexchange.com/questions/367597/almost-no-commands-working-relocation-error-symbol-getrlimit-version-glibc 解决办法，unset LD_LIBRARY_PATH，没说具体原因
  4. 打开vim提示错误vim: : ATUSHHH-! : Error 43692576的罪魁祸首 https://stackoverflow.com/questions/31155824/dlopen-in-libc-and-libdl
Read More

__FILE__路径显示过长

23 Sep 2019 | |

有运行时解决办法，把 __FILE__结果裁剪一下，太弱智了

#define __FILENAME__ (strrchr(__FILE__, '/') ? strrchr(__FILE__, '/') + 1 : __FILE__)

见参考链接，居然还采纳了你敢信？？

正确的编译期做法是第二个答案

如果是cmake

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D__FILENAME__='\"$(subst  ${CMAKE_SOURCE_DIR}/,,$(abspath $<))\"'")

另外@houjw-hx 提到notdir，更清爽，在此补充表示感谢

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -D__FILENAME__='"$(notdir $<)"'")

确实简单一些。不太了解cmake这些小接口，我都是搜到能对付用的就直接用了。。

如果是makefile

CXX_FLAGS+=-D__FILENAME__='\"$(subst $(SOURCE_PREFIX)/,,$(abspath $<))\"'"

然后把__FILE__替换成__FILENAME__或者把上面的__FILENAME__替换成__FILE__

可能会有告警，但是无关紧要

但是如果设置了-Werror可能会编译不过，需要设定-Wno-builtin-macro-redefined

cmake

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-builtin-macro-redefined")

不然会有<command line>:41:9: error: redefining builtin macro [-Werror,-Wbuiltin-macro-redefined] 编译错误

ref

  1. https://stackoverflow.com/questions/8487986/file-macro-shows-full-path/16658858# 第一个答案是运行时裁剪，第二个答案更好。
  2. https://public.kitware.com/pipermail/cmake/2013-January/053117.html cmake做法
  3. https://blog.csdn.net/huojianying123456/article/details/70176755 makefile做法
  4. https://blog.csdn.net/yindongjie1221/article/details/90614261 这个写了一大堆，太复杂了。没用
  5. https://stackoverflow.com/questions/53182242/how-to-override-the-value-of-time-and-date-macros-using-command-line-opt 告警处理方法
Read More
wanghenshui
王很水
majar buzz kill
^