Redis添加区间集

jieforest · 发表于 2013-8-18 11:06

Defining the Interval Set

With the majority of the supporting tie-in code written, we can turn our focus on the actual data structure and the functions that respond to the external commands. First, we should add our command functions to the command table at line 115 of src/redis.c.

{"iadd",iaddCommand,-5,"wm",0,NULL,1,1,1,0,0},
{"irem",iremCommand,-3,"w",0,NULL,1,1,1,0,0},
{"irembystab",irembystabCommand,3,"w",0,NULL,1,1,1,0,0},
{"istab",istabCommand,-3,"r",0,NULL,1,1,1,0,0},

复制代码

We’ll define that AVL management functions as well as the four above functions in src/t_iset.c, a new module we create to hold just our custom datatype.

jieforest · 发表于 2013-8-18 11:07

I won’t be going through every aspect of the datatype, as the implementation is almost 1,000 lines long (view the full source). However, I do want to touch on a couple of points.

1) The avlCreate() function creates a structure for holding an interval tree as well as an internal Redis dict using dictCreate(). We use this dict to maintain the set of values that have already been added to the interval sets, guaranteeing constant member lookup and deletion.

2) The avlFree() function calls decrRefCount() with the robj at the node being freed. This is required to ensure Redis properly removes the object when no longer referenced (it may still be referenced in the dict mentioned above).

3) The iaddCommand() function is variadic, and thus can be used to add multiple items to the set with a single call. This is a good example method to reference for implementing similar functionality.

mchdba · 发表于 2013-8-18 11:27

jieforest 发表于 2013-8-17 10:44
我工作十多年了，职位是架构师，熟悉并关注的领域很多。可能是职务的原因吧，我自我评价：博而不精。

那你是老前辈了，以后在mongodb上面多多指教吧！

jieforest · 发表于 2013-8-19 08:53

Persistence

Redis provides two forms of disk persistence: RDB and AOF. RDB is a binary storage format that represents snapshots of the entire Redis database at any point in time. AOF (append-only file) is an append-only log of all Redis commands that have been run to build the database in its current format.

For our custom datatype, we will build in support for both types of persistence. If you can be sure that you will only use one type of persistence, you can implement support for only that format. Be forewarned, however, that the Redis server will throw a panic if you attempt to use a persistence strategy that is not supported by your custom type.

jieforest · 发表于 2013-8-19 08:56

RDB

We’ll start off by adding RDB support for interval sets. First, we need to define a constant that represents our interval type for RDB at the datatype definitions starting at line 72 of src/rdb.h.

#define REDIS_RDB_TYPE_ISET 5

复制代码

Next, we need to add the code responsible for saving the interval set. First we need to add the interval set case to the switch statement inrdbSaveObjectType() at line 430 of src/rdb.c.

case REDIS_ISET:
return rdbSaveType(rdb,REDIS_RDB_TYPE_ISET);

复制代码

jieforest · 发表于 2013-8-19 08:56

Second, we will add the actual save logic to rdbSaveObject() at line 478 of src/rdb.c.

else if (o->type == REDIS_ISET) {
avl * tree = o->ptr;
dictIterator *di = dictGetIterator(tree->dict);
dictEntry *de;
if ((n = rdbSaveLen(rdb,dictSize(tree->dict))) == -1) return -1;
nwritten += n;
while((de = dictNext(di)) != NULL) {
robj *eleobj = dictGetKey(de);
double *scores = dictGetVal(de);
if ((n = rdbSaveStringObject(rdb,eleobj)) == -1) return -1;
nwritten += n;
if ((n = rdbSaveDoubleValue(rdb,scores[0])) == -1) return -1;
nwritten += n;
if ((n = rdbSaveDoubleValue(rdb,scores[1])) == -1) return -1;
nwritten += n;
}
dictReleaseIterator(di);
}

复制代码

jieforest · 发表于 2013-8-19 08:57

This code creates an iterator on the dict internal to the interval set and proceeds to walk the dict. For each element encountered, the element’s value is saved along with the minimum and maximum scores associated with the interval.

After finishing with the save logic, we need to implement load logic in the rdbLoadObject() function at line 771 of src/rdb.c.

else if (rdbtype == REDIS_RDB_TYPE_ISET) {
size_t isetlen;
avl * tree;
size_t maxelelen = 0;
if ((isetlen = rdbLoadLen(rdb,NULL)) == REDIS_RDB_LENERR) return NULL;
o = createIsetObject();
tree = o->ptr;
while(isetlen--) {
robj *ele;
double score1;
double score2;
avlNode *inode;
if ((ele = rdbLoadEncodedStringObject(rdb)) == NULL) return NULL;
ele = tryObjectEncoding(ele);
if (rdbLoadDoubleValue(rdb,&score1) == -1) return NULL;
if (rdbLoadDoubleValue(rdb,&score2) == -1) return NULL;
/* Don't care about integer-encoded strings. */
if (ele->encoding == REDIS_ENCODING_RAW &&
sdslen(ele->ptr) > maxelelen)
maxelelen = sdslen(ele->ptr);
inode = avlInsert(tree, score1, score2, ele);
dictAdd(tree->dict,ele,&inode->scores);
incrRefCount(ele); /* Added to dictionary. */
}
}

复制代码

jieforest · 发表于 2013-8-19 08:57

We start the load code by reading the number of elements to expect during the load; this was automatically written by rdbSaveObject(). We then simply create a new interval set with createIsetObject() and then read in each node one by one, adding each to the tree withavlInsert() and dictAdd.

With that, the RDB code is complete.

Append-Only File

AOF support is much simpler; by default, each command sent to the Redis server is appended to the log, and thus support is already baked in. However, Redis does intelligently rewrite the append-only file when the file gets too big to eliminate redundancy. For instance, if a specific element has been added and deleted 500 times, we shouldn’t have 500 copies of the same add and delete commands. Thus we need to add a method that will iterate the interval set and write out the IADD commands to regenerate the set.