站点图标 江湖人士

使用GUID做为数据库主键,如何提升性能?

使用GUID做为数据库主键,如何提升性能?

几乎任何数据库系统上使用正确的方法都可以使GUID几乎与整数主键一样快。

介绍

本文概述了一种将GUID值用作主键/聚集索引的方法,它可以避免大部分正常缺点,将适用于由Jimmy Nilsson在其作为主键的GUID成本中开发的连续GUID的COMB模型。虽然这种基本模型已被各种库和框架(包括NHibernate)使用,但大多数实现似乎都是针对Microsoft SQL Server的。本文试图将该方法适用于一个灵活的系统,该系统可以与Oracle,PostgreSQL和MySQL等其他常用数据库系统一起使用,并且特别针对.NET Framework的一些偏心。

背景

历史上,数据库设计的一个非常常见的模型使用顺序整数来标识一行数据,通常在插入新行时由服务器本身生成。这是一种简单,干净的方法,适用于许多应用。

但是,也有一些情况不理想。随着对象关系映射(ORM)框架(如NHibernate和ADO.NET实体框架)的越来越多的使用,依靠服务器生成关键值增加了大多数人更喜欢避免的复杂性。同样,复制方案也会使依赖单一权威来源进行关键值创建成为问题 – 整个目标是最大限度地减少单一权限的角色。

一个诱人的选择是使用GUID作为关键值。一个GUID(全局唯一标识符),也称为UUID,是一个128位的值,可以在整个空间和时间内保证唯一性。在RFC 4122中描述了创建GUID的标准,但大多数现在常用的GUID创建算法本质上是一个非常长的随机数,或者将随机出现的组件与本地系统的某种识别信息组合在一起,例如一个网络MAC地址。

GUID的优点是允许开发人员即时创建新的密钥值,而无需检入服务器,也不必担心该值可能已被其他人使用。乍一看,他们似乎为这个问题提供了很好的答案。

那么问题是什么?那么,表现。为了获得最佳性能,大多数数据库将行存储在所谓的聚簇索引中,这意味着表中的行实际上是按照排序顺序存储在磁盘上的,通常基于主键值。这使得找到一行就像在索引中快速查找一样简单,但是如果它们的主键不在列表的末尾,它可以使向表中添加新行非常缓慢。例如,请考虑以下数据:

ID  名称
1 福尔摩斯
4 沃森,J。
7 Moriarty,J.

到目前为止非常简单:按照ID列的值顺序存储行。如果我们添加一个ID为8的新行,这是没有问题的:该行刚刚结束。

ID 名称
1 福尔摩斯
4 沃森,J。
7 Moriarty,J.
8 Lestrade,I.

但是现在假设我们想插入一个ID为5的行:

ID 名称
1 福尔摩斯
4 沃森,J。
哈德森夫人。
7 Moriarty,J.
8 Lestrade,I.

第7行和第8行必须向下移动以腾出空间。这里没有什么大不了的,但是当你正在讨论将某些东西插入到具有数百万行的表格中间时,它就开始成为一个问题。而当你想要每秒做上百次时,它确实可以真正地加起来。

而这与GUID的问题:它们可能是也可能不是真正随机的,但大多看起来  是随机的,在这个意义上,他们通常不会产生任何特定种类的顺序。出于这个原因,在任何重要大小的数据库中使用GUID值作为主键的一部分通常被认为是一种非常糟糕的做法。插入可能非常缓慢并且涉及大量不必要的磁盘活动。

顺序GUID

那么,解决方案是什么?那么,GUID的主要问题是他们缺乏序列。所以,我们添加一个序列。COMB方法(代表COMBined GUID /时间戳)用一个保证增加或至少不减少每个新值的GUID替换一部分GUID。顾名思义,它通过使用从当前日期和时间生成的值来完成此操作。

为了说明,请考虑这个典型的GUID值列表:

fda437b5-6edd-42dc-9bbd-c09d10460ad0
2cb56c59-ef3d-4d24-90e7-835ed5968cdc
6bce82f3-5bd2-4efc-8832-986227592f26
42af7078-4b9c-4664-ba01-0d492ba3bd83

