键值存储中的反向索引和数据建模
Reverse Indexing and Data modeling in Key-Value store
我是 key-value 商店的新手。我的 objective 是使用嵌入式键值存储来保持持久数据模型。如果使用传统 RDBMS 设计，数据模型包含很少的相关 table。我正在检查 medium article 为键值存储建模 table。尽管这篇文章将 Level DB 与 Java 结合使用，但我计划在我的工作中将 RocksDB 或 FASTER 与 C++ 结合使用。
它使用一种方案，其中一个键用于每行的每个属性，如下例所示。
$table_name:$primary_key_value:$attribute_name = $value
当用户代码确切知道要获取哪个键时，以上内容适用于点查找。但是有一些场景，比如搜索具有相同电子邮件地址的用户，或者搜索某个年龄以上的用户或搜索特定性别的用户。在搜索场景中，文章对所有键执行线性扫描。在每次迭代中，它都会检查键的模式，并在找到具有匹配模式的键后应用业务逻辑（检查匹配值）。
看来，这种搜索效率很低，最坏的情况下需要遍历整个商店。解决这个问题需要反向查找table。我的问题是
How to model the reverse lookup table ? Is it some sort of reinvention of wheel ? Is there any alternative way ?
一个容易想到的解决方案是为每个可索引 属性 设置一个 separate ? 存储，如下所示。
$table_name:$attribute_name:$value_1 = $primary_key_value
使用这种方法，直接的问题是
How to handle collisions in this reverse lookup table ? because multiple $primary_keys may be associated with the same vale.
作为即时解决方案，可以存储 array 多个主键，而不是存储单个值，如下所示。
$table_name:$attribute_name:$value_1 = [$primary_key_value_1, ... , $primary_key_value_N]
但是这种类型的建模需要用户代码从字符串中解析数组，并在多次操作后再次将其序列化为字符串（假设底层键值存储不知道数组值）。
Is it efficient to store multiple keys as array value ? or there exists some vendor provided efficient way ?
假设像设计这样的字符串数组有效，每个可索引属性都必须有这样的索引。因此，这提供了对索引内容和不索引内容的细粒度控制。想到的下一个设计决定是这些索引将存储在哪里？
should the indexes be stored in a separate store/file ? or in the same store/file the actual data belongs to ? Should there be a different store for each property ?
对于这个问题，我没有任何线索，因为这两种方法都需要或多或少相同数量的 I/O。然而，拥有大数据文件将在磁盘上有更多的东西而在内存上更少的东西（所以更多 I/O），而对于多个文件，内存上的东西会更多，因此页面错误会更少。根据特定键值存储的架构，这个假设可能是完全错误的。同时，拥有太多文件变成了管理复杂文件结构的问题。此外，维护索引需要用于插入、更新和删除操作的事务。拥有多个文件会导致多个树中的单个更新，而拥有单个文件会导致单个树中的多个更新。
Is transaction more specifically transaction involving multiple store/files supported ?
不仅索引还有一些 table 的元信息，这些信息也需要与 table 数据一起保存。要生成新的主键（自动递增），需要事先了解最后生成的行号或最后一个主键，因为 COUNT(*) 之类的东西不起作用。此外，由于所有键都未编入索引，meta 信息可能包括哪些属性已编入索引以及哪些属性未编入索引。
How to store the meta information of each table ?
meta table 也出现了同样的一组问题。例如meta 应该是一个单独的 store/file 吗？此外，正如我们注意到并非所有属性都被索引，我们甚至可能决定将每一行存储为数据存储中的 JSON 编码值，并将其与索引存储一起保存。底层键值存储供应商会将 JSON 视为字符串值，如下所示。
$table_name:data:$primary_key_value = {$attr_1_name: $attr_1_value, ..., $attr_N_name: $attr_N_value}
...
$table_name:index:$attribute_name = [$primary1, ..., $primaryN]
但是通过指向主键的索引仍然可以进行反向查找。
Is there any drawbacks of using JSON encoded values instead of storing all properties as separate keys ?
到目前为止，除了强制用户使用 JSON 编码和 JSON encoding/decoding 的一些堆分配外，我找不到使用此方法的任何缺点。
上述问题并非特定于任何特定应用程序。这些问题非常普遍，可以与使用 key-value 商店的所有开发相关联。所以知道有没有再造轮子是很有必要的。
Is there any defacto standard solution of all the problems mentioned in the question ? Does the solutions differ from the one stated in the question ?
How to model the reverse lookup table ? Is it some sort of reinvention of wheel ? Is there any alternative way ?
- 您描述的所有方式都是创建索引的有效方式。
- 它不在RocksDB中重新发明轮子，因为RocksDB不支持索引。
- 这取决于数据，一般情况下你需要将索引值和主键复制到另一个space来创建索引。
How to handle collisions in this reverse lookup table ? because multiple $primary_keys may be associated with the same vale.
您可以使用 JSON（或其他方式）序列化 pks。这种方法的问题是当 pks 变得非常大时（这可能是也可能不是问题）。
Is it efficient to store multiple keys as array value ? or there exists some vendor provided efficient way ?
有了 RocksDB，你什么都做不了 "easier"。
你没有提到下面的方法：
$table_name:$attribute_name:$value_1:$primary_key_value_1 = ""
$table_name:$attribute_name:$value_1:$primary_key_value_2 = ""
...
$table_name:$attribute_name:$value_1:$primary_key_value_n = ""
其中值为空。索引 pk 是键的一部分。
should the indexes be stored in a separate store/file ? or in the same store/file the actual data belongs to ? Should there be a different store for each property ?
这取决于键值存储。使用 rocksdb，如果你需要事务，你必须坚持一个 db 文件。
Is transaction more specifically transaction involving multiple store/files supported ?
只有 Oracle Berkeley DB 和 WiredTiger 支持该功能。
How to store the meta information of each table ?
元数据可以在数据库或代码中。
Is there any drawbacks of using JSON encoded values instead of storing all properties as separate keys ?
是的，就像我上面说的，如果你把所有的pk编码成一个值，当pk的数量很大时，可能会导致下游出现问题。例如，您需要阅读整个列表才能进行分页。
Is there any defacto standard solution of all the problems mentioned in the question ? Does the solutions differ from the one stated in the question ?
总结一下：
- 使用 RocksDB，使用单个数据库文件
- 在索引中，将主键编码在键中，并将值留空，以便能够分页。
我是 key-value 商店的新手。我的 objective 是使用嵌入式键值存储来保持持久数据模型。如果使用传统 RDBMS 设计，数据模型包含很少的相关 table。我正在检查 medium article 为键值存储建模 table。尽管这篇文章将 Level DB 与 Java 结合使用，但我计划在我的工作中将 RocksDB 或 FASTER 与 C++ 结合使用。
它使用一种方案，其中一个键用于每行的每个属性，如下例所示。
$table_name:$primary_key_value:$attribute_name = $value
当用户代码确切知道要获取哪个键时，以上内容适用于点查找。但是有一些场景，比如搜索具有相同电子邮件地址的用户，或者搜索某个年龄以上的用户或搜索特定性别的用户。在搜索场景中，文章对所有键执行线性扫描。在每次迭代中，它都会检查键的模式，并在找到具有匹配模式的键后应用业务逻辑（检查匹配值）。
看来，这种搜索效率很低，最坏的情况下需要遍历整个商店。解决这个问题需要反向查找table。我的问题是
How to model the reverse lookup table ? Is it some sort of reinvention of wheel ? Is there any alternative way ?
一个容易想到的解决方案是为每个可索引 属性 设置一个 separate ? 存储，如下所示。
$table_name:$attribute_name:$value_1 = $primary_key_value
使用这种方法，直接的问题是
How to handle collisions in this reverse lookup table ? because multiple
$primary_keys may be associated with the same vale.
作为即时解决方案，可以存储 array 多个主键，而不是存储单个值，如下所示。
$table_name:$attribute_name:$value_1 = [$primary_key_value_1, ... , $primary_key_value_N]
但是这种类型的建模需要用户代码从字符串中解析数组，并在多次操作后再次将其序列化为字符串（假设底层键值存储不知道数组值）。
Is it efficient to store multiple keys as array value ? or there exists some vendor provided efficient way ?
假设像设计这样的字符串数组有效，每个可索引属性都必须有这样的索引。因此，这提供了对索引内容和不索引内容的细粒度控制。想到的下一个设计决定是这些索引将存储在哪里？
should the indexes be stored in a separate store/file ? or in the same store/file the actual data belongs to ? Should there be a different store for each property ?
对于这个问题，我没有任何线索，因为这两种方法都需要或多或少相同数量的 I/O。然而，拥有大数据文件将在磁盘上有更多的东西而在内存上更少的东西（所以更多 I/O），而对于多个文件，内存上的东西会更多，因此页面错误会更少。根据特定键值存储的架构，这个假设可能是完全错误的。同时，拥有太多文件变成了管理复杂文件结构的问题。此外，维护索引需要用于插入、更新和删除操作的事务。拥有多个文件会导致多个树中的单个更新，而拥有单个文件会导致单个树中的多个更新。
Is transaction more specifically transaction involving multiple store/files supported ?
不仅索引还有一些 table 的元信息，这些信息也需要与 table 数据一起保存。要生成新的主键（自动递增），需要事先了解最后生成的行号或最后一个主键，因为 COUNT(*) 之类的东西不起作用。此外，由于所有键都未编入索引，meta 信息可能包括哪些属性已编入索引以及哪些属性未编入索引。
How to store the meta information of each table ?
meta table 也出现了同样的一组问题。例如meta 应该是一个单独的 store/file 吗？此外，正如我们注意到并非所有属性都被索引，我们甚至可能决定将每一行存储为数据存储中的 JSON 编码值，并将其与索引存储一起保存。底层键值存储供应商会将 JSON 视为字符串值，如下所示。
$table_name:data:$primary_key_value = {$attr_1_name: $attr_1_value, ..., $attr_N_name: $attr_N_value}
...
$table_name:index:$attribute_name = [$primary1, ..., $primaryN]
但是通过指向主键的索引仍然可以进行反向查找。
Is there any drawbacks of using JSON encoded values instead of storing all properties as separate keys ?
到目前为止，除了强制用户使用 JSON 编码和 JSON encoding/decoding 的一些堆分配外，我找不到使用此方法的任何缺点。
上述问题并非特定于任何特定应用程序。这些问题非常普遍，可以与使用 key-value 商店的所有开发相关联。所以知道有没有再造轮子是很有必要的。
Is there any defacto standard solution of all the problems mentioned in the question ? Does the solutions differ from the one stated in the question ?
How to model the reverse lookup table ? Is it some sort of reinvention of wheel ? Is there any alternative way ?
- 您描述的所有方式都是创建索引的有效方式。
- 它不在RocksDB中重新发明轮子，因为RocksDB不支持索引。
- 这取决于数据，一般情况下你需要将索引值和主键复制到另一个space来创建索引。
How to handle collisions in this reverse lookup table ? because multiple $primary_keys may be associated with the same vale.
您可以使用 JSON（或其他方式）序列化 pks。这种方法的问题是当 pks 变得非常大时（这可能是也可能不是问题）。
Is it efficient to store multiple keys as array value ? or there exists some vendor provided efficient way ?
有了 RocksDB，你什么都做不了 "easier"。
你没有提到下面的方法：
$table_name:$attribute_name:$value_1:$primary_key_value_1 = ""
$table_name:$attribute_name:$value_1:$primary_key_value_2 = ""
...
$table_name:$attribute_name:$value_1:$primary_key_value_n = ""
其中值为空。索引 pk 是键的一部分。
should the indexes be stored in a separate store/file ? or in the same store/file the actual data belongs to ? Should there be a different store for each property ?
这取决于键值存储。使用 rocksdb，如果你需要事务，你必须坚持一个 db 文件。
Is transaction more specifically transaction involving multiple store/files supported ?
只有 Oracle Berkeley DB 和 WiredTiger 支持该功能。
How to store the meta information of each table ?
元数据可以在数据库或代码中。
Is there any drawbacks of using JSON encoded values instead of storing all properties as separate keys ?
是的，就像我上面说的，如果你把所有的pk编码成一个值，当pk的数量很大时，可能会导致下游出现问题。例如，您需要阅读整个列表才能进行分页。
Is there any defacto standard solution of all the problems mentioned in the question ? Does the solutions differ from the one stated in the question ?
总结一下：
- 使用 RocksDB，使用单个数据库文件
- 在索引中，将主键编码在键中，并将值留空，以便能够分页。