用户日活月活怎么统计 - Redis HyperLogLog 详解

HyperLogLog 是一种概率数据结构,用来估算数据的基数。数据集可以是网站访客的 IP 地址,E-mail 邮箱或者用户 ID。

基数就是指一个集合中不同值的数目,比如 a, b, c, d 的基数就是 4,a, b, c, d, a 的基数还是 4。虽然 a 出现两次,只会被计算一次。

精确的计算数据集的基数需要消耗大量的内存来存储数据集。在遍历数据集时,判断当前遍历值是否已经存在唯一方法就是将这个值与已经遍历过的值进行一一对比。当数据集的数量越来越大,内存消耗就无法忽视,甚至成了问题的关键。

使用 Redis 统计集合的基数一般有三种方法,分别是使用 Redis 的 HashMap,BitMap 和 HyperLogLog。前两个数据结构在集合的数量级增长时,所消耗的内存会大大增加,但是 HyperLogLog 则不会。

Redis 的 HyperLogLog 通过牺牲准确率来减少内存空间的消耗,只需要12K内存,在标准误差0.81%的前提下,能够统计2^64个数据。所以 HyperLogLog 是否适合在比如统计日活月活此类的对精度要不不高的场景。

Read More
Share

十二张图带你了解 Redis 的数据结构和对象系统

Redis是一个开源的 key-value 存储系统,它使用六种底层数据结构构建了包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象的对象系统。今天我们就通过12张图来全面了解一下它的数据结构和对象系统的实现原理。

本文的内容如下:

  • 首先介绍六种基础数据结构:动态字符串,链表,字典,跳跃表,整数集合和压缩列表。
  • 其次介绍 Redis 的对象系统中的字符串对象(String)、列表对象(List)、哈希对象(Hash)、集合对象(Set)和有序集合对象(ZSet)
Read More
Share

分布式数据缓存中的一致性哈希算法

一致性哈希算法在分布式缓存领域的 MemCache,负载均衡领域的 Nginx 以及各类 RPC 框架中都有广泛的应用,它主要是为了解决传统哈希函数添加哈希表槽位数后要将关键字重新映射的问题。

本文会介绍一致性哈希算法的原理及其实现,并给出其不同哈希函数实现的性能数据对比,探讨Redis 集群的数据分片实现等,文末会给出实现的具体 github 地址。

Memcached 与客户端分布式缓存

Memcached 是一个高性能的分布式缓存系统,然而服务端没有分布式功能,各个服务器不会相互通信。它的分布式实现依赖于客户端的程序库,这也是 Memcached 的一大特点。比如第三方的 spymemcached 客户端就基于一致性哈希算法实现了其分布式缓存的功能。

其具体步骤如下:

Read More
Share

Guava的布隆过滤器

 程序世界的算法都要在时间,资源占用甚至正确率等多种因素间进行平衡。同样的问题,所属的量级或场景不同,所用算法也会不同,其中也会涉及很多的trade-off。

If there’s one rule in programming, it’s this: there will always be trade-offs.

你是否真的存在

 今天我们就来探讨如何判断一个值是否存在于已有的集合问题。这类问题在很多场景下都会遇到,比如说防止缓存击穿,爬虫重复URL检测,字典纠缠和CDN代理缓存等。

Read More
Share

TCP报文发送的那些事

 今天我们来总结学习一下TCP发送报文的相关知识,主要包括发送报文的步骤,MSS,滑动窗口和Nagle算法。

发送报文

 该节是根据陶辉大神的系列文章总结。如下图所示,我们一起来看一下TCP发送报文时操作系统内核都做了那些事情。其中有些概念在接下来的小节中会介绍。

 首先,用户程序在用户态调用send方法来发送一段较长的数据。然后send函数调用内核态的tcp_sendmsg方法进行处理。

send方法返回成功,内核也不一定真正将IP报文都发送到网络中了,也就是说内核发送报文和send方法是不同步的。所以,内核将用户态内存中的发送数据,拷贝到内核态内存中,不依赖于用户态内存,这样可以使得进程可以快速释放发送数据占用的用户态内存。

 在拷贝过程中,内核将待发送数据,按照MSS来划分成多个尽量接近MSS大小的分片,放到这个TCP连接对应的tcp_write_queue发送队列中

Read More
Share

基于Redis和Lua的分布式限流

 Java单机限流可以使用AtomicInteger,RateLimiter或Semaphore来实现,但是上述方案都不支持集群限流。集群限流的应用场景有两个,一个是网关,常用的方案有Nginx限流和Spring Cloud Gateway,另一个场景是与外部或者下游服务接口的交互,因为接口限制必须进行限流。

 本文的主要内容为:

  • Redis和Lua的使用场景和注意事项,特别是KEY映射的问题
  • Spring Cloud Gateway中限流的实现
