Персональный анализ исходного кода Redis 1 ---- HyperLoglog (реализация Golang)

1 кардинальная статистика

Алгоритм HLL используется для кардинальной статистики.

Что такое кардинальность статистики: например, если вам дан массив [1,2,2,3,3,5,5), мощность этого массива равна 4 (всего 4 неповторяющихся элемента). Что ж, теперь вы знаете, что такое кардинальность статистики.
Для решения этой проблемы проще всего, конечно, использовать растровое изображение для достижения каждого бита, указывающего, появилось ли число, например, для представления приведенной выше строки чисел используйте следующее растровое изображение для представления:

011101

преимущество: Относительно экономит место, и операция слияния проста, как в приведенном выше сценарии приложения 1, если вы хотите подсчитать2 дняСколько ip-адресов есть для доступа, вам нужно только вынуть растровую структуру двух дней и выполнить операцию «или».
недостаток: Сложность пространства все еще слишком велика, 1 байт имеет только 8 бит, то есть 1 байт может однозначно представлять только 8 IP-адресов (8 разных клиентов) Тогда:
1k может представлять 1024 * 8 = 8192
1М может представлять 1024 * 1024 * 8 = 8388608 (около 8 миллионов)
Если ссылок на товары много, необходимо считать ежедневные данные и т. д. Для ежедневной ссылки на каждый продукт требуется более 1 МБ памяти, что слишком много, и память не может его вместить.

相反：使用HLL ，对于精度要求不是特别高的时候，只需要12k的内存，很神奇！ ! !

2 Принцип алгоритма HLL

Чтобы привести пример подбрасывания монеты, с которым мы наиболее знакомы, вероятность выпадения орла и решки равна 1/2. Продолжайте подбрасывать монету до тех пор, пока не появится голова, запишите количество подбрасываний k и запишите процесс подбрасывания монеты. несколько раз, пока голова не появится как первичная.Процесс Нури, для n процессов Бернулли получаем n значений количества бросков головой $ k_1, k_2 ... k_n $ , где максимальное значение здесьk_max.
Видя, что это может немного сбить с толку, давайте посмотрим на проблему и свяжемся с нашей проблемой.При выполнении кардинальной статистики это на самом деле эта проблема:

Теперь цель состоит в том, чтобы придумать набор данных о количестве бросков ( $ k_1, k_2 ... k_n $ ), Вы хотите предсказать, в общей сложности многие времена делают процесс Bernoulli (предполагая n), чтобы получить такие данные ах?

По математическому выводу---прямо дайте вывод: пользуйтесь $2^{k_ max}$ как оценка n.

Например: Проделав набор процессов Бернулли, обнаружилось, что после 5 последовательных решек появилась 1 голова.Сколько процессов Бернулли надо сделать в этой ситуации? ответ: $ 2^6 = 64 $ эксперименты.

На самом деле это основа для нашей кардинальной статистики HLL.

Возвращаясь к проблеме кардинальной статистики, нам нужно подсчитать количество неповторяющихся элементов в наборе данных.После хеш-функции каждого элемента в наборе его можно выразить в виде строки двоичных чисел, состоящей из 0 и 1 Двоичная строка может быть аналогична одному разу в эксперименте с подбрасыванием монеты: 1 выпадает орлом, а 0 — решкой. Позиция первой 1 из младшей позиции в двоичной строке может быть понята как количество подбрасываний kk, при которых первый орел появляется в эксперименте с подбрасыванием монеты, тогда на основе приведенного выше вывода мы можем передать максимальный бросок орлу. в экспериментах с несколькими подбрасываниями монеты.Также можно использовать количество раз, чтобы оценить, сколько экспериментов было проведено в целом, и максимальное значение первой 1 позиции вхождения.$ k_{max}k maxОценить общее количество различных чисел (общая база).

Следовательно, основная идея HLL состоит в том, чтобы оценить общую базу первого 1 из первых 1 числа чисел в коллекции, но этот метод прогнозирования имеет большую ошибку, чтобы улучшить ошибку, HLL вводится в обыденное понятие.

Например, также возьмем подбрасывание монеты в качестве примера, если есть только один набор экспериментов с подбрасыванием монеты, удача хорошая, и первый эксперимент подбрасывается 10 раз до первого подбрасывания.Очевидно, предполагаемая ошибка количества количество экспериментов, полученных по формуле, относительно велико.Большой;если 100 групп проводят эксперимент с подбрасыванием монеты одновременно, вероятность такого везения очень мала.Общее количество экспериментов можно оценить исходя из среднего арифметического 100 групп.

