Posts

一个基于共享内存，多线程多进程并发安全，key value 变长 的 LRU 缓存。 内部基于 TLSF 内存分配器, 和 LevelDB 的 LRUCache 代码实现 # 一，介绍 # 一个基于共享内存，多线程多进程并发安全，key value 变长 的 LRU 缓存。 内部基于 TLSF 内存分配器, 和 LevelDB 的 LRUCache 代码

1. 背景 # 后台开发很常见一大类需求是 线程安全 高性能 容器数据结构 开源的 https://github.com/greg7mdp/parallel-hashmap parallel-hashmap 是对 Google 的 abseil-cpp 库的改进，可供开发中直接使用。

1. IR-book 经典教材中的思路 # Faster postings list intersection via skip pointers 通过跳指针，实现更快的 posting list 求交 https://nlp.stanford.edu/IR-book/html/htmledition/faster-postings-list-intersection-via-skip-pointers-1.html

一，问题背景 # 多进程之间需要传输大量数据的时候，比如多进程 RPC 框架的进程之间通信，常用共享内存队列。 但是共享内存队列难免会有 入队+出队 2次 memcpy 。 而且要变长共享内存队列，如果支持多生产者进程+多消费者进程 ，就要处理线程安全方面的问题， 比较麻烦。 process_vm_readv() , process_vm_writev() 是 Linux 3.2 新增的 syscall，用于在多个进程的地址空间之间，高效传输大块数据。 https://www.man7.org/linux/man-pages/man2/process_vm_readv.2.html https://github.com/open-mpi/ompi/blob/master/opal/mca/btl/sm/btl_sm_get.c#L96 在此， 我提个设想，可以用 process_vm_readv 实现一个多进程内存队列，相比之下，优势是： 在处理 多线程/多进程 并发时，更简单 省掉一次 memcpy。 下面 demo 代码演示了这个思路。 为了方便，直接用 posix mq 来传输 iovec 数组，也没有考虑多路复用。 真实项目可能需要 eventfd 之内的机制来做 notify。 实测了下，3个进程加起来有 5.5 GB/秒 的速度。

一，介绍 # 比赛题目很简单：构造一个程序，在 stdout 上打印出自身的 MD5，程序越短越好。按最终程序文件大小字节数排名，文件越小，排名越靠前。 只能使用 ld-linux-x86-64.so, libc.so, libdl.so, libgcc_s.so, libm.so, libstdc++.so 。 禁止了 socket, shmget, fork, execvc 等 syscall 。 汇编高手如云，本人只做到 752 字节，只拿到 27 名。 但忙活好几天，学到不少东西，也有苦劳，还是值得记录一下。 基本是纯 C 实现，没有动用汇编。

1. 问题 # 一个 C++ 程序，如果 throw 了 exception ，但是又没有 catch，那么一般会产生 coredump， 问题是，在 gcc 4.x 版本产生的 coredump 文件中，没有 throw 时候的堆栈信息，导致不知道是哪里 throw 的，没法查问题。 原因是 gcc 4.x 的 /libstdc++-v3/src/c++11/thread.cc:92 里面有个 catch(…)，所以 stack unwind 了，就没了 throw 时候的 stack 。 void * execute_native_thread_routine(){ try { ... }catch(...){ std::terminate(); } } https://abcdabcd987.com/libstdc++-bug/ 一个解决办法是可以升级 GCC 7 ，或者可以用更简单的办法：

一，背景介绍 # ElasticSearch 是由 Lucene 包装上分布式复制一致性算法等附加功能，构成的开源搜索引擎系统。 近两年在业界热度大增，主要有 3 种应用场景： 全文搜索引擎 NOSQL 数据库 日志分析数据库 ELK 很多垂直领域搜索需求，都可以基于 ElasticSearch 来设计架构。 ElasticSearch 能大幅度提升相关业务的迭代开发速度，实现类似 sql 数据库增删改查一样的快速开发。 并在相对高 qps 的在线业务中，保证毫秒级的延迟，提供极高的可用性和稳定性。 经过持续的研读官方文档，调研业界经验，并在实践中应用反思后，总结出一套架构方案。供参考，欢迎意见建议。

