Kann SQL Server Kollisionen in vom System generierten Einschränkungsnamen erstellen?

14

Ich habe eine Anwendung, die Millionen von Tabellen in einer SQL Server 2008-Datenbank erstellt (nicht gruppiert). Ich möchte ein Upgrade auf SQL Server 2014 (geclustert) durchführen, erhalte jedoch unter Last eine Fehlermeldung:

"In der Datenbank befindet sich bereits ein Objekt mit dem Namen" PK__tablenameprefix__179E2ED8F259C33B "."

Dies ist ein vom System generierter Einschränkungsname. Es sieht aus wie eine zufällig generierte 64-Bit-Zahl. Ist es möglich, dass ich aufgrund der großen Anzahl von Tabellen Kollisionen sehe? Angenommen, ich habe 100 Millionen Tabellen, dann berechne ich beim Hinzufügen der nächsten Tabelle weniger als eine 1-in-1-Billion-Wahrscheinlichkeit für eine Kollision, aber das setzt eine gleichmäßige Verteilung voraus. Ist es möglich, dass SQL Server seinen Algorithmus zur Namensgenerierung zwischen 2008 und 2014 geändert hat, um die Kollisionswahrscheinlichkeit zu erhöhen?

Der andere wichtige Unterschied ist, dass meine 2014-Instanz ein Clustered Pair ist, aber ich habe Mühe, eine Hypothese zu erstellen, warum dies den obigen Fehler verursachen würde.

PS Ja, ich weiß, dass das Erstellen von Millionen von Tabellen verrückt ist. Dies ist ein Blackbox-Code von Drittanbietern, über den ich keine Kontrolle habe. Trotz des Wahnsinns funktionierte es in Version 2008 und jetzt nicht in Version 2014.

Bearbeiten: Bei näherer Betrachtung scheint das generierte Suffix immer mit 179E2ED8 zu beginnen - was bedeutet, dass der zufällige Teil eigentlich nur eine 32-Bit-Zahl ist und die Wahrscheinlichkeit von Kollisionen bei jedem Hinzufügen einer neuen Tabelle nur 1 zu 50 beträgt ist eine viel engere Übereinstimmung mit der Fehlerrate, die ich sehe!

jl6
quelle
Die Tabellennamen sind unterschiedlich, verwenden jedoch eine Namenskonvention, die dazu führt, dass mindestens die ersten 11 Zeichen identisch sind. Dies scheint alles zu sein, was SQL Server zum Generieren des Einschränkungsnamens verwendet.
jl6
Die zugrunde liegende Hardware ist anders (neuere Generation von DL380), aber nicht wesentlich leistungsfähiger. Ziel dieser Übung ist es, den nicht unterstützten SQL Server 2008 zu ersetzen und nicht den Durchsatz zu verbessern, und die Hardware wurde entsprechend bereitgestellt.
jl6

Antworten:

15

Kann SQL Server Kollisionen in vom System generierten Einschränkungsnamen erstellen?

Dies hängt von der Art der Einschränkung und der Version von SQL Server ab.

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

Beispielergebnisse 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           |
+--------------------------+-----------+---------------+----------------------+

Beispielergebnisse 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           |
+--------------------------+------------+---------------+----------------------+

Bei Standardeinschränkungen, Prüfeinschränkungen und Fremdschlüsseleinschränkungen sind die letzten 4 Bytes des automatisch generierten Namens eine hexadezimale Version der Objekt-ID der Einschränkung. Da objectidgarantiert eindeutig ist, muss der Name auch eindeutig sein. Auch in Sybase verwenden diesetabname_colname_objectid

Für eindeutige Einschränkungen und Primärschlüsseleinschränkungen verwendet Sybase

tabname_colname_tabindid, wobei tabindid eine String-Verkettung der Tabellen-ID und der Index-ID ist

Auch dies würde die Einzigartigkeit garantieren.

SQL Server verwendet dieses Schema nicht.

In SQL Server 2008 und 2017 wird am Ende des vom System generierten Namens eine 8-Byte-Zeichenfolge verwendet. Der Algorithmus hat sich jedoch dahingehend geändert, wie die letzten 4 Bytes davon generiert werden.

