一种使用多级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存储路径字符串并优化访问的方法”

fastjson 反序列化源码解析

fastjson从0.X版本到最新版本,由于其特殊的编码(即特别编码优化),让人对其实现思路很难处理,加上没有注释,因此在学习了解时也很困难。因此,本篇即从基本概念入手,忽略其一些特殊处理点(对实际结果无意义),了解其反序列化实现思路。
本文基于fastjson版本 1.2.4

1 基本概念

  • token-词法标记      用于标识当前在解析过程中解析到的对象的一个标记,具体的值参考 JSONToken。比如 {,即表示当前正在解析的是一个类似map或对象的格式,而},则表示当前对象已经到底了。
  • ch-当前字符    用于表示当前已经读取到的字符是什么,如 abc,当位置为1时,则当前字符为 b
  • bp-解析字符位置    用于表示当前字符所位于原始字符串中的哪一个位置,与ch是相对应的,它始终表示最新的一个位置,如果需要记录一些历史位置。如字符串起始位置,数字起始位置等,则需要使用其它标记,如np。
  • sbuf-字符缓冲    在解析字符串时的特殊存储区域,主要是用于解析转义字符时的临时存储区。即如果原字符串为 a\\t,则实际解析的字符串应该为a\t,那么原字符串为3位长,解析之后为2位长。即需要另行存储。字符缓冲区如名所示,为一个字符数组,需要需要单独的定义来存储长度信息,如使用sp。
  • sp-字符缓冲区位置    这个用于表示在字符缓冲区之间记录当前字符串(或数字串)等的长度信息,同时也等同于当前的一个位置(如果坐标从0开始)。
  • np-数字解析位置    用于实际表示在解析到常量信息时起始点的标记位置。通过np + sp,即计算得出相应的区间值了。

继续阅读“fastjson 反序列化源码解析”

java内部类final语义实现

本文描述在java内部类中,经常会引用外部类的变量信息。但是这些变量信息是如何传递给内部类的,在表面上并没有相应的线索。本文从字节码层描述在内部类中是如何实现这些语义的。

本地临时变量 基本类型

final int x = 10;

new Runnable() {
    @Override
    public void run() {
        System.out.println(x);
    }
}.run();

当输出内部类字节码(javap -p -s -c -v)时,如下所示:

         0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: bipush        10
         5: invokevirtual #3                  // Method java/io/PrintStream.println:(I)V
         8: return

可以看出,此常量值直接被写在内部类的临时变量中,即相当于进行了一次变量copy。

继续阅读“java内部类final语义实现”

guava中的FinalizableReferenceQueue解析

1 引用队列的监控和回调
当创建一个引用队列时,我们需要对这个队列进行监控,即开启一个新的线程来循环判断此队列信息,并从中获取相应的数据信息。在guava中,也是通过创建一个线程然后在循环中进行判断,如下所示(类com.google.common.base.internal.Finalizer):

    Thread thread = new Thread(finalizer);
    thread.setName(Finalizer.class.getName());
    thread.setDaemon(true);

    thread.start();

即创建一个以finalizer runnable对象的线程,然后启动之,为避免阻止进程结束,采用了后台线程的模式。那在这个finalizer中,其运行如下所示:

while (true) {
      try {
        if (!cleanUp(queue.remove())) {
          break;
        }
      } catch (InterruptedException e) { /* ignore */ }
    }

即不断地获取队列中的数据,然后调用cleanUp方法.而在cleanUp方法中,其实就是调用相应对象的回调方法,即当一个对象已经被gc时的回调。

在guava中,从队列中移除的是一个是reference对象。在java体系中,并没有在reference对象中定义相应的回调方法,因此guava为jdk的reference增加了新的定义接口,称之为FinalizableReference。在这个接口中,即定义了一个相应的回调函数,如下所示:

/** 当引用被gc之后,此方法会被触发调用 */
  void finalizeReferent();

因为增加了新的接口,因此我们自己来使用的话,就即要继承于jdk的weakReference,又要实现此接口。为方便,guava定义了3套与jdk兼容的引用对象。即FinalizableWeakReference,FinalizableSoftReference和FinalizablePhantomReference。可以理解为就是一个对jdk原类型的一个适配。

继续阅读“guava中的FinalizableReferenceQueue解析”

ReferenceQueue的使用

1 何为ReferenceQueue

在java的引用体系中,存在着强引用,软引用,虚引用,幽灵引用,这4种引用类型。在正常的使用过程中,我们定义的类型都是强引用的,这种引用类型在回收中,只有当其它对象没有对这个对象的引用时,才会被GC回收掉。简单来说,对于以下定义:

Object obj = new Object();
Ref ref = new Ref(obj);

在这种情况下,如果ref没有被GC,那么obj这个对象肯定不会GC的。因为ref引用到了obj。如果obj是一个大对象呢,多个这种对象的话,应用肯定一会就挂掉了。

那么,如果我们希望在这个体系中,如果obj没有被其它对象引用,只是在这个Ref中存在引用时,就把obj对象gc掉。这时候就可以使用这里提到的Reference对象了。

我们希望当一个对象被gc掉的时候通知用户线程,进行额外的处理时,就需要使用引用队列了。ReferenceQueue即这样的一个对象,当一个obj被gc掉之后,其相应的包装类,即ref对象会被放入queue中。我们可以从queue中获取到相应的对象信息,同时进行额外的处理。比如反向操作,数据清理等。

2 使用队列进行数据监控

一个简单的例子,通过往map中放入10000个对象,每个对象大小为1M字节数组。使用引用队列监控被放入的key的回收情况。代码如下所示:

继续阅读“ReferenceQueue的使用”

Java字节码中的一些特定处理

我们在阅读JAVA字节码时,应该会对其中的一些设定有疑问。为什么是这样的呢,这里从我个人的理解对其中的一些名词进行理解,同时也方便在阅读此书的读者参考。书名为《Java虚拟机规范(Java SE 7版)》

本文包括的一些描述为以下列表

  • 常量池大小设定
  • stackMapTable属性
  • new指令后的dup
  • attribute属性
  • long和double的特殊处理
  • monitorenter和monitorexit的使用场景
  • enclosingMethod属性
  • localVariableTable和localVariableTypeTable
  • constantValue属性

常量池大小设定
常量池的大小的虽然为N,但实际的常量数量即为N-1,但并不是说它的下标值为0到N-1,它的下标是从1到N-1。这里面省略了下标值为0的值,虽然字节码中没有此值。我们可以认为下标为0的值即代表某一种null值。包括其它地方进行引用时,也采用的这个位置处理。如字节码中常量池大小为26,那么最后一个下标肯定为25.

继续阅读“Java字节码中的一些特定处理”