Before we start If we consider the entire course as an artistic journey through an oil painting, then before setting off officially, we need to make some preparations, just like we always plan ahead before every trip. You might say, “But isn’t it more fun to travel without a plan, full of unknowns!” However, with … Continue reading “Learn to Apprieciate a Painting – History and Genres: What You Must Know About Oil Painting”
There is no excerpt because this is a protected post.
问题背景 本问题来源于实际问题，社交平台设计上为了保证回复帖的并发一致性，需要在回复帖前获取楼层的分布式锁，获取分布式锁的可以有资格修改存在Redis中的楼层数。目前逻辑是，如果竞争分布式锁失败，那么会直接报错，用户感知发帖失败。现在怀疑该设计会使得错误率随着QPS的提升有显著提升。本文从该问题出发，使用泊松分布与指数分布作为基本模型，探讨系统性能随容量变化的趋势。 问题描述与模型建立 问题描述如下。现有一社交平台，用户会有以下操作： 1. 发主题帖 2. 回复主题帖 存在如下碰撞可能，某一主题帖如果没有任何回复内容，在时间\( t_q\)内被至少一个用户回复，会发生碰撞。现已知每日主题帖的数量为\( Pst\)，每日回复主题帖的数量为\( Rpst\)，求每日发生碰撞次数的分布，并且探讨随着平台的使用量增大，碰撞概率发生变化的趋势。 用户在社交平台上针对某一主题帖进行回帖，可以看作服从泊松分布。有关泊松分布，可以参考本站先前的博客统计模拟(二)——泊松分布与二项分布模拟与统计模拟(六)——保险模型有关泊松分布的叙述。 用通俗的语言解释泊松分布，如现在已知每家海底捞在高峰时段平均每小时招待150名客人，求高峰时期招待用户数量的分布。 \[ P(X(t)=k)=e^{-\lambda t}\dfrac{(\lambda t)^i}{k!} \] 其中 \( \lambda\) 为单位时间内的事件发生概率，为了求2.5小时内招待350-400名客人的概率，可以将代入参数： \[ \sum_{k=350}^{400} P(X(k)) =\sum_{k=400}^{500} \dfrac{(150 \times 2.5)^k e^{(-150 \times 2.5)}}{k!} \approx 0.8122 \] 泊松分布与指数分布有着密不可分的关系，从当前时刻开始计算，时间 t 内事件发生的概率服从指数分布。（等价于时间 t 内事件发生次数不为0） \[ P(X < t) = 1 – e^{-\lambda t} \] 在本问题中，每个主题帖每秒钟平均的回复数为\( \lambda = Rpst/86400/Pst\)。假设当前存在一个主题帖，在24h内无人回复会沉帖。那么该主题帖的状态的转移状态为： … Continue reading “再谈泊松分布与指数分布”
Redis 支持基于 HyperLogLog 的基数计数统计，其算法思想和前两篇提到的 Linear Counting 和 LogLog Counting 的算法类似，本篇主要分析其源码——github:antirez/redis/src/hyperloglog.c 中的代码 Header Header 总共有 16 个字节，分别为 HYLL E N/U Cardin 如下图所示： HYLL 是 4 个魔法字节，为”HYLL” E 为 1 个字节表示Dense/Sparse N/U 为未来留下的空字节，共 3 个字节 Cardin 为缓存区，8 个字节 代码实现如下： struct hllhdr { char magic[4]; /* “HYLL” */ uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */ uint8_t notused[3]; /* … Continue reading “HyperLogLog 算法（三）—— Redis 中的 HyperLogLog”
LogLog 算法 在上一篇 HyperLogLog 算法（一）——Bitmap 与 LinearCounting中介绍了 Linear Counting 的算法，缺点在于从渐进复杂性的角度看，空间复杂度仍为 O(Nmax)，其空间利用效率依旧不高。基于 Linear Counting 算法，LogLog Counting 算法的空间复杂度仅有 O(log2(log2(Nmax)))，使得通过KB级内存估计数亿级别的基数成为可能。 考虑如下伯努利过程 A ：不停抛掷一枚均匀硬币，出现反面则继续抛掷，出现正面则停止抛掷，抛掷出的反面次数为 \( k\) ，那么可以容易得出： \[ P_A(x=k)=(\frac{1}{2})^k \quad k=0,1,2,3,4,5,…\] 考虑如下问题 1： 进行 \( n\) 次 A 过程，每一次过程的总抛掷次数都不大于某常数 \( k_{max}\) 的概率是多少？容易得出： \[ P_1(x\leq k_{max}) = [1-(\frac{1}{2})^{k_{max}}]^n\] 进行 \( n\) 次 A 过程，至少有一次过程，其抛掷次数等于常数 \( k_{max}\) 的概率是多少？容易得出： \[ P_2(x = … Continue reading “HyperLogLog 算法（二）——LogLog 与 HpyerLogLog”
从计数谈起 在漫长的求职刷 leetcode 的过程中，会遇到一个普遍的情景，但是苦于所学的语言没有封装数据结构去描述这一情景，所以一直以来都是自己在代码里实现。直到某一天看到关于 hyperloglog 的算法，才发现本问题比想象的要复杂得多，那就是计数的问题。 所谓计数，用来统计一个集合中出现的各个不同元素的个数，由于在 leetcode 中太普遍，以至于一时间没有找到什么特别有代表性的问题可以贴在这里，但是普遍情况下使用 HashMap 实现，例如： class Counter<T>{ private HashMap<T, Integer> countMap; public Counter<T>(){ HashMap<T, Integer> countMap = new HashMap(); } public void add(T t){ countMap.put(this.get(t) + 1); } public int get(T t){ return countMap.getOrDefault(t, 0); } } 如果计数类型是正整数，还可以考虑直接用 Index 数组计数，即数组的 Index 为计数的元素，但是前提是元素不能太大。 class Counter{ private int[] countMap; public Counter(int … Continue reading “HyperLogLog 算法（一）——Bitmap 与 LinearCounting”
在实际工作中遇到这么一个序列化的问题，需要根据一个用户表的老用户进行拓展，每一个老用户需要派生几个不同业务线的新用户。方法是在部署之后，从传入的参数中读取Json数据构建Map，Map的 Key 值为老的用户Id，Value 值为老用户对应的新的用户 Id 表。 为此，在拓展的任务代码里加入了如下内部类用于接收 Json： public class SomeJob{ public void deserialization(String paramStr){ … } class FlushPair{ long oldUserId; List<long> newUserIds; //getter and setter and default constructor … } } </long> Json 的格式如下所示： [ { “newUserIds”: [119,120,121], “oldUserId”:1 }, { “newUserIds”:[122,123,124], “oldUserId\”:2 }, { “newUserIds”:[125,126,127], “oldUserId”:13 }, … ] Json 的字符串命名为 paramStr，在下面代码中被反序列化： import … Continue reading “由一个NPE问题引发的内部类概览”
本文主要简单盘点 MyBatis 用法, MyBatis 源码解读, 以及 Mybatis / Hibernate 比较 基本概念 MyBatis 是一种 Java ORM (Object Related Map) 框架, 所谓 ORM 是指对象关系映射, 即将数据库的一张表和 POJO 对应起来, ORM 模型即描述了二者的映射关系. 传统操作数据库的方法是通过 JDBC 来实现的, 但是 JDBC 只是定义了接口规范, 具体实现是数据库厂商实现的, 例如 MySQL 的 JDBC 连接器可能是 Oracle 自己实现, SQLServer 的 JDBC 连接器可能就是靠微软来实现. 传统的 JDBC 存在一个问题, 即重复代码量大, 严格按照一定的顺序连接->打开->执行->读取->转换->关闭. MyBatis 这种 ORM 框架就出现了. MyBatis … Continue reading “MyBatis 原理探析”
早在一年前, 就调研过主流的流处理平台, 但是对于其原理一直知之甚少, 借着实践的机会, 特意整理一些流处理的内容以供学习 在交易系统, 物联网, 电信系统中广泛用到流处理系统. 流处理的特点是处理的数据特点在于数据流的规模是无限的, 反馈是实时的, 关注的对象应该是其服务, 而不是数据本身的联系. 典型的流处理平台有 Spark Streaming, Storm, Flink, Samza 等等. 本篇主要总结一下 Spark Streaming 与 Storm 的区别. 描述一个流处理系统时, 我们常常用有向无环图描述其拓扑结构 一般的流处理系统基本不是单机系统, 基本都会把拓扑结点放到分布式平台上. 在总结之前, 先介绍如下几个概念: 编程模型/运行时模型 运行时模型是流处理系统最大的特点, 也是 Spark Streaming 与 Storm 最大的不同, 其差异均来自于这个特性. 原生的流处理系统实现的都是原生流处理模型, 每一个记录到达之后会立即被处理. 非原生的流处理系统实现的是批处理模型, 数据会被人为的按照一定规则分成一批一批的数据, 每一批数据到达之后会进行统一处理. 原生流处理系统 批处理系统 Storm 是典型的原生流处理系统, 但是也可以支持批处理, Spark Streaming 将 Spark 中的 … Continue reading “流处理平台 Spark Streaming 与 Storm”
终于支持markdown了, 排版突然变化望见谅 大型网站系统与 Java 中间件实践 分布式系统 为什么要使用分布式系统? 升级单机处理能力的性价比越来越低 单机处理能力存在瓶颈 稳定性与可用性 多种并发执行模式 生产者消费者模型是一种典型的基于共享容器的多线程工作方式 通过事件协同的模式, 例如触发事件(中断) 多进程模式, 涉及到进程间通信, 序列化与反序列化等等, 但单进程不可用, 整体可能部分可用 BIO/NIO/AIO BIO 阻塞, 方式是一个 socket 需要一个线程, 建立, 读, 写都会产生阻塞 NIO 基于事件驱动, 采用反应堆模式, 可以在一个线程中处理多个 socket (较为常用) AIO 异步IO, 采用 Proactor 模式, 通知发生在动作之前, Selector 发现事件后调用 Handler 处理. 控制器 硬件负载均衡 LVS (Linux Virtual Server) 名称服务 (Name Server) 规则服务器 主从模式 … Continue reading “大型网站系统与 Java 中间件实践”