В Redis используется принцип сегментирования, конкретный принцип реализации следующий: Сначала появился объект redis (строка), а после хеширования было сгенерировано 8-байтовое хеш-значение.

graph LR
A[redis object]-->|hash function| B(64 bit)

Затем используйте первые 14 бит из 64 битов в качестве нижнего индекса корзины, чтобы размер корзины был $ 2^{14} = 16348 $
Последние 50 бит эквивалентны случайному процессу Бернулли.Мы находим счетчик позиций, где впервые появляется 1. Если текущий счетчик больше, чем старый счетчик в корзине, то обновляем oldcount=count.

1.2 Сценарии применения кардинальной статистики

1. Статистика сайта Сколько в день доступ по ip адресу;
1. Подсчитайте, сколько разных клиентов посещают ссылку на продукт каждый день;
...

Приложений еще много.Вообще говоря требования статистики очень четкие.Им не нужны очень точные значения.Нужны только аналогичные оценочные значения.В то же время их не нужно хранить в наборах,потому что наборы на самом деле потребляет много памяти.Чем эффективнее структура памяти, тем лучше. На самом деле этот алгоритм HLL можно использовать для экономии памяти.

1.4 Алгоритм процесса HyperLogLog

1.4.1 Создание объекта HLL

Определение структуры заголовка HLL:


struct hllhdr {
    char magic[4];      /* "HYLL" 魔数，前面4个字节表示这是一个hll对象*/
    uint8_t encoding;   /* 存储方式，后面会讲到，分为HLL_DENSE or HLL_SPARSE两种存储方式 */
    uint8_t notused[3]; /*保留字段，因为redis是自然字节对齐的，所以空着也是空着，不如定义一下 Reserved for future use, must be zero. */
    uint8_t card[8];    /*缓存的当前hll对象的基数值 Cached cardinality, little endian. */
    uint8_t registers[]; /* Data bytes. 对于dense存储方式，这里就是一个12k的连续数组，对于sparse存储方式，这里长度是不定的，后面会讲到*/
};

Создайте объект холл:

/* Create an HLL object. We always create the HLL using sparse encoding.
 * This will be upgraded to the dense representation as needed.
 这里英文注释其实已经写的很清楚了，默认hll对象使用sparse的编码方式，这样比较节约内存，但是sparse方式存储其实比较难以理解，代码实现也比较复杂，但是对于理解来说，其实就是对于里面hll桶的存储方式的不同，HLL算法本身逻辑上没有区别
 */
robj *createHLLObject(void) {
    robj *o;
    struct hllhdr *hdr;
    sds s;
    uint8_t *p;
    int sparselen = HLL_HDR_SIZE +
                    (((HLL_REGISTERS+(HLL_SPARSE_XZERO_MAX_LEN-1)) /
                     HLL_SPARSE_XZERO_MAX_LEN)*2);  
    //头长度+(16384 + (16384-1) / 16384 * 2)，也就是2个字节，默认因为基数统计里面所有的桶都是0，用spase方式存储，只需要2个字节
    int aux;

    /* Populate the sparse representation with as many XZERO opcodes as
     * needed to represent all the registers. */
    aux = HLL_REGISTERS;
    s = sdsnewlen(NULL,sparselen);
    p = (uint8_t*)s + HLL_HDR_SIZE;
    while(aux) {
        int xzero = HLL_SPARSE_XZERO_MAX_LEN;
        if (xzero > aux) xzero = aux;
        HLL_SPARSE_XZERO_SET(p,xzero);
        p += 2;
        aux -= xzero;
    }
    serverAssert((p-(uint8_t*)s) == sparselen);

    /* Create the actual object. */
    o = createObject(OBJ_STRING,s);
    hdr = o->ptr;
    memcpy(hdr->magic,"HYLL",4);
    hdr->encoding = HLL_SPARSE;
    return o;
}

3 пфад процесс

3.1 Использование плотного хранилища

Подойдите к потоку байтов, передайте указатель void * и длину len, пройти черезMurmurHash64AФункция Вычисляет 64-битное хеш-значение. Первые 14 бит из 64 бит (это значение можно изменить) используются как индекс, а последние 50 бит используются как поток битов. 2 ^ 14 == 16384, всего 16384 корзины. Каждое ведро использует 6 бит памяти.

