Czy SQL Server może tworzyć kolizje w nazwach ograniczeń generowanych przez system?

14

Mam aplikację, która tworzy miliony tabel w bazie danych SQL Server 2008 (bez klastrów). Chcę uaktualnić do programu SQL Server 2014 (klastrowane), ale po załadowaniu pojawia się komunikat o błędzie:

„W bazie danych znajduje się już obiekt o nazwie„ PK__tablenameprefix__179E2ED8F259C33B ”

Jest to nazwa ograniczenia generowana przez system. Wygląda jak losowo wygenerowana liczba 64-bitowa. Czy to możliwe, że widzę kolizje z powodu dużej liczby tabel? Zakładając, że mam 100 milionów tabel, liczę mniej niż 1-na-1-tryliona szansy na kolizję podczas dodawania kolejnej tabeli, ale to zakłada równomierny rozkład. Czy to możliwe, że SQL Server zmienił algorytm generowania nazw między wersjami 2008 i 2014, aby zwiększyć prawdopodobieństwo kolizji?

Inną znaczącą różnicą jest to, że moja instancja z 2014 r. Jest parą klastrową, ale staram się sformułować hipotezę, dlaczego wygenerowałoby to powyższy błąd.

PS Tak, wiem, że tworzenie milionów stolików jest szalone. To jest kod innej firmy czarnej skrzynki, nad którym nie mam kontroli. Mimo szaleństwa działało w wersji 2008, a teraz nie w wersji 2014.

Edycja: przy bliższej inspekcji generowany sufiks zawsze zaczyna się od 179E2ED8 - co oznacza, że ​​losowa część jest w rzeczywistości tylko liczbą 32-bitową, a prawdopodobieństwo kolizji wynosi zaledwie 1 na 50 za każdym razem, gdy dodawana jest nowa tabela, co jest znacznie bardziej zbliżony do poziomu błędu, który widzę!

jl6
źródło
Nazwy tabel są różne, ale używają konwencji nazewnictwa, która powoduje, że co najmniej pierwsze 11 znaków jest takich samych, i wydaje się, że to wszystko SQL Server używa do generowania nazwy ograniczenia.
jl6
Podstawowy sprzęt jest inny (nowa generacja DL380), ale nie znacznie wyższa wydajność. Celem tego ćwiczenia jest zastąpienie nieobsługiwanego programu SQL Server 2008, a nie poprawa przepustowości, a sprzęt został odpowiednio przygotowany.
jl6

Odpowiedzi:

16

Czy SQL Server może tworzyć kolizje w nazwach ograniczeń generowanych przez system?

Zależy to od rodzaju ograniczenia i wersji SQL Server.

CREATE TABLE T1
(
A INT PRIMARY KEY CHECK (A > 0),
B INT DEFAULT -1 REFERENCES T1,
C INT UNIQUE,
CHECK (C > A)
)

SELECT name, 
       object_id, 
       CAST(object_id AS binary(4)) as object_id_hex,
       CAST(CASE WHEN object_id >= 16000057  THEN object_id -16000057 ELSE object_id +2131483591 END AS BINARY(4)) AS object_id_offset_hex
FROM sys.objects
WHERE parent_object_id = OBJECT_ID('T1')
ORDER BY name;

drop table T1

Przykładowe wyniki 2008

+--------------------------+-----------+---------------+----------------------+
|           name           | object_id | object_id_hex | object_id_offset_hex |
+--------------------------+-----------+---------------+----------------------+
| CK__T1__1D498357         | 491357015 | 0x1D498357    | 0x1C555F1E           |
| CK__T1__A__1A6D16AC      | 443356844 | 0x1A6D16AC    | 0x1978F273           |
| DF__T1__B__1B613AE5      | 459356901 | 0x1B613AE5    | 0x1A6D16AC           |
| FK__T1__B__1C555F1E      | 475356958 | 0x1C555F1E    | 0x1B613AE5           |
| PK__T1__3BD019AE15A8618F | 379356616 | 0x169C85C8    | 0x15A8618F           |
| UQ__T1__3BD019A91884CE3A | 427356787 | 0x1978F273    | 0x1884CE3A           |
+--------------------------+-----------+---------------+----------------------+

Przykładowe wyniki 2017

+--------------------------+------------+---------------+----------------------+
|           name           | object_id  | object_id_hex | object_id_offset_hex |
+--------------------------+------------+---------------+----------------------+
| CK__T1__59FA5E80         | 1509580416 | 0x59FA5E80    | 0x59063A47           |
| CK__T1__A__571DF1D5      | 1461580245 | 0x571DF1D5    | 0x5629CD9C           |
| DF__T1__B__5812160E      | 1477580302 | 0x5812160E    | 0x571DF1D5           |
| FK__T1__B__59063A47      | 1493580359 | 0x59063A47    | 0x5812160E           |
| PK__T1__3BD019AE0A4A6932 | 1429580131 | 0x5535A963    | 0x5441852A           |
| UQ__T1__3BD019A981F522E0 | 1445580188 | 0x5629CD9C    | 0x5535A963           |
+--------------------------+------------+---------------+----------------------+

