AppEngine Memcache原子获取和删除 [英] AppEngine Memcache atomic get-and-delete

问题描述

我想将身份验证质询存储在我按随机整数编制索引的Google AppEngine的Memcache中.因此，例如，我有如下条目:

I would like to store authentication challenges in Google AppEngine's Memcache that I index by a random integer. So, for example I have entries like:

 5932 -> IUH#(*HKJSBOHFBAHV&EG*Y$#)*HF739r7fGA$74gflUSAB
11234 -> (*&YGy3g87gfGYJKY#GRO&Fta9p8yfdlhuH$UT#K&GAk&#G
-3944 -> 8yU#*&GfgKGF&Y@dy;0aU#(Y9fyhgyL$BVGAZD(O$fg($&G
   .
   :

如果客户端随后尝试对请求进行身份验证，它将向我发送质询ID(例如-3944)和相应的计算得出的响应.

If a client then tries to authenticate a request, it will send me the challenge ID (e.g. -3944) and the corresponding calculated response.

现在，我的服务器需要从列表中获取挑战号-3944并将其标记为已使用或(最好)立即将其删除，以防止重播攻击(第二个请求已通过相同的挑战进行了身份验证).然后，服务器计算响应本来应该是什么，然后基于(不匹配)匹配来接受或拒绝身份验证.

Now, my server needs to grab challenge number -3944 out of the list and mark it used or (better yet) delete it immediately to prevent replay attacks (a second request being authenticated with the same challenge). Then, the server calculates what the response should have been and accepts or rejects the authentication based on a (mis-)match.

出于性能和配额的原因，我想避免不得不使用DataStore来应对挑战.我将拥有一个允许客户端请求更多挑战并重试请求的系统，这样，清除Memcache的罕见情况也不会成为问题.

For performance and quota reasons, I would like to avoid having to use the DataStore for the challenges. I will have a system in place that allows the client to request more challenges and retry the request, so that the rare cases where Memcache gets purged aren't going to be an issue either.

是否有一种方法可以在Memcache中执行原子的获取和删除操作，该操作将仅返回一次给定键的条目，并在(之后，对相同键的任何请求返回 null 除非已重新设置)?对于从未设置的任何键，它也应该返回 null .

Is there a way to do an atomic get-and-delete operation in Memcache, that will return the entry for a given key exactly once and return null for any request for the same key after (unless it has been set again)? It should also return null for any keys that were never set.

PS:我正在使用Java.

PS: I'm using Java.

推荐答案

在它上睡了一个晚上之后，我想出了几种方法.两者都不是特别优雅，但让我把它们放在这里是值得深思的:

After sleeping on it for a night, I came up with a couple of approaches. Neither one of which is particularly elegant, but let me put them here as food for thought:

MemCache确实提供(至少)4条命令，这些命令以某种方式自动修改条目并返回有关其先前状态的信息(其中两个也由@Moshe Shaham指出):

MemCache does offer (at least) 4 commands that atomically modify an entry in some way and return some information about its previous state (two of them were pointed out by @Moshe Shaham as well):

1. 删除:               删除条目并返回它是否存在

1. delete:                 deletes an entry and returns whether it existed
2. increment:           increments an entry and returns its new value
3. put:                      puts an entry and returns whether it existed (if used with the right policy)
4. putIfUntouched:   puts an entry if it still matches an expected state (returns whether it did)

让我为他们每个人提供一个可能的实现.前三个将特定于整数键，并要求实际的条目具有正键(因为它们将使用相应的负键作为标记项).

Let me provide a possible implementation for each of them. The first 3 will be specific to integer keys and will require that the actual entries have a positive key (as they will use the corresponding negative key as a marker-entry).

注意:以下示例本质上是概念性的.其中一些可能仍允许出现竞争条件，而我实际上尚未测试其中任何一个.因此，将它们与一粒盐一起食用.

Note: The examples given below are conceptual in nature. Some of them might still allow for race-conditions and I haven't actually tested any of them. So, take them with a grain of salt.

在这里:

1.删除

首次存储条目时，将标记与标记一起存储(带有派生的对应键).根据尝试删除此标记的成功来对获取和删除操作进行门操作.

When first storing the entry, store a marker along with it (with a derived corresponding key). Gate the get-and-delete based on the success of an attempt to delete this marker.

public void putForAtomicGnD(MemcacheService memcache, int key, Object value) {
    assert key>=0;
    memcache.put(key, value);    // Put entry
    memcache.put(-key-1, null);  // Put a marker
}

public Object atomicGetAndDelete(MemcacheService memcache, int key) {
    assert key>=0;
    if (!memcache.delete(-key-1)) return null;  // Are we first to request it?
    Object result = memcache.get(key);          // Grab content
    memcache.delete(key);                       // Delete entry
    return result;
}

可能的竞争条件:putForAtomicGnD可能会覆盖正在读取的值.可以通过使用

Possible race-condition: A putForAtomicGnD might overwrite a value that is in the process of being read. Can be avoided by using ADD_ONLY_IF_NOT_PRESENT policy for put and millisNoReAdd for delete.

可能的优化:使用 2.递增

具有与每次进入和删除门相关的条目的读取计数器.

Have a read-counter associated with each entry that gates get-and-delete.

public Object atomicGetAndDelete(MemcacheService memcache, int key) {
    assert key>=0;
    if (memcache.increment(-key-1, 1L, 0L) != 1L) return null; // Are we 1st?
    Object result = memcache.get(key);                         // Grab content
    memcache.delete(key);                                      // Delete entry
    return result;
}

注意:如此处所示，此代码仅允许每个键使用一次.要重新使用，需要删除相应的标记，这会导致竞争状态(再次可以通过millisNoReAdd解决).

Note: As shown here, this code only allows every key to be used once. To re-use, corresponding marker needs to be deleted, which leads to race-condition (again resolvable via millisNoReAdd).

3.放

具有与读取和删除门相关的每个条目相关的读取标志(标记条目不存在).本质上与方法"1.删除"相反.

Have a read-flag (non-existence of marker entry) associated with each entry that gates get-and-delete. Essentially the inverse of approach "1. delete".

public Object atomicGetAndDelete(MemcacheService memcache, int key) {
    assert key>=0;
    if (!memcache.put(-key-1, null, null, SetPolicy.ADD_ONLY_IF_NOT_PRESENT))
        return null;                    // Are we 1st?
    Object result = memcache.get(key);  // Grab content
    memcache.delete(key);               // Delete entry
    memcache.delete(-key-1, 10000);     // Delete marker with millisNoReAdd
    return result;
}

可能的竞争条件:另一个看跌期权可能会覆盖一个正在读取的值.同样，可以使用millisNoReAdd来解决.

Possible race-condition: Another put might overwrite a value that is in the process of being read. Again, resolvable with use of millisNoReAdd.

可能的优化:使用 4. putIfUntouched

我当前的最爱:尝试获取一个条目并将其在模拟交易中设置为空，并使用该条目的成功来控制删除.

My current favorite: Try to get an entry and set it to null in a simulated transaction and use success of that to gate delete.

public Object atomicGetAndDelete(MemcacheService memcache, Object key) {
    IdentifiableValue result = memcache.getIdentifiable(key);
    if (result==null) return null;                     // Entry didn't exist
    if (result.getValue()==null) return null;          // Someone else got it
    if (!memcache.putIfUntouched(key, result, null)) return null;  // Still 1st?
    memcache.delete(key);                              // Delete entry
    return result.getValue();
}

注意:这种方法几乎完全是通用的(对密钥类型没有限制)，因为它不需要能够从给定的标记对象派生出密钥.它唯一的限制是它不支持实际的 null 条目，因为该值保留表示已采取的条目".

Note: This approach is almost completely general (no restrictions on key-type) as it does not need to be able to derive a key for a marker object from the given one. The only restriction it has is that it does not support actual null-entries as this value is reserved to denote "entry already taken".

可能的比赛条件?我目前看不到任何东西，但也许我缺少了什么?

Possible race-conditions? I don't currently see any, but maybe I'm missing something?

可能的优化:putIfUntouched with立即过期(在此处查找方法！)，而不是删除

Possible optimization: putIfUntouched with immediate Expiration (find out how here!) instead of delete.

结论

似乎有很多方法可以做到这一点，但是到目前为止我所提出的方法都不是特别优雅.请使用此处给出的示例主要作为思考的食物，让我们看看我们是否可以提出一种更清洁的解决方案，或者至少使自己相信上面的示例之一(putIfUntouched?)确实可以可靠地工作.

There seem to be a bunch of ways to do this, but none of the ones I've come up with so far look particularly elegant. Please use the examples given here primarily as food for thought and let's see if we can come up with a cleaner solution, or at least convince ourselves that one of the ones above (putIfUntouched?) will actually work reliably.

这篇关于AppEngine Memcache原子获取和删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！