请注意,这些值不是以任何特定的顺序出现,而是基本上是随机的。用这种类型的值作为主键插入一百万行可能会很慢。

现在考虑这个假设的特殊GUID值列表:

00000001-a411-491d-969a-77bf40f55175
00000002-d97d-4bb9-a493-cad277999363
00000003-916c-4986-a363-0a9b9c95ca52
00000004-f827-452b-a3be-b77a3a4c95aa

第一个数字块已经被逐渐增加的序列所取代 – 比方说,自程序开始以来的毫秒数。插入一百万行这些值不会太糟糕,因为每行只会附加到列表的末尾,不需要对现有数据进行任何重新组合。

现在我们有了我们的基本概念,我们需要深入了解GUID如何构建以及它们如何由不同数据库系统处理的一些细节。

128位GUID由四个主要块组成,分别称为Data1,Data2,Data3和Data4,您可以在下面的示例中看到它们:

11111111-2222-3333-4444-444444444444

Data1是四个字节,Data2是两个字节,Data3是两个字节,Data4是八个字节(Data3的几位和Data4的第一部分保留用于版本信息,但这或多或少是结构)。

目前使用的大多数GUID算法,尤其是那些.NET Framework使用的算法,几乎都只是奇特的随机数生成器(微软用来包含本地机的MAC地址作为GUID的一部分,但几年前由于隐私问题)。这对我们来说是个好消息,因为这意味着玩弄价值的不同部分不太可能损害价值的独特性。

但不幸的是,对我们来说,不同的数据库以不同的方式处理GUID。某些系统(Microsoft SQL Server,PostgreSQL)具有内置的GUID类型,可直接存储和操作GUID。没有原生GUID支持的数据库对于如何模拟它们有不同的约定。例如,MySQL通常通过将字符串表示形式写入char(36)列来存储GUID。Oracle通常将GUID值的原始字节存储在原始(16)列中。

它变得更加复杂,因为Microsoft SQL Server的一个偏心是它根据最低有效的六个字节(即Data4块的最后六个字节)来排序GUID值。因此,如果我们想要创建一个连续的GUID来与SQL Server一起使用,那么我们必须将顺序部分放在最后。大多数其他数据库系统在开始时会需要它。

算法

通过查看数据库处理GUID的不同方式,很明显,对于顺序GUID,不可能有一种适合所有情况的算法; 我们必须为我们的特定应用程序定制它。在做了一些实验之后,我确定了三种主要的方法,涵盖了几乎所有的用例:

(为什么不将GUID存储为字符串与存储为字节的GUID相同?由于.NET处理GUID的方式,字符串表示可能不是您期望的小端系统上的字符串,而大多数机器可能正在运行。后面会详细介绍。)

我在代码中将这些选择表示为枚举:

public enum SequentialGuidType
{
  SequentialAsString,
  SequentialAsBinary,
  SequentialAtEnd
}

现在我们可以定义一个方法来生成我们的GUID,它接受这些枚举值之一,并相应地调整结果:

public Guid NewSequentialGuid(SequentialGuidType guidType)
{
  ... 
}

但是,我们究竟如何创建一个顺序的GUID?究竟哪一部分我们保持“随机”,我们用时间戳替换哪部分?那么,针对SQL Server量身定制的原始COMB规范会用时间戳值替换Data4的最后六个字节。这部分出于方便,因为这六个字节是SQL Server用来订购GUID值的内容,但时间戳的六个字节是足够平衡的。这为随机组件留下了十个字节。

对我来说最有意义的是从一个全新的随机GUID开始。就像我刚刚说的,我们需要十个随机字节:

var rng = new System.Security.Cryptography.RNGCryptoServiceProvider();
byte[] randomBytes = new byte[10];
rng.GetBytes(randomBytes);

我们用它  RNGCryptoServiceProvider来生成随机分量,因为它System.Random有一些不适合于此目的的缺陷(例如,它产生的数字遵循一些可识别的模式,并且将在不超过2 32  次迭代后循环)。由于我们依赖随机性给予我们尽可能多的唯一性保证,所以我们的利益是确保我们的初始状态尽可能强烈随机,并   RNGCryptoServiceProvider 提供密码强的随机数据。

