确保已查看的项目不再被看到

Question

我有一个可能的解决方案来解决我正在尝试解决的问题，但是我想通过这里运行它以保证安全。面临的挑战是确保在考试申请中通过一些测试问题的用户在后续测试中不会再遇到这些问题。

我没有使用SQL数据库，这将允许我使用左连接，子查询，临时表等。我正在使用Google App Engine的数据存储，并希望在单个HTTP请求和单个线程中获取所需的信息，最好在一秒钟之内。

假设有一个特定类型的100,000个词汇问题池（例如同义词）。应用程序将从考试中选择30个问题。这是我正在考虑的：

• 当一个问题被创建时，为它指定一个随机整数在池中的位置。
• 在个人第一次考试时，选择一个随机数，然后选择前100个问题，按位置排序，其位置大于该数量。把这个数字作为一个问题窗口的下界，也作为整个游泳池的起始位置。跟踪结果集中最后一个问题的（最大）位置作为新窗口的上限。
• 从窗口中随机选择30个问题，然后将它们作为部分。将剩下的70个问题存储起来，以便稍后在考试中使用，并可能在随后的考试中使用。
• 随着用户浏览其他章节（例如练习），并且当前窗口中剩余问题的列表已耗尽，请从池中选择接下来的100个问题，这些问题的位置大于上次存储的上限。使旧的上界成为新的下界并找到新窗口的上界。
• 如果查询返回的问题少于100个，则绕回到0的位置并继续，直到遇到原始起点（任何人都不可能经过整个池，但重要的是肯定）。

这些职位随机分配的主要原因是为了消除写作问题的风格变化的影响，例如，在较少的经验和较晚的经验较少的时候写出的问题。

应用程序将为问题指定位置而不检查位置是否唯一。如果有足够多的问题，birthday paradox表明重复职位将变得越来越普遍。我的想法是偶尔出现重复也不会有什么坏处，并且这会使事情变得更简单，而不是确保给定的职位是唯一的，这可能会导致重试和相关的网络成本。没有重复的问题比确保向用户显示一系列问题中的每个问题更重要。

有没有更好的方法来做到这一点？可以不担心重复职位吗？

Answer 1

使用0到1之间的浮点数而不是整数。它有一个很好的域，它不会随着实体数量的变化而变化，双倍有一个52比特的尾数，在我们可以预料到一次碰撞之前给我们大约2^26个对象;远远超过你处理的内容。

Answer 2

我不认为你需要从100个问题池中“随机选择30个”。这100人是随机选择的 - 如果你拿到前30名，这些将会被随机分配。你的代码会更简单，不会随机性。

Answer 3

把项目按一定的顺序，并给每一个数字。为从零开始的用户维护一个计数器。为每个用户生成一个随机（ish）密钥。选择一个函数，它将0 ... N范围内的整数与0 ... N范围内的另一个整数进行映射，使得对于任何关键值，整数之间的映射都是双射的。当你需要一个物品时，取出计数器的值，将其与键一起放入函数中，并使用该数字索引到物品列表中。增加计数器。

您需要为每个用户存储的所有内容都是密钥和计数器，并且您有保证不会重复任何项目。这基本上是一种即时构建巨大排列的方式。

问题当然是选择功能！

一个简单的将是f(counter, key) = (counter + key) mod N，虽然这将起作用，但它不会随机化所有项目，所以每个人都会按照相同的顺序获得项目，只是从不同的地方开始。如果N + 1是素数，则可以使用F（计数器，键）=（（（计数器+ 1）*（键+ 1））模（N + 1））-1，这将工作得很好。如果范围是0 ... 2^64，则可以使用具有64位块的任何分组密码，这将提供出色的随机性。但目前还不清楚你是否可以适应更小的尺寸。

我会仔细研究一下，看看能不能找到一个通用的函数。这是我遇到的一个问题，最终得到一个好的答案会很棒。如果我找到任何东西，我会编辑这个答案。

编辑：好的，我们走吧！我从a thread i started on sci.crypt获得了关键点子，特别是来自一个全能网络英雄Paul Rubin。

战略略有改变。把你的项目放在一个列表中，这样它们可以被索引访问。选择一个数B，使得2^B> = N - 任何值都可以，但是你真的想要最小的那个（即N-1的基数2对数的上限）。然后我们将2^B表示为M.设置一个计数器，它将从0运行到M-1，每个用户的密钥可以是任意字节串 - 随机整数可能是最简单的。设置魔术函数，这是一个双射，又名排列，在整数集合0 ... M-1（见下文！）。当你想要一个项目时，取计数器的值，增加计数器，然后通过魔术函数将原始值得到一个索引;如果索引大于N-1，则将其丢弃，然后重复该过程。重复，直到你得到一个小于N的指数。有时候，你需要经过一个或多个无用的指数，然后才能得到一个好的指数，但平均而言，这将需要M/N次尝试，这并不算太糟糕（如果您选择尽可能小的B，则小于2）。

