一种使用多级Hash存储路径字符串并优化访问的方法

在进行web开发,经常会使用各种不一样的路径进行相应的逻辑定义。特别是使用spring体系时,会使用各种path来定义访问方法。浏览器在访问某个API时,服务端则会使用特定的匹配逻辑来匹配到具体应该访问某个方法。如例子如下

@GetMapping({"/index/**", "index2"})
public String index() throws Exception {
}

在如上的定义中,可以匹配如下的路径

/index2
/index
/index/abc
/index/abc/def

当在项目中定义的路径过多时,默认情况下,常规的逻辑即是根据代码中定义的 path,遍列匹配请求路径,最终找到匹配的方法。当path过多时,在一定程度上其本身的性能也不会太快. 在笔者的实际项目中,大部分的path定义如下

/a/api/business1/index
/b/api/business1/index
/c/api/business1/index
/a/api/business1/*/path1/*
/b/api/business1/*/path1/*
/c/api/business1/*/path1/*
/a/api/business1/**
/b/api/business1/**
/c/api/business1/**

可以看出,path 定义中,有相同的前缀,只是末尾或中间有一些不同。在这种典型的场景中,有点类似于前缀树的概念。不过是按 / 进行分隔节点.
在标准的前缀树(字典树)中,都是按单个字母(字符)来进行节点划分,并没有一种按不固定的字符串(每个/中的字符串长度不定)进行前缀划分的逻辑.

本文描述了一种通过多级Hash存储,来模拟前缀树,并通过优化访问路径,来提升匹配速度的算法. 考虑到具体使用场景,本文描述的算法,仅处理 插入和查找 的逻辑,不处理更新或删除的逻辑.

继续阅读“一种使用多级Hash存储路径字符串并优化访问的方法”

一种在json场景针对pojo对象动态添加扁平属性的方法

本方法在几年前均已实现,这里将其重新整理一下,以作备忘
在典型的应用场景中,经常会有这样的需求,即当业务返回单个pojo对象时,需要临时追加几个属性在这个对象中并一起返回至前端。如下例子所示:

public class Abc {
    String username;
}

此对象仅有1个属性,但返回至前端时,需要返回类似如下的数据结构:

{
    "username": "张三",
    "sex": "MALE",
    "age": 20
}

有一些作法通过再定义新的类,如 AbcVO 通过继承原类并添加新字段来支持;或者不再使用对象,则是直接使用map代替. 前者会造成类爆炸,后者会造成API语义不清晰.

本文描述了一种标准的 Attr 接口结构,并通过json序列化器(如jackson或fastjson)支持的注解,通过简单的default 方法定义,完成属性添加。并同时支持序列化和反序列化的应用场景.

这里采用接口,以及default 方法设计,原有的类通过一个简单的额外implements,即可支持此特性,无需其它的改造,也不需要额外实现接口方法,即可使用此特性.

继续阅读“一种在json场景针对pojo对象动态添加扁平属性的方法”

使用 Servlet3.1 WriteListener进行异步响应输出以及踩过的坑

在标准的spring mvc项目中,当对象数据已经产生时,不管是输出json,还是view,最终均是将相应的数据直接写入response的outputStream中。这里的输出是同步式调用的,即意味着只有当整个数据完整地写到输出流中时,整个业务线程才会被认为执行结束。

这就意味着在传统的基于请求的慢速攻击之外,还有一种基于响应的慢速攻击,其思路即是客户端强制让整个接收变慢,而服务端因为缓存区不足以存储完整的响应数据,而被动地阻塞调用端,进而阻塞业务线程。

在Servlet 3.0版本中,提出了业务中的异步处理,即 通过 HttpServletRequest#startAsync 来开启异步处理。等业务处理完成之后,才通过 AsyncContext#complete 来结束处理。在中间,可以仍然通过 HttpServletResponse#getOutputStream 来输出数据. 这里的异步处理仅仅是将容器的处理线程解放出来,即当业务处理需要长时间或者需要故意挂起请求(如LongPull)时,才有相应的意义。在最终输出数据时,这里仍然是阻塞的,只不过是阻塞业务线程(而非容器线程).造成的后果即是缓慢地IO操作造成线程阻塞。

随着 NIO 的出现,所有Web容器均使用了Nio来处理请求,即当整个请求已经完整读取完毕之后,才转交由具体的业务线程来处理,即在这里的io读取均为非阻塞读取,由很少数的线程就可以处理上百(千)个请求的网络请求. 在 Servlet 3.1 版本中, 规范中给出了 异步响应的概念,即可以通过响应式来达到异步非阻塞输出数据的效果. 从调用端来看,调用write之后即刻返回,并不会阻塞业务线程。后续未刷新到缓冲区的数据将在后续通过标准Nio流程由web容器的IO线程负责处理.

一个参考使用例子如下所示(参考于 https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/HTML5andServlet31/HTML5andServlet%203.1.html):

//开启异步
val context = request.startAsync();
val response = context.getResponse();
val servletOut = response.getOutputStream();

//定义响应监听器,以可写时输出相应的数据
val writeListener = new WriteListenerImpl(context, servletOut, actionQueue);
servletOut.setWriteListener(writeListener);

//一个参考的监听器实现
public class WriteListenerImpl implements WriteListener {
    private ServletOutputStream output = null;
    private Queue queue = null;
    private AsyncContext context = null;

    private boolean flag = false;

    @Override
    public void onWritePossible() throws IOException {
        if (flag) {
            return;
        }

        //这里仅当output.isReady() 时才会调用write方法,否则会报 IllegalStateException
        while (queue.peek() != null && output.isReady()) {
            val action = queue.poll();
            doWrite(action);
        }
    }

    private void doWrite(Action action) throws IOException {
        //已完成标记位
        if (action == Action.COMPLETE) {
            flag = true;
        }

        action.run(context, servletOut);
    }
}
继续阅读“使用 Servlet3.1 WriteListener进行异步响应输出以及踩过的坑”

Jboss EnhancedQueueExecutor源码解读

在JDK线程池中自带的Executor遵循一种典型的生产者,消费者队列模型,即一个统一的阻塞队列,然后一个线程数组不停地消费其中的数据。其本身的处理逻辑为 coreSize->queueSize->maxSize 的增长方式,即先尝试增加 coreSize, 然后再不断地将任务放进队列中,如果队列满了,则再尝试增加 maxSize, 直至拒绝任务。

通过一些手法可以调整策略为 coreSize->maxSize->queueSize。

本文则描述一个由 jboss-threads 中提到的 EnhancedQueueExecutor,中文为增加型队列执行器。其除支持典型的executor模型外,也同样保留如 coreSize,maxSize, queueSize 这些模型。与jdk中实现相区别的是,其本身采用单个链表来完成任务的提交和线程的执行,同时采用额外的数据来存储计数类数据. 更重要的是,其默认线程策略即 coreSize->maxSize->queueSize, 同时可以根据参数调整此策略.

创建对象与ThreadPoolExecutor类似,指定相应的参数即可,如下所示:

EnhancedQueueExecutor executor = new EnhancedQueueExecutor.Builder()
        .setCorePoolSize(corePoolSize)
        .setMaximumPoolSize(maxPoolSize)
        .setKeepAliveTime(Duration.ofMinutes(5))
        .setMaximumQueueSize(1024)
        .setThreadFactory(threadFactory)
        .setExceptionHandler(uncaughtExceptionHandler)
        .setRegisterMBean(false)
        .setGrowthResistance(growthResistance) //增长因子,控制新线程创建逻辑(if >= coreSize时)
        .build();
继续阅读“Jboss EnhancedQueueExecutor源码解读”

使用自定义FutureTask实现大小不固定的定时线程池

在使用定时任务执行线程池ScheduledThreadPoolExecutor时,在相应的定义中,只需要通过coreSize来定义1个大小固定的线程池,并且在其具体的定义中,因为队列长度是无限的,因此maxSize实际上也没有任何作用。其问题在于,如果coreSize定义过大,则会造成线程池中大量的空闲线程,实际上没有任务可作.

如定义1个coreSize为10的定时线程池,即使只周期性的执行1个任务,在一段时间之后,其池中的执行线程会逐渐增多,直到达到coreSize上限. 并且由于定时调度的原因,不能设置 allowCoreThreadTimeOut, 此设置会导致定时的任务因为无线程可用而不会触发,原因在于任务的定时是通过执行线程的takeTask操作被动触发的。

本文通过一个单线程定时线程池和一个额外的普通的ExecutorService进行协作,定时线程池只负责调度,而具体的执行则交给执行线程池来处理。而执行线程池的线程本身是可以设置或处理达到线程数可调节。通过2个线程池之间进行协作,完成调度完成。

同时,本实现也将专门处理 scheduleWithFixedDelay 或 scheduleWithFixedDelay 中的延时处理,保证任务必须在前1个任务执行完成之后才处理下一个任务,而避免简单调度中可能产生同1个任务由于执行超时出现并行执行的问题.

本文将定义定时线程池称之为 defineScheduledExecutor,类型为ScheduledThreadPoolExecutor; 实际执行线程池称之为 realExecutor,类型为 ExecutorService

继续阅读“使用自定义FutureTask实现大小不固定的定时线程池”

实现优先使用运行线程及调整线程数大小的线程池

当前在JDK中默认使用的线程池 ThreadPoolExecutor,在具体使用场景中,有以下几个缺点

  1. core线程一般不会timeOut
  2. 新任务提交时,如果工作线程数小于 coreSize,会自动先创建线程,即使当前工作线程已经空闲,这样会造成空闲线程浪费
  3. 设置的maxSize参数只有在队列满之后,才会生效,而默认情况下容器队列会很大(比如1000)

如一个coreSize为10,maxSize为100,队列长度为1000的线程池,在运行一段时间之后的效果会是以下2个效果:

  1. 系统空闲时,线程池中始终保持10个线程不变,有一部分线程在执行任务,另一部分线程一直wait中(即使设置allowCoreThreadTimeOut)
  2. 系统繁忙时,线程池中线程仍然为10个,但队列中有还没有执行的任务(不超过1000),存在任务堆积现象

本文将描述一下简单版本的线程池,参考于 Tomcat ThreadPoolExecutor, 实现以下3个目标

  1. 新任务提交时,如果有空闲线程,直接让空闲线程执行任务,而非创建新线程
  2. 如果coreSize满了,并且线程数没有超过maxSize,则优先创建线程,而不是放入队列
  3. 其它规则与ThreadPoolExecutor一致,如 timeOut机制
继续阅读“实现优先使用运行线程及调整线程数大小的线程池”