午夜综合激情,亚洲欧美日韩国产综合在线,亚洲欧美www

redis如何删除�q�期数据

阿二 — Tue, 29 Nov 2011 11:57:00 GMT

随着nosql风潮兴�v�Q?/span>redis作�ؓ当中一个耀眼的明星�Q�也��来��多的被��x��和��用，我在工作中也�q�泛的用��C��redis来充�?/span>cache�?/span>key-value DB�Q�但当大家发现数据越来越多时�Q�不��有些担心，redis能撑的住吗，虽然官方已经有漂亮的benchmark�Q�自�׃��可以做做压力��试�Q�但是看看源码，也是��认问题最直接的办法之一。比如目前我们要��认的一个问题是�Q?/span>redis是如何删除过期数据的�Q?/span>

用一个可�?/span>"find reference"�?/span>IDE,沿着setex(Set the value and expiration of a key)命��o一�H�究竟：

void setexCommand(redisClient *c) {
c->argv[3] = tryObjectEncoding(c->argv[3]);
setGenericCommand(c,0,c->argv[1],c->argv[3],c->argv[2]);
}

setGenericCommand是一个实�?/span>set,setnx,setex的通用函数�Q�参数设�|�不同而已�?/span>

void setCommand(redisClient *c) {
    c->argv[2] = tryObjectEncoding(c->argv[2]);
    setGenericCommand(c,0,c->argv[1],c->argv[2],NULL);
}

void setnxCommand(redisClient *c) {
    c->argv[2] = tryObjectEncoding(c->argv[2]);
    setGenericCommand(c,1,c->argv[1],c->argv[2],NULL);
}

void setexCommand(redisClient *c) {
    c->argv[3] = tryObjectEncoding(c->argv[3]);
    setGenericCommand(c,0,c->argv[1],c->argv[3],c->argv[2]);
}

再看setGenericCommand�Q?br />

1 void setGenericCommand(redisClient *c, int nx, robj *key, robj *val, robj *expire) {
2     long seconds = 0; /* initialized to avoid an harmness warning */
3
4     if (expire) {
5         if (getLongFromObjectOrReply(c, expire, &seconds, NULL) != REDIS_OK)
6             return;
7         if (seconds <= 0) {
8             addReplyError(c,"invalid expire time in SETEX");
9             return;
10         }
11     }
12
13     if (lookupKeyWrite(c->db,key) != NULL && nx) {
14         addReply(c,shared.czero);
15         return;
16     }
17     setKey(c->db,key,val);
18     server.dirty++;
19     if (expire) setExpire(c->db,key,time(NULL)+seconds);
20     addReply(c, nx ? shared.cone : shared.ok);
21 }
22

13行处�?/span>"Set the value of a key, only if the key does not exist"的场景，17行插入这�?/span>key�Q?/span>19行设�|�它的超�Ӟ��注意旉��戛_��l�被讄��成了到期旉��。这里要看一�?/span>redisDb(�?/span>c->db)的定义：

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
    dict *io_keys;              /* Keys with clients waiting for VM I/O */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;
} redisDb;

仅关�?/span>dict�?/span>expires�Q�分别来�?/span>key-value和它的超�Ӟ��也就是说如果一�?/span>key-value是有��时的，那么它会存在dict里，同时也存�?/span>expires里，�c�M��q�样的�Ş式：dict[key]:value,expires[key]:timeout.

当然key-value没有��时�Q?/span>expires里就不存在这�?/span>key�?/span>剩下setKey�?/span>setExpire两个函数无非是插数据��C��个字兔R��Q�这里不再详�q��?/span>

那么redis是如何删除过�?/span>key的呢�?/span>

通过查看dbDelete的调用者，首先注意到这一个函敎ͼ�是用来删除过�?/span>key的�?/span>

