CPU 100% 占用率，但是怎么排查不出是哪一个线程使用最高？

java-web

前话

之前实习时负责公司标签系统的重构，由于用户身上的标签是随即变化的，也会很大，因此经过方案调研后选择采用Bitmap进行存储用户身上的标签ID信息数据。但是在前几天发生高CPU问题，怎么定位都定位不到是哪一个线程出现的高CPU，后面同为实习的小伙伴利用arthas的thread -n -i命令成功定位出问题所在（我怎么没有想到它，这就是大佬和菜鸡的区别吧～）

定位

通过arthas的thread -n -i命令发现，大多数的线程都卡在了com.googlecode.javaewah.EWAHCompressedBitmap#get方法，每一个线程始终占用9%的CPU，十多个线程下来，累加起来就引发了高CPU问题

问题代码（非公司内代码，仅仅参考）

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
private void on_ewah(int[] arrays, int[] query) {

        for (int c = 0; c < 16; c ++) {
            executorService.execute(() -> {
                EWAHCompressedBitmap bitmap = new EWAHCompressedBitmap();

                for (int i = 0; i < totalSize; i++) {
                    bitmap.set(query[i]);
                }

                long startTime = System.currentTimeMillis();

                for (int i = 0; i < totalSize; i++) {

                    int index = arrays[i];

                    if (bitmap.get(index)) {
                        bitmap.clear(index);
                    }
                }
                System.out.println("spend ewah [" + (System.currentTimeMillis() - startTime) + "] ms");
                LATCH.countDown();
            });
        }

}

分析

既然定位到了具体的问题方法，因此先看下此方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Query the value of a single bit. Relying on this method when speed is
 * needed is discouraged. The complexity is linear with the size of the
 * bitmap.
 * 
 * (This implementation is based on zhenjl's Go version of JavaEWAH.)
 * 
 * The current bitmap is not modified.
 *
 * @param i the bit we are interested in
 * @return whether the bit is set to true
 */
public boolean get(final int i) {
    ...
}

可以看到，官方的注释是说明了，此方法的时间复杂度是线性复杂度，随着bitmap的大小而变动，而我们在代码中，却又是在循环中调用这个方法，极端情况下，会导致时间复杂度升级为O(N^2)

这个时候就需要探究下为什么EWAHCompressedBitmap对于get(int index)会是线性复杂度了

创建一个EWAHCompressedBitmap

1
2
3
4
5
6
7
8
9

public EWAHCompressedBitmap() {
        this(new LongArray());
    }

private EWAHCompressedBitmap(Buffer buffer) {
        this.buffer = buffer;
        this.rlw = new RunningLengthWord(this.buffer, 0);
    }

可以看到，在EWAHCompressedBitmap中最终所有元素都存储在this.buffer中，那么存储的形式是怎么样的呢？大概用一个图描述一下

Word

如果插入一个74的话，是怎么样？首先我们需要计算74=64 * 1 + 10，因此需要两个long，第一个long是[0-63]，第二个long是[64,127]，而第一个long呢，是不存储任何元素的，因此可以被压缩，也就是Run Length的数据如下

高31位 中间23位 最低位
1 1 0

即，当前Word中，有一个Long是存储了字面量信息74的，压缩了64个bit，这64个bit具有相同的值0

picture

那么查询的时候呢？由于EWAHCompressedBitmap除了一个long[]之外，只有一个position变量指向最后一个Run Length，因此，如果要随机获取数据的话，时间复杂度就是O(N)级别的。

修改方案

第一种，采用Set对EWAHCompressedBitmap存储的数据进行copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void on_ewah(int[] arrays, int[] query) {
        for (int c = 0; c < 16; c ++) {
            executorService.execute(() -> {
                EWAHCompressedBitmap bitmap = new EWAHCompressedBitmap();
                for (int i = 0; i < totalSize; i++) {
                    bitmap.set(query[i]);
                }
                long startTime = System.currentTimeMillis();
                Set<Integer> data = new HashSet<Integer>(bitmap.toList());
                for (int i = 0; i < totalSize; i++) {
                    int index = arrays[i];
                    if (data.contains(index)) {
                        bitmap.clear(index);
                    }
                }
                System.out.println("spend ewah [" + (System.currentTimeMillis() - startTime) + "] ms");
                LATCH.countDown();
            });
        }
    }

但是者有一点不好的地方，极端情况下，EWAHCompressedBitmap存储的数组长度很可能是标签限制最大数量的两倍，假设我只允许一个用户身上只有1000个标签的话，那么bitmap有长度为2000的数组，set又copy了1000的数据，无端徒增1000个long的数据开销

第二种，采用RoaringBitmap替换EWAHCompressedBitmap

RoaringBitmap存储的数据在RoaringArray这个对象里面，这个对象我们可以看下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public final class RoaringArray implements Cloneable, Externalizable, AppendableStorage<Container> {
  private static final char SERIAL_COOKIE_NO_RUNCONTAINER = 12346;
  private static final char SERIAL_COOKIE = 12347;
  private static final int NO_OFFSET_THRESHOLD = 4;

  // bumped serialVersionUID with runcontainers, so default serialization
  // will not work...
  private static final long serialVersionUID = 8L;

  static final int INITIAL_CAPACITY = 4;

  char[] keys = null;

  Container[] values = null;

  int size = 0;
}

可以看到这里RoaringBitmap多了一个char[] keys，在根据相关源码可以发现，这个keys，是有序的，可以通过二分查找去定位某个key在什么地方

接着再看下RoaringBitmap的add方法

1
2
3
4
5
6
7
8
9
10
11
public void add(final int x) {
    final char hb = Util.highbits(x);
    final int i = highLowContainer.getIndex(hb);
    if (i >= 0) {
      highLowContainer.setContainerAtIndex(i,
          highLowContainer.getContainerAtIndex(i).add(Util.lowbits(x)));
    } else {
      final ArrayContainer newac = new ArrayContainer();
      highLowContainer.insertNewKeyValueAt(-i - 1, hb, newac.add(Util.lowbits(x)));
    }
  }

可以看到有这一行特殊的代码

1
final char hb = Util.highbits(x)

这里是去待存入数据的高16位作为key，存到keys数组里面的，在根据key，去定位一个Container用于存储这个数据，而存储的值，我们又可以看到这段代码

1
Util.lowbits(x) => (char) x

相当于将int x的低16位作为value存储到Container中，而Container的实现分为

  • ArrayContainer
  • BitmapContainer
  • RunContainer

每一个Container的get的时间复杂度都不一样

  • ArrayContainer，由于用到的是二分查找，因此时间复杂度是O(logN)
1
2
3
4
@Override
  public boolean contains(final char x) {
    return Util.unsignedBinarySearch(content, 0, cardinality, x) >= 0;
  }
  • BitmapContainer，直接进行定位
1
2
3
4
@Override
  public boolean contains(final char i) {
    return (bitmap[i >>> 6] & (1L << i)) != 0;
  }
  • RunContainer，也是二分查找，时间复杂度是O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
  public boolean contains(char x) {
    int index = unsignedInterleavedBinarySearch(valueslength, 0, nbrruns, x);
    if (index >= 0) {
      return true;
    }
    index = -index - 2; // points to preceding value, possibly -1
    if (index != -1) {// possible match
      int offset = (x) - (getValue(index));
      int le = (getLength(index));
      return offset <= le;
    }
    return false;
  }

而其实Container的查找也需要走一次二分查找，但是，Container的数量最多为1<<16 => 65535个，因此时间复杂度最大也仅仅为O(log65535)

具体博文:RoaringBitmap数据结构及原理