顺便提及，计算一个数的基体2的对数的上限是容易的：

int lb(int x) { 
    int lb = 0; 
    while (x > 0) { 
     ++lb; 
     x >>= 1; 
    } 
    return lb; 
} 

好了，所以魔术功能，其中多个从0映射... M-1到另一个这样的号码。我在上面提到了分组密码，这就是我们要使用的。除了我们的块是B位长，这是可变的，比正常的64或128位小。所以我们需要一个适用于小型变量块的密码。所以我们要写我们自己的 - 一个可变尺寸的轻微不平衡Feistel cipher。简单！

要做到Feistel密码，您需要：

• 号B_L和B_R这样B_L + B_R = B.在平衡Feistel密码中，B_L = B_R，所以B必须是偶数;我们将使用B_L = B/2和B_R = B - B_L，即类似于平衡网络，但当B为奇数时，B_R略大一些。
• 一些回合，称为C;我们会用i来计数，这会从0到C-1。我被告知4和10是绝对最低限度，所以让我们继续与12保持安全。
• 密钥表，这仅仅是为每个回合都称为K_I，所有从i上述主密钥导出的密钥。你可以在每一轮使用相同的密钥;正确的密码有一些从主密钥中生成子密钥的方法。我建议只将整数连接到主密钥。
• 的循环函数，称为F，其需要一个B_R位的子块和一个循环密钥，并产生一个B_L比特子块;在这些限制之内，它可以是绝对的任何东西。这是Feistel密码的核心。对我们来说，最好的选择就是使用一个已经存在的加密散列函数，因为这很容易且可靠。 SHA-1是目前的最爱。我们给它一个循环键，然后是输入子块，计算散列，然后从一端取B_L位（与哪个无关）作为我们的输出。

Feistel密码是这样工作的：

1. 以一个B比特输入字
2. 对于i从0到C-1：
   1. 拆分字分成左右子块L和R，分别用B_L和B_R位
   2. 将R和K_i放入循环函数F以产生加密值X
   3. 添加X为L，不考虑任何进位，它从顶部比特
   4. 重新组装大号溢出和圆R是错误的方法，在左侧和L在右侧R，以形成用于B中的新的值

对于B的最终值是加密的值，并且是从密码的输出。解密这个过程非常简单 - 上面的步骤相反 - 但由于我们不需要解密，所以不用担心。

所以你去。维护一个计数器（以及一个密钥和M的值），用一个小密码对其值进行加密，并将结果用作索引。考虑到密码是一个排列组合，很容易证明这不会重复，这会让您的客户满意。更好的是，考虑到密码的密码属性，你也可以声称学生将无法预测下一个问题（这可能不重要，但听起来很酷）。

这一切不仅仅是增加一个计数器，并给他们以项目更复杂一些，但它并不难。你可以在一百行的java中做到这一点。那么，i can do it in a hundred lines of java - 我不知道你！ :)

顺便说一句，这将与项目的成长池的工作，只要你总是在结尾处添加项目，但它绝不会挑项目编号比M高在许多情况下，虽然，会给你一些成长空间。

Answer 4

这是一种考虑的方法。没有很多时间来编写和编辑，所以提前道歉以解决任何问题。创建一个包含您的100K问题的模型，以便您可以使用密钥名称（例如question_000001，question_0000002等）访问它们。当学生注册时使用三个TextProperties创建他/她的记录。创建记录时，从1-100K生成一组随机数字并将其序列化为分隔文本字符串。第二个字符串是记录尚未被任务队列处理的回答问题。第三个字符串用于TQ处理后的回答问题。

当用户登录时，发送要被约束的字符串的前N个字段（N =足够多的问题以服务于任何类型的会话）以及整个已回答的问题字符串。在客户端，将它们分解成一系列要问的问题，并回答问题。如果问题在哈希中，请跳过它。当用户解决这些问题时，每个人都会通过简单的get_by_id调用来处理您的在线处理程序。当每个问题得到解答时，客户端将其发送到GAE，在GAE中将问题编号附加到最近回答问题的文本字段，并设置一个布尔值标记以便稍后进行TQ处理。一天或一天​​左右，运行一个任务队列流程，通过拆分要提问的问题文本字段并删除自上次更新后回答的所有问题来更新记录。将这些作为已完成的问题移至第三个文本字段。

请注意，您只需使用两个文本字段即可跳过很多这样的内容，并在发布答案时进行更新。然而，我的倾向是总是尽可能少地使用在线处理程序，并将事情推向TQ。

没有计数器（总是通过获取分割GAE文本字段的长度可用），没有查询（TQ布尔标志查询除外）。没有复杂性。有很多方法可以提高效率：传输的数据量。等

希望我有更多的时间来更确保这是100％符合您的需求，但必须去。所以我给你留下了一个“HTH”-stevep