Следующий 50-битный поток выглядит так:
00001000....11000Первое вхождение 1 записывается как счетчик, поэтому максимальное значение счетчика равно 50, чего достаточно для представления 6 битами. 2^6 = 64

Следовательно, фактическое пространство для хранения объекта HLL составляет 16384 (сегмента) * ( 6 бит на ведро) / 8 = 12288 байт. То есть используется около 12к памяти. На самом деле это самая мощная часть redis, на самом деле, если для его хранения используется один байт, то это фактически 16к памяти, но чтобы сохранить 4к памяти, их создается куча. Это сохраняется только в плотном режиме, что является относительно пустой тратой места.Хранение в разреженном режиме, описанное ниже, более экономит место.

После вычисления индекса (индекс корзины) и счетчика (позиция, в которой 1 появляется впервые в следующих 50 битах), следующим шагом будет обновление корзины. Найдите ведро по индексу, а затем посмотрите, больше ли текущий счетчик, чем старый. Если он больше, обновите oldcount = count. В это время, ради производительности, текущая кардинальность не будет подсчитываться, но флаг в заголовке HLL будет установлен в 1, указывая, что при следующем выполнении операции pfcount текущее значение кэша устарело и требует для повторного подсчета значение кэша. В более позднем процессе pfcount, если будет обнаружено, что эта метка недействительна, он пересчитает новую кардинальность и поместит ее в кеш кардинальности.

/* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */
int hllAdd(robj *o, unsigned char *ele, size_t elesize) {
    struct hllhdr *hdr = o->ptr;
    switch(hdr->encoding) {
    case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);
    case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);//sparse
    default: return -1; /* Invalid representation. */
    }
}



/* "Add" the element in the dense hyperloglog data structure.
 * Actually nothing is added, but the max 0 pattern counter of the subset
 * the element belongs to is incremented if needed.
 *
 * This is just a wrapper to hllDenseSet(), performing the hashing of the
 * element in order to retrieve the index and zero-run count. */
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
    long index;
    uint8_t count = hllPatLen(ele,elesize,&index);//index就是桶的下标， count则是后面50个bit位中1第一次出现的位置
    /* Update the register if this element produced a longer run of zeroes. */
    return hllDenseSet(registers,index,count);
}


/* ================== Dense representation implementation  ================== */

/* Low level function to set the dense HLL register at 'index' to the
 * specified value if the current value is smaller than 'count'.
 *
 * 'registers' is expected to have room for HLL_REGISTERS plus an
 * additional byte on the right. This requirement is met by sds strings
 * automatically since they are implicitly null terminated.
 *
 * The function always succeed, however if as a result of the operation
 * the approximated cardinality changed, 1 is returned. Otherwise 0
 * is returned. */
int hllDenseSet(uint8_t *registers, long index, uint8_t count) {
    uint8_t oldcount;
    //找到对应的index获取其中的值
    HLL_DENSE_GET_REGISTER(oldcount,registers,index);
    if (count > oldcount) { //如果新的值比老的大，就更新来的
        HLL_DENSE_SET_REGISTER(registers,index,count);
        return 1;
    } else {
        return 0;
    }
}



/* Given a string element to add to the HyperLogLog, returns the length
 * of the pattern 000..1 of the element hash. As a side effect 'regp' is
 * set to the register index this element hashes to. */
int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
    uint64_t hash, bit, index;
    int count;

    /* Count the number of zeroes starting from bit HLL_REGISTERS
     * (that is a power of two corresponding to the first bit we don't use
     * as index). The max run can be 64-P+1 = Q+1 bits.
     *
     * Note that the final "1" ending the sequence of zeroes must be
     * included in the count, so if we find "001" the count is 3, and
     * the smallest count possible is no zeroes at all, just a 1 bit
     * at the first position, that is a count of 1.
     *
     * This may sound like inefficient, but actually in the average case
     * there are high probabilities to find a 1 after a few iterations. */
    hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
    index = hash & HLL_P_MASK; /* Register index. */
    hash >>= HLL_P; /* Remove bits used to address the register. */
    hash |= ((uint64_t)1<<HLL_Q); /* Make sure the loop terminates
                                     and count will be <= Q+1. */
    bit = 1;
    count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */
    while((hash & bit) == 0) {
        count++;
        bit <<= 1;
    }
    *regp = (int) index;

    serverLog(LL_NOTICE,"pf hash idx=%d, count=%d", index, count);
    return count;
}

