Skip Graphs

o problema

Em 2003, localizar recurso em rede sem autoridade central já tinha duas respostas ruins e uma boa pela metade. Napster centralizava e não escalava. Gnutella buscava por flooding e gastava em mensagem o que economizava em coordenação. Freenet não dava garantia nenhuma de latência e podia deixar de achar dado que está lá. A resposta boa era a distributed hash table: CAN, Chord, Pastry, Tapestry e Viceroy espalhavam nó e chave por um espaço de identificadores usando hash, e roteavam em O(log m) com m máquinas.

O preço era o hash. Ele distribui carga precisamente porque destrói a ordem das chaves: depois de hashear, “todas as chaves entre x e y” deixa de ser uma pergunta que a estrutura sabe responder, e recursos relacionados não ficam perto uns dos outros. Suportar range query em sistema peer-to-peer estava registrado na literatura como questão em aberto. A alternativa óbvia — distribuir uma skip list — não fecha: os poucos nós do nível mais alto são ponto único de falha e hot spot que processa fração constante das buscas, e como cada nó tem em média O(1) vizinhos, basta probabilidade constante de falha para isolar boa parte dos sobreviventes. Ainda por cima, Pastry e Chord precisam saber de antemão o tamanho do sistema ou do keyspace.

a ideia

Numa skip list existe uma torre só, e quem está no topo dela paga por todo mundo. Num skip graph existem muitas listas em cada nível, e todo nó está no topo de alguma delas: cada nó enxerga uma skip list privada, e essas n skip lists compartilham os níveis de baixo.

Quem decide o desenho é o membership vector m(x), uma palavra aleatória infinita sobre um alfabeto Σ. Para cada palavra finita w existe uma lista duplamente ligada S_w com todos os nós cujo membership vector começa por w, em ordem crescente de chave. O nível 0 é S_ε, todos os nós em sequência. Subindo, as listas se dividem por caractere até virarem singletons, em média depois de O(log n) níveis. O lema 1 fecha a construção: para qualquer palavra infinita z, a sequência S_{z↾i} é uma skip list com parâmetro p = 1/|Σ|. Por isso os algoritmos de skip list valem sem adaptação — um skip graph é um trie de skip lists.

como funciona

A busca começa no nível mais alto do nó de origem e anda para o lado da chave sem ultrapassá-la, descendo um nível sempre que o próximo passo passaria do alvo, até chegar ao nível 0. Devolve o nó da chave ou o dono da maior chave menor que ela.

ao receber ⟨search, startNode, key, level⟩ em v:
  se v.key = key: responde foundOp a startNode
  se v.key < key:
    enquanto level ≥ 0:
      se v.neighbor[R][level].key < key:
        encaminha ⟨search, ...⟩ a v.neighbor[R][level]; para
      senão: level ← level - 1
  senão: o simétrico, com neighbor[L] e comparação >
  se level < 0: responde notFoundOp a startNode

Como o caminho percorrido é o mesmo da skip list privada do nó de origem, a análise de Pugh se aplica direto: O(log n) mensagens e O(log n) tempo esperados.

O insert tem duas etapas. O novo nó u pede o maxLevel de um nó introdutor, roda uma busca por si mesmo para achar e emendar seus vizinhos no nível 0. Depois, para cada nível ℓ, ele caminha lateralmente (buddyOp) até achar os nós mais próximos s < u < y cujo membership vector coincide com o dele em ℓ+1 caracteres, e liga-se a eles no nível ℓ+1 — em média 2/p nós contatados por nível. Se outro nó entrou no meio do caminho, u avança sobre ele antes de ligar, para não quebrar a ordem. O delete é o inverso: de cima para baixo, u manda predecessor e sucessor de cada nível se apontarem entre si; quem está esperando mensagem de um delete alheio não se remove antes de responder.

Range query sai de graça: achar um elemento do intervalo custa O(log n), e o broadcast pelos r nós do intervalo custa O(log r) de tempo e O(r log n) mensagens.

o que isso custou

Ponteiro. Cada recurso mantém O(log n) links, o que dá O(n log n) links na rede inteira, contra O(m log m) de um DHT com m máquinas. Os autores admitem que é requisito de armazenamento bem maior, e que o mecanismo de reparo — cada máquina conferindo periodicamente seus links — pode virar enxurrada de mensagem. Reduzir o número de ponteiros sem perder localidade fica declarado como questão em aberto.

O insert é O(log n) contra O(log m); o paper responde que a diferença é fator constante a menos que alguma máquina guarde número superpolinomial de recursos, e que o DHT compra essa vantagem entregando consulta complexa e localidade. As consultas complexas, aliás, valem só em uma dimensão: um atributo por skip graph. O balanceamento também não vem junto: mapear cada máquina aos recursos que ela hospeda dá segurança e manageability, hashear dá boa distribuição de carga — e devolve o problema que a estrutura existia para evitar. A resiliência é assimétrica: fração grande de falhas aleatórias, sim; contra adversário escolhendo alvos, a garantia é uma fração O(1/log n). E o modelo é parcialmente síncrono com crash permanente: não trata nó malicioso nem nó que volta.

onde isso aparece hoje

A herança direta é Skip Lists, de onde vem a torre probabilística inteira; o skip graph é a resposta à pergunta de por que ela não sobrevive sozinha num sistema distribuído. Do outro lado da comparação está Chord, o DHT que o paper usa como referência de custo e que carrega, junto com o consistent hashing, exatamente a limitação denunciada aqui: chave hasheada é chave sem ordem. Bancos que vieram desse ramo, como o Dynamo, oferecem get e put por chave e deixam a varredura ordenada de fora — o mesmo trade-off, escolhido do lado oposto.

A ideia estrutural — camadas cada vez mais esparsas sobre uma lista completa, com sorteio decidindo quem sobe — reaparece fora de peer-to-peer, notadamente na busca aproximada por vizinho mais próximo do HNSW, que organiza os candidatos em níveis com a mesma lógica de express lane.