Visão Geral

Como as estruturas subjacentes para set e hash já foram abordadas anteriormente, e dada sua complexidade inferior em comparação com a quicklist, este artigo apresenta uma análise completa dessas duas estruturas em um único bloco.

Determinando Qual Função é Invocada por um Comando

Para identificar o fluxo de execução de um comando específico, consulte os recursos disponíveis no blog relacionado.

Conjunto (Set)

O tipo set utiliza três representações internas: listpack, intset e hashtable. A transição entre elas depende do tipo de codificação atual e dos limites configuráveis como size_hint, server.set_max_listpack_entries e server.set_max_intset_entries.

• Conversão unidirecional: O set pode ser convertido de listpack ou intset para hashtable, mas não há suporte para retornar ao formato original. Também não há conversão direta entre listpack e intset.
• Seleção inicial: Ao criar um novo conjunto, o Redis verifica se o primeiro elemento pode ser interpretado como inteiro. Com base na quantidade de elementos (passada via size_hint), decide-se se inicia com intset.
• Otimizações de memória: O armazenamento em hashtable inclui melhorias específicas para reduzir o uso de memória — detalhadas em outras publicações.
• Iteração combinada: O iterador do set é capaz de percorrer elementos de qualquer uma das três estruturas internas de forma transparente.
• Operação de interseção: Antes da execução, os conjuntos são ordenados pelo tamanho crescente. Em seguida, itera-se sobre o menor conjunto, verificando a presença de cada elemento nos demais.

for each element in smallest_set:
  for each set in other_sets:
    if element not in set:
      remove element from smallest_set

• União e diferença compartilham lógica: Ambas as operações usam uma mesma função interna. A união exige varredura completa de todos os elementos, enquanto a diferença pode ser otimizada.
• Algoritmo de diferença 1 (complexidade O(n·m)): Para cada elemento no conjunto menor, verifica-se sua presança em todos os outros conjuntos.
• Algoritmo de diferença 2 (complexidade O(N)): Itera-se sobre os outros conjuntos e remove apenas os elementos presentes no menor.

for each element in other_sets:
  if element in smallest_set:
    remove element from smallest_set

• Implementação do intset: Representado como um array ordenado. Busca usa busca binária; inserção requer deslocamento de elementos após a posição de inserção.

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;

    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is, mid);
        if (value > cur) {
            min = mid + 1;
        } else if (value < cur) {
            max = mid - 1;
        } else {
            break;
        }
    }
    // ...
}

• Expansão de intset: Diferentemente de vetores dinâmicos como em C++, o aumento de tamanho é feito incrementando apenas uma posição, não dobrando o espaço.

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    // ...
    is = intsetResize(is, intrev32ifbe(is->length) + 1);
    if (pos < intrev32ifbe(is->length))
        intsetMoveTail(is, pos, pos + 1);
    // ...
}

Hash (Map)

O tipo hash funciona como um mapa chave-valer, implementado usando listpack, listpack extended ou hashtable. A conversão para hashtable ocorre quando:

• O comprimento de uma string inserida excede server.hash_max_listpack_value;
• O número total de campos ultrapassar server.hash_max_listpack_entries;
• O listpack não conseguir mais adicionar novos elementos.

Observa-se que mesmo um listpack ocupando mais de 1 GB pode permanecer ativo — porém, isso só aconteceria com configurações extremas de hash_max_listpack_entries e hash_max_listpack_value. Na função hashTypeAdd, há uma verificação pós-inserção que pode acionar a conversão.

size_t new_fields = (end - start + 1) / 2;
if (new_fields > server.hash_max_listpack_entries) {
    hashTypeConvert(o, OBJ_ENCODING_HT, &db->hexpires);
    dictExpand(o->ptr, new_fields);
    return;
}

for (i = start; i <= end; i++) {
    if (!sdsEncodedObject(argv[i])) continue;
    size_t len = sdslen(argv[i]->ptr);
    if (len > server.hash_max_listpack_value) {
        hashTypeConvert(o, OBJ_ENCODING_HT, &db->hexpires);
        return;
    }
    sum += len;
}
if (!lpSafeToAdd(hashTypeListpackGetLp(o), sum))
    hashTypeConvert(o, OBJ_ENCODING_HT, &db->hexpires);

• Falta de operações de conjunto: O hash não oferece operações como hdiff, apesar de ter sido proposto. O autor do recurso admitiu falta de clareza sobre cenários práticos, conforme discutido no issue #12879.
• Menor otimização de memória: Diferentemente do set, o hash não possui tantas otimizações de armazenamento.
• Tempo de expiração: Como o hash suporta tempo de expiração, ele precisa de acesso à hora atual. O Redis usa gettimeofday com cache, embora o mecanismo exato de atualização ainda seja tema de estudo futuro.