(然而,它也相对较慢,所以如果性能很关键,你可能需要考虑另一种方法 – Guid.NewGuid()比如简单地用数据初始化一个字节数组,我避免了这种方法,因为Guid.NewGuid()它本身并不保证随机性;这就是目前的实施似乎有效,所以我选择谨慎行事,并坚持我所知道的方法 可靠运行。)

好的,我们现在有了我们新值的随机部分,剩下的部分是用我们的时间戳替换它的一部分。我们确定了一个六字节的时间戳,但它应该基于什么?一个明显的选择是使用DateTime.Now(或者,正如Rich Andersen指出的那样,DateTime.UtcNow以获得更好的性能),并以某种方式将其转换为6字节的整数值。该Ticks属性是诱人的:它返回自公元0001年1月1日以来已经过去的100纳秒间隔的数量。但是,有几次故障。

首先,由于Ticks返回一个64位整数,而我们只有48位可用,所以我们不得不砍掉两个字节,其余48位的值为100纳秒的间隔让我们在不到一年的时间内溢出和周期。这会破坏我们试图建立的连续顺序,并破坏我们希望获得的性能提升,并且由于许多应用程序的服务时间会超过一年,因此我们不得不使用时间精确度量。

另一个困难就是DateTime.UtcNow分辨率有限。根据文档,该值可能只会每10毫秒更新一次。(在某些系统上它似乎更新更频繁,但我们不能依赖这一点。)

好消息是,这两种结果相互抵消:有限的分辨率意味着使用整个Ticks价值没有意义。因此,我们不是直接使用tick,而是将10000除以给出自0001年1月1日以来经过的毫秒数,然后将最不重要的48位作为我们的时间戳。我使用毫秒,因为尽管DateTime.UtcNow 目前在某些系统上的分辨率限制为10毫秒,但未来可能会有所改进,我想为此留出空间。将时间戳的分辨率降低到几毫秒也会使我们在大约5800 AD之前溢出并循环; 希望对大多数应用来说这已经足够了。

在我们继续之前,关于这种方法的简短脚注:使用1毫秒分辨率时间戳意味着生成的非常接近的GUID可能具有相同的时间戳值,因此不会是顺序的。这可能是一些应用程序常见的情况,实际上我尝试了一些替代方法,例如使用更高分辨率的计时器,例如System.Diagnostics.Stopwatch,或将时间戳与“计数器”相结合,以确保序列一直持续到时间戳更新。但是,在测试过程中,我发现这并没有产生明显的差异,即使在同一毫秒的时间内生成了几十甚至几百个GUID。这与Jimmy Nilsson在测试COMB时遇到的情况一致。考虑到这一点,我采用了这里概述的方法,因为它简单得多。

代码如下:

long timestamp = DateTime.UtcNow.Ticks / 10000L;
byte[] timestampBytes = BitConverter.GetBytes(timestamp);

现在我们有我们的时间戳。但是,由于我们使用数字值来获取字节BitConverter,所以我们必须考虑字节顺序。

if (BitConverter.IsLittleEndian)
{
  Array.Reverse(timestampBytes); 
}

我们有我们的GUID的随机部分的字节,我们有时间戳的字节,所以剩下的就是把它们组合起来。在这一点上,我们必须根据SequentialGuidType传递给我们方法的值来定制格式。对于SequentialAsBinarySequentialAsString类型,我们首先复制时间戳,然后是随机组件。对于SequentialAtEnd类型,相反。

byte[] guidBytes = new byte[16];

switch (guidType)
{
  case SequentialGuidType.SequentialAsString:
  case SequentialGuidType.SequentialAsBinary:
    Buffer.BlockCopy(timestampBytes, 2, guidBytes, 0, 6);
    Buffer.BlockCopy(randomBytes, 0, guidBytes, 6, 10);
    break; 

  case SequentialGuidType.SequentialAtEnd:
    Buffer.BlockCopy(randomBytes, 0, guidBytes, 0, 10);
    Buffer.BlockCopy(timestampBytes, 2, guidBytes, 10, 6);
    break;
}