1 int expireIfNeeded(redisDb *db, robj *key) {
2     time_t when = getExpire(db,key);
3
4     if (when < 0) return 0; /* No expire for this key */
5
6     /* Don't expire anything while loading. It will be done later. */
7     if (server.loading) return 0;
8
9     /* If we are running in the context of a slave, return ASAP:
10      * the slave key expiration is controlled by the master that will
11      * send us synthesized DEL operations for expired keys.
12      *
13      * Still we try to return the right information to the caller,
14      * that is, 0 if we think the key should be still valid, 1 if
15      * we think the key is expired at this time. */
16     if (server.masterhost != NULL) {
17         return time(NULL) > when;
18     }
19
20     /* Return when this key has not expired */
21     if (time(NULL) <= when) return 0;
22
23     /* Delete the key */
24     server.stat_expiredkeys++;
25     propagateExpire(db,key);
26     return dbDelete(db,key);
27 }
28

ifNeed表示能删则删�Q�所�?/span>4行没有设�|�超时不删，7行在"loading"时不删，16行非��d��不删�Q?/span>21行未到期不删�?/span>25行同步从库和文�g�?/span>

再看看哪些函数调用了expireIfNeeded�Q�有lookupKeyRead�Q?/span>lookupKeyWrite�Q?/span>dbRandomKey�Q?/span>existsCommand�Q?/span>keysCommand。通过�q�些函数命名可以看出�Q�只要访问了某一�?/span>key�Q�顺带做的事情就是尝试查看过期�ƈ删除�Q�这��׃��证了用户不可能访问到�q�期�?/span>key。但是如果有大量�?/span>key�q�期�Q��ƈ且没有被讉K��刎ͼ�那么��浪费了许多内存�?/span>Redis是如何处理这个问题的呢�?/span>

dbDelete的调用者里�q�发现这样一个函敎ͼ�

1 /* Try to expire a few timed out keys. The algorithm used is adaptive and
2  * will use few CPU cycles if there are few expiring keys, otherwise
3  * it will get more aggressive to avoid that too much memory is used by
4  * keys that can be removed from the keyspace. */
5 void activeExpireCycle(void) {
6     int j;
7
8     for (j = 0; j < server.dbnum; j++) {
9         int expired;
10         redisDb *db = server.db+j;
11
12         /* Continue to expire if at the end of the cycle more than 25%
13          * of the keys were expired. */
14         do {
15             long num = dictSize(db->expires);
16             time_t now = time(NULL);
17
18             expired = 0;
19             if (num > REDIS_EXPIRELOOKUPS_PER_CRON)
20                 num = REDIS_EXPIRELOOKUPS_PER_CRON;
21             while (num--) {
22                 dictEntry *de;
23                 time_t t;
24
25                 if ((de = dictGetRandomKey(db->expires)) == NULL) break;
26                 t = (time_t) dictGetEntryVal(de);
27                 if (now > t) {
28                     sds key = dictGetEntryKey(de);
29                     robj *keyobj = createStringObject(key,sdslen(key));
30
31                     propagateExpire(db,keyobj);
32                     dbDelete(db,keyobj);
33                     decrRefCount(keyobj);
34                     expired++;
35                     server.stat_expiredkeys++;
36                 }
37             }
38         } while (expired > REDIS_EXPIRELOOKUPS_PER_CRON/4);
39     }
40 }
41

�q�个函数的意囑ַ��l�有说明�Q?/span>删一点点�q�期key�Q�如果过�?/span>key较少�Q�那也只用一点点cpu�?/span>25行随机取一�?/span>key�Q?/span>38行删key成功的概率较低就退出。这个函数被攑֜�一�?/span>cron里，每毫�U�被调用一�ơ。这个算法保证每�ơ会删除一定比例的key�Q�但是如�?/span>key总量很大�Q�而这个比例控制的太大�Q�就需要更多次的��@环，��费cpu�Q�控制的太小�Q�过期的key��׃��变多�Q�浪费内�?#8212;—�q�就是时�I�权衡了�?/span>

最后在dbDelete的调用者里�q�发现这样一个函敎ͼ�

