StringCache是啥？

​ 众所周知，http协议是文本协议，因此传输过程中的ByteChunk和CharChunk最终都会转为String。tomcat为了减少内存占用，减少对GC的影响，提出了StringCache的解决方案。

​ 先看下StringCache的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// org.apache.tomcat.util.buf.StringCache
/**
 * This class implements a String cache for ByteChunk and CharChunk.
 *
 * @author Remy Maucherat
 */
public class StringCache {
  /**
     * Statistics hash map for byte chunk.
     */
    protected static final HashMap<ByteEntry,int[]> bcStats =
            new HashMap<>(cacheSize);


    /**
     * toString count for byte chunk.
     */
    protected static int bcCount = 0;


    /**
     * Cache for byte chunk.
     */
    protected static ByteEntry[] bcCache = null;


    /**
     * Statistics hash map for char chunk.
     */
    protected static final HashMap<CharEntry,int[]> ccStats =
            new HashMap<>(cacheSize);


    /**
     * toString count for char chunk.
     */
    protected static int ccCount = 0;


    /**
     * Cache for char chunk.
     */
    protected static CharEntry[] ccCache = null;


    /**
     * Access count.
     */
    protected static int accessCount = 0;


    /**
     * Hit count.
     */
    protected static int hitCount = 0;


    // ------------------------------------------------------------ Properties
}

StringCache包含两类，一类是ByteChunk转过来的，一类是CharChunk转过来的。底层的缓存逻辑是一致的，只是类型不同，我们只需关注一种即可。缓存使用数组实现，以ByteChunk为例，数组的类型是ByteEntry:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//org.apache.tomcat.util.buf.StringCache.ByteEntry
   // -------------------------------------------------- ByteEntry Inner Class
private static class ByteEntry {

  // 底层的byte数组
  private byte[] name = null;
  // String的字符集
  private Charset charset = null;
  // 对应的String实现
  private String value = null;

  @Override
  public String toString() {
    return value;
  }
  @Override
  public int hashCode() {
    return value.hashCode();
  }
  @Override
  public boolean equals(Object obj) {
    if (obj instanceof ByteEntry) {
      return value.equals(((ByteEntry) obj).value);
    }
    return false;
  }
}

这个类一目了然，这里不再赘述。当调用StringCache的toString方法时，会优先从cache中取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// org.apache.tomcat.util.buf.StringCache#toString(org.apache.tomcat.util.buf.ByteChunk)
if (bcCache == null) {
  // 缓存维护逻辑，此处省略，后面会讲
} else {
  // 调用计数
  accessCount++;
  // Find the corresponding String
  // 二分查找
  String result = find(bc);
  if (result == null) {
    // 没有命中，直接走原来的逻辑
    return bc.toStringInternal();
  }
  // Note: We don't care about safety for the stats
  // 命中计数
  hitCount++;
  return result;
}

cache的查找使用的是二分法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//org.apache.tomcat.util.buf.StringCache#findClosest(org.apache.tomcat.util.buf.ByteChunk, org.apache.tomcat.util.buf.StringCache.ByteEntry[], int)
/**
     * Find an entry given its name in a sorted array of map elements.
     * This will return the index for the closest inferior or equal item in the
     * given array.
     * @param name The name to find
     * @param array The array in which to look
     * @param len The effective length of the array
     * @return the position of the best match
     */
protected static final int findClosest(ByteChunk name, ByteEntry[] array,
                                       int len) {

  // 二分查找的low和high
  int a = 0;
  int b = len - 1;

  // Special cases: -1 and 0
  if (b == -1) {
    return -1;
  }

  if (compare(name, array[0].name) < 0) {
    return -1;
  }
  if (b == 0) {
    return 0;
  }
	// 以上是特殊的case
  int i = 0;
  while (true) {
    // 取中间坐标，用位运算避免溢出风险
    i = (b + a) >>> 1;
    // compare的结果， -1, 0, 1
    int result = compare(name, array[i].name);
    // 在右侧，更新low
    if (result == 1) {
      a = i;
    } else if (result == 0) {
      // 正好查找到
      return i;
    } else {
      // 在左侧，缩减high
      b = i;
    }
    // 特殊情况
    if ((b - a) == 1) {
      int result2 = compare(name, array[b].name);
      if (result2 < 0) {
        return a;
      } else {
        return b;
      }
    }
  }

}

缓存维护

缓存的核心是缓存的维护。StringCache更像一个半成品，采用固定长度的缓存。

