在 150B 行中存储 VARCHAR 的最有效方法 table
Most efficient way to store VARCHAR in 150B-row table
我们必须在 MySQL InnoDB 数据库中提取和存储 1500 亿条记录。特别是一个字段是一个 VARCHAR 字段，因为它占用了很多 space。其特点：
- 可以为 NULL
- 高度重复但我们无法删除重复数据，因为它会以指数方式增加摄取时间
- 平均长度约为 75 个字符
- 它必须有一个索引，因为它必须与另一个索引连接 table
- 我们不需要以人类可读的格式存储它，但我们需要能够将它与另一个 table 相匹配，后者必须具有与此列相同的格式
我试过以下方法：
- 压缩 table，这对 space 有帮助，但会显着增加摄取时间，所以我不确定压缩是否对我们有用
- 尝试哈希到 SHA2，将字符串长度减少到 56，这为我们提供了合理的 space 节省，但还不够。此外，我不确定 SHA2 是否会为此类数据生成唯一值
- 正在考虑 MD5，它将字符串长度进一步减少到可能合适的水平，但再次不确定 MD5 是否足以生成唯一值以与另一个匹配 table
你说它高度重复？
我的第一个想法是使用实际的 varchar 值和指向该值的主 int 键创建另一个 table。
然后现有的 table 可以简单地更改为包含对该值的引用作为外键（另外还可以有效地索引）。
像 MD5 这样的散列函数在 32 个十六进制字符的字符串中生成 128 位散列，但您可以使用 UNHEX() to cut that in half to 16 binary characters, and store the result in a column of type BINARY(16). See my answer to What data type to use for hashed password field and what length?
MD5 有 2128 个不同的哈希，或 340,282,366,920,938,463,463,374,607,431,768,211,456。两个不同的字符串导致碰撞的可能性相当低，即使您有 150 亿个不同的输入。请参阅 How many random elements before MD5 produces collisions? 如果您仍然担心，请使用 SHA1 或 SHA2。
不过，我对您尝试使用散列函数感到有点困惑。您不必关心原始字符串是什么，因为您必须了解散列是不可逆的。也就是说，您无法从哈希中获取原始字符串。
我喜欢@Data Mechanics 的回答，您应该在查找中枚举唯一的字符串输入 table，并使用 BIGINT 主键（INT 只有 4+ 十亿个值，所以它不是足够大以容纳 150 亿行）。
我理解您的意思，您必须查找字符串才能获得主键。您需要做的是编写您自己的程序来执行此数据输入。您的程序将执行以下操作：
- 创建内存中的哈希 table 以将字符串映射到整数主键。
- 读取您输入的一行
- 如果散列 table 还没有输入条目，请将该字符串插入查找 table 并获取生成的插入 ID。将其作为新条目存储在您的散列 table 中，字符串作为键，插入 ID 作为该条目的值。
- 否则散列 table 确实已经有一个条目，只需从散列 table.
中读取主键 bigint
- 将 bigint 作为外键插入到您的真实数据中 table，以及您要加载的其他数据。
- 循环到第 2 步。
不幸的是，它需要超过 1 TB 的内存来保存 150 亿个条目的 HashMap，即使在将字符串用作 HashMap 的键之前对字符串进行 MD5 也是如此。
因此我建议将完整的映射集合放入数据库 table，并将其中的一个子集保存在内存中。所以你必须围绕上面的 3. 做一个额外的步骤，如果内存中的 HashMap 没有你的字符串的条目，首先检查数据库。如果它在数据库中，则将其加载到 HashMap 中。如果它不在数据库中，则继续将其插入数据库，然后插入到 HashMap。
您可能对使用像 LruHashMap 这样的 class 感兴趣。它是一个具有最大大小的 HashMap（您可以根据可以分配给它的内存量来选择）。如果您在新元素已满时放入它，它会踢出最近最少引用的元素。我在 Apache Lucene 中找到了这个的实现，但也有其他实现。只需 Google 即可。
varchar是普通文本吗？这样是可压缩的3:1。 压缩 仅一个字段可能会减少到 25-30 字节。然后使用 VARBINARY(99).
INT（4 个字节）不够大 无法标准化 150 亿个不同的值，因此您需要更大的东西。 BIGINT 占用 8 个字节。 BINARY(5) 和 DECIMAL(11,0) 各占 5 个字节，但处理起来比较麻烦。
但是您担心归一化速度。我会更关心摄取速度，特别是如果您需要索引此列!
构建 table 需要多长时间？ 您还没有说架构是什么；我猜你可以在一个 InnoDB 块中放入 100 行。我会说你正在使用 SSD 并且可以获得 10K IOPs。 1.5B 块 / 10K blocks/sec = 150K 秒 = 2 天。这假设除了 ordered PRIMARY KEY 之外没有索引。 （如果没有订购，那么您将在 table 周围跳来跳去，您将需要更多的 IOP；将估计更改为 6 个月。）
列上的索引 实际上是 table 1500 亿 'rows' -- 仅索引 BTree 就需要数 TB。您可以在插入行时为字段建立索引，也可以稍后建立索引。
- 在插入时建立索引，即使有 InnoDB 的 "change buffer" 的好处，最终也会减慢到每插入一行命中 1 个磁盘快不了多少。您使用的是 SSD 吗？ （旋转驱动器的额定速度约为 10 毫秒/命中。）假设您每秒可以获得 10K 次命中（插入）。算出来是 15M 秒，也就是 6 个月。
- 构建索引 after loading the entire table... 这有效地构建了一个包含 1500 亿行的文件，对其进行排序，然后按顺序构建索引。这可能需要一周，而不是几个月。但是......在索引构建期间，它需要足够的磁盘 space 用于 table 的第二个副本（可能更多）。
那么，也许我们可以用类似的方式进行归一化？可是等等。你说这个栏目太大了，你连 table 都加载不出来？所以我们必须压缩或规范化那一列？
加载将如何完成？
- 多次
LOAD DATA 调用（可能最好）？单排INSERTs（至少把“2天”改成“2周”）？多排INSERTs（100-1000为佳）?
autocommit？做空交易？一笔巨额交易（这是致命的）？ （建议每 COMMIT 1K-10K 行。）- 单线程（可能速度不够快）？多线程（其他问题）？
- My discussion of high-speed-ingestion.
或者 table 会是 MyISAM 吗？磁盘占用空间将大大减少。我的大部分其他评论仍然适用。
回到MD5/SHA2。建立规范化 table，假设它比 RAM 中可以缓存的大得多，也将是一个杀手，不管你怎么做。但是，让我们先解决一些其他细节问题。
另请参阅 TokuDB（适用于较新版本的 MariaDB）以获得良好的高速摄取 和索引 。 TokuDB 将根据您的 table 大小减慢 some，而 InnoDB/MyISAM 将减慢到 crawl，正如我已经解释过的. TokuDB 也会自动压缩；有人说是 10 倍。我没有任何速度或 space 估计，但我认为 TokuDB 非常有前途。
B计划
看来真正的问题在于压缩或规范化 'router address'。回顾一下：在 1500 亿行中，大约有 150 亿个不同的值，加上 NULLs 的一小部分。字符串平均为 75 个字节。由于字符串的性质，压缩可能无效。所以，让我们专注于规范化。
id 至少需要 5 个字节（以处理 15B 个不同的值）；字符串平均为 75 个字节。 （我假设这是字节，而不是字符。）加上 BTree 等的一些开销，总数最终达到 2TB 左右。
我假设路由器地址在 table 加载期间相当随机，因此查找要插入的 'next' 地址是在不断增长的索引 BTree 中的随机查找。一旦索引增长超过 buffer_pool 的容量（小于 768GB），将越来越频繁地需要 I/O。到加载结束时，插入的 4 行中大约有 3 行将不得不 等待 从该索引 BTree 读取以检查已存在的行。我们预计加载时间为 个月，即使使用 SSD。
那么，可以做什么呢？考虑以下。使用 MD5 和 UNHEX 对地址进行哈希处理 - 16 字节。将其保留在 table 中。同时用 md5 的十六进制值加上路由器地址 - 150B 行（跳过 NULL）写入一个 file。使用重复数据删除对文件进行排序。 （在 md5 上排序。）从排序后的文件（15B 行）构建规范化 table。
结果：加载速度相当快（但很复杂）。路由器地址不是 75 字节（也不是 5 字节），而是 16。规范化 table 存在并且有效。
我们必须在 MySQL InnoDB 数据库中提取和存储 1500 亿条记录。特别是一个字段是一个 VARCHAR 字段，因为它占用了很多 space。其特点：
- 可以为 NULL
- 高度重复但我们无法删除重复数据，因为它会以指数方式增加摄取时间
- 平均长度约为 75 个字符
- 它必须有一个索引，因为它必须与另一个索引连接 table
- 我们不需要以人类可读的格式存储它，但我们需要能够将它与另一个 table 相匹配，后者必须具有与此列相同的格式
我试过以下方法：
- 压缩 table，这对 space 有帮助，但会显着增加摄取时间，所以我不确定压缩是否对我们有用
- 尝试哈希到 SHA2，将字符串长度减少到 56，这为我们提供了合理的 space 节省，但还不够。此外，我不确定 SHA2 是否会为此类数据生成唯一值
- 正在考虑 MD5，它将字符串长度进一步减少到可能合适的水平，但再次不确定 MD5 是否足以生成唯一值以与另一个匹配 table
你说它高度重复？ 我的第一个想法是使用实际的 varchar 值和指向该值的主 int 键创建另一个 table。
然后现有的 table 可以简单地更改为包含对该值的引用作为外键（另外还可以有效地索引）。
像 MD5 这样的散列函数在 32 个十六进制字符的字符串中生成 128 位散列，但您可以使用 UNHEX() to cut that in half to 16 binary characters, and store the result in a column of type BINARY(16). See my answer to What data type to use for hashed password field and what length?
MD5 有 2128 个不同的哈希，或 340,282,366,920,938,463,463,374,607,431,768,211,456。两个不同的字符串导致碰撞的可能性相当低，即使您有 150 亿个不同的输入。请参阅 How many random elements before MD5 produces collisions? 如果您仍然担心，请使用 SHA1 或 SHA2。
不过，我对您尝试使用散列函数感到有点困惑。您不必关心原始字符串是什么，因为您必须了解散列是不可逆的。也就是说，您无法从哈希中获取原始字符串。
我喜欢@Data Mechanics 的回答，您应该在查找中枚举唯一的字符串输入 table，并使用 BIGINT 主键（INT 只有 4+ 十亿个值，所以它不是足够大以容纳 150 亿行）。
我理解您的意思，您必须查找字符串才能获得主键。您需要做的是编写您自己的程序来执行此数据输入。您的程序将执行以下操作：
- 创建内存中的哈希 table 以将字符串映射到整数主键。
- 读取您输入的一行
- 如果散列 table 还没有输入条目，请将该字符串插入查找 table 并获取生成的插入 ID。将其作为新条目存储在您的散列 table 中，字符串作为键，插入 ID 作为该条目的值。
- 否则散列 table 确实已经有一个条目，只需从散列 table. 中读取主键 bigint
- 将 bigint 作为外键插入到您的真实数据中 table，以及您要加载的其他数据。
- 循环到第 2 步。
不幸的是，它需要超过 1 TB 的内存来保存 150 亿个条目的 HashMap，即使在将字符串用作 HashMap 的键之前对字符串进行 MD5 也是如此。
因此我建议将完整的映射集合放入数据库 table，并将其中的一个子集保存在内存中。所以你必须围绕上面的 3. 做一个额外的步骤，如果内存中的 HashMap 没有你的字符串的条目，首先检查数据库。如果它在数据库中，则将其加载到 HashMap 中。如果它不在数据库中，则继续将其插入数据库，然后插入到 HashMap。
您可能对使用像 LruHashMap 这样的 class 感兴趣。它是一个具有最大大小的 HashMap（您可以根据可以分配给它的内存量来选择）。如果您在新元素已满时放入它，它会踢出最近最少引用的元素。我在 Apache Lucene 中找到了这个的实现，但也有其他实现。只需 Google 即可。
varchar是普通文本吗？这样是可压缩的3:1。 压缩 仅一个字段可能会减少到 25-30 字节。然后使用 VARBINARY(99).
INT（4 个字节）不够大 无法标准化 150 亿个不同的值，因此您需要更大的东西。 BIGINT 占用 8 个字节。 BINARY(5) 和 DECIMAL(11,0) 各占 5 个字节，但处理起来比较麻烦。
但是您担心归一化速度。我会更关心摄取速度，特别是如果您需要索引此列!
构建 table 需要多长时间？ 您还没有说架构是什么；我猜你可以在一个 InnoDB 块中放入 100 行。我会说你正在使用 SSD 并且可以获得 10K IOPs。 1.5B 块 / 10K blocks/sec = 150K 秒 = 2 天。这假设除了 ordered PRIMARY KEY 之外没有索引。 （如果没有订购，那么您将在 table 周围跳来跳去，您将需要更多的 IOP；将估计更改为 6 个月。）
列上的索引 实际上是 table 1500 亿 'rows' -- 仅索引 BTree 就需要数 TB。您可以在插入行时为字段建立索引，也可以稍后建立索引。
- 在插入时建立索引，即使有 InnoDB 的 "change buffer" 的好处，最终也会减慢到每插入一行命中 1 个磁盘快不了多少。您使用的是 SSD 吗？ （旋转驱动器的额定速度约为 10 毫秒/命中。）假设您每秒可以获得 10K 次命中（插入）。算出来是 15M 秒，也就是 6 个月。
- 构建索引 after loading the entire table... 这有效地构建了一个包含 1500 亿行的文件，对其进行排序，然后按顺序构建索引。这可能需要一周，而不是几个月。但是......在索引构建期间，它需要足够的磁盘 space 用于 table 的第二个副本（可能更多）。
那么，也许我们可以用类似的方式进行归一化？可是等等。你说这个栏目太大了，你连 table 都加载不出来？所以我们必须压缩或规范化那一列？
加载将如何完成？
- 多次
LOAD DATA调用（可能最好）？单排INSERTs（至少把“2天”改成“2周”）？多排INSERTs（100-1000为佳）? autocommit？做空交易？一笔巨额交易（这是致命的）？ （建议每COMMIT1K-10K 行。）- 单线程（可能速度不够快）？多线程（其他问题）？
- My discussion of high-speed-ingestion.
或者 table 会是 MyISAM 吗？磁盘占用空间将大大减少。我的大部分其他评论仍然适用。
回到MD5/SHA2。建立规范化 table，假设它比 RAM 中可以缓存的大得多，也将是一个杀手，不管你怎么做。但是，让我们先解决一些其他细节问题。
另请参阅 TokuDB（适用于较新版本的 MariaDB）以获得良好的高速摄取 和索引 。 TokuDB 将根据您的 table 大小减慢 some，而 InnoDB/MyISAM 将减慢到 crawl，正如我已经解释过的. TokuDB 也会自动压缩；有人说是 10 倍。我没有任何速度或 space 估计，但我认为 TokuDB 非常有前途。
B计划
看来真正的问题在于压缩或规范化 'router address'。回顾一下：在 1500 亿行中，大约有 150 亿个不同的值，加上 NULLs 的一小部分。字符串平均为 75 个字节。由于字符串的性质，压缩可能无效。所以，让我们专注于规范化。
id 至少需要 5 个字节（以处理 15B 个不同的值）；字符串平均为 75 个字节。 （我假设这是字节，而不是字符。）加上 BTree 等的一些开销，总数最终达到 2TB 左右。
我假设路由器地址在 table 加载期间相当随机，因此查找要插入的 'next' 地址是在不断增长的索引 BTree 中的随机查找。一旦索引增长超过 buffer_pool 的容量（小于 768GB），将越来越频繁地需要 I/O。到加载结束时，插入的 4 行中大约有 3 行将不得不 等待 从该索引 BTree 读取以检查已存在的行。我们预计加载时间为 个月，即使使用 SSD。
那么，可以做什么呢？考虑以下。使用 MD5 和 UNHEX 对地址进行哈希处理 - 16 字节。将其保留在 table 中。同时用 md5 的十六进制值加上路由器地址 - 150B 行（跳过 NULL）写入一个 file。使用重复数据删除对文件进行排序。 （在 md5 上排序。）从排序后的文件（15B 行）构建规范化 table。
结果：加载速度相当快（但很复杂）。路由器地址不是 75 字节（也不是 5 字节），而是 16。规范化 table 存在并且有效。