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

Spring AOP(一) AOP基本概念

 Spring框架自诞生之日就拯救我等程序员于水火之中,它有两大法宝,一个是IoC控制反转,另一个便是AOP面向切面编程。今日我们就来破一下它的AOP法宝,以便以后也能自由使出一手AOP大法。

 AOP全名Aspect-oriented programming面向切面编程大法,它有很多兄弟,分别是经常见的面向对象编程,朴素的面向过程编程和神秘的函数式编程等。所谓AOP的具体解释,以及和OOP的区别不清楚的同学可以自行去了解。

 AOP实现的关键在于AOP框架自动创建的AOP代理,AOP代理主要分为静态代理和动态代理。本文就主要讲解AOP的基本术语,然后用一个例子让大家彻底搞懂这些名词,最后介绍一下AOP的两种代理方式:

  • 以AspectJ为代表的静态代理。
Read More
Share

AbstractQueuedSynchronizer超详细原理解析

 今天我们来研究学习一下AbstractQueuedSynchronizer类的相关原理,java.util.concurrent包中很多类都依赖于这个类所提供队列式同步器,比如说常用的ReentranLockSemaphoreCountDownLatch等。
 为了方便理解,我们以一段使用ReentranLock的代码为例,讲解ReentranLock每个方法中有关AQS的使用。

ReentranLock示例

 我们都知道ReentranLock的加锁行为和Synchronized类似,都是可重入的锁,但是二者的实现方式确实完全不同的,我们之后也会讲解Synchronized的原理。除此之外,Synchronized的阻塞无法被中断,而ReentrantLock则提供了可中断的阻塞。下面的代码是ReentranLock的函数,我们就以此为顺序,依次讲解这些函数背后的实现原理。

ReentrantLock lock = new ReentrantLock();

Read More
Share

LongAdder原理完全解析

 对LongAdder的最初了解是从Coolshell上的一篇文章中获得的,但是一直都没有深入的了解过其实现,只知道它相较于AtomicLong来说,更加适合写多读少的并发情景。今天,我们就研究一下LongAdder的原理,探究一下它如此高效的原因。

基本原理和思想

 Java有很多并发控制机制,比如说以AQS为基础的锁或者以CAS为原理的自旋锁。不了解AQS的朋友可以阅读我之前的AQS源码解析文章。一般来说,CAS适合轻量级的并发操作,也就是并发量并不多,而且等待时间不长的情况,否则就应该使用普通锁,进入阻塞状态,避免CPU空转。

 所以,如果你有一个Long类型的值会被多线程修改,那么使用CAS进行并发控制比较好,但是如果你是需要锁住一些资源,然后进行数据库操作,那么还是使用阻塞锁比较好。

 第一种情况下,我们一般都使用AtomicLongAtomicLong是通过无限循环不停的采取CAS的方法去设置内部的value,直到成功为止。那么当并发数比较多或出现更新热点时,就会导致CAS的失败机率变高,重试次数更多,越多的线程重试,CAS失败的机率越高,形成恶性循环,从而降低了效率。

 而LongAdder的原理就是降低对value更新的并发数,也就是将对单一value的变更压力分散到多个value值上,降低单个value的“热度”。

Read More
Share