/* This function gets called when 'maxmemory' is set on the config file to limit
* the max memory used by the server, and we are out of memory.
* This function will try to, in order:
*
* - Free objects from the free list
* - Try to remove keys with an EXPIRE set
*
* It is not possible to free enough memory to reach used-memory < maxmemory
* the server will start refusing commands that will enlarge even more the
* memory usage.
*/
void freeMemoryIfNeeded(void)

�q�个函数太长��׃��再详�q�C��Q�注释部分说明只有在配置文�g中设�|�了最大内存时候才会调用这个函敎ͼ�而设�|�这个参数的意义是，你把redis当做一个内�?/span>cache而不�?/span>key-value数据库�?/span>

以上3�U�删除过�?/span>key的途径�Q�第二种定期删除一定比例的key是主要的删除途径�Q�第一�U?#8220;��L��删除”保证�q�期key不会被访问到�Q�第三种是一个当内存��出讑֮�时的暴力手段。由此也能看�?/span>redis设计的��y妙之处，

阿二 2011-11-29 19:57 发表评论

Poco::TCPServer框架解析

阿二 — Thu, 09 Sep 2010 17:05:00 GMT

摘要: POCO C++ Libraries提供一�?C++ 的类库用以开发基于网�l�的可移植的应用�E�序�Q�功能涉及线�E�、文件、流�Q�网�l�协议包括：HTTP、FTP、SMTP �{�，�q�提�?XML 的解析和 SQL 数据库的讉K��接口。不仅给我的工作带来极大的便利，而且设计巧妙�Q�代码易读，注释丰富�Q�也是非常好的学习材料�?nbsp; 阅读全文

阿二 2010-09-10 01:05 发表评论

阿二 — Tue, 09 Sep 2008 14:49:00 GMT

题目和基本思�\都来源网上，本�h加以整理�?/p>

题目�Q�在一个文件中�?10G 个整敎ͼ�乱序排列�Q�要求找��Z��位数。内存限制�ؓ 2G。只写出思�\卛_��Q�内存限制�ؓ 2G的意思就是，可以使用2G的空间来�q�行�E�序�Q�而不考虑�q�台机器上的其他软�g的占用内存）�?/p>

关于中位敎ͼ�数据排序后，位置在最中间的数倹{��即��数据分成两部分�Q�一部分大于该数��|��一部分��于该数倹{��中位数的位�|�：当样本数为奇数时�Q�中位数=(N+1)/2 ; 当样本数为偶数时�Q�中位数为N/2�?+N/2的均��|��那么10G个数的中位数�Q�就�W?G大的��C��W?G+1大的数的均��g��Q��?/p>

分析�Q�明显是一道工�E�性很强的题目�Q�和一般的查找中位数的题目有几点不同�?br>1. 原数据不能读�q�内存，不然可以用快速选择�Q�如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整敎ͼ�仍有4G�U�取��|��需要一�?6G大小的数�l�来计数�?/p>

2. 若看成从N个数中找出第K大的敎ͼ�如果K个数可以读进内存�Q�可以利用最��或最大堆�Q�但�q�里K=N/2,�?G个数�Q�仍然不能读�q�内存�?/p>

3. 接上�Q�对于N个数和K个数都不能一�ơ读�q�内存的情况�Q�《编�E�之��》里�l�出一个方案：设k

解法�Q�首先假设是32位无�W�号整数�?br>1. ��M��?0G个整敎ͼ�把整数映��到256M个区�D�中�Q�用一�?4位无�W�号整数�l�每个相应区�D�记数�?br>说明�Q�整数范围是0 - 2^32 - 1�Q�一共有4G�U�取��|��映射�?56M个区�D�，则每个区�D�|��16�Q?G/256M = 16�Q�种��|��?6个值算一�D�， 0�?5是第1�D�，16�?1是第2�D�，……2^32-16 �?^32-1是第256M�D�c��一�?4位无�W�号整数最大值是0�?G-1�Q�这里先不考虑溢出的情��c��d��占用内存256M×8B=2GB�?/p>

2. 从前到后�Ҏ��一�D늚�计数累加�Q�当累加的和��过5G时停止，扑և��q�个区段�Q�即累加停止时达到的区段�Q�也是中位数所在的区段�Q�的数��D��_��设�ؓ[a�Q�a+15]�Q�同时记录篏加到前一个区�D늚��L��Q�设为m。然后，释放除这个区�D�占用的内存�?/p>

3. 再读一�?0G个整敎ͼ�把在[a�Q�a+15]内的每个��D��敎ͼ��x��16个计数�?/p>

4. �Ҏ��的计��C��ơ篏加，每次的和设�ؓn�Q�当m+n的��D��q?G时停止，此时的这个计数所对应的数��是中位数�?/p>

�ȝ��Q?br>1.以上�Ҏ��只要��M��遍整敎ͼ��Ҏ��个整��C��只是常数旉��的操作，��M��来说是线性时间�?/p>

2. 考虑其他情况�?br>若是有符��L��整数�Q�只需改变映射卛_��。若�?4为整敎ͼ�则增加每个区�D늚�范围�Q�那么在�W�二�ơ读数时�Q�要考虑更多的计数。若�q�某个计数溢出，那么可认定所在的区段或代表整��Cؓ所求，�q�里只需做好相应的处理。噢�Q�忘了还要找�W?G+1大的��C��Q�相信有了以上的成果�Q�找到这个数也不难了吧�?/p>

3. 时空权衡�?br>��p��256个区�D�也许只是恰好配�?GB的内存（其实也不是，呵呵�Q�。可以增大区�D�范��_��减少区段数目�Q�节省一些内存，虽然增加�W�二部分的对单个数值的计数�Q�但�W�一部分�Ҏ��个区�D늚�计数加快了（��M��改变�Q�？待测�Q��?/p>

4. 映射时尽量用位操作，�׃��每个区段的�v炚w��?的整数幂�Q�映��v来也很方�ѝ�?br>

阿二 2008-09-09 22:49 发表评论

阿二 — Tue, 09 Sep 2008 12:21:00 GMT

博客�W�一��，�q�望大家多多指点�?br>
看了半天的boost::multi_array文档�Q�才发现可以用shape()[]�q�个的东西，来取某一�l�的长度

而关于视��N��分，��弟看的一知半解，
比如�Q�怎么��h��一�?×4的矩阵分�?�?×2的矩阵呢
虽然可以用别的途径解决�Q�但�q�是想看下multi_array的视图操�?

本来要实��C��Strassen��法的，
下面是普通的矩阵乘法�?br>

#include <iostream>
#include "boost/multi_array.hpp"
using namespace std;

typedef boost::multi_array<int, 2> matrix;

matrix matrix_multiply(matrix& a,matrix& b)
{
    matrix::index row=a.shape()[0];
    matrix::index col=b.shape()[1];
    matrix c(boost::extents[row][col]);

    for (matrix::index i=0; i!=a.shape()[0]; ++i)
        for (matrix::index j=0; j!=b.shape()[1]; ++j)
            for (matrix::index k=0; k!=a.shape()[1]; ++k)
                c[i][j]+=a[i][k]*b[k][j];

    return c;
}

void print(const matrix& m)
{
    for (matrix::index i=0; i!=m.shape()[0]; cout<<endl,++i)
        for (matrix::index j=0; j!=m.shape()[1]; ++j)
                cout<<m[i][j]<<" ";
}

int main() {

    int values[] = {
        0, 1, 2,
        3, 4, 5
    };
    const int values_size = 6;
    matrix A(boost::extents[2][3]);
    matrix B(boost::extents[3][2]);
    A.assign(values,values + values_size);
    B.assign(values,values + values_size);

        cout<<"matrix A"<<endl;
        print(A);
    cout<<endl;cout<<"*"<<endl;cout<<"matrix B"<<endl;
        print(B);
    cout<<endl;cout<<"="<<endl;cout<<"matrix C"<<endl;
    print(matrix_multiply(A,B));
    cout<<endl;

    return 0;
}

阿二 2008-09-09 20:21 发表评论