0

这与一致性哈希有关，虽然我从概念上理解我需要做什么，但我很难将其转换为代码。

我正在尝试将给定的键空间（例如 128 位）划分为大小相等的分区。我想要每个分区的上限（最高键）。

基本上，我将如何完成这个？

#define KEYSPACE_BYTE_SIZE  16
#define KEYSPACE_BIT_SIZE   (KEYSPACE_BYTE_SIZE * 8)

typedef struct _key
{ 
    char byte[KEYSPACE_BYTE_SIZE];
} key;

key * partition_keyspace( int num_partitions )
{
    key * partitions = malloc( sizeof(key) * num_partitions );

    // ...

}

编辑：

我想另一种说法是：

for (i = 0; i < num_partitions; i++)
{
    partitions[i] = ((2 ^ KEYSPACE_BIT_SIZE) / num_partitions) * i;
}

当然，问题是 2 ^ 128 是一个非常大的数字，并且不能包含在 C 中用于进行数学运算的任何单个整数变量中（因此是 char[16] 结构）。

我真的不想为此使用大量库（或任何库）。

编辑：

虽然，实际上我正在寻找的数字是：

for (i = 0; i < num_partitions; i++)
{
    partitions[i] = (((2 ^ KEYSPACE_BIT_SIZE) / num_partitions) * (i + 1)) - 1;
}
4

3 回答 3

2

任何特定分区中的最高密钥显然都由所有位组成1。如果您n的密钥有低位，m分区ID 有高位，那么您需要做的就是运行一个m-bit 计数器，并将其与1 连接n。
为了说明，假设一个 8 位键空间，高 2 位用于分区（so num_partitions = 2^2 = 4，低 6 位用于键。每个分区中的最高键将是这四个：

00 111111
01 111111
10 111111
11 111111

为了生成它们，您需要做的就是：

for (int i = 0; i < num_partitions; i++)
    highest_key = (i << 6) | 0x3f // where 6 is key_bits and 0x3f is six ones.

当然，这是假设num_partitions是 2 的幂。

自然，对于像您这样大的键空间，它不会像上面那样简单，因为您不能将所有内容都放入一个变量中。不过，原理还是一样的。只要你num_partitions的足够小，你可以将计数器放入一个普通int变量中，将其复制到高位，然后用 1 填充其余部分是微不足道的。

于 2010-05-28T21:04:49.360 回答
0

根据 tzaman 的回答，这是我的解决方案。它最多允许 255 个分区（尽管可以更改）。它不需要 2 num_partitions 的幂......它只会让最后一个分区占用剩下的任何东西。

如果您发现任何错误，请告诉我... :)

key * partition_keyspace( unsigned int num_partitions )
{
    assert( num_partitions > 0 );
    assert( num_partitions < 0xFF );

    key * partitions = (key *) malloc( sizeof(key) * num_partitions );

    // fill every bit
    memset( partitions, 0xFF, sizeof(key) * num_partitions );

    // calculate how many bits of the top byte needs to be filled by 1's
    unsigned char fill_bits = 0;
    while (num_partitions > (1 << fill_bits)) fill_bits++;
    fill_bits = 8 - fill_bits;

    // fill the top byte with the base number of 1's
    unsigned char fill_part = 0;
    for (unsigned int i = 0; i < fill_bits; i++) fill_part |= 1 << i;

    // last partition takes up whatever remains, so don't process it (hence the -1)
    for (unsigned char i = 0; i < num_partitions - 1; i++)
    {
        partitions[i].byte[0] = fill_part | (i << fill_bits);
    }

    return partitions;
}
于 2010-05-28T22:02:58.943 回答
0

我不确定我是否理解您的问题的上下文 - 我没有研究过一致的哈希。

这个问题几乎等同于“我如何在没有排序的情况下进行排序”。

另一种方法可能是这样做：

iter = seed() #initialize to the bottom of the hash keys
for(i = 0 to partitionbound)
{
   iter = nextIter(iter);
}

这是线性时间。但是，它不需要密钥空间的先验知识，除非 nextIter 遵循某种顺序。

如果你正在对 [0, 2^128] -> {values} 进行分区，例如，你正在做一些分布式计算或你有什么，你的运气要好得多，因为整数结构良好。

我建议在一个结构中使用 4 个 32 位整数并编写自己的 bigint 例程来解决您需要解决的问题，这有点愚蠢。

如果你有不使用 C++ 的自由，Common Lisp 内置了 bigints。我发现它很方便。

如果您有可表示的键...

然而，当在一些空间 a 中寻找一些大小相等的 k 分区时，我会这样处理问题：

if( n % k)
{
   return "not equal-sized partition!"
}
//could be forking/threading, whatever.
for(int i = 0; i < n; i+=k)
{
   process(i, i+k-1);
}


process(bottom, top)
{
   sort(a[bottom], a[top]);
   return a[top]; //you'll have to figure out where to dump the results.
}
于 2010-05-28T20:28:16.153 回答