到现在为止还挺好。但是现在我们遇到了.NET Framework的怪诞之处:它不仅将GUID视为一系列字节。出于某种原因,它将GUID视为包含32位整数,两个16位整数和八个单独字节的结构。换句话说,它将Data1块视为一个Int32,将Data2和Data3块视为两个Int16,将Data4块视为一个  Byte[8]

这对我们意味着什么?那么,主要问题就是再次进行字节排序。由于.NET认为它处理数值,我们必须补偿小端系统 – 但是! – 仅适用于将GUID值转换为字符串的应用程序,并且在GUID的开头有时间戳部分(时间戳部分末尾的部分在“数字”部分中没有任何重要的部分) GUID,所以我们不必对它们做任何事情)。

这就是我之前提到的区分将存储为字符串的GUID和将作为二进制数据存储的GUID的原因。对于将它们存储为字符串的数据库,ORM框架和应用程序可能希望使用该ToString() 方法来生成SQL INSERT语句,这意味着我们必须纠正字节序问题。对于将它们存储为二进制数据的数据库,它们可能会Guid.ToByteArray() 用于为INSERT生成字符串,这意味着不需要进行更正。所以,我们有最后一件事要补充:

if (guidType == SequentialGuidType.SequentialAsString && 
    BitConverter.IsLittleEndian)
{
  Array.Reverse(guidBytes, 0, 4);
  Array.Reverse(guidBytes, 4, 2);
}

现在我们完成了,我们可以使用我们的字节数组来构造并返回一个GUID:

return new Guid(guidBytes);

使用代码

要使用我们的方法,我们首先必须确定哪种类型的GUID最适合我们的数据库和我们正在使用的任何ORM框架。以下是一些常见数据库类型的快速经验法则,虽然这些可能因应用程序的细节而异:

数据库  GUID列 SequentialGuidType值
Microsoft SQL Server 唯一标识符 SequentialAtEnd
MySQL的 炭(36) SequentialAsString
神谕 原料(16) SequentialAsBinary 
PostgreSQL的 UUID SequentialAsString
SQLite的 变化  变化 

(对于SQLite数据库,没有本地的GUID列类型,但有一些扩展模仿了这种功能,但是,GUID值可以作为16字节的二进制数据或36个字符的文本内部存储,具体取决于BinaryGUID参数传递给连接字符串,所以没有“一刀切”的答案。)

以下是我们新方法生成的一些示例。

首先,NewSequentialGuid(SequentialGuidType.SequentialAsString):

39babcb4-e446-4ed5-4012-2e27653a9d13
39babcb4-e447-ae68-4a32-19eb8d91765d
39babcb4-e44a-6c41-0fb4-21edd4697f43
39babcb4-e44d-51d2-c4b0-7d8489691c70

如您所见,前六个字节(前两个块)按顺序排列,其余为随机的。将这些值插入到将GUID存储为字符串(如MySQL)的数据库中应该提供比非顺序值更高的性能增益。

接下来,NewSequentialGuid(SequentialGuidType.SequentialAtEnd):

a47ec5e3-8d62-4cc1-e132-39babcb4e47a
939aa853-5dc9-4542-0064-39babcb4e47c
7c06fdf6-dca2-4a1a-c3d7-39babcb4e47d
c21a4d6f-407e-48cf-656c-39babcb4e480 

正如我们所期望的那样,最后六个字节是顺序的,其余的是随机的。我不知道为什么SQL Server以uniqueidentifier这种方式来索引索引,但它确实如此,并且这应该很好。

最后,NewSequentialGuid(SequentialGuidType.SequentialAsBinary):

b4bcba39-58eb-47ce-8890-71e7867d67a5
b4bcba39-5aeb-42a0-0b11-db83dd3c635b
b4bcba39-6aeb-4129-a9a5-a500aac0c5cd
b4bcba39-6ceb-494d-a978-c29cef95d37f 

当以这种格式查看时ToString()会输出,我们可以看到有些东西看起来不对。前两个数据块因其所有字节颠倒而“混乱”(这是由于前面讨论过的字节顺序问题)。如果我们要将这些值插入到文本字段中(就像他们将在MySQL下一样),那么性能并不理想。

