设想
假设我们有一个table
用户和一个item
用户。这两个表有一个关联表,用于user_item
定义many to many
关系。
我们开始100条
item
记录我们有 5 亿条
user
记录。因此我们必须生成 50_000_000_000
user_item
(500 亿)我们可能有更多
分片或分区都不容易,因为这样会减慢任何其他操作(否则我们需要扫描所有内容)
假设查询模式 (
INSERT
,SELECT
,UPDATE
) 是基本/典型的 m2m 模式(可以在任何教程或示例中找到)
问题
无论模式如何,处理数据库中数十亿个多对多关系的最佳设计或已知解决方案是什么?
架构
想象一下这个简单的模式
CREATE DATABASE IF NOT EXISTS `playground` CHARACTER SET = latin1;
USE playground;
CREATE TABLE IF NOT EXISTS `user`
(
`id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
`name` VARCHAR(255) NOT NULL,
PRIMARY KEY (`id`),
INDEX `user__name_fk` (`name`)
) ENGINE = InnoDB
DEFAULT CHARSET = latin1
ROW_FORMAT = DYNAMIC;
CREATE TABLE IF NOT EXISTS `item`
(
`id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
`name` VARCHAR(255) NOT NULL,
PRIMARY KEY (`id`),
INDEX `user__name` (`name`)
) ENGINE = InnoDB
DEFAULT CHARSET = latin1
ROW_FORMAT = DYNAMIC;
CREATE TABLE IF NOT EXISTS `user_item`
(
`user_id` BIGINT UNSIGNED NOT NULL,
`item_id` BIGINT UNSIGNED NOT NULL,
PRIMARY KEY (`user_id`, `item_id`),
INDEX `user_item__item` (`item_id`),
FOREIGN KEY `user_id_fk` (`user_id`) REFERENCES `user` (`id`) ON DELETE CASCADE,
FOREIGN KEY `item_id_fk` (`item_id`) REFERENCES `item` (`id`) ON DELETE CASCADE
) ENGINE = InnoDB
DEFAULT CHARSET = latin1
ROW_FORMAT = DYNAMIC;
-- create some default items
INSERT INTO `item` (`name`) VALUES ('item_1'), ('item_2'), ('item_3'), ('item_4'), ('item_5'), ('item_6'), ('item_7'), ('item_8'), ('item_9'), ('item_10');
-- create some users
INSERT INTO `user` (`name`) VALUES ('user_1'), ('user_2'), ('user_3'), ('user_4'), ('user_5'), ('user_6'), ('user_7'), ('user_8'), ('user_9'), ('user_10');
INSERT INTO `user_item` (`user_id`, `item_id`) VALUES (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10);
更多信息
我并不是在问如何在 MySQL 中使用多对多关系,我知道这一点。我是在问当相关记录的数量呈指数增长到如此大的规模时,针对扩展问题最广为人知的解决方案是什么。
另外,我故意没有添加任何查询模式(INSERT
、、),因为SELECT
这是不相关的。假设最/典型的 M2M 模式。我不想失去对有关扩展和大量数据的真正问题的关注。UPDATE
一定有一些技巧或一些已知的解决方法,对吗?我也在考虑 NoSQL 数据库,因此答案可能包括与 MySQL(或任何 SQL 数据库)无关的任何内容,
我觉得这应该是许多大公司都会面临的一个常见问题,因此应该有一个(或几个)通用的解决方案。这个问题的根本原因是,虽然 MySQL 非常适合创建关系,但它会成倍地增加关联的 m2m 表。
5 亿 x 100 == 500 亿只是一个例子。但理论上可能会发生。
澄清
- 我故意省略了查询,因为您可以假设最简单的查询。
- 我确信如果我举了几个例子,就会开始对特定查询进行流行优化,这不是问题
- 我问的是一个非常高层次的问题,如果没有真正已知的解决方案,那么解释为什么就足够了(假设是正确的)
这是一个简单的多对多查询的示例。
SELECT user.*, item.* FROM user
LEFT JOIN user_item ON user.id = user_item.user_id
LEFT JOIN item ON item.id = user_item.item_id
WHERE user.name = 'user_1';
类似但不一样的问题
前言
不幸的是,我认为您误解了:
希望这个答案有助于澄清这一点。
我先说一下我曾经使用过大型表(约 1 TB 大),其中包含数十亿行,查询通常在 1 秒内运行,在非常普通的硬件(4 个 CPU、16 GB 内存)上运行。内存)。
我还要指出,静态数据的大小并不是选择特定数据库系统的原因,因为从性能角度来看,它们都相对平等地处理相同数量的数据(无论您谈论的是 NoSQL 数据库还是 RDBMS) 。
数据组织
X 量的数据总是需要 Y 量的时间才能从磁盘读取。例如,在 100 GB 的表中,1 GB 的数据总是需要恒定的时间才能从磁盘读取,无论使用哪个数据库系统来存储该数据。类似于皮卡车如何将 100 块砖从一个地方运送到另一个地方,无论皮卡车是什么颜色,它仍然需要恒定的时间来运输砖块。
最耗时的是从一堆砖块(桌子)中找出客户想要运输的砖块。如果客户想要 100 块红砖,而这些砖块都存放在地上的一个大型无组织堆中(未索引的堆数据结构),有 10 种不同的颜色,那么要找到这 100 块红砖需要花很长时间才能找到所有砖块。
输入索引
索引是一种功能(几乎每个数据库系统都提供),用于将数据组织成一种高效的数据结构以供搜索(默认情况下通常为 B 树)。索引会按照定义中指定的列的顺序对表中的数据进行排序,然后将相关数据排序在一起,从而使搜索效率远高于无组织的堆表。
因此,如果我们对随机的砖堆应用索引,比如按颜色,那么所有红色砖块将堆叠在一起,然后蓝色砖块会堆叠在一起,然后黄色砖块会堆叠在一起,等等。现在,我们不必翻遍整个无序的砖堆,而是可以直接走到红色部分,拿起我们能拿到的前 100 块砖。这显然比漫无目的地搜索所有砖块要高效得多。
数据库中的表中数据组织方式也是如此。如果在该表上创建了适当的索引,那么可以直接通过这些索引查找与请求这些行的查询相对应的行,而不必扫描整个表。
为什么查询是相关的
我将强调一下我刚才所说的内容:
关于索引如何工作的提醒:
因此,为了使索引对特定查询有效且有用,需要根据该查询中具体使用的列进行适当的定义。
在我之前关于砖块的示例中,颜色是正在搜索的字段。如果我们按颜色对砖块进行排序(按颜色定义索引),而客户想要按尺寸对砖块进行排序,那么我们创建的索引对我们没有帮助。这类似于
WHERE
查询中的子句。了解最常运行哪些查询,更重要的是了解这些查询使用哪些谓词(JOIN
和WHERE
子句),有助于我们定义最合适的索引来服务这些查询。这一切都是齐头并进的,如果不谈论您特别想要良好执行的查询,几乎不可能谈论实践中的性能。
了解哪些查询最需要优化的另一个原因是它可能会影响您的表设计和架构。还有其他原因,但太多了,无法在一个答案中深入讨论。所以我坚持讨论这个讨论中最重要的一个(在我看来),即索引。
结局
是的,也不是。您对数据分割的看法是正确的,但您认为必须通过分区或分片来做到这一点的想法是错误的。这些不是用于性能调优的一般性讨论的正确工具,并且仅用于非常特定的目的。相反,您再次需要索引,它会按照底层数据结构(同样是B 树)中的组织方式为您拆分数据。
B 树的
O(log2(n))
搜索时间复杂度取决于其数据组织方式。这意味着,在一个包含 500 亿行的表中,也就是n = 50 billion
,搜索时间为log2(50 billion) = ~36
。换句话说,要在包含 500 亿行的表中查找 B 树索引,在最坏的情况下,只需抓取其中的 36 行即可找到您请求的数据。我的图形计算器可以在几毫秒内搜索 36 行数据。如您所见,有效地管理要搜索的数据是一个已解决的问题,与您最初的想法不同。
针对您的问题的最佳解决方案就是您已经设计的方案。
这是因为所有 RDBMS 都是为处理这种情况而设计的:一组具有多对多关系的表,以及可能有数十亿行,您可以在其中 SELECT、INSERT 或 DELETE 行。
任何“特殊”存储系统,如 NoSQL、列式存储、分区等,只有当您有“特殊”需求并且您的使用模式不再通用时才有用。
但对于数据库中数据的所有 OLTP 和 OLAP 正常处理,您提供的模式是典型的,因为它是在缺乏更具体的数据特征或使用模式的情况下解决问题的最佳模式。
如果您需要一次访问几行,则需要索引,并且您拥有所有需要的索引。如果您需要访问大量数据,没有什么比完整扫描更有效的了。
仅当您的数据不再“通用”,而是显示一些可以通过一些调整进行优化的特殊性(在组成中或在访问模式中)时,才可能进行更多优化,但只要您没有这种特殊性,无法进行优化,并且扩展也不是问题,因为 RDBMS 就是专门为此任务而设计的。
当然,当有数十亿条记录时,响应会变慢,但如果您具有典型的访问模式,则没有通用方法可以更有效地存储这数十亿条记录。
由于只有 100 个项目...如果没有更多项目,请更改为
SMALL UNSIGNED
(最大 65K)。这将节省 30GB。 (缩小表 --> 更少的 I/O 和更好的缓存 -->也许更好的查询性能。)考虑使用
item VARCHAR(..)
inuser_item
而不是needing the
itemstable. If the strings are usually "short", the cost of the extra space will be offset by avoiding an extra lookup. [I did this quite successfully with
picture_idand
标签`。]如果您始终使用其中一个索引,则 500 亿行并不是一个严重的问题。
考虑
INT UNSIGNED
一下user_id
——它将节省 4 个字节BIGINT
,但仅限于 40 亿。检查SELECT MAX(user_id) FROM user
一下您是否[无论出于何种原因]已经达到数十亿美元。“否则我们需要扫描所有内容”——什么查询导致了大扫描?
重要吗
ON DELETE CASCADE
?[这可能不重要。]PARTITIONing
对于删除旧数据很有用,但对于性能却无用SELECTs
。当数据太多以至于写入成为问题时,分片可能会很有用。但安装和维护比较麻烦。
当您遇到 TB 级的表时,您应该计算填满表需要多长时间。500 亿行,即使是分批处理,也可能需要数周或数月。硬件 RAID 控制器可能会有所帮助。
好的,我会将我的答案标记为已接受,但如果将来出现另一个更完整的答案,我可以更改它,我真的不在乎,重要的是我的问题的最正确/完整的答案。
我的问题被严重误解了,并且朝着不同的方向发展(除了Andrea B.那个)。
但是,尤其是由于评论中的“对话”,部分答案浮现出来,所以如果我们结合评论+答案,我认为我们可以正确回答。但我没有标记 Andrea B. 的答案,因为在学习之后我有了一个更完整的答案。
那么我们如何解决可能的表,在这种情况下是多对多 - 关联表(与其他表相比,其大小本质上是最容易增长的)。
我们可以假设模式本身已经设计得非常好(列数据类型等),查询模式也是如此(
SELECT
,INSERT
...),想象/假设它们已经优化到了极致,而且确实没有更好的方法来实现它们。如果读到这个答案的人不确定,可以去看看Rick James 的《多对多》指南,我觉得很酷。但是在您的情况下,想象一下您还知道该表的行数将呈指数增长,并且迟早将超过数十亿,您会怎么做?
首先,似乎没有一种可以接受的始终有效的方法或“技术”,因此以下所有解决方案可能有效也可能无效(也称为所有解决方法)。
在所有“解决方案”中,似乎它们都有一个共同点,基本上都有某种形式:
分治算法
换句话说,您需要找到一种尽可能拆分数据的方法,使其更易于管理。但与此同时,不要拆分太多,因为您可能最终处于最糟糕的位置,例如,您需要能够仍然
SELECT
快速检索数据,因此请记住避免“扫描”所有这些“分割”“部分”(这里我仍然在很高的层次上谈论,并且是一个抽象的想法,我没有谈论任何具体的事情!)这是技巧
WHERE
按子句拆分数据INDEX
WHERE
按子句拆分数据这是最明显的一个,而且非常基本,但可能不适用于所有查询,或者有时您确实需要查找某些内容并需要扫描“所有数据”。显然,这里有
LIMIT
所有OFFSET
好的实践。另外,从评论中复制粘贴(抱歉,如果可能的话我会链接评论)
拆分数据
INDEX
摘自JD的 Finale回答 (在谈到砖块之后)其实非常有趣。
我不会添加他写的内容以避免重复,因此您应该查看该答案,但该技术是正确的。虽然我个人知道这一点,但如果你以这种方式思考并牢记这种解释,我认为情况会有所不同。实际上,我们只是使用索引来分割“数据群体”,即分而治之。
分割使用数据 | “档案”概念
例如使用最近最少使用(LRU)
因此,这不一定适用于所有情况,但如果您可以实现一种逻辑,基本上,如果您知道数据是“旧的”或较少使用的数据,则可以避免访问所有数据。以下可能有不同的方法来实现这一点
DATETIME
- (或者可能甚至id
大于<VALUE>
等等。对于第二点,例如,如果您识别出数据中的一种模式,其中大量数据(甚至可能是大多数)不再被访问,您可以将其移动(或重命名表)到另一个数据中(
user_item_archive
),然后创建一个新的user_item
并研究新的。这过于简单化并且取决于用例,但重要的是概念。我很确定网上有关于这个概念的文章,如果有人找到任何(或者如果我将来会)我们可以在此处添加。
分片
这是唯一“众所周知”的技术,但它肯定是一把双刃剑。
percona 上的这个博客很有趣
有人提到分区,但我不推荐,因为在我看来,它几乎没有用例,而且我在需要删除数据时看到更多。访问已经分区的数据可能会带来很多麻烦。
此外,从Rick James 的回答中,第一部分尝试优化模式示例(这很好,但它只是一个示例),最后 2 位在我看来很有趣