一，问题背景 # 很多时候，我们需要确保进程只有一个实例运行。 有几种方法： http://stackoverflow.com/questions/2964391/preventing-multiple-process-instances-on-linux http://stackoverflow.com/questions/5339200/how-to-create-a-single-instance-application-in-c-or-c https://github.com/qtproject/qt-solutions/tree/master/qtsingleapplication/src 比较常规的做法，是对一个文件加文件锁 flock，比如对 pid 文件 flock( LOCK_EX|LOCK_NB ) 但是这种方法有些弊端： 如果文件被 mv 或者 rm，是会被绕过的。 如果磁盘故障比如磁盘满，目录没有写权限，会失败。 二，abstract namespace unix socket # http://linux.die.net/man/7/unix unix socket 有3种： 基于文件的 socketpair 创建的，匿名的 abstract namespace 的，Linux特有 Linux 下， AF_UNIX socket 支持一种特殊的 abstract namespace unix socket 。 相比 普通的基于文件系统的 unix socket，abstract namespace unix socket ： 没有磁盘文件 进程挂了以后自动删除，无残留文件 无需担心与 文件系统上的文件冲突，不需要关心文件系统上的绝对路径是否存在的问题

可以对抗输入数据模式的排序算法。 quick sort 在输入数据接近有序的情况下，效率不高。 Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns. pdqsort is an extension and improvement of David Mussers introsort. All code is available for free under the zlib license.

一，问题背景 # 随着深度学习的广泛应用，在搜索引擎/推荐系统/机器视觉等业务系统中，越来越多的深度学习模型部署到线上服务。 机器学习模型在离线训练时，一般要将输入的数据做特征工程预处理，再输入模型在 TensorFlow PyTorch 等框架上做训练。 1.常见的特征工程逻辑 # 常见的特征工程逻辑有： 分箱/分桶 离散化 log/exp 对数/幂等 math numpy 常见数学运算 特征缩放/归一化/截断 交叉特征生成 分词匹配程度计算 字符串分隔匹配判断tong 缺省值填充等 数据平滑 onehot 编码，hash 编码等 这些特征工程代码，当然一般使用深度学习最主要的语言 python 实现。 二，业务痛点 # 离线训练完成，模型上线部署后，同样要用 C++ 重新实现 这些 python 的特征工程逻辑代码。 我们发现，“用 C++ 重新实现” 这个步骤，给实际业务带来了大量的问题： 繁琐，费时费力，极容易出现 python 和 C++ 代码不一致 不一致会直接影响模型在线上的效果，导致大盘业务指标不如预期，产生各种 bad case 不一致难以发现，无法测试，无法监控，经常要靠用户投诉反馈，甚至大盘数据异常才能发现

一，问题背景 # 中文分词应用比较广泛的开源算法，是 jieba 结巴分词，结巴分词较高性能的实现是 C++ 版本的 CppJieba : https://github.com/yanyiwu/cppjieba 在实际使用 CppJieba 的过程中，我们发现 CppJieba 的内存占用比较高。 比如对一个 76W 词 大小 11MB 的词典 ，加载 2份 （比如为了支持平滑改动用户词典）就需要耗费 505MB内存。 这对一些多进程的后台服务，浪费大量内存，难以接受，因此这里希望削减内存耗费。 经过初步调查，确定改进方法，然后动手改造，最终把 505MB 缩减到了 4.7MB ，实现了 99% 内存降低。 此处也有 issue 讨论 https://github.com/yanyiwu/cppjieba/issues/3 代码在 https://github.com/byronhe/cppjieba 。

分词是中文搜索的重要环节，目前分词算法已经比较成熟，分词错误的主要是由于未登录词。 因此发现业务领域语料库中的新词，减少未登录词，对改善搜索引擎的用户体验有重要意义。 新词发现的一种常用算法，是 matrix67 大神 2012 年提出的 《互联网时代的社会语言学：基于SNS的文本数据挖掘》 https://www.matrix67.com/blog/archives/5044 其主要思路，是统计语料中出现的所有 ngram 子字符串的凝固度，自由度，信息熵。 算法中需要统计所有 ngram 子字符串的 左熵右熵，实现该算法时，一般以子字符串为 key，用哈希表来存。 但随着语料库变大时，内存消耗变大， 比如之前的 python 版本实现，对 200MB 的语料，就需要约 30G 内存来存哈希表， 导致单机内存不足无法运行，而且对这样规模的语料库，算法需要跑一两天才能出结果。 这里我应用一些工程实现方面的技巧， 把用哈希表统计左熵右熵的计算，拆分成多个子哈希表，分批计算，并利用多核并行，大幅度优化了算法的性能。

http://giflib.sourceforge.net/whatsinagif/index.html http://giflib.sourceforge.net/whatsinagif/bits_and_bytes.html https://gif.ski/ gifski 可以从视频生成高质量的 gif 浓缩的才是精华：浅析 GIF 格式图片的存储和压缩 https://cloud.tencent.com/developer/article/1004763 用av1视频替代 gif https://www.singhkays.com/blog/its-time-replace-gifs-with-av1-video “Replace animated GIFs with video for faster page loads” : https://web.dev/replace-gifs-with-videos/ https://web.dev/efficient-animated-content/ http://blog.pkh.me/p/21-high-quality-gif-with-ffmpeg.html 每帧一个调色板，就可以消除噪点。 https://medium.com/@Peter_UXer/small-sized-and-beautiful-gifs-with-ffmpeg-25c5082ed733

