执行 C++ 代码时快速频繁地访问文件
Fast and frequent file access while executing C++ code
我正在寻找关于如何最好地实现我的代码以满足以下要求的建议。在执行我的 c++ 代码期间，我经常需要访问存储在字典中的数据，而字典本身存储在一个文本文件中。字典包含 1 亿个条目，在任何时间点，我的代码都会查询与这 1 亿个条目中的某个特定条目相对应的数据。进行这些查询没有特定的模式，而且在程序执行的生命周期内，并不是查询字典中的所有条目。此外，字典在程序的生命周期内将保持不变。每个表项对应的数据并不都是一样长的。我的词典文件大小约为 24 GB，而我只有 16 GB 的 RAM 内存。我需要我的应用程序非常快，所以我想知道如何最好地实现这样一个系统，以便可以最大限度地减少读取访问时间。
我也是编词典的人，所以我可以灵活地将我的词典分成几个小册子。在考虑我能做什么的时候，我想到了以下，但不确定两者是否都好。
- 如果我从文件开头开始存储字典中每个条目的行偏移量，那么要读取相应条目的数据，我可以直接跳转到相应的偏移量。有没有一种方法可以使用 say ifstream 来执行此操作，而无需遍历所有行直到偏移行？在网络上快速搜索似乎表明这至少对于 ifstream 是不可能的，还有其他方法可以做到吗？
- 另一个极端的想法是为字典中的每个条目创建一个文件，这样我就有 1 亿个文件。这种方法在打开和关闭文件流时有明显的开销。
总的来说，我不相信我想到的任何一种方法都是好的，所以我想听听一些建议。
一旦您决定使用 on-disk 数据结构，它就不再是一个 C++ 问题，而是一个系统设计问题。你想实现一个 disk-based 字典。
从现在开始，您应该考虑以下因素：您的磁盘参数是什么？是固态硬盘吗？硬盘？你每秒的平均查找率是多少？您的 Lookup() 方法有 20usec - 10ms 的延迟是否合适？
On-disk 词典需要 随机 磁盘搜索。这种寻道对于 SSD 有几十微秒的延迟，对于 HDD 有 3-10ms 的延迟。此外，您可以进行多少次此类搜索也是有限制的。例如，您可以阅读 this article。 CPU 不再是瓶颈，IO 变得很重要。
如果您想追求这个方向 - 有最先进的 C++ 库可以为您提供 on-disk key-value store（不需要 out-of- 进程数据库）或者您可以自己做一些简单的事情。
如果您的应用程序是批处理而不是 server/UI 程序，即您有另一个有限的项目流要加入字典，那么我建议阅读外部算法，例如 Hash Join 或 MapReduce。在这些情况下，可以这样组织您的数据，而不是拥有 1 个 24GB 的巨大词典，您可以拥有 10 个大小为 2.4GB 的词典，然后依次加载每个词典并加入。但是为此，我需要了解您要解决的问题类型。
总而言之，您需要先设计系统，然后再编写解决方案。使用 mmap 或尝试或评论中提到的其他技巧是局部优化（如果有的话），它们不太可能 game-changers。在进行 back-on-the-envelope 计算以了解主要方向之前，我不会急于探索它们。
好吧，如果您只需要访问键值，并且数据大于内存所能容纳的数据，那么答案就是 NoSQL 数据库。这意味着键和任意值的哈希类型索引。如果您没有其他限制，例如来自许多客户端的并发访问或扩展的可扩展性，您可以自己推出。对于自定义 NoSQL 数据库来说，最重要的问题是提供索引文件大小的键的预期数量。您可以找到相当不错的散列算法，并且必须在更大的索引文件和更高的冲突风险之间做出决定。无论如何，除非您想使用 tera 字节的索引文件，否则您的代码必须准备好应对可能的冲突。
详细的示例说明远远超出了我在 SO 答案中所能写的，但它应该给你一个起点。
下一个优化将是什么应该缓存在内存中。这取决于您期望查询的方式。如果不太可能多次查询同一个键，您可以只依赖 OS 和文件系统缓存，稍微改进一下内存映射文件，否则缓存（索引 and/or值）是有道理的。在这里您可以再次选择并实施缓存算法。
或者如果您认为它太复杂而无益，您可以搜索是否有一个免费的 NoSQL 数据库可以满足您的要求...
我正在寻找关于如何最好地实现我的代码以满足以下要求的建议。在执行我的 c++ 代码期间，我经常需要访问存储在字典中的数据，而字典本身存储在一个文本文件中。字典包含 1 亿个条目，在任何时间点，我的代码都会查询与这 1 亿个条目中的某个特定条目相对应的数据。进行这些查询没有特定的模式，而且在程序执行的生命周期内，并不是查询字典中的所有条目。此外，字典在程序的生命周期内将保持不变。每个表项对应的数据并不都是一样长的。我的词典文件大小约为 24 GB，而我只有 16 GB 的 RAM 内存。我需要我的应用程序非常快，所以我想知道如何最好地实现这样一个系统，以便可以最大限度地减少读取访问时间。
我也是编词典的人，所以我可以灵活地将我的词典分成几个小册子。在考虑我能做什么的时候，我想到了以下，但不确定两者是否都好。
- 如果我从文件开头开始存储字典中每个条目的行偏移量，那么要读取相应条目的数据，我可以直接跳转到相应的偏移量。有没有一种方法可以使用 say ifstream 来执行此操作，而无需遍历所有行直到偏移行？在网络上快速搜索似乎表明这至少对于 ifstream 是不可能的，还有其他方法可以做到吗？
- 另一个极端的想法是为字典中的每个条目创建一个文件，这样我就有 1 亿个文件。这种方法在打开和关闭文件流时有明显的开销。
总的来说，我不相信我想到的任何一种方法都是好的，所以我想听听一些建议。
一旦您决定使用 on-disk 数据结构，它就不再是一个 C++ 问题，而是一个系统设计问题。你想实现一个 disk-based 字典。
从现在开始，您应该考虑以下因素：您的磁盘参数是什么？是固态硬盘吗？硬盘？你每秒的平均查找率是多少？您的 Lookup() 方法有 20usec - 10ms 的延迟是否合适？
On-disk 词典需要 随机 磁盘搜索。这种寻道对于 SSD 有几十微秒的延迟，对于 HDD 有 3-10ms 的延迟。此外，您可以进行多少次此类搜索也是有限制的。例如，您可以阅读 this article。 CPU 不再是瓶颈，IO 变得很重要。
如果您想追求这个方向 - 有最先进的 C++ 库可以为您提供 on-disk key-value store（不需要 out-of- 进程数据库）或者您可以自己做一些简单的事情。
如果您的应用程序是批处理而不是 server/UI 程序，即您有另一个有限的项目流要加入字典，那么我建议阅读外部算法，例如 Hash Join 或 MapReduce。在这些情况下，可以这样组织您的数据，而不是拥有 1 个 24GB 的巨大词典，您可以拥有 10 个大小为 2.4GB 的词典，然后依次加载每个词典并加入。但是为此，我需要了解您要解决的问题类型。
总而言之，您需要先设计系统，然后再编写解决方案。使用 mmap 或尝试或评论中提到的其他技巧是局部优化（如果有的话），它们不太可能 game-changers。在进行 back-on-the-envelope 计算以了解主要方向之前，我不会急于探索它们。
好吧，如果您只需要访问键值，并且数据大于内存所能容纳的数据，那么答案就是 NoSQL 数据库。这意味着键和任意值的哈希类型索引。如果您没有其他限制，例如来自许多客户端的并发访问或扩展的可扩展性，您可以自己推出。对于自定义 NoSQL 数据库来说，最重要的问题是提供索引文件大小的键的预期数量。您可以找到相当不错的散列算法，并且必须在更大的索引文件和更高的冲突风险之间做出决定。无论如何，除非您想使用 tera 字节的索引文件，否则您的代码必须准备好应对可能的冲突。
详细的示例说明远远超出了我在 SO 答案中所能写的，但它应该给你一个起点。
下一个优化将是什么应该缓存在内存中。这取决于您期望查询的方式。如果不太可能多次查询同一个键，您可以只依赖 OS 和文件系统缓存，稍微改进一下内存映射文件，否则缓存（索引 and/or值）是有道理的。在这里您可以再次选择并实施缓存算法。
或者如果您认为它太复杂而无益，您可以搜索是否有一个免费的 NoSQL 数据库可以满足您的要求...