基于共享内存的key-value存储

wapysun

浏览: 21695592 次
性别:
来自: 杭州

最近访客更多访客>>

devcang

hunankeda110

辽东小小

apex53

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2012-06 ( 77)
2012-05 ( 587)
2012-04 ( 177)
更多存档...

EXT Linux 多线程 XML 算法

1 定义

MemKeyValue 是一个基于共享内存的随机访问存储模型，可供不同的进程同时调用。

2 应用场景及需求

MemKeyValue 主要应用在如下场景，有一份数据，只用初始化一次，然后多个进程都会用到这份数据。采用 MemKeyValue 共享内存的方式，可以多个进程同时共享一份数据，从而能够达到节省内存，减少操作的目的。

根据应用场景，提炼出具体的需求

a 共享内存

b 读写

c c/c++

d 无视线程安全

e 内存利用率 80% 以上

3 实现

3.1 进程间通信方式的选定

由于需要在不同的进程间共享内存，首先，进程间主要需要共享大量的数据，其次，进程间不一定存在父子进程的关系。所以，最终，选择采用 System V 共享内存的方式，主要用到的系统调用如下

shmget() 、 shmat() 、 shmdt() 及 shmctl()

头文件：

#include <sys/ipc.h>

#include <sys/shm.h>

shmget （）用来获得共享内存区域的 ID ，如果不存在指定的共享区域就创建相应的区域。 shmat() 把共享内存区域映射到调用进程的地址空间中去，这样，进程就可以方便地对共享区域进行访问操作。 shmdt() 调用用来解除进程对共享内存区域的映射。 shmctl 实现对共享内存区域的控制操作。这里我们不对这些系统调用作具体的介绍，读者可参考相应的手册页面，后面的范例中将给出它们的调用方法。

需要注意的是 shmget 的内部实现包含了许多重要的系统 V 共享内存机制； shmat 在把共享内存区域映射到进程空间时，并不真正改变进程的页表。当进程第一次访问内存映射区域访问时，会因为没有物理页表的分配而导致一个缺页异常，然后内核再根据相应的存储管理机制为共享内存映射区域分配相应的页表。

3.2 算法选择及内层模型

结合应用场景及实现方式，采用双重 hash 的方式来实现


A
B
D

C
E

图中

A 无碰撞，

B 经 A 碰撞以，即 A->B

C 以 A ， B 碰撞 , 即 A->B->C

D 无碰撞

E 经 D 碰撞，即 D->E

由此，我们可以看出，对于这种形式的结构，也维护有一个隐式的“链表”，即 hash 算法的碰撞位置

3.3 主要接口及实现

Hashtable.h

* Creates a new hash table with the specified characteristics.

* Returns NULL if insufficent space is available or

* the new hash table otherwise.

struct hashtable *hashtable_create( const char * path,long capacity, float max_usage_percent, short key_size, short value_size,

void * stop_cond, void * del_cond);

* Inserts the specified (key, datum) pair into the specified hash table.

* Returns -ENOMEM on memory allocation error,

* -EINVAL for general errors or

* 0 otherwise.

int hashtable_update(struct hashtable *h, void *k, void* d);

* Searches for the entry with the specified key in the hash table.

* Returns NULL if no entry has the specified key or

* the datum of the entry otherwise.

int hashtable_search(struct hashtable *h, void* key , void *datum);

Hashtable.c

struct hashtable *hashtable_create( const char * path,long capacity, float max_usage_percent,short key_size,short value_size,void * stop_cond, void * del_cond)