3.2 процесс подсчета пф

Процесс статистической кардинальности, если флаг кеша действителен, возвращает значение кеша напрямую, в противном случае пересчитывает все 16384 сегмента HLL, а затем выполняет статистическую коррекцию. Конкретный принцип коррекции требует большого количества математических знаний и документов.

/* Return the approximated cardinality of the set based on the harmonic
 * mean of the registers values. 'hdr' points to the start of the SDS
 * representing the String object holding the HLL representation.
 *
 * If the sparse representation of the HLL object is not valid, the integer
 * pointed by 'invalid' is set to non-zero, otherwise it is left untouched.
 *
 * hllCount() supports a special internal-only encoding of HLL_RAW, that
 * is, hdr->registers will point to an uint8_t array of HLL_REGISTERS element.
 * This is useful in order to speedup PFCOUNT when called against multiple
 * keys (no need to work with 6-bit integers encoding). */
uint64_t hllCount(struct hllhdr *hdr, int *invalid) {
    double m = HLL_REGISTERS;
    double E;
    int j;
    int reghisto[HLL_Q+2] = {0};

    /* Compute register histogram */
    if (hdr->encoding == HLL_DENSE) {
        hllDenseRegHisto(hdr->registers,reghisto);
    } else if (hdr->encoding == HLL_SPARSE) {
        hllSparseRegHisto(hdr->registers,
                         sdslen((sds)hdr)-HLL_HDR_SIZE,invalid,reghisto);
    } else if (hdr->encoding == HLL_RAW) {
        hllRawRegHisto(hdr->registers,reghisto);
    } else {
        serverPanic("Unknown HyperLogLog encoding in hllCount()");
    }

    /* Estimate cardinality form register histogram. See:
     * "New cardinality estimation algorithms for HyperLogLog sketches"
     * Otmar Ertl, arXiv:1702.01284 */
    //这里具体的修正流程，要去看论文，就照着抄过来实现就可以了。 
    double z = m * hllTau((m-reghisto[HLL_Q+1])/(double)m);
    for (j = HLL_Q; j >= 1; --j) {
        z += reghisto[j];
        z *= 0.5;
    }
    z += m * hllSigma(reghisto[0]/(double)m);
    E = llroundl(HLL_ALPHA_INF*m*m/z);

    return (uint64_t) E;
}

4. Постскриптум

На самом деле принцип очень простой, и он требует много математических знаний, и понять все это невозможно, я должен чувствовать, что экономия памяти Redis действительно ненормальна. Для разреженного режима сэкономленная память наводит еще больший ужас, потому что на самом деле это мало влияет на понимание принципа работы алгоритма hll, поэтому в этой статье мы не будем его подробно представлять.

Наконец, вставьте код гиперлоглога, который я имитировал с помощью golang:

package goRedis

import (
	"bytes"
	"encoding/binary"
	"fmt"
	"math"
)

const seed = 0xadc83b19

const hll_dense = 1
const hll_sparse = 2

const hll_p = 14
const hll_q = 64 - hll_p
const hll_registers = 1 << hll_p
const hll_p_mask = hll_registers - 1
const hll_bits = 6
const hll_sparse_val_max_value = 32
const hll_alpha_inf = 0.721347520444481703680

type hllhdr struct {
	magic      string
	encoding   uint8
	notused    [3]uint8
	card       [8]uint64
	registers  []byte //实际存储的，因为后面如果encoding方式采用sparse的话，长度会变化，所以使用slice比较好
	vaildCache bool
}

func initHLL(encoding uint8) *hllhdr {
	hdr := new(hllhdr)
	hdr.magic = "HYLL"
	hdr.encoding = encoding

	if encoding == hll_dense {
		hdr.registers = make([]byte, hll_registers*1) // 先简单实现下 用一个字节存6个bit
	} else {
		panic("HLL SPARSE encoding format doesn't support.")
	}
	return hdr
}

func hllDenseSet(hllObj *hllhdr, index uint64, count int) bool {
	if count > int(hllObj.registers[index]) {
		hllObj.registers[index] = byte(count)
		return true
	}
	return false
}

func PfAddCommand(hllObj *hllhdr, val []byte) {
	index, count := hllPartLen(val)
	if hllObj.encoding == hll_dense {
		hllDenseSet(hllObj, index, count)
		hllObj.vaildCache = false
	} else {
		panic("HLL SPARSE encoding format doesn't support.")
	}
}