借助 ext4 文件系统的 打洞 功能，可以实现一个消息队列 https://gist.github.com/CAFxX/571a1558db9a7b393579 fallocate(fd, FALLOC_FL_PUNCH_HOLE|FALLOC_FL_KEEP_SIZE, offset, length); Punching holes in files https://lwn.net/Articles/415889/ 怎样对大文件的中间部分进行增删？ 首先，如果复制/写文件的后半段的话，肯定是可以实现的，但是这样不“高效”。 所以这里的需求是 “怎样在大文件中间 insert 或者 delete 一段数据而不用读写文件的后半部分”。

TrafficServer 是Apache基金会的 HTTP/HTTP2 代理服务器。 TrafficServer 的 HTTP2 部分主要的代码在 : trafficserver/proxy/http2/HTTP2.h, HTTP2.cc trafficserver/proxy/http2/Http2Stream.h, Http2Stream.cc trafficserver/proxy/http2/Http2ClientSession.h, Http2ClientSession.cc trafficserver/proxy/http2/Http2ConnectionState.h, Http2ConnectionState.cc trafficserver/proxy/http2/ Http2DependencyTree.h, Http2DependencyTree.cc trafficserver/proxy/http2/HPACK.h, HPACK.cc trafficserver/proxy/http2/HuffmanCodec.h, HuffmanCodec.cc

Proxygen 的整体架构 一个 HTTPSession 对应一个 tcp 连接。 HTTPSession 中包含HTTPCodec ，HTTPCodec用来在 HTTPMessage(Request/Response) 和 字节流之间做转换（就是解析/序列化）。 一个 HTTPTransaction 对应一个 HTTP2 的Stream ，也就是一次 Req/Resp Handler 是业务逻辑处理的基类。

最近发现密码学很有意思，刚好还和工作有点关系，就研究了一下，本文是其中一部分笔记和一些思考。 密码学理论艰深，概念繁多，本人知识水平有限，错误难免，如果您发现错误，请务必指出，非常感谢! 本文禁止转载 本文目标： 学习鉴赏TLS协议的设计，透彻理解原理和重点细节 跟进一下密码学应用领域的历史和进展 整理现代加密通信协议设计的一般思路 本文有门槛，读者需要对现代密码学有清晰而系统的理解，建议花精力补足背景知识再读。本文最后的参考文献里有一些很不错的学习资料。

问题背景 # https://timyang.net/programming/load-average/ 2015.08.13 高可用架构群 Load 编程比赛，Tim 在群征集一段代码使 load average 最高 多线程写几个 while 循环的方法太 trivial 了，就不提了。 下面是 byronhe 的两个解：

本文介绍目前现代密码学的最先进技术， 前半部分主要翻译自 《Cryptographic Right Answers》，附上收集的资料，和byron个人的理解。 密码学理论艰深，概念繁多，本人知识水平有限，错误难免，如果您发现错误，请务必指出，非常感谢! 下文分类介绍在各种适用场景下，你应该使用的现代密码学算法 # 1. 加密数据 : # 按照优先级，应该选择: (1) 首选 NaCl库，或者libsodium库，使用里面的crypto_secretbox()/crypto_secretbox_open() 函数 (2) Chacha20-Poly1305 算法 (3) AES-GCM 算法 适用场景:当你需要避免把明文数据在网络上传输的时候。 以上3种算法，都是AEAD类的算法，AEAD是2015年最好的选择。 其中的(2)和(3)在结构上类似：一个流加密模式的算法，配合一个多项式结构的MAC。 (2)是一个流加密算法，配合一个为通用cpu优化的MAC算法， 对密码学库的实现者来说，Poly1305也比GCM更容易安全地实现。 AES-GCM是工业标准(TLS目前主要用的就是AES-GCM)，现代CPU通常都有专门为AES-GCM设计的硬件指令，但是在没有硬件指令支持的CPU上(比如32位的arm)，(3)性能低于(2)。

下文以nginx为例，介绍如何部署一个高性能，高安全性的https服务器。 并附送一个优化出来的openssl编译脚本，可以编译出一个高性能，高安全性的openssl库，您可以直接复制粘贴使用。 此处直接给出实践指导，后续再写文章解释tls协议的这些原理细节。 nginx下https配置的优化点，主要有: session ticket session id cache ocsp stapling http KeepAlive ECDHE等ciphersuite优化 openssl 编译优化 一， nginx https的配置 # 先贴一下nginx配置，如下。 是根据mozilla的权威文档 ,和生成工具(选择 nginx，intermediate ) 生成的配置为基础，加入session ticket等配置的结果