但是,此问题正在出现,因为该列表中的四个值是使用该ToString()方法生成的。假设相同的四个GUID使用返回的数组转换为十六进制字符串  Guid.ToByteArray()

39babcb4eb5847ce889071e7867d67a5
39babcb4eb5a42a00b11db83dd3c635b
39babcb4eb6a4129a9a5a500aac0c5cd
39babcb4eb6c494da978c29cef95d37f

例如,ORM框架很可能会为Oracle数据库生成INSERT语句,您可以看到,如果以这种方式进行格式化,则该序列将再次可见。

因此,现在我们有一种方法可以为三种不同的数据库类型生成顺序的GUID值:存储为字符串(MySQL,有时是SQLite),存储为二进制数据(Oracle,PostgreSQL)和Microsoft SQL Server,它有自己奇怪的存储方案。

我们可以进一步定制我们的方法,让它根据应用程序设置中的值自动检测数据库类型,或者我们可以创建一个接受DbConnection 我们正在使用的重载  并从中确定正确的类型,但这取决于关于应用程序的详细信息以及任何正在使用的ORM框架。称之为功课!

基准

为了测试,我专注于四个常用数据库系统:Microsoft SQL Server 2008,MySQL 5.5,Oracle XE 11.2和PostgreSQL 9.1,所有这些都在我的桌面上运行在Windows 7下。(如果有人想在更多的数据库类型或其他操作系统下运行测试,我会很乐意尽我所能来帮助!)

通过使用每个数据库系统的命令行工具将2百万行插入到具有GUID主键和100个字符的文本字段的表中,执行测试。使用上述三种方法中的每一种进行一项测试,使用该Guid.NewGuid()方法作为对照进行第四项测试。为了比较,我还运行了第五次测试,将200万行插入到具有整数主键的类似表中。在第一百万行之后记录完成插入的时间(以秒为单位),然后在第二百万行之后再次记录。结果如下:

对于SQL Server,我们希望该SequentialAtEnd方法工作得最好(因为它特别适用于SQL Server),而且看起来不错:使用该方法的GUID插入仅比整数主键慢8.4% – 绝对可以接受。这比随机GUID的性能提高了75%。您也可以看到,SequentialAsBinarySequentialAsString方法相比随机的GUID只提供了一个小的好处,正如我们所期望的那样。另一个重要的指标是,对于随机GUID,第二百万个插入花费的时间超过了第一百万,这与大量的页面混排保持聚簇索引一致,因为更多的行被添加到中间,而对于SequentialAtEnd方法中,第二百万次花费的时间与第一次花费的时间几乎相同,表明新行仅仅被附加到表的末尾。到现在为止还挺好。

 

正如你所看到的,MySQL的 非连续GUID表现非常糟糕 – 如此糟糕,我必须切断图表的顶部以使其他条形可读(第二百万行只要第一行百万)。然而,该SequentialAsString方法的性能与整数主键几乎相同,这是我们所期望的,因为GUID通常在MySQL中存储为char(36)字段。使用该SequentialAsBinary方法的性能也很相似,可能是由于即使字节顺序不正确,整个值也是“排序”的顺序。

 

甲骨文很难掌握。将GUID存储为原始(16)列,我们期望该SequentialAsBinary 方法是最快的,并且它是,但即使是随机的GUID也不会比整数慢太多。而且,连续的GUID插入 比整数插入更快,这是难以接受的。虽然顺序GUID确实在这些基准测试中产生了可衡量的改进,但我不得不怀疑这里的怪异是否由于我没有为Oracle编写好的批量插入的经验。如果其他人想刺戳它,请告诉我!

 

最后,PostgreSQL。与Oracle一样,即使使用随机GUID,性能也不会太差,但顺序GUID的差异更为明显。正如预期的那样,该SequentialAsString方法最快,只比整数主键长7.8%,几乎是随机GUID的两倍。

补充笔记

还有其他一些事情需要考虑。插入顺序GUID的性能受到很多重视,但创建它们的性能如何?生成一个连续的GUID需要多长时间Guid.NewGuid()?那肯定会慢一点:在我的系统中,我可以在140毫秒内生成一百万个随机GUID,但是连续的GUID花费了2800毫秒 – 速度减慢了二十倍。