func hllTau(x float64) float64 {
	if x == 0. || x == 1. {
		return 0.
	}
	var zPrime float64
	y := 1.0
	z := 1 - x
	for {
		x = math.Sqrt(x)
		zPrime = z
		y *= 0.5
		z -= math.Pow(1-x, 2) * y
		if zPrime == z {
			break
		}
	}
	return z / 3

}

func hllDenseRegHisto(hllObj *hllhdr, reghisto *[hll_q + 2]int) {
	for i := 0; i < hll_registers; i++ {
		reg := hllObj.registers[i]
		reghisto[reg]++
	}
}

func hllSigma(x float64) float64 {
	if x == 1. {
		return math.MaxInt64
	}
	var zPrime float64
	y := float64(1)
	z := x
	for {
		x *= x
		zPrime = z
		z += x * y
		y += y
		if zPrime == z {
			break
		}
	}
	return z
}

func hllCount(hllObj *hllhdr) int {
	m := float64(hll_registers)
	var reghisto [hll_q + 2]int
	if hllObj.encoding == hll_dense {
		hllDenseRegHisto(hllObj, &reghisto)
	} else {
		panic("impliment me..")
	}

	z := m * hllTau((m - (float64(reghisto[hll_q+1]))/m))
	for j := hll_q; j >= 1; j-- {
		z += float64(reghisto[j])
		z *= 0.5
	}
	z += m * hllSigma(float64(reghisto[0])/m)
	E := math.Round(hll_alpha_inf * m * m / z)

	return int(E)

}

func PfCountCommand(hllObj *hllhdr) int {
	var ret int
	if hllObj.vaildCache {
		return 0
	} else {
		ret = hllCount(hllObj)
	}

	return ret
}

func CreateHLLObject() *hllhdr {
	hdr := initHLL(hll_dense)
	return hdr
}

func Murmurhash(buff []byte, seed uint32) uint64 {
	buffLen := uint64(len(buff))
	m := uint64(0xc6a4a7935bd1e995)
	r := uint32(47)
	h := uint64(seed) ^ (buffLen * m)

	for i := uint64(0); i < buffLen-(buffLen&7); {
		var k uint64
		bBuffer := bytes.NewBuffer(buff[i : i+8])
		binary.Read(bBuffer, binary.LittleEndian, &k)

		k *= m
		k ^= k >> r
		k *= m
		h ^= k
		h *= m

		binary.Write(bBuffer, binary.LittleEndian, &k)
		i += 8
	}
	switch buffLen & 7 {
	case 7:
		h ^= uint64(buff[6]) << 48
		fallthrough
	case 6:
		h ^= uint64(buff[5]) << 40
		fallthrough
	case 5:
		h ^= uint64(buff[4]) << 32
		fallthrough
	case 4:
		h ^= uint64(buff[3]) << 24
		fallthrough
	case 3:
		h ^= uint64(buff[2]) << 16
		fallthrough
	case 2:
		h ^= uint64(buff[1]) << 8
		fallthrough
	case 1:
		h ^= uint64(buff[0])
		fallthrough
	default:
		h *= m
	}

	h ^= h >> r
	h *= m
	h ^= h >> r
	return h
}

func hllPartLen(buff []byte) (index uint64, count int) {
	hash := Murmurhash(buff, seed)
	index = hash & uint64(hll_p_mask) //这里就是取出后14个bit，作为index
	hash >>= hll_p                    //右移把后面14个bit清理掉,注意这里的bit流其实是倒序的
	hash |= uint64(1) << hll_q        //当前的最高位设置1，其实是一个哨兵，避免count为0
	bit := uint64(1)
	count = 1
	for (hash & bit) == 0 {
		count++
		bit <<= 1
	}
	fmt.Printf("pf hash idx=%d, count=%d\n", index, count)

	return index, count
}

//func hllSparseSet(o, index int64, count int64) {
//	if count > hll_sparse_val_max_value {
//		goto promote
//	}
//
//promote:
//}

Тестовый код:

func TestAll(t *testing.T) {
	hllObj := CreateHLLObject()
	test1 := []string{"apple", "apple", "orange", "ttt", "aaa"}

	for _, str := range test1 {
		PfAddCommand(hllObj, []byte(str))
	}

	println(PfCountCommand(hllObj))
}