本文是《挑战程序设计竞赛》中线段树一节的读书笔记。主要介绍了线段树和RMQ(range minimun query)的原理和实现。
Compartmentalization方式scale复制状态机
Scaling Replicated State Machines with Compartmentalization,VLDB 21'
本文是针对Multi-Paxos协议的实现方案瓶颈做的扩展性方案,主要的方法论是compartmentalization,这个词本意是分离,在这里作为一种方法论,其含义是将各个功能进行剥离分开,并分别进行扩展。
Multi-Paxos的多个模块都有一些实现方案上的瓶颈,假设读者已经熟悉Multi-Paxos协议内容,我们根据论文的思路看看各个瓶...
Helping compiler help you : Ispike, BOLT
《BOLT: A Practical Binary Optimizer for Data Centers and Beyond》 CGO 2019
《Ispike: A Post-link Optimizer for the IntelR ItaniumR Architectur》 CGO 2004
Helping compiler help you
现在数据中心跑的程序二进制文件普遍都比较大而且代码逻辑比较复杂,因此编译过程的优化在很多情况下能够显著提升性能。编译优化是一种 helping compiler help you的方式。
编译优化常见的几种优化技术...
Quorum System的故障概率和负载
最近读到一个有趣的话题:Quorum System的故障概率和负载。
首先是一些概念:
节点集合 V=\{v_1, v_2, .., v_n\}
Quorum Q\subseteq V
Quorum System \mathcal{S} \subseteq 2^V,且Q_1 \cap Q2 \neq \emptyset, \forall Q1,Q2 \in\mathcal{S}
故障概率Failure Probability: 假设每个节点故障概率为p,Quorum System \mathcal{S}的故障概率记为F_p( \mathcal{S})等于每个Quorum都至少有一个节点发...
以史为鉴:数据模型变迁史
这两天看了篇数据模型的论文,What Goes Around Comes Around。这篇论文是2005年Stonebraker和Hellerstein两位泰斗写的,讲的是数据库的数据模型35年的变迁历史,另外论文还总结了一些经验。
这是一个非常有趣的话题,能够让我们更多地去从市场和产品角度看问题,尤其是考虑到不断迭代的甚至是越来越快地迭代的数据库技术。
数据模型Data Model的9个历史阶段:
Hierarchical(IMS): 1960年代末到197...
找工作备忘(腾讯 百度 阿里 网易游戏 知乎 笔试面试题 )
找工作流水账及笔试面试题。我的笔试面试经历,腾讯实习,百度,阿里,网易游戏,知乎等的笔试题目和面试题目
RocksDB演进
《Evolution of Development Priorities in Key-value Stores ServingLarge-scale Applications: The RocksDB Experience》FAST'20
这篇文章是讲述Facebook大规模部署RocksDB的经验,主要是RocksDB优化目标的演变。
RocksDB应用比较广,除了作为KV产品服务业务,也在很多其他系统中作为存储组件。
Streaming Processing: Flink, Kafaka Stream, Samba, Facebook's Stylus.
Logging/Queuing Service: Fa...
WordPress公式范例
没想到wordpress的latex插件支持的这么好。
写了几个例子,右键"Show Math As" "Tex Commands"可以看原始文本。
Ubuntu 12.04编译安装3.15.6新内核
本文是Ubuntu 12.04编译安装3.15.6新内核的个人经验,重点是过程中没遇到什么问题,所以对各位读者用处可能不大。大致步骤:下载、解压源码;安装必要的工具;配置;编译;安装;启动新内核。
几道面试趣题( 打印重复数字 编码扑克牌 煎饼堆排序 随机选取数字 统计1的个数 )
逛Quora的时候,看到一个有趣的问题。”What are the best programming interview questions you've ever asked or been asked?” (在编程面试中,你问过或者被问过的最好的问题是什么)里面有几道题目很有意思,在这里分享给大家。
第一道题:有一个长度为N+1的数组,里面的元素都是1~N的整数,但有些数字可能重复多次。例如1,1,3 ,3或者 1,3,2,2。现在要求打印出重复的数字(有多个数字重复时,可打印任意一个)。
第二道题目:去掉大小王的52张扑克牌,你和你的朋友事先约定一种策略,使得:我任意给你5张扑克牌,你选择一张留下,剩余的4张给你的朋友,你的朋友能够根据事先约定的策略,知道你留下的牌是什么。
从连续不断的数字流中随机选取一个数字(数字流只能过一遍),要求保证任意时刻,已经过去的数字流中任意一个数字被选中的概率相等。
给定整数N,计算从1到N的数字的二进制表示中所有1的个数。