HLL是什么

HyperLogLog（HLL）算法经常在数据库中被用来统计某一字段的Distinct Value，比如Redis的HyperLogLog结构。目前在我们项目中用于UV统计。
网上有一篇大佬博文十分深入：
https://www.jianshu.com/p/55defda6dcd2
注意：
1.此算法是近似估算值，该算法能在一定误差内近似统计去重数，可以输出空间内去重数大小，若要求UV详细数据则该方法不适用。
2.需要在空间与准确性中取舍。若要求准确性较高，则HLL生成的空间就会较大。

基本流程

统计基本流程：

说明：

• hll空间处理时一般使用的是对象字节，而存储时一般不会将对象字节存入，所以这里我们可以将空间对象转换为base64再存储。
• 这里涉及到对放入对象的hash处理，这里的hash方法值十分重要，直接影响到基数准确与否，目前我们使用的Guava工具包： com.google.common.hash.HashFunction#hashString

具体实现(Java)

HLL我们使用的工具包为java-hll
地址：java-hll

     /*** 根据value向指定key空间进行基数整合* @param ea* @param moduleKey 模块key* @param key 模块中物料 key* @param value 新增value*/public void incrementUV(String ea, String moduleKey, String key, String value){Preconditions.checkArgument(!Strings.isNullOrEmpty(ea));Preconditions.checkArgument(!Strings.isNullOrEmpty(moduleKey));Preconditions.checkArgument(!Strings.isNullOrEmpty(key));Preconditions.checkArgument(!Strings.isNullOrEmpty(value));SerializableHLL existedHLL;// 从库中获取是否有对应hll_valueString existedHllBytesBase64 = uvHllStatisticDao.getHllValue(ea, moduleKey, key);if(existedHllBytesBase64 == null){// 创建一个新的空间existedHLL = HLLUtil.newHLL();}else{// 将已有的数据转换为空间existedHLL = HLLUtil.newHLLFromBytesBase64(existedHllBytesBase64);}// 在空间中添加数据existedHLL.addRaw(HLLUtil.hash(value));// 计算空间内数据总数long newCount = existedHLL.cardinality();uvHllStatisticDao.upsertHllValuesAndCount(ea, moduleKey, key, existedHLL.toBytesBase64(), (int)newCount);}

上面方法是其中一个使用案例，在这里封装了一个HLLUtil的工具包

public class HLLUtil {/*** log2m 桶数的log-base-2 比如桶数为64，则log2m=6，该参数应在4-30之间*/private static final int LOG2M = 8;/*** 每个桶的位数，在1-8之间（最大为一个字节）*/private static final int REG_WIDTH = 8;/*** 当EXPLICIT提升为SPARSE的阈值，取值为1-18*/private static final int EXP_THRESH = 5;private static final HashFunction HASH_FUNCTION = Hashing.murmur3_128(1853);public static SerializableHLL newHLL(){/*** 第三个参数：标识SPARSE是否被使用* 第四个参数：计算的类型* EXPLICIT 进准存储，基于Long的Hashset* SPARSE 稀疏计算，数据量不大时为节省空间，只保存有值的桶* FULL 大部分桶有值时，用位向量存储桶内内容*/HLL hll = new HLL(LOG2M, REG_WIDTH, EXP_THRESH, false, HLLType.EXPLICIT);return new SerializableHLL(hll);}public static SerializableHLL newHLL(byte[] hllSpace){HLL hll = HLL.fromBytes(hllSpace);return new SerializableHLL(hll);}public static SerializableHLL newHLLFromBytesBase64(String base64){return new SerializableHLL(HLL.fromBytes(Base64.getDecoder().decode(base64)));}/*** 使用的是EXPLICIT计算方式所以需要计算Hash这里使用的是Guava 工具包* @return hash值*/public static long hash(CharSequence charSequence){return HASH_FUNCTION.hashString(charSequence, Charset.forName("UTF-8")).asLong();}
}

HLL 序列化对象类

public class SerializableHLL implements Serializable {private static final long serialVersionUID = 1L;private transient HLL targetHLL;public SerializableHLL(HLL targetHLL) {this.targetHLL = targetHLL;}public synchronized void addRaw(final long rawValue) {targetHLL.addRaw(rawValue);}public synchronized long cardinality() {return targetHLL.cardinality();}public synchronized byte[] toBytes(){return targetHLL.toBytes();}public synchronized String toBytesBase64(){return Base64.getEncoder().encodeToString(targetHLL.toBytes());}public synchronized void merge(SerializableHLL hll){this.targetHLL.union(hll.targetHLL);}public synchronized void merge(byte[] hllSpace){this.targetHLL.union(HLL.fromBytes(hllSpace));}private void writeObject(ObjectOutputStream oos) throws IOException{oos.defaultWriteObject();byte[] bs = targetHLL.toBytes();oos.writeInt(bs.length);oos.write(bs);}private void readObject(ObjectInputStream ois) throws IOException, ClassNotFoundException{ois.defaultReadObject();int byteLength = ois.readInt();byte[] bs = new byte[byteLength];ois.read(bs);targetHLL = HLL.fromBytes(bs);}
}