Im Jahr 2008 stellen die letzten 4 Bytes einen vorzeichenbehafteten Ganzzahlzähler dar, der gegenüber dem object_idvon versetzten -16000057Wert mit einem negativen Umbruch auf max. Vorzeichenbehafteten Int. (Die Bedeutung von 16000057ist, dass dies das Inkrementobject_id ist, das zwischen dem sukzessiven Erstellen angewendet wird .) Dies garantiert immer noch die Einzigartigkeit.

Ab 2012 sehe ich überhaupt kein Muster zwischen der object_id der Einschränkung und der Ganzzahl, die erhalten wird, indem die letzten 8 Zeichen des Namens als hexadezimale Darstellung eines vorzeichenbehafteten int behandelt werden.

Die Funktionsnamen in der Aufrufliste im Jahr 2017 zeigen, dass es jetzt eine GUID als Teil des Namensgenerierungsprozesses erstellt (auf 2008 sehe ich keine Erwähnung von MDConstraintNameGenerator). Ich vermute, das ist eine Quelle der Zufälligkeit. Offensichtlich werden nicht die gesamten 16 Bytes der GUID in den 4 Bytes verwendet, die sich jedoch zwischen den Einschränkungen ändern.

Geben Sie hier die Beschreibung des Links ein

Ich gehe davon aus, dass der neue Algorithmus aus Effizienzgründen auf Kosten einer erhöhten Wahrscheinlichkeit von Kollisionen in extremen Fällen wie Ihrem durchgeführt wurde.

Dies ist ein pathologischer Fall, da das Präfix des Tabellennamens und der Spaltenname des PK (sofern dies die 8 Zeichen vor den letzten 8 beeinflusst) für Zehntausende von Tabellen identisch sein müssen, bevor dies wahrscheinlich wird, aber durchaus reproduzierbar ist leicht mit dem unten.

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

Ein Beispiel, das unter SQL Server 2017 für eine neu erstellte Datenbank ausgeführt wurde, schlug in etwas mehr als einer Minute fehl (nachdem 50.931 Tabellen erstellt wurden).

Meldung 2714, Ebene 16, Status 30, Zeile 15 In der Datenbank befindet sich bereits ein Objekt mit dem Namen "PK__abcdefgh__3BD019A8175067CE". Meldung 1750, Ebene 16, Status 1, Zeile 15 Einschränkung oder Index konnte nicht erstellt werden. Siehe vorherige Fehler.

Martin Smith
quelle
11

Angenommen, ich habe 100 Millionen Tabellen, dann berechne ich weniger als eine 1-in-1-Billion-Chance für eine Kollision

Denken Sie daran, dies ist das " Geburtstagsproblem ". Sie versuchen nicht, eine Kollision für einen einzelnen Hash zu generieren, sondern messen die Wahrscheinlichkeit, dass keines der vielen Wertepaare kollidiert.

Bei N Tabellen gibt es also N * (N-1) / 2 Paare, also hier ungefähr 10 16 Paare. Wenn die Wahrscheinlichkeit einer Kollision 2 bis 64 beträgt , beträgt die Wahrscheinlichkeit, dass ein einzelnes Paar nicht kollidiert, 1-2 bis 64 , aber bei so vielen Paaren beträgt die Wahrscheinlichkeit, dass hier keine Kollisionen auftreten, ungefähr (1-2 bis 64 ) 10 16 oder mehr wie 1 / 10.000. Siehe zB https://preshing.com/20110504/hash-collision-probabilities/

Und wenn es sich nur um einen 32-Bit-Hash handelt, überschreitet die Wahrscheinlichkeit einer Kollision die Hälfte bei nur 77.000 Werten.

David Browne - Microsoft
quelle
2
Und 77K-Werte zu erreichen, ohne auf eine Kollision zu stoßen, ist höchstwahrscheinlich unwahrscheinlich, da Sie für alle vorhergehenden Kreationen zuvor Glück gehabt haben müssen. Ich frage mich, an welchem ​​Punkt die kumulative Wahrscheinlichkeit einer Kollision 50% erreicht
Martin Smith