Read More
Share

超详细的Guava RateLimiter限流原理解析

 限流是保护高并发系统的三把利器之一,另外两个是缓存和降级。限流在很多场景中用来限制并发和请求量,比如说秒杀抢购,保护自身系统和下游系统不被巨型流量冲垮等。

 限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务或进行流量整形。

 常用的限流方式和场景有:限制总并发数(比如数据库连接池、线程池)、限制瞬时并发数(如nginx的limit_conn模块,用来限制瞬时并发连接数,Java的Semaphore也可以实现)、限制时间窗口内的平均速率(如Guava的RateLimiter、nginx的limit_req模块,限制每秒的平均速率);其他还有如限制远程接口调用速率、限制MQ的消费速率。另外还可以根据网络连接数、网络流量、CPU或内存负载等来限流。

 比如说,我们需要限制方法被调用的并发数不能超过100(同一时间并发数),则我们可以用信号量Semaphore实现。可如果我们要限制方法在一段时间内平均被调用次数不超过100,则需要使用RateLimiter

限流的基础算法

 我们先来讲解一下两个限流相关的基本算法:漏桶算法和令牌桶算法。

Read More
Share

TCP/IP的底层队列

 自从上次学习了TCP/IP的拥塞控制算法后,我越发想要更加深入的了解TCP/IP的一些底层原理,搜索了很多网络上的资料,看到了陶辉大神关于高性能网络编程的专栏,收益颇多。今天就总结一下,并且加上自己的一些思考。

 我自己比较了解Java语言,对Java网络编程的理解就止于Netty框架的使用。Netty的源码贡献者Norman Maurer对于Netty网络开发有过一句建议,”Never block the event loop, reduce context-swtiching”。也就是尽量不要阻塞IO线程,也尽量减少线程切换。我们今天只关注前半句,对这句话感兴趣的同学可以看一下蚂蚁通信框架实践

 为什么不能阻塞读取网络信息的IO线程呢?这里就要从经典的网络C10K开始理解,服务器如何支持并发1万请求。C10K的根源在于网络的IO模型。Linux 中网络处理都用同步阻塞的方式,也就是每个请求都分配一个进程或者线程,那么要支持1万并发,难道就要使用1万个线程处理请求嘛?这1万个线程的调度、上下文切换乃至它们占用的内存,都会成为瓶颈。解决C10K的通用办法就是使用I/O 多路复用,Netty就是这样。

Netty的reactor模型

Read More
Share

TCP拥塞控制算法简介

 最近花了些时间在学习TCP/IP协议上,首要原因是由于本人长期以来对TCP/IP的认识就只限于三次握手四次分手上,所以希望深入了解一下。再者,TCP/IP和Linux系统层级的很多设计都可以用于中间件系统架构上,比如说TCP 拥塞控制算法也可以用于以响应时间来限流的中件间。更深一层,像TCP/IP协议这种基础知识和原理性的技术,都是经过长时间的考验的,都是前人智慧的结晶,可以给大家很多启示和帮助。

 本文中会出现一些缩写,因为篇幅问题,无法每个都进行解释,如果你不明白它的含义,请自己去搜索了解,做一个主动寻求知识的人。

 TCP协议有两个比较重要的控制算法,一个是流量控制,另一个就是阻塞控制。

 TCP协议通过滑动窗口来进行流量控制,它是控制发送方的发送速度从而使接受者来得及接收并处理。而拥塞控制是作用于网络,它是防止过多的包被发送到网络中,避免出现网络负载过大,网络拥塞的情况。

 拥塞算法需要掌握其状态机和四种算法。拥塞控制状态机的状态有五种,分别是Open,Disorder,CWR,Recovery和Loss状态。四个算法为慢启动,拥塞避免,拥塞发生时算法和快速恢复。

Read More
Share

Spring AOP(二) 修饰者模式和JDK Proxy

 在上边一篇文章中我们介绍了Spring AOP的基本概念,今天我们就来学习一下与AOP实现相关的修饰者模式和Java Proxy相关的原理,为之后源码分析打下基础。

修饰者模式

 Java设计模式中的修饰者模式能动态地给目标对象增加额外的职责(Responsibility)。它使用组合(object composition),即将目标对象作为修饰者对象(代理)的成员变量,由修饰者对象决定调用目标对象的时机和调用前后所要增强的行为。

 装饰模式包含如下组成部分:

  • Component: 抽象构件,也就是目标对象所实现的接口,有operation函数
Read More
Share