一些快速测试表明,大部分缓慢的原因是由于使用  RNGCryptoServiceProvider我们的随机数据; 切换到System.Random 结果下降到大约400毫秒。但我仍然不建议这样做,因为System.Random 这些目的仍然存在问题。但是,也可以使用替代算法,这种算法既快又可接受强 – 坦率地说,我对随机数生成器的了解不多。

慢创建是一个问题吗?我个人认为可以接受。除非您的应用程序涉及非常频繁的插入操作(在这种情况下,GUID键可能因其他原因而不理想),与快速数据库操作的优势相比,偶尔创建GUID的成本会变得很低。

另一个问题是:用时间戳替换GUID的六个字节意味着只有十个字节留给随机数据。这是否会危害独特性?那么,这取决于具体情况。包括时间戳意味着,任何两个GUID的创建超过几毫秒的间隔更保证是唯一的-一个承诺,一个完全随机的GUID(如由返回Guid.NewGuid())不能进行。但是关于GUID的创建非常接近呢?那么,十个字节的密码强度随机性意味着2 80,或1,208,925,819,614,629,174,706,176种可能的组合。在几毫秒内产生两个具有相同随机分量的GUID的可能性可能是微不足道的,相比之下,数据库服务器的可能性及其所有备份被同时的野猪攻击破坏。

最后一个问题是,这里生成的GUID在技术上不符合RFC 4122中规定的格式 – 例如,它们缺少通常占据第48到51位的版本号。我个人认为这不是什么大问题; 我不知道任何实际上关心GUID内部结构的数据库,省略版本块会给我们额外的四位随机性。但是,如果需要,我们可以轻松地将其添加回来。

最终代码

这是该方法的完整版本。对上面给出的代码进行了一些小的修改(例如将随机数生成器抽象为静态实例,并对该switch()块进行重构):

using System;
using System.Security.Cryptography;

public enum SequentialGuidType
{
  SequentialAsString,
  SequentialAsBinary,
  SequentialAtEnd
} 

public static class SequentialGuidGenerator
{
  private static readonly RNGCryptoServiceProvider _rng = new RNGCryptoServiceProvider();

  public static Guid NewSequentialGuid(SequentialGuidType guidType)
  {
    byte[] randomBytes = new byte[10];
    _rng.GetBytes(randomBytes);

    long timestamp = DateTime.UtcNow.Ticks / 10000L;
    byte[] timestampBytes = BitConverter.GetBytes(timestamp);

    if (BitConverter.IsLittleEndian)
    {
      Array.Reverse(timestampBytes);
    }

    byte[] guidBytes = new byte[16];

    switch (guidType)
    {
      case SequentialGuidType.SequentialAsString:
      case SequentialGuidType.SequentialAsBinary:
        Buffer.BlockCopy(timestampBytes, 2, guidBytes, 0, 6);
        Buffer.BlockCopy(randomBytes, 0, guidBytes, 6, 10);

        // If formatting as a string, we have to reverse the order
        // of the Data1 and Data2 blocks on little-endian systems.
        if (guidType == SequentialGuidType.SequentialAsString && BitConverter.IsLittleEndian)
        {
          Array.Reverse(guidBytes, 0, 4);
          Array.Reverse(guidBytes, 4, 2);
        }
        break;

      case SequentialGuidType.SequentialAtEnd:
        Buffer.BlockCopy(randomBytes, 0, guidBytes, 0, 10);
        Buffer.BlockCopy(timestampBytes, 2, guidBytes, 10, 6);
        break;
    }

    return new Guid(guidBytes);
  }
}

最终代码和演示项目可以在https://github.com/jhtodd/SequentialGuid找到[ ^ ]

结论

正如我在开头提到的那样,一般的COMB方法已经被各种框架大量使用,总体概念并不是特别新颖,对我来说当然也不是原创的。我的目标是说明如何调整方法以适应不同的数据库类型,并提供基准信息,强调需要量身定制的方法。

通过一点努力和适量的测试,就可以实现一种生成顺序GUID的一致方式,在几乎任何数据库系统下都可以轻松地将其用作高性能主键。

退出移动版