Como parte de nosso processo de ETL, comparamos as linhas do teste com o banco de dados de relatórios para descobrir se alguma das colunas realmente mudou desde que os dados foram carregados pela última vez.
A comparação é baseada na chave exclusiva da tabela e em algum tipo de hash de todas as outras colunas. Atualmente, usamos HASHBYTES
com o SHA2_256
algoritmo e descobrimos que ele não é dimensionado em servidores grandes se muitos threads de trabalho simultâneos estiverem chamando HASHBYTES
.
A taxa de transferência medida em hashes por segundo não aumenta além de 16 threads simultâneos ao testar em um servidor de 96 núcleos. Eu testo alterando o número de MAXDOP 8
consultas simultâneas de 1 a 12. O teste com MAXDOP 1
mostrou o mesmo gargalo de escalabilidade.
Como solução, quero tentar uma solução SQL CLR. Aqui está minha tentativa de declarar os requisitos:
- A função deve ser capaz de participar de consultas paralelas
- A função deve ser determinística
- A função deve receber uma entrada de uma string
NVARCHAR
ou (todas as colunas relevantes são concatenadas)VARBINARY
- O tamanho de entrada típico da string será de 100 a 20.000 caracteres. 20000 não é um máximo
- A chance de uma colisão de hash deve ser aproximadamente igual ou melhor que o algoritmo MD5.
CHECKSUM
não funciona para nós porque há muitas colisões. - A função deve ser bem dimensionada em servidores grandes (a taxa de transferência por encadeamento não deve diminuir significativamente à medida que o número de encadeamentos aumenta)
Para Application Reasons™, suponha que não posso salvar o valor do hash para a tabela de relatórios. É um CCI que não suporta gatilhos ou colunas computadas (há outros problemas também nos quais não quero entrar).
O que é uma maneira escalável de simular HASHBYTES
usando uma função SQL CLR? Meu objetivo pode ser expresso como obter o maior número possível de hashes por segundo em um servidor grande, portanto, o desempenho também importa. Eu sou terrível com CLR, então não sei como fazer isso. Se isso motivar alguém a responder, pretendo adicionar uma recompensa a essa pergunta assim que puder. Abaixo está um exemplo de consulta que ilustra muito aproximadamente o caso de uso:
DROP TABLE IF EXISTS #CHANGED_IDS;
SELECT stg.ID INTO #CHANGED_IDS
FROM (
SELECT ID,
CAST( HASHBYTES ('SHA2_256',
CAST(FK1 AS NVARCHAR(19)) +
CAST(FK2 AS NVARCHAR(19)) +
CAST(FK3 AS NVARCHAR(19)) +
CAST(FK4 AS NVARCHAR(19)) +
CAST(FK5 AS NVARCHAR(19)) +
CAST(FK6 AS NVARCHAR(19)) +
CAST(FK7 AS NVARCHAR(19)) +
CAST(FK8 AS NVARCHAR(19)) +
CAST(FK9 AS NVARCHAR(19)) +
CAST(FK10 AS NVARCHAR(19)) +
CAST(FK11 AS NVARCHAR(19)) +
CAST(FK12 AS NVARCHAR(19)) +
CAST(FK13 AS NVARCHAR(19)) +
CAST(FK14 AS NVARCHAR(19)) +
CAST(FK15 AS NVARCHAR(19)) +
CAST(STR1 AS NVARCHAR(500)) +
CAST(STR2 AS NVARCHAR(500)) +
CAST(STR3 AS NVARCHAR(500)) +
CAST(STR4 AS NVARCHAR(500)) +
CAST(STR5 AS NVARCHAR(500)) +
CAST(COMP1 AS NVARCHAR(1)) +
CAST(COMP2 AS NVARCHAR(1)) +
CAST(COMP3 AS NVARCHAR(1)) +
CAST(COMP4 AS NVARCHAR(1)) +
CAST(COMP5 AS NVARCHAR(1)))
AS BINARY(32)) HASH1
FROM HB_TBL WITH (TABLOCK)
) stg
INNER JOIN (
SELECT ID,
CAST(HASHBYTES ('SHA2_256',
CAST(FK1 AS NVARCHAR(19)) +
CAST(FK2 AS NVARCHAR(19)) +
CAST(FK3 AS NVARCHAR(19)) +
CAST(FK4 AS NVARCHAR(19)) +
CAST(FK5 AS NVARCHAR(19)) +
CAST(FK6 AS NVARCHAR(19)) +
CAST(FK7 AS NVARCHAR(19)) +
CAST(FK8 AS NVARCHAR(19)) +
CAST(FK9 AS NVARCHAR(19)) +
CAST(FK10 AS NVARCHAR(19)) +
CAST(FK11 AS NVARCHAR(19)) +
CAST(FK12 AS NVARCHAR(19)) +
CAST(FK13 AS NVARCHAR(19)) +
CAST(FK14 AS NVARCHAR(19)) +
CAST(FK15 AS NVARCHAR(19)) +
CAST(STR1 AS NVARCHAR(500)) +
CAST(STR2 AS NVARCHAR(500)) +
CAST(STR3 AS NVARCHAR(500)) +
CAST(STR4 AS NVARCHAR(500)) +
CAST(STR5 AS NVARCHAR(500)) +
CAST(COMP1 AS NVARCHAR(1)) +
CAST(COMP2 AS NVARCHAR(1)) +
CAST(COMP3 AS NVARCHAR(1)) +
CAST(COMP4 AS NVARCHAR(1)) +
CAST(COMP5 AS NVARCHAR(1)) )
AS BINARY(32)) HASH1
FROM HB_TBL_2 WITH (TABLOCK)
) rpt ON rpt.ID = stg.ID
WHERE rpt.HASH1 <> stg.HASH1
OPTION (MAXDOP 8);
Para simplificar um pouco as coisas, provavelmente usarei algo como o seguinte para benchmarking. Vou postar resultados com HASHBYTES
na segunda-feira:
CREATE TABLE dbo.HASH_ME (
ID BIGINT NOT NULL,
FK1 BIGINT NOT NULL,
FK2 BIGINT NOT NULL,
FK3 BIGINT NOT NULL,
FK4 BIGINT NOT NULL,
FK5 BIGINT NOT NULL,
FK6 BIGINT NOT NULL,
FK7 BIGINT NOT NULL,
FK8 BIGINT NOT NULL,
FK9 BIGINT NOT NULL,
FK10 BIGINT NOT NULL,
FK11 BIGINT NOT NULL,
FK12 BIGINT NOT NULL,
FK13 BIGINT NOT NULL,
FK14 BIGINT NOT NULL,
FK15 BIGINT NOT NULL,
STR1 NVARCHAR(500) NOT NULL,
STR2 NVARCHAR(500) NOT NULL,
STR3 NVARCHAR(500) NOT NULL,
STR4 NVARCHAR(500) NOT NULL,
STR5 NVARCHAR(2000) NOT NULL,
COMP1 TINYINT NOT NULL,
COMP2 TINYINT NOT NULL,
COMP3 TINYINT NOT NULL,
COMP4 TINYINT NOT NULL,
COMP5 TINYINT NOT NULL
);
INSERT INTO dbo.HASH_ME WITH (TABLOCK)
SELECT RN,
RN % 1000000, RN % 1000000, RN % 1000000, RN % 1000000, RN % 1000000,
RN % 1000000, RN % 1000000, RN % 1000000, RN % 1000000, RN % 1000000,
RN % 1000000, RN % 1000000, RN % 1000000, RN % 1000000, RN % 1000000,
REPLICATE(CHAR(65 + RN % 10 ), 30)
,REPLICATE(CHAR(65 + RN % 10 ), 30)
,REPLICATE(CHAR(65 + RN % 10 ), 30)
,REPLICATE(CHAR(65 + RN % 10 ), 30)
,REPLICATE(CHAR(65 + RN % 10 ), 1000),
0,1,0,1,0
FROM (
SELECT TOP (100000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
) q
OPTION (MAXDOP 1);
SELECT MAX(HASHBYTES('SHA2_256',
CAST(N'' AS NVARCHAR(MAX)) + N'|' +
CAST(FK1 AS NVARCHAR(19)) + N'|' +
CAST(FK2 AS NVARCHAR(19)) + N'|' +
CAST(FK3 AS NVARCHAR(19)) + N'|' +
CAST(FK4 AS NVARCHAR(19)) + N'|' +
CAST(FK5 AS NVARCHAR(19)) + N'|' +
CAST(FK6 AS NVARCHAR(19)) + N'|' +
CAST(FK7 AS NVARCHAR(19)) + N'|' +
CAST(FK8 AS NVARCHAR(19)) + N'|' +
CAST(FK9 AS NVARCHAR(19)) + N'|' +
CAST(FK10 AS NVARCHAR(19)) + N'|' +
CAST(FK11 AS NVARCHAR(19)) + N'|' +
CAST(FK12 AS NVARCHAR(19)) + N'|' +
CAST(FK13 AS NVARCHAR(19)) + N'|' +
CAST(FK14 AS NVARCHAR(19)) + N'|' +
CAST(FK15 AS NVARCHAR(19)) + N'|' +
CAST(STR1 AS NVARCHAR(500)) + N'|' +
CAST(STR2 AS NVARCHAR(500)) + N'|' +
CAST(STR3 AS NVARCHAR(500)) + N'|' +
CAST(STR4 AS NVARCHAR(500)) + N'|' +
CAST(STR5 AS NVARCHAR(2000)) + N'|' +
CAST(COMP1 AS NVARCHAR(1)) + N'|' +
CAST(COMP2 AS NVARCHAR(1)) + N'|' +
CAST(COMP3 AS NVARCHAR(1)) + N'|' +
CAST(COMP4 AS NVARCHAR(1)) + N'|' +
CAST(COMP5 AS NVARCHAR(1)) )
)
FROM dbo.HASH_ME
OPTION (MAXDOP 1);
Como você está apenas procurando por alterações, não precisa de uma função hash criptográfica.
Você pode escolher um dos hashes não criptográficos mais rápidos da biblioteca Data.HashFunction de código aberto de Brandon Dahler, licenciado sob a licença MIT permissiva e aprovada pela OSI .
SpookyHash
é uma escolha popular.Exemplo de implementação
Código fonte
A fonte fornece duas funções, uma para entradas de 8000 bytes ou menos, e uma versão LOB. A versão não-LOB deve ser significativamente mais rápida.
Você pode envolver um binário LOB
COMPRESS
para colocá-lo abaixo do limite de 8.000 bytes, se isso valer a pena para o desempenho. Alternativamente, você pode dividir o LOB em segmentos abaixo de 8000 bytes, ou simplesmente reservar o uso deHASHBYTES
para o caso LOB (já que entradas mais longas escalam melhor).Código pré-construído
Obviamente, você pode pegar o pacote para si mesmo e compilar tudo, mas eu construí os assemblies abaixo para facilitar o teste rápido:
https://gist.github.com/SQLKiwi/365b265b476bf86754457fc9514b2300
Funções T-SQL
Uso
Um exemplo de uso dado os dados de exemplo na pergunta:
Ao usar a versão LOB, o primeiro parâmetro deve ser convertido ou convertido para
varbinary(max)
.Plano de execução
Assustador Seguro
A biblioteca Data.HashFunction usa vários recursos de linguagem CLR que são considerados
UNSAFE
pelo SQL Server. É possível escrever um Spooky Hash básico compatível com oSAFE
status. Um exemplo que escrevi baseado no SpookilySharp de Jon Hanna está abaixo:https://gist.github.com/SQLKiwi/7a5bb26b0bee56f6d28a1d26669ce8f2
Não tenho certeza se o paralelismo será significativamente melhor com SQLCLR. No entanto, é realmente fácil de testar, pois existe uma função hash na versão gratuita da biblioteca SQL# SQLCLR (que eu escrevi) chamada Util_HashBinary . Os algoritmos suportados são: MD5, SHA1, SHA256, SHA384 e SHA512.
Ele recebe um
VARBINARY(MAX)
valor como entrada, então você pode concatenar a versão da string de cada campo (como está fazendo atualmente) e depois converter paraVARBINARY(MAX)
, ou você pode ir diretamenteVARBINARY
para cada coluna e concatenar os valores convertidos (isso pode ser mais rápido, pois você não está lidando com strings ou a conversão extra de string paraVARBINARY
). Abaixo está um exemplo mostrando ambas as opções. Ele também mostra aHASHBYTES
função para que você possa ver que os valores são os mesmos entre ela e SQL#.Util_HashBinary .Observe que os resultados de hash ao concatenar os
VARBINARY
valores não corresponderão aos resultados de hash ao concatenar osNVARCHAR
valores. Isso ocorre porque a forma binária doINT
valor "1" é 0x00000001, enquanto a forma UTF-16LE (ou sejaNVARCHAR
, ) doINT
valor de "1" (em forma binária, pois é sobre isso que uma função de hash operará) é 0x3100.Você pode testar algo mais comparável ao Spooky não-LOB usando:
Observação: Util_HashBinary usa o algoritmo SHA256 gerenciado que está integrado ao .NET e não deve usar a biblioteca "bcrypt".
Além desse aspecto da pergunta, existem alguns pensamentos adicionais que podem ajudar nesse processo:
Pensamento Adicional nº 1 (pré-calcular hashes, pelo menos alguns)
Você mencionou algumas coisas:
e:
e:
Parece que os dados nesta tabela de relatórios são estáveis por um período de tempo e só são modificados por esse processo de ETL.
Se nada mais modificar esta tabela, então realmente não precisamos de um gatilho ou exibição indexada (originalmente pensei que você poderia).
Como você não pode modificar o esquema da tabela de relatórios, seria possível ao menos criar uma tabela relacionada para conter o hash pré-calculado (e o horário UTC de quando foi calculado)? Isso permitiria que você tivesse um valor pré-calculado para comparar com a próxima vez, deixando apenas o valor de entrada que requer o cálculo do hash. Isso reduziria o número de chamadas para um
HASHBYTES
ouSQL#.Util_HashBinary
pela metade. Você simplesmente se juntaria a essa tabela de hashes durante o processo de importação.Você também criaria um procedimento armazenado separado que simplesmente atualiza os hashes dessa tabela. Ele apenas atualiza os hashes de qualquer linha relacionada que foi alterada para atual e atualiza o carimbo de data/hora dessas linhas modificadas. Este proc pode/deve ser executado ao final de qualquer outro processo que atualize esta tabela. Ele também pode ser programado para ser executado de 30 a 60 minutos antes do início desse ETL (dependendo de quanto tempo leva para ser executado e quando qualquer um desses outros processos pode ser executado). Ele pode até ser executado manualmente se você suspeitar que pode haver linhas fora de sincronia.
Notou-se então que:
Essas muitas tabelas tornam mais difícil ter uma tabela extra por cada uma para conter os hashes atuais, mas isso não é impossível, pois poderia ser script, pois seria um esquema padrão. O script precisaria apenas levar em conta o nome da tabela de origem e a descoberta da(s) coluna(s) PK da tabela de origem.
Ainda assim, independentemente de qual algoritmo de hash prova ser o mais escalável, ainda recomendo encontrar pelo menos algumas tabelas (talvez haja algumas que sejam MUITO maiores que o restante das 500 tabelas) e configurar uma tabela relacionada para capturar hashes atuais para que os valores "atuais" possam ser conhecidos antes do processo ETL. Mesmo a função mais rápida não pode superar nunca ter que chamá-la em primeiro lugar ;-).
Pensamento Adicional nº 2 (
VARBINARY
em vez deNVARCHAR
)Independentemente de SQLCLR vs built-in
HASHBYTES
, eu ainda recomendaria converter diretamente paraVARBINARY
, pois isso deve ser mais rápido. Concatenar strings não é muito eficiente. E , além de converter valores não string em strings em primeiro lugar, o que requer esforço extra (suponho que a quantidade de esforço varia de acordo com o tipo de base:DATETIME
exigindo mais deBIGINT
), enquanto a conversão paraVARBINARY
simplesmente fornece o valor subjacente (na maioria dos casos).E, de fato, testando o mesmo conjunto de dados que os outros testes usaram, e usando
HASHBYTES(N'SHA2_256',...)
, mostrou um aumento de 23,415% no total de hashes calculado em um minuto. E esse aumento foi por não fazer nada além de usarVARBINARY
em vez deNVARCHAR
! ? (consulte a resposta do wiki da comunidade para obter detalhes)Pensamento Adicional nº 3 (esteja atento aos parâmetros de entrada)
Testes adicionais mostraram que uma área que afeta o desempenho (sobre esse volume de execuções) são os parâmetros de entrada: quantos e quais tipos.
A função Util_HashBinary SQLCLR que está atualmente na minha biblioteca SQL# tem dois parâmetros de entrada: um
VARBINARY
(o valor para hash) e umNVARCHAR
(o algoritmo a ser usado). Isso se deve ao meu espelhamento da assinatura daHASHBYTES
função. No entanto, descobri que, se eu removesse oNVARCHAR
parâmetro e criasse uma função que fizesse apenas SHA256, o desempenho melhoraria bastante. Suponho que mesmo mudar oNVARCHAR
parâmetro paraINT
teria ajudado, mas também suponho que nem mesmo ter oINT
parâmetro extra é pelo menos um pouco mais rápido.Além disso,
SqlBytes.Value
pode ter um desempenho melhor do queSqlBinary.Value
.Criei duas novas funções: Util_HashSHA256Binary e Util_HashSHA256Binary8k para este teste. Eles serão incluídos na próxima versão do SQL# (sem data definida para isso ainda).
Também descobri que a metodologia de teste poderia ser ligeiramente melhorada, então atualizei o equipamento de teste na resposta do wiki da comunidade abaixo para incluir:
CHECKSUM
registrou mais de 9 mil colisões, o que é 9% (caramba).Pensamento Adicional nº 4 (
HASHBYTES
+ SQLCLR juntos?)Dependendo de onde está o gargalo, pode até ajudar usar uma combinação de
HASHBYTES
UDF integrada e SQLCLR para fazer o mesmo hash. Se as funções internas forem restritas de maneira diferente/separadamente das operações SQLCLR, essa abordagem poderá ser mais efetiva do que qualquer uma delas.HASHBYTES
ou SQLCLR individualmente. Com certeza vale a pena testar.Pensamento Adicional nº 5 (cache de objeto de hash?)
O cache do objeto do algoritmo de hash, conforme sugerido na resposta de David Browne, certamente parece interessante, então tentei e encontrei os dois pontos de interesse a seguir:
Por qualquer motivo, não parece fornecer muita melhoria de desempenho, se houver. Eu poderia ter feito algo errado, mas aqui está o que eu tentei:
O
ManagedThreadId
valor parece ser o mesmo para todas as referências SQLCLR em uma consulta específica. Testei várias referências à mesma função, bem como uma referência a uma função diferente, todas as 3 recebendo valores de entrada diferentes e retornando valores de retorno diferentes (mas esperados). Para ambas as funções de teste, a saída foi uma string que incluía aManagedThreadId
representação em string do resultado do hash. oManagedThreadId
valor era o mesmo para todas as referências de UDF na consulta e em todas as linhas. Mas, o resultado do hash foi o mesmo para a mesma string de entrada e diferente para diferentes strings de entrada.Embora eu não tenha visto nenhum resultado errôneo em meus testes, isso não aumentaria as chances de uma condição de corrida? Se a chave do dicionário for a mesma para todos os objetos SQLCLR chamados em uma consulta específica, eles compartilharão o mesmo valor ou objeto armazenado para essa chave, certo? A questão é que, mesmo que parecesse funcionar aqui (até certo ponto, novamente não parecia haver muito ganho de desempenho, mas funcionalmente nada quebrou), isso não me dá confiança de que essa abordagem funcionará em outros cenários.
Esta não é uma resposta tradicional, mas achei que seria útil postar benchmarks de algumas das técnicas mencionadas até agora. Estou testando em um servidor de 96 núcleos com SQL Server 2017 CU9.
Many scalability problems are caused by concurrent threads contending over some global state. For example, consider classic PFS page contention. This can happen if too many worker threads need to modify the same page in memory. As code becomes more efficient it may request the latch faster. That increases contention. To put it simply, efficient code is more likely to lead to scalability issues because the global state is contended over more severely. Slow code is less likely to cause scalability issues because the global state isn't accessed as frequently.
HASHBYTES
scalability is partially based on the length of the input string. My theory was to why this occurs is that access to some global state is needed when theHASHBYTES
function is called. The easy global state to observe is a memory page needs to be allocated per call on some versions of SQL Server. The harder one to observe is that there's some kind of OS contention. As a result, ifHASHBYTES
is called by the code less frequently then contention goes down. One way to reduce the rate ofHASHBYTES
calls is to increase the amount of hashing work needed per call. Hashing work is partially based on the length of the input string. To reproduce the scalability problem I saw in the application I needed to change the demo data. A reasonable worst case scenario is a table with 21BIGINT
columns. The definition of the table is included in the code at the bottom. To reduce Local Factors™, I'm using concurrentMAXDOP 1
queries that operate on relatively small tables. My quick benchmark code is at the bottom.Note the functions return different hash lengths.
MD5
andSpookyHash
are both 128 bit hashes,SHA256
is a 256 bit hash.RESULTS (
NVARCHAR
vsVARBINARY
conversion and concatenation)In order to see if converting to, and concatenating,
VARBINARY
is truly more efficient / performant thanNVARCHAR
, anNVARCHAR
version of theRUN_HASHBYTES_SHA2_256
stored procedure was created from the same template (see "Step 5" in BENCHMARKING CODE section below). The only differences are:_NVC
BINARY(8)
for theCAST
function was changed to beNVARCHAR(15)
0x7C
was changed to beN'|'
Resulting in:
instead of:
The table below contains the number of hashes performed in 1 minute. The tests were performed on a different server than was used for the other tests noted below.
Looking at just the averages, we can calculate the benefit of switching to
VARBINARY
:That returns:
RESULTS (hash algorithms and implementations)
The table below contains the number of hashes performed in 1 minute. For example, using
CHECKSUM
with 84 concurrent queries resulted in over 2 billion hashes being performed before time ran out.If you prefer to see the same numbers measured in terms of work per thread-second:
Some quick thoughts on all of the methods:
CHECKSUM
: very good scalability as expectedHASHBYTES
: scalability issues include one memory allocation per call and a large amount of CPU spent in the OSSpooky
: surprisingly good scalabilitySpooky LOB
: the spinlockSOS_SELIST_SIZED_SLOCK
spins out of control. I suspect this is a general issue with passing LOBs through CLR functions, but I'm not sureUtil_HashBinary
: looks like it gets hit by the same spinlock. I haven't looked into this so far because there's probably not a lot that I can do about it:Util_HashBinary 8k
: very surprising results, not sure what's going on hereFinal results tested on a smaller server:
BENCHMARKING CODE
SETUP 1: Tables and Data
SETUP 2: Master Execution Proc
SETUP 3: Collision Detection Proc
SETUP 4: Cleanup (DROP All Test Procs)
SETUP 5: Generate Test Procs
TEST 1: Check For Collisions
TEST 2: Run Performance Tests
VALIDATION ISSUES TO RESOLVE
While focusing on the performance testing of a singular SQLCLR UDF, two issues that were discussed early on were not incorporated into the tests, but ideally should be investigated in order to determine which approach meets all of the requirements.
In a comment that has since been deleted, Paul White had mentioned:
So that is something to consider, and clearly requires testing. If the SQLCLR options do not provide any benefit over the built-in
HASHBYTES
, then that adds weight to Solomon's suggestion of capturing existing hashes (for at least the largest tables) into related tables.You can probably improve the performance, and perhaps the scalability of all the .NET approaches by pooling and caching any objects created in the function call. EG for Paul White's code above:
SQL CLR discourages and tries to prevent using static/shared variables, but it will let you use shared variables if you mark them as readonly. Which, of course, is meaningless as you can just assign a single instance of some mutable type, like
ConcurrentDictionary
.