在启动初期，有一个训练的阈值，调用次数没有达到阈值之前，只会做stat；超过阈值之后，才会根据前面统计到的stat来构建cache。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
// org.apache.tomcat.util.buf.StringCache#toString(org.apache.tomcat.util.buf.ByteChunk)
// If the cache is null, then either caching is disabled, or we're
// still training
if (bcCache == null) {
  // bcCache为空，1.在training阶段，2. cache被禁用了
  // 所以这里直接调用了对应的toString方法
  String value = bc.toStringInternal();
  // 缓存开关打开了，开始构建缓存的统计信息
  // 这里有个String上线的限制，有相应的bug：https://bz.apache.org/bugzilla/show_bug.cgi?id=41057
  if (byteEnabled && (value.length() < maxStringSize)) {
    // If training, everything is synced
    synchronized (bcStats) {
      // If the cache has been generated on a previous invocation
      // while waiting for the lock, just return the toString
      // value we just calculated
      // double checked lock, 在同步代码块中再次check
      if (bcCache != null) {
        return value;
      }
      // Two cases: either we just exceeded the train count, in
      // which case the cache must be created, or we just update
      // the count for the string
      // 超过训练阈值，构建cache逻辑
      if (bcCount > trainThreshold) {
        long t1 = System.currentTimeMillis();
        // Sort the entries according to occurrence
        // stats中每个item的出现次数
        TreeMap<Integer,ArrayList<ByteEntry>> tempMap =
          new TreeMap<>();
        for (Entry<ByteEntry,int[]> item : bcStats.entrySet()) {
          ByteEntry entry = item.getKey();
          int[] countA = item.getValue();
          Integer count = Integer.valueOf(countA[0]);
          // Add to the list for that count
          ArrayList<ByteEntry> list = tempMap.get(count);
          if (list == null) {
            // Create list
            list = new ArrayList<>();
            tempMap.put(count, list);
          }
          list.add(entry);
        }
        // Allocate array of the right size
        // 不能超过缓存的上限
        int size = bcStats.size();
        if (size > cacheSize) {
          size = cacheSize;
        }
        ByteEntry[] tempbcCache = new ByteEntry[size];
        // Fill it up using an alphabetical order
        // and a dumb insert sort
        ByteChunk tempChunk = new ByteChunk();
        int n = 0;
        while (n < size) {
          // TreeMap，这里取lastKey就是出现次数最多的
          Object key = tempMap.lastKey();
          ArrayList<ByteEntry> list = tempMap.get(key);
          // 出现次数并列的情况
          for (int i = 0; i < list.size() && n < size; i++) {
            ByteEntry entry = list.get(i);
            tempChunk.setBytes(entry.name, 0,
                               entry.name.length);
            // 二分查找，找到插入位置
            int insertPos = findClosest(tempChunk,
                                        tempbcCache, n);
            if (insertPos == n) {
              tempbcCache[n + 1] = entry;
            } else {
              System.arraycopy(tempbcCache, insertPos + 1,
                               tempbcCache, insertPos + 2,
                               n - insertPos - 1);
              tempbcCache[insertPos + 1] = entry;
            }
            n++;
          }
          // 删除掉已经处理的
          tempMap.remove(key);
        } // while loop
        bcCount = 0;
        // 构建完成，清理掉stat数据
        bcStats.clear();
        bcCache = tempbcCache;
        if (log.isDebugEnabled()) {
          long t2 = System.currentTimeMillis();
          log.debug("ByteCache generation time: " +
                    (t2 - t1) + "ms");
        }
      } else {
        // ----------------- 以下是收集训练数据的过程 -----------------
        bcCount++;
        // Allocate new ByteEntry for the lookup
        ByteEntry entry = new ByteEntry();
        entry.value = value;
        int[] count = bcStats.get(entry);
        if (count == null) {
          int end = bc.getEnd();
          int start = bc.getStart();
          // Create byte array and copy bytes
          entry.name = new byte[bc.getLength()];
          System.arraycopy(bc.getBuffer(), start, entry.name,
                           0, end - start);
          // Set encoding
          entry.charset = bc.getCharset();
          // Initialize occurrence count to one
          count = new int[1];
          count[0] = 1;
          // Set in the stats hash map
          bcStats.put(entry, count);
        } else {
          // 更新出现的次数
          count[0] = count[0] + 1;
        }
      }
    }
  }
  return value;
} else {
  // 走缓存的逻辑，这里忽略
}

tomcat相关开关

  • tomcat.util.buf.StringCache.cacheSize

    • 缓存大小
    • 默认200个entry

  • tomcat.util.buf.StringCache.byte.enabled

    • ByteChunk缓存开关
    • 默认开启

  • tomcat.util.buf.StringCache.char.enabled

    • CharChunk缓存开关
    • 默认关闭

  • tomcat.util.buf.StringCache.trainThreshold

    • 采样次数的阈值
    • 默认20000

  • tomcat.util.buf.StringCache.maxStringSize

性能影响

从源码角度看，这个缓存的开销主要有两部分：

  • 缓存生成的开销（前期统计和缓存生成）
  • 缓存使用的开销（底层是有序数组，使用二分法查找）

tomcat默认的缓存大小是200，但是这个ByteChunk非常底层，uri中的参数、postbody中的内容、header中的内容等都会使用到，很容易被污染。而且缓存的效果取决于启动初期的流量，如果是预热请求，收集到的采样数据可能不准确。

生产环境，通过观测，有些场景下，cpu开销约为1%，主要花费在二分查找上：

看看是啥？

  • dump出来内存，直接看StringCache存了什么：

  • 使用arthas查看tomcat暴露出来的mbean信息

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    [arthas@96]$ mbean | grep -i StringCache
    Catalina:type=StringCache
    [arthas@96]$ mbean Catalina:type=StringCache
     OBJECT_NAME     Catalina:type=StringCache                                                                                                               
    --------------------------------------------------------                                                                                                 
     NAME            VALUE                                                                                                                                   
    --------------------------------------------------------                                                                                                 
     accessCount     2120845422                                                                                                                              
     modelerType     org.apache.tomcat.util.buf.StringCache                                                                                                  
     hitCount        1218278493                                                                                                                              
     cacheSize       200                                                                                                                                     
     trainThreshold  20000                                                                                                                                   
     charEnabled     false                                                                                                                                   
     byteEnabled     true

    注意，计数存在溢出的情况。

参考