W przypadku ograniczeń domyślnych, ograniczeń sprawdzania i ograniczeń klucza obcego ostatnie 4 bajty automatycznie wygenerowanej nazwy są szesnastkową wersją objectid ograniczenia. Ponieważ objectidsą one gwarantowane jako unikalne, nazwa musi być również unikalna. Również w Sybase te zastosowaniatabname_colname_objectid

W przypadku ograniczeń unikalnych i ograniczeń klucza podstawowego używa Sybase

tabname_colname_tabindid, gdzie tabindid jest ciągiem połączenia identyfikatora tabeli i identyfikatora indeksu

To także gwarantowałoby wyjątkowość.

SQL Server nie używa tego schematu.

Zarówno w programie SQL Server 2008, jak i 2017 używa 8-bajtowego ciągu na końcu nazwy generowanej przez system, jednak algorytm zmienił sposób generowania ostatnich 4 bajtów.

W 2008 r. Ostatnie 4 bajty reprezentują podpisany licznik liczb całkowitych, który jest przesunięty w stosunku do o object_idprzez -16000057dowolne zawijanie wartości ujemnych do maksymalnej liczby całkowitej ze znakiem . (Istotne 16000057jest to, że jest to przyrost stosowany między sukcesywnie tworzonymiobject_id ). To wciąż gwarantuje wyjątkowość.

Od 2012 roku w górę nie widzę żadnego wzorca między object_id ograniczenia a liczbą całkowitą uzyskaną przez traktowanie ostatnich 8 znaków nazwy jako szesnastkowej reprezentacji podpisanej liczby int.

Nazwy funkcji na stosie wywołań w 2017 r. Pokazują, że teraz tworzy identyfikator GUID w ramach procesu generowania nazw (w 2008 r. Nie widzę wzmianki o MDConstraintNameGenerator). Wydaje mi się, że jest to źródło losowości. Najwyraźniej nie używa całego 16 bajtów z GUID w tych 4 bajtach, które jednak zmieniają się między ograniczeniami.

wprowadź opis linku tutaj

Zakładam, że nowy algorytm został wykonany z jakiegoś powodu ze względu na wydajność kosztem zwiększonej możliwości kolizji w ekstremalnych przypadkach, takich jak Twoja.

Jest to dość patologiczny przypadek, ponieważ wymaga przedrostka nazwy tabeli i nazwy kolumny PK (o ile wpływa to na 8 znaków poprzedzających ostatnie 8), aby były one identyczne dla dziesiątek tysięcy tabel, zanim stanie się prawdopodobne, ale można je całkiem odtworzyć z łatwością poniżej.

CREATE OR ALTER PROC #P
AS
    SET NOCOUNT ON;

    DECLARE @I INT = 0;


    WHILE 1 = 1
      BEGIN
          EXEC ('CREATE TABLE abcdefghijklmnopqrstuvwxyz' + @I + '(C INT PRIMARY KEY)');
          SET @I +=1;
      END 

GO

EXEC #P

Przykład uruchomiony na SQL Server 2017 dla nowo utworzonej bazy danych nie powiódł się w nieco ponad minutę (po utworzeniu 50 931 tabel)

Msg 2714, poziom 16, stan 30, wiersz 15 W bazie danych znajduje się już obiekt o nazwie „PK__abcdefgh__3BD019A8175067CE”. Msg 1750, poziom 16, stan 1, wiersz 15 Nie można utworzyć ograniczenia ani indeksu. Zobacz poprzednie błędy.

Martin Smith
źródło
11

Zakładając, że mam 100 milionów tabel, obliczam mniej niż 1-na-1-tryliona szansy na kolizję

Pamiętaj, że to jest „ problem urodzinowy ”. Nie próbujesz generować kolizji dla pojedynczego danego skrótu, ale raczej mierzysz prawdopodobieństwo, że żadna z wielu par wartości się nie zderzy.

Tak więc w przypadku N tabel istnieją N * (N-1) / 2 pary, więc tutaj około 10 16 par. Jeśli prawdopodobieństwo zderzenia wynosi 2–64 , prawdopodobieństwo, że pojedyncza para nie zderzy się, wynosi 1-2–64 , ale przy tak wielu parach prawdopodobieństwo braku zderzeń wynosi około ( 1-2–64 ) 10 16 lub więcej jak 1/10 000. Zobacz np. Https://preshing.com/20110504/hash-collision-probabilities/

A jeśli jest to tylko 32-bitowy skrót, prawdopodobieństwo kolizji przekracza 1/2 przy wartościach tylko 77k.

David Browne - Microsoft
źródło
2
A przede wszystkim uzyskanie wartości 77K bez kolizji jest prawdopodobnie mało prawdopodobne, ponieważ wcześniej trzeba było mieć szczęście do wszystkich poprzednich kreacji. Zastanawiam się, o co chodzi w tym, że skumulowane prawdopodobieństwo kolizji sięga 50%
Martin Smith