{

struct hashtable * p;

key_t shm_mem_key;

int i;

p = (struct hashtable *) malloc (sizeof(*p));

if (NULL == p)

return NULL;

p->capacity = capacity;

/* initialize the shared memory address space */

shm_mem_key = ftok(path,0);

if (shm_mem_key == -1){

free(p);

perror("ftok error");

return NULL;

}

* Here have two scenario, first,if it's the first time the shared memory

* created, the memory should created and initialized;

* Second,if the memory is already created and "dirty" now, just attached

* on it.

p->shm_id =shmget(shm_mem_key, p->capacity ,IPC_CREAT | IPC_EXCL | 0666);

/* shared memory first created */

if(p->shm_id !=-1){

p->htable=(void *)shmat(p->shm_id,NULL,0);

if( (void *)-1 == p->htable ){

free(p);

perror("shmat error\n");

return NULL;

}

/* does this have problem when we set the stop condition?? */

p->capacity = capacity;

p->size = calculate_size( capacity, key_size, value_size);

p->key_size = key_size;

p->value_size = value_size;

memcpy( p->stop_cond, stop_cond, p->key_size);

memcpy( p->del_cond, del_cond,p->key_size);

if ( p->key_size == 4){

p->hash_value = bit_32_hash;

}else if (p->key_size == 8 ){

p->hash_value = bit_64_hash;

}

memset(p->htable,0,p->capacity);

for ( i =0; i< p->size; i++ ){

memcpy( ((unsigned char *)p->htable) + i* (p->key_size + p->value_size),p->stop_cond,p->key_size);

}

… …

} else {

p->shm_id = shmget(shm_mem_key,p->capacity,IPC_CREAT );

if(p->shm_id==-1)

{

free(p);

perror("shmget error\n");

return NULL;

}

p->htable=(void *)shmat(p->shm_id,NULL,0);

if( (void *)-1 == p->htable ){

free(p);

perror("shmat error\n");

return NULL;

}

… …

if ( p->key_size == 4){

p->hash_value = bit_32_hash;

}else if (p->key_size == 8 ){

p->hash_value = bit_64_hash;

}

return p;

}

int hashtable_update(struct hashtable *h, void* k, void* d)

{

long hvalue,rehash_value;

unsigned char * cur;

int n;

… …

n=0;

rehash_value =0;

hvalue = h->hash_value(h,k);

cur = ((unsigned char *) h->htable) + hvalue * (h->key_size + h->value_size );

while ( memcmp(cur,h->stop_cond,h->key_size) !=0 ) {

/* this is update the value with the same key */

if ( memcmp(cur,k,h->key_size) == 0 ){

memcpy( cur + h->key_size, d, h->value_size);

return 1;

}

n++;

/* if some extreme situation, maybe dead loop */

if ( n > 1000000){

h->collision_times += n;

memcpy(h->save_info_base + 16, &h->collision_times,8);

return -2;

}

rehash_value = ( hvalue + n*( 1 + ( hvalue >> 5 + 1) ) ) % (h->size );

cur = ((unsigned char *) h->htable ) + rehash_value * ( h->key_size + h->value_size );

}

memcpy(cur, k, h->key_size);

memcpy( cur + h->key_size, d, h->value_size);

return 0;

}

int hashtable_search(struct hashtable *h, void* k, void * datum)

{

long hvalue,rehash_value;

unsigned char * cur;

int n;

if ( !h)

return 0;

n=0;

rehash_value =0;

hvalue = h->hash_value(h,k);

cur = ((unsigned char *) h->htable) + hvalue * ( h->key_size + h->value_size );

while ( memcmp(cur,h->stop_cond,h->key_size) !=0){

if (memcmp(cur,k,h->key_size ) == 0 ){

memcpy(datum, cur + h->key_size,h->value_size);

return 0;

}

n++;

/* if some extreme situation, maybe dead loop */

if ( n > 1000000){

h->collision_times += n;

memcpy(h->save_info_base + 16, &h->collision_times,8);

return -2;

}

rehash_value = ( hvalue + n*( 1 + ( hvalue >> 5 + 1 ) ) ) % (h->size );

cur = ((unsigned char * ) h->htable) + rehash_value * ( h->key_size + h->value_size);

}

return -1;

}

4 具体的应用场景

5 问题

1 在 Linux 下共享内存的默认大小太小

在 linux 下，共享内存的默认大小为 32M, 在实际的应用场景中，是远远不够的。需要采用如下的方式更改共享内存的大小

sysctl -w kernel.shmmax=134217728

( 更改成 128M)

2 MemKeyValue 不是线程安全的

考虑到效率的原因，本没有做同步的机制，因此，在支持多线程的调用时，需要上层应用来做线程间的同步，即在调用 update 操作时加锁。

3 进程间没有同步的机制

进程间没有同步的机制，当前的应用场景是一个进程写，其它的进程多，因此，不考虑多进程间的同步。而如果要扩展到多进程的应用，则需要考虑这个问题。

分享到：

5种方法解除开机密码 | 《MFC那点儿事》の设备上下文DC

2010-10-04 11:28
浏览 1020
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论