key-value存储实现

文章目录

  • 一、项目简介
  • 二、项目流程图
  • 三、网络
    • 3.1、epoll实现
    • 3.2、io_uring实现
  • 四、协议
  • 五、存储
    • 5.1、array实现
    • 5.2、rbtree实现
    • 5.3、hash实现
  • 六、测试

一、项目简介

key-value存储其实是一个小型的redis，用户在客户端输入存储相关的指令发送给服务器端，服务器在接受到指令之后对指令做对应的操作。在整个过程中，涉及到客户端和服务器端使用什么样的网络模型，如epoll，io_uring，ntyco等等，服务器端对指令做操作涉及到的数据结构，如array，rbtree，hash等等。
在本项目中，网络层的组件选择了epoll，io_uring，存储数据结构选择了array，rbtree，hash。

二、项目流程图

在这里插入图片描述

三、网络

在网络具体实现中，把收发数据存放在不同的数组当中，下面是结构体定义：

struct conn_item{int fd;char rbuffer[BUFFER_LENGTH];char wbuffer[BUFFER_LENGTH];int rlen;int wlen;union {RCALLBACK accept_callback;RCALLBACK recv_callback;}recv_t;RCALLBACK send_callback;};

3.1、epoll实现

如果对epoll不熟悉，可以参考我的博文：高性能网络编程

下面是具体实现

#include "kvstore.h"#include <sys/socket.h>
#include <errno.h>
#include <netinet/in.h>#include <stdio.h>
#include <string.h>
#include <unistd.h>#include <pthread.h>
#include <sys/poll.h>
#include <sys/epoll.h>
#include <sys/time.h>#define PORT 8000
#define SERVER_ADR "127.0.0.1"
struct conn_item connlist[1048576] = {0};int epfd = 0;int init_serv(unsigned short port)
{int fd = socket(PF_INET, SOCK_STREAM, 0);struct sockaddr_in sever_adr;memset(&sever_adr, 0, sizeof(sever_adr));sever_adr.sin_family = AF_INET;sever_adr.sin_port = htons(port);sever_adr.sin_addr.s_addr = htonl(INADDR_ANY);if ((bind(fd, (const struct sockaddr *)&sever_adr, sizeof(sever_adr))) == -1){perror("bind error");return -1;}if ((listen(fd, 10)) == -1){perror("listen error");return -1;}return fd;
}int set_event(int fd, int event, int flag)
{if (flag){struct epoll_event ev;ev.data.fd = fd;ev.events = event;epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev);}else{struct epoll_event ev;ev.data.fd = fd;ev.events = event;epoll_ctl(epfd, EPOLL_CTL_MOD, fd, &ev);}
}int send_cb(int fd)
{char *buffer = connlist[fd].wbuffer;int idx = connlist[fd].wlen;int count = send(fd, buffer, idx, 0);set_event(fd, EPOLLIN, 0);memset(connlist[fd].wbuffer, 0, BUFFER_LENGTH);connlist[fd].wlen = 0;return count;
}int recv_cb(int fd)
{char *buffer = connlist[fd].rbuffer;int idx = connlist[fd].rlen;int count = recv(fd, buffer, BUFFER_LENGTH, 0);if (count == 0){printf("disconnect\n");epoll_ctl(epfd, EPOLL_CTL_DEL, fd, NULL);close(fd);return -1;}connlist[fd].rlen = count;kvstore_request(&connlist[fd]);connlist[fd].wlen = strlen(connlist[fd].wbuffer);set_event(fd, EPOLLOUT, 0);memset(connlist[fd].rbuffer, 0, BUFFER_LENGTH);connlist[fd].rlen = 0;return count;
}int accept_cb(int fd)
{struct sockaddr_in clnt_adr;memset(&clnt_adr, 0, sizeof(clnt_adr));socklen_t len = sizeof(clnt_adr);int connfd = accept(fd, (struct sockaddr *)&clnt_adr, &len);if (connfd < 0){perror("accept error");return -1;}set_event(connfd, EPOLLIN, 1);connlist[connfd].fd = connfd;memset(connlist[connfd].rbuffer, 0, BUFFER_LENGTH);connlist[connfd].rlen = 0;memset(connlist[connfd].wbuffer, 0, BUFFER_LENGTH);connlist[connfd].wlen = 0;connlist[connfd].send_callback = send_cb;connlist[connfd].recv_t.recv_callback = recv_cb;return connfd;
}int epoll_entry()
{int port_count = 20;unsigned short port = 2048;int i = 0;epfd = epoll_create(1);int sockfd;for (i = 0; i < port_count; i++){sockfd = init_serv(port + i);connlist[sockfd].fd = sockfd;connlist[sockfd].recv_t.accept_callback = accept_cb;set_event(sockfd, EPOLLIN, 1);}struct epoll_event events[1024] = {0};while (1){int nfds = epoll_wait(epfd, events, 1024, -1);if (nfds < 0){perror("epoll wait error");return -1;}int i;for (i = 0; i < nfds; i++){int connfd = events[i].data.fd;if (events[i].events & EPOLLIN){int count = connlist[connfd].recv_t.recv_callback(connfd);}else if (events[i].events & EPOLLOUT){int count = connlist[connfd].send_callback(connfd);}}}
}

其实，这部分代码也是针对epoll实现的一个改写，关键还是在于掌握epoll如何使用。项目只是把这些知识点组织起来。

3.2、io_uring实现

如果对io_uring不熟悉，可以参考我的博文：【C】io_uring原理与实战

下面是具体实现

#include "kvstore.h"
#include <unistd.h>
#include <liburing.h>
#include <netinet/in.h>struct conn_info
{int fd;int event;
};int init_server(unsigned short port)
{int sockfd = socket(AF_INET, SOCK_STREAM, 0);struct sockaddr_in serveraddr;memset(&serveraddr, 0, sizeof(struct sockaddr_in));serveraddr.sin_family = AF_INET;serveraddr.sin_addr.s_addr = htonl(INADDR_ANY);serveraddr.sin_port = htons(port);if (-1 == bind(sockfd, (struct sockaddr *)&serveraddr, sizeof(struct sockaddr))){perror("bind");return -1;}listen(sockfd, 10);return sockfd;
}#define ENTRIES_LENGTH 1024#define EVENT_ACCEPT 0
#define EVENT_READ 1
#define EVENT_WRITE 2struct conn_item connlist[1048576] = {0};int set_event_accept(struct io_uring *ring, int sockfd, struct sockaddr *addr, socklen_t *addrlen, int flags)
{struct io_uring_sqe *sqe = io_uring_get_sqe(ring);struct conn_info accept_info;accept_info.fd = sockfd;accept_info.event = EVENT_ACCEPT;io_uring_prep_accept(sqe, sockfd, addr, addrlen, flags);memcpy(&sqe->user_data, &accept_info, sizeof(accept_info));
}int set_event_recv(struct io_uring *ring, int sockfd, int flags)
{struct io_uring_sqe *sqe = io_uring_get_sqe(ring);struct conn_info accept_info;accept_info.fd = sockfd;accept_info.event = EVENT_READ;io_uring_prep_recv(sqe, sockfd, connlist[sockfd].rbuffer, BUFFER_LENGTH, flags);memcpy(&sqe->user_data, &accept_info, sizeof(accept_info));
}int set_event_send(struct io_uring *ring, int sockfd, int flags)
{struct io_uring_sqe *sqe = io_uring_get_sqe(ring);struct conn_info accept_info;accept_info.fd = sockfd;accept_info.event = EVENT_WRITE;io_uring_prep_send(sqe, sockfd, connlist[sockfd].wbuffer, connlist[sockfd].wlen, flags);memcpy(&sqe->user_data, &accept_info, sizeof(accept_info));
}int io_uring_entry()
{unsigned short port = 8001;int sockfd = init_server(port);struct io_uring_params params;memset(&params, 0, sizeof(params));struct io_uring ring;memset(&ring, 0, sizeof(ring));io_uring_queue_init_params(ENTRIES_LENGTH, &ring, &params);struct sockaddr_in clntadr;socklen_t len = sizeof(clntadr);set_event_accept(&ring, sockfd, (struct sockaddr *)&clntadr, &len, 0);char buffer[BUFFER_LENGTH] = {0};while (1){io_uring_submit(&ring);struct io_uring_cqe *cqe;io_uring_wait_cqe(&ring, &cqe);struct io_uring_cqe *cqes[128];int nready = io_uring_peek_batch_cqe(&ring, cqes, 128);int i;for (i = 0; i < nready; i++){struct io_uring_cqe *entry = cqes[i];struct conn_info result;memcpy(&result, &entry->user_data, sizeof(result));if (result.event == EVENT_ACCEPT){set_event_accept(&ring, sockfd, (struct sockaddr *)&clntadr, &len, 0);int connfd = entry->res;connlist[connfd].fd = connfd;memset(connlist[connfd].rbuffer, 0, BUFFER_LENGTH);connlist[connfd].rlen = 0;memset(connlist[connfd].wbuffer, 0, BUFFER_LENGTH);connlist[connfd].wlen = 0;set_event_recv(&ring, connfd, 0);}else if (result.event == EVENT_READ){kvstore_request(&connlist[result.fd]);connlist[result.fd].wlen = strlen(connlist[result.fd].wbuffer);// printf("wbuffer is %s\n",connlist[result.fd].wbuffer);int ret = entry->res;if (ret == 0){close(result.fd);}else if (ret > 0){memset(connlist[result.fd].rbuffer, 0, BUFFER_LENGTH);connlist[result.fd].rlen = 0;set_event_send(&ring, result.fd, 0);}}else if (result.event == EVENT_WRITE){memset(connlist[result.fd].wbuffer, 0, BUFFER_LENGTH);connlist[result.fd].wlen = 0;set_event_recv(&ring, result.fd, 0);}}io_uring_cq_advance(&ring, nready);}
}

四、协议

协议的设置也是参照redis的一些命令格式，实现一些CRUD的操作，下面是具体的协议格式

    "SET","GET","DEL","MOD","COUNT","RSET","RGET","RDEL","RMOD","RCOUNT","HSET","HGET","HDEL","HMOD","HCOUNT"

其中R代表rbtree，H代表hash。
下面是关于如何实现协议的具体代码

int kvstore_spilt_token(char *msg, char **tokens)
{if (msg == NULL || tokens == NULL)return -1;int idx = 0;char *ch = strtok(msg, " ");while (ch != NULL){tokens[idx++] = ch;ch = strtok(NULL, " ");}return idx;
}int kvstore_parser_protocol(struct conn_item *item, char **tokens, int count)
{if (item == NULL || tokens[0] == NULL || count == 0)return -1;int cmd = KVS_CMD_START;for (cmd = KVS_CMD_START; cmd < KVS_CMD_SIZE; cmd++){if (strcmp(commands[cmd], tokens[0]) == 0){break;}}char *msg = item->wbuffer;char *key = tokens[1];char *value = tokens[2];memset(msg, 0, BUFFER_LENGTH);switch (cmd){
#if ENABLE_ARRAY_KVENGINE// arraycase KVS_CMD_SET:{int ress = kvstore_array_set(key, value);if (!ress){snprintf(msg, BUFFER_LENGTH, "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "FAILED");}break;}case KVS_CMD_GET:{char *val = kvstore_array_get(key);if (val){snprintf(msg, BUFFER_LENGTH, "%s", val);}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_DEL:{ // printf("del\n");int resd = kvstore_array_delete(key);if (resd < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else if (resd == 0){snprintf(msg, BUFFER_LENGTH, "%s", "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_MOD:{ // printf("mod\n");int resm = kvstore_array_modify(key, value);if (resm < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else if (resm == 0){snprintf(msg, BUFFER_LENGTH, "%s", "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_COUNT:{int counta = kvstore_array_count();if (counta < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else{snprintf(msg, BUFFER_LENGTH, "%d", counta);}break;}
#endif#if ENABLE_RBTREE_KVENGINE// rbtreecase KVS_CMD_RSET:{int resr = kvstore_rbtree_set(key, value);if (!resr){snprintf(msg, BUFFER_LENGTH, "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "FAILED");}break;}case KVS_CMD_RGET:{char *valr = kvstore_rbtree_get(key);if (valr){snprintf(msg, BUFFER_LENGTH, "%s", valr);}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_RDEL:{int resrd = kvstore_rbtree_delete(key);if (resrd < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else if (resrd == 0){snprintf(msg, BUFFER_LENGTH, "%s", "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_RMOD:{int resrm = kvstore_rbtree_modify(key, value);if (resrm < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else if (resrm == 0){snprintf(msg, BUFFER_LENGTH, "%s", "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_RCOUNT:{int countr = kvstore_rbtree_count();if (countr < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else{snprintf(msg, BUFFER_LENGTH, "%d", countr);}break;}
#endif#if ENABLE_HASH_KVENGINEcase KVS_CMD_HSET:{int res = kvstore_hash_set(key, value);if (!res){snprintf(msg, BUFFER_LENGTH, "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "FAILED");}break;}// hashcase KVS_CMD_HGET:{char *val = kvstore_hash_get(key);if (val){snprintf(msg, BUFFER_LENGTH, "%s", val);}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_HDEL:{int res = kvstore_hash_delete(key);if (res < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else if (res == 0){snprintf(msg, BUFFER_LENGTH, "%s", "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_HMOD:{int res = kvstore_hash_modify(key, value);if (res < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else if (res == 0){snprintf(msg, BUFFER_LENGTH, "%s", "SUCCESS");}else{snprintf(msg, BUFFER_LENGTH, "NO EXIST");}break;}case KVS_CMD_HCOUNT:{int count = kvstore_hash_count();if (count < 0){ // serversnprintf(msg, BUFFER_LENGTH, "%s", "ERROR");}else{snprintf(msg, BUFFER_LENGTH, "%d", count);}break;}
#endifdefault:break;}
}int kvstore_request(struct conn_item *item)
{char *msg = item->rbuffer;char *tokens[KVSTORE_MAX_TOKENS];int count = kvstore_spilt_token(msg, tokens);kvstore_parser_protocol(item, tokens, count);return 0;
}

具体流程，服务器端通过网络获取到客户端传来的指令，将指令发送到kvstore_request，由kvstore_spilt_token对指令进行解析，由kvstore_parser_protocol执行具体的指令。

五、存储

5.1、array实现

Array其实就是数组，在数组中CRUD，下面是具体的实现
首先，定义一个结构体

struct kvs_array_item {char *key;char *value;
};#define KVS_ARRAY_SIZE		1024typedef struct array_s {struct kvs_array_item *array_table;int array_idx;
} array_t;extern array_t Array;

然后，数组执行CRUD的具体实现

#include "kvstore.h"array_t Array;int kvstore_array_create(array_t *arr)
{if (!arr)return -1;arr->array_table = (struct kvs_array_item *)kvstore_malloc(KVS_ARRAY_SIZE * sizeof(struct kvs_array_item));if (!arr->array_table){return -1;}memset(arr->array_table, 0, KVS_ARRAY_SIZE * sizeof(struct kvs_array_item));arr->array_idx = 0;return 0;
}void kvstore_array_destory(array_t *arr)
{if (!arr)return;if (arr->array_table)kvstore_free(arr->array_table);return;
}int kvs_array_set(array_t *arr, char *key, char *value)
{if (arr == NULL || key == NULL || value == NULL)return -1;if (arr->array_idx == KVS_ARRAY_SIZE)return -1;char *kcopy = kvstore_malloc(strlen(key)+1);if (kcopy == NULL)return -1;memset(kcopy,0,strlen(key)+1);strncpy(kcopy, key, strlen(key));char *vcopy = kvstore_malloc(strlen(value)+1);if (vcopy == NULL){kvstore_free(kcopy);return -1;}memset(vcopy,0,strlen(value)+1);strncpy(vcopy, value, strlen(value)+1);int i = 0;for (i = 0; i < arr->array_idx; i++){if (arr->array_table->key == NULL){arr->array_table[i].key = kcopy;arr->array_table[i].value = vcopy;arr->array_idx++;return 0;}}if (i < KVS_ARRAY_SIZE && i == arr->array_idx){arr->array_table[arr->array_idx].key = kcopy;arr->array_table[arr->array_idx].value = vcopy;arr->array_idx++;}return 0;
}char *kvs_array_get(array_t *arr, char *key)
{if (arr == NULL){return NULL;}int i;for (i = 0; i < arr->array_idx; i++){if (arr->array_table[i].key == NULL){return NULL;}if (strcmp(arr->array_table[i].key, key) == 0){return arr->array_table[i].value;}}return NULL;
}int kvs_array_delete(array_t *arr, char *key)
{int i;if (arr == NULL || key == NULL)return -1;for (i = 0; i < arr->array_idx; i++){if (strcmp(arr->array_table[i].key, key) == 0){kvstore_free(arr->array_table[i].value);arr->array_table[i].value = NULL;kvstore_free(arr->array_table[i].key);arr->array_table[i].key = NULL;arr->array_idx--;return 0;}}return i;
}int kvs_array_modify(array_t *arr, char *key, char *value)
{int i = 0;if (arr == NULL || key == NULL || value == NULL)return -1;for (i = 0; i < arr->array_idx; i++){if (strcmp(arr->array_table[i].key, key) == 0){kvstore_free(arr->array_table[i].value);arr->array_table[i].value = NULL;char *vcopy = kvstore_malloc(strlen(value) + 1);strncpy(vcopy, value, strlen(value) + 1);arr->array_table[i].value = vcopy;return 0;}}return i;
}int kvs_array_count(array_t *arr)
{if (!arr)return -1;return arr->array_idx;
}

5.2、rbtree实现

红黑树是一个比较难的内容，在实现具体操作前需要充分理解原理。如果对红黑树的原理并不熟悉的可以参考我的上一篇博文：一文速学—红黑树。

在上一篇博文中讲解了红黑树实现原理，以及如何实现，在这里只需要对红黑树稍微改写一下就能够达成目的。下面是实现代码

具体实现前需要再头文件中做一些声明

typedef struct _rbtree rbtree_t;extern rbtree_t Tree;

下面是具体实现


rbtree Tree;int kvstore_rbtree_create(rbtree_t *tree)
{if (tree == NULL){perror(" rbtree error");return -1;}memset(tree, 0, sizeof(rbtree));tree->nil = (rbtree_node *)malloc(sizeof(rbtree_node));tree->nil->key = malloc(1);*(tree->nil->key) = '\0';tree->root = tree->nil;tree->nil->color = BLACK;return 0;
}
void kvstore_rbtree_destory(rbtree_t *tree)
{if (!tree)return;if (tree->nil->key)kvstore_free(tree->nil->key);rbtree_node *node = tree->root;while (node != tree->nil){node = rbtree_mini(tree, tree->root);if (node == tree->nil)break;node = rbtree_delete(tree, node);if (!node){kvstore_free(node->key);kvstore_free(node->value);kvstore_free(node);}}
}
int kvs_rbtree_set(rbtree_t *tree, char *key, char *value)
{rbtree_node *node = (rbtree_node *)malloc(sizeof(rbtree_node));if (!node)return -1;node->key = kvstore_malloc(strlen(key) + 1);if (node->key == NULL){kvstore_free(node);return -1;}memset(node->key, 0, strlen(key) + 1);strcpy(node->key, key);node->value = kvstore_malloc(strlen(value) + 1);if (node->value == NULL){kvstore_free(node->key);kvstore_free(node);return -1;}memset(node->value, 0, strlen(value) + 1);strcpy(node->value, value);rbtree_insert(tree, node);tree->count++;return 0;
}char *kvs_rbtree_get(rbtree_t *tree, char *key)
{rbtree_node *node = rbtree_search(tree, key);if (node == tree->nil){return NULL;}return node->value;
}
int kvs_rbtree_delete(rbtree_t *tree, char *key)
{rbtree_node *node = rbtree_search(tree, key);if (node == tree->nil)return -1;rbtree_node *cur = rbtree_delete(tree, node);if (!cur){kvstore_free(cur->key);kvstore_free(cur->value);kvstore_free(cur);}tree->count--;return 0;
}
int kvs_rbtree_modify(rbtree_t *tree, char *key, char *value)
{rbtree_node *node = rbtree_search(tree, key);if (node == tree->nil){return -1;}char *temp = node->value;kvstore_free(temp);node->value = kvstore_malloc(strlen(value) + 1);if (node->value == NULL)return -1;strcpy(node->value, value);return 0;
}
int kvs_rbtree_count(rbtree_t *tree)
{return tree->count;
}

5.3、hash实现

哈希表其实不是一个很难理解的概念，网上有很多关于哈希表的介绍。哈希表是通过哈希函数定位元素在哈希表的哪个位置。哈希表还存在另一个问题，哈希冲突。

哈希冲突有多种解决方法，具体解决方法可以参考：哈希冲突
本文使用的是链式解决方法。

如果大家对于算法感兴趣可以阅读：Hello算法
里面实现了很多常见的算法，并且具有大多数编程语言实现的版本。

具体实现前需要再头文件中做一些声明

typedef struct hashtable_s hashtable_t;extern hashtable_t Hash;

下面是具体代码实现

#include "kvstore.h"
#include <string.h>#define MAX_KEY_LEN 128
#define MAX_VALUE_LEN 512#define MAX_TABLE_SIZE 102400
#define ENABLE_POINTER_KEY 1typedef struct hashnode_s
{
#if ENABLE_POINTER_KEYchar *key;char *value;
#elsechar key[MAX_KEY_LEN];char value[MAX_VALUE_LEN];
#endifstruct hashnode_s *next;} hashnode_t;typedef struct hashtable_s
{int count;int max_slots;hashnode_t **nodes;
} hashtable_t;hashtable_t Hash;static int _hash(char *key, int size)
{if (!key)return -1;int sum = 0;int i = 0;while (key[i] != 0){sum += key[i];i++;}return sum % size;
}hashnode_t *_create_node(char *key, char *value)
{hashnode_t *node = (hashnode_t *)kvstore_malloc(sizeof(hashnode_t));if (!node)return NULL;#if ENABLE_POINTER_KEYnode->key = kvstore_malloc(strlen(key) + 1);if (!node->key){kvstore_free(node);return NULL;}strcpy(node->key, key);node->value = kvstore_malloc(strlen(value) + 1);if (!node->value){kvstore_free(node->key);kvstore_free(node);return NULL;}strcpy(node->value, value);#endifnode->next = NULL;return node;
}int put_kv_hashtable(hashtable_t *hash, char *key, char *value)
{if (!hash || !key || !value)return -1;int idx = _hash(key, MAX_TABLE_SIZE);hashnode_t *node = hash->nodes[idx];while (node != NULL){if (strcmp(node->key, key) == 0){return 1;}node = node->next;}hashnode_t *new_node = _create_node(key, value);new_node->next = hash->nodes[idx];hash->nodes[idx] = new_node;hash->count++;return 0;
}char *get_kv_hashtable(hashtable_t *hash, char *key)
{if (!hash || !key)return NULL;int idx = _hash(key, MAX_TABLE_SIZE);hashnode_t *node = hash->nodes[idx];while (node != NULL){if (strcmp(node->key, key) == 0){return node->value;}node = node->next;}return NULL;
}int init_hashtable(hashtable_t *hash)
{if (!hash)return -1;hash->nodes = (hashnode_t **)kvstore_malloc(sizeof(hashnode_t *) * MAX_TABLE_SIZE);if (!hash->nodes)return -1;hash->count = 0;hash->max_slots = MAX_TABLE_SIZE;return 0;
}int delete_kv_hashtable(hashtable_t *hash, char *key)
{if (!hash || !key)return -2;int idx = _hash(key, MAX_TABLE_SIZE);hashnode_t *head = hash->nodes[idx];if (head == NULL)return -1;if (strcmp(head->key, key) == 0){hashnode_t *tmp = head->next;hash->nodes[idx] = tmp;
#if ENABLE_POINTER_KEYif (head->key){kvstore_free(head->key);}if (head->value){kvstore_free(head->value);}kvstore_free(head);
#elsefree(head);
#endifhash->count--;return 0;}hashnode_t *cur=head;while (cur->next!=NULL){if(strcmp(cur->next->key,key)==0) break;cur=cur->next;}if(cur->next==NULL){return-1;}hashnode_t *tmp=cur->next;cur->next=tmp->next;
#if ENABLE_POINTER_KEYif (tmp->key) {kvstore_free(tmp->key);}if (tmp->value) {kvstore_free(tmp->value);}kvstore_free(tmp);
#elsefree(tmp);
#endifhash->count --;return 0;}void dest_hashtable(hashtable_t *hash){if(!hash) return;int i=0;for(i=0;i<hash->max_slots;i++){hashnode_t* node=hash->nodes[i];while (node!=NULL){hashnode_t *tmp=node;node=node->next;hash->nodes[i]=node;kvstore_free(tmp);}}kvstore_free(hash->nodes);
}int count_kv_hashtable(hashtable_t *hash) {return hash->count;
}int kvs_hash_count(hashtable_t *hash) {return hash->count;
}int exist_kv_hashtable(hashtable_t *hash, char *key) {char *value = get_kv_hashtable(hash, key);if (value) return 1;else return 0;}int kvs_hash_modify(hashtable_t *hash, char *key, char *value) {if(!hash || !key || !value) return -1;int idx=_hash(key,MAX_TABLE_SIZE);hashnode_t *node=hash->nodes[idx];while(node!=NULL){if(strcmp(node->key,key)==0){kvstore_free(node->value);node->value=kvstore_malloc(strlen(value)+1);if(node->value){strcpy(node->value,value);return 0;}else{assert(0);}}node=node->next;}return -1;
}int kvstore_hash_create(hashtable_t *hash)
{return init_hashtable(hash);
}int kvs_hash_set(hashtable_t *hash, char *key, char *value)
{return put_kv_hashtable(hash, key, value);
}char *kvs_hash_get(hashtable_t *hash, char *key)
{return get_kv_hashtable(hash, key);
}int kvs_hash_delete(hashtable_t *hash, char *key)
{return delete_kv_hashtable(hash, key);
}void kvstore_hash_destory(hashtable_t *hash)
{return dest_hashtable(hash);
}

六、测试

针对上面的框架我们可以制定下面几种测试样例：
在这里插入图片描述
针对上面的样例，使用下面的测试代码，进行10w次的CRUD测试


#include <stdio.h>
#include <string.h>
#include <stdlib.h>#include <getopt.h>#include <sys/socket.h>
#include <sys/time.h>#include <arpa/inet.h>#define MAX_MAS_LENGTH 512
#define TIME_SUB_MS(tv1, tv2) ((tv1.tv_sec - tv2.tv_sec) * 1000 + (tv1.tv_usec - tv2.tv_usec) / 1000)int connect_tcpserver(const char *ip, unsigned short port)
{int connfd = socket(AF_INET, SOCK_STREAM, 0);struct sockaddr_in tcpserver_addr;memset(&tcpserver_addr, 0, sizeof(struct sockaddr_in));tcpserver_addr.sin_family = AF_INET;tcpserver_addr.sin_addr.s_addr = inet_addr(ip);tcpserver_addr.sin_port = htons(port);int ret = connect(connfd, (struct sockaddr *)&tcpserver_addr, sizeof(struct sockaddr_in));if (ret){perror("connect");return -1;}return connfd;
}int send_msg(int connfd, char *msg, int length)
{int res = send(connfd, msg, length, 0);if (res < 0){perror("send error");exit(1);}return res;
}int recv_msg(int connfd, char *msg, int length)
{int res = recv(connfd, msg, length, 0);if (res < 0){perror("recv error");exit(1);}return res;
}void equals(char *pattern, char *result, char *casename)
{if (strcmp(pattern, result) == 0){// printf("==> PASS --> %s\n", casename);}else{printf("==> FAILED --> %s, '%s' != '%s'\n", casename, pattern, result);}
}void test_case(int connfd, char *msg, char *pattern, char *casename)
{if (!msg || !pattern || !casename)return;send_msg(connfd, msg, strlen(msg));char result[MAX_MAS_LENGTH] = {0};recv_msg(connfd, result, MAX_MAS_LENGTH);equals(pattern, result, casename);
}void array_testcase(int connfd)
{test_case(connfd, "SET Name King", "SUCCESS", "SETCase");test_case(connfd, "GET Name", "King", "GETCase");test_case(connfd, "MOD Name Darren", "SUCCESS", "MODCase");test_case(connfd, "GET Name", "Darren", "GETCase");test_case(connfd, "DEL Name", "SUCCESS", "DELCase");test_case(connfd, "GET Name", "NO EXIST", "GETCase");
}void rbtree_testcase(int connfd)
{test_case(connfd, "RSET Name King", "SUCCESS", "SETCase");test_case(connfd, "RGET Name", "King", "GETCase");test_case(connfd, "RMOD Name Darren", "SUCCESS", "MODCase");test_case(connfd, "RGET Name", "Darren", "GETCase");test_case(connfd, "RDEL Name", "SUCCESS", "DELCase");test_case(connfd, "RGET Name", "NO EXIST", "GETCase");
}void hash_testcase(int connfd)
{test_case(connfd, "HSET Name King", "SUCCESS", "HSETCase");test_case(connfd, "HGET Name", "King", "HGETCase");test_case(connfd, "HMOD Name Darren", "SUCCESS", "HMODCase");test_case(connfd, "HGET Name", "Darren", "HGETCase");test_case(connfd, "HDEL Name", "SUCCESS", "HDELCase");test_case(connfd, "HGET Name", "NO EXIST", "HGETCase");
}void array_testcase_10w(int connfd)
{int count = 100000;int i = 0;while (i++ < count){array_testcase(connfd);}
}void rbtree_testcase_10w(int connfd)
{int count = 100000;int i = 0;while (i++ < count){rbtree_testcase(connfd);}
}void hash_testcase_10w(int connfd)
{int count = 100000;int i = 0;while (i++ < count){hash_testcase(connfd);}
}int main(int argc, char *argv[])
{int ret;char ip[16] = {0};int port = 0;int mode = 1;int opt;while ((opt = getopt(argc, argv, "s:p:m:?")) != -1){switch (opt){case 's':strcpy(ip, optarg);break;case 'p':port = atoi(optarg);break;case 'm':mode = atoi(optarg);break;default:return -1;}}int connfd = connect_tcpserver(ip, port);if (mode & 0x1){struct timeval tv_begin;gettimeofday(&tv_begin, NULL);array_testcase_10w(connfd);struct timeval tv_end;gettimeofday(&tv_end, NULL);int time_used = TIME_SUB_MS(tv_end, tv_begin);printf("array testcase--> time_used: %d, qps: %d\n", time_used, 600000 * 1000 / time_used);}if (mode & 0x2){struct timeval tv_begin;gettimeofday(&tv_begin, NULL);rbtree_testcase_10w(connfd);struct timeval tv_end;gettimeofday(&tv_end, NULL);int time_used = TIME_SUB_MS(tv_end, tv_begin);printf("rbtree testcase--> time_used: %d, qps: %d\n", time_used, 600000 * 1000 / time_used);}if (mode & 0x4){struct timeval tv_begin;gettimeofday(&tv_begin, NULL);hash_testcase_10w(connfd);struct timeval tv_end;gettimeofday(&tv_end, NULL);int time_used = TIME_SUB_MS(tv_end, tv_begin);printf("hash testcase--> time_used: %d, qps: %d\n", time_used, 600000 * 1000 / time_used);}return 0;
}

测试结果如下：
在这里插入图片描述
整体来说，数据结构相同情况下，io_uring会比epoll的时间要更少，性能更优。数据结构自身对比，hash的qps最高，array的qps最低，说明在KV存储中hash的性能更好(这个结果也可能受限于测试样例，其他类型的测试样例可能是红黑树会优于哈希表，但两者都会优于array)。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/477241.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

大公司如何实现打印机共享的？如何对打印机进行管控或者工号登录后进行打印？异地打印机共享的如何实现可以帮助用户在不同地理位置使用同一台打印机完成打印任务？

大公司如何实现打印机共享的？如何对打印机进行管控或者工号登录后进行打印？异地打印机共享的如何实现可以帮助用户在不同地理位置使用同一台打印机完成打印任务？

大公司如何实现打印机共享的&#xff1f;如何对打印机进行管控或者工号登录后进行打印&#xff1f;异地打印机共享的如何实现可以帮助用户在不同地理位置使用同一台打印机完成打印任务&#xff1f; 如果在局域网内&#xff0c;可以不需要进行二次开发&#xff0c;通过对打印机进…
阅读更多...
微软发布Win11 24H2系统11月可选更新KB5046740！

微软发布Win11 24H2系统11月可选更新KB5046740！

系统之家11月22日报道&#xff0c;微软针对Win11 24H2系统推出2024年11月最新可选更新补丁KB5046740&#xff0c;更新后系统版本后升至26100.2454&#xff0c;此次更新后修复当应用程序以PDF和XLSX格式导出图表对象时停止响应、无法使用API查找旋转信息等问题。以下小编将给大家…
阅读更多...
探索 RocketMQ：企业级消息中间件的选择与应用

探索 RocketMQ：企业级消息中间件的选择与应用

一、关于RocketMQ RocketMQ 是一个高性能、高可靠、可扩展的分布式消息中间件&#xff0c;它是由阿里巴巴开发并贡献给 Apache 软件基金会的一个开源项目。RocketMQ 主要用于处理大规模、高吞吐量、低延迟的消息传递&#xff0c;它是一个轻量级的、功能强大的消息队列系统&…
阅读更多...
李宏毅机器学习课程知识点摘要（6-13集）

李宏毅机器学习课程知识点摘要（6-13集）

pytorch简单的语法和结构 dataset就是数据集&#xff0c;dataloader就是分装好一堆一堆的 他们都是torch.utils.data里面常用的函数&#xff0c;已经封装好了 下面的步骤是把数据集读进来 这里是读进来之后&#xff0c;进行处理 声音信号&#xff0c;黑白照片&#xff0c;红…
阅读更多...
Wekan看板安装部署与使用介绍

Wekan看板安装部署与使用介绍

Wekan看板安装部署与使用介绍 1. Wekan简介 ​ Wekan 是一个开源的看板式项目管理工具&#xff0c;它的配置相对简单&#xff0c;因为大多数功能都是开箱即用的。它允许用户以卡片的形式组织和跟踪任务&#xff0c;非常适合敏捷开发和日常任务管理。Wekan 的核心功能包括看板…
阅读更多...
【Mysql】开窗聚合函数----SUM,AVG, MIN,MAX

【Mysql】开窗聚合函数----SUM,AVG, MIN,MAX

1、概念 在窗口中&#xff0c;每条记录动态地应用聚合函数&#xff08;如&#xff1a;SUM(),AVG(),MAX(),MIN(),COUNT(),&#xff09;可以动态计算在指定的窗口内的各种聚合函数值。 2、操作 以下操作将基于employee表进行操作。 sum() 进行sum的时候&#xff0c;没有order …
阅读更多...
EWA Volume Splatting

EWA Volume Splatting

摘要 本文提出了一种基于椭圆高斯核的直接体绘制新框架&#xff0c;使用了一种投影方法&#xff08;splatting approach&#xff09;。为避免混叠伪影&#xff08;aliasing artifacts&#xff09;&#xff0c;我们引入了一种重采样滤波器的概念&#xff0c;该滤波器结合了重建核…
阅读更多...
Vue实训---0-完成Vue开发环境的搭建

Vue实训---0-完成Vue开发环境的搭建

1.在官网下载和安装VS Code编辑器 完成中文语言扩展&#xff08;chinese&#xff09;&#xff0c;安装成功后&#xff0c;需要重新启动VS Code编辑器&#xff0c;中文语言扩展才可以生效。 安装Vue-Official扩展&#xff0c;步骤与安装中文语言扩展相同&#xff08;专门用于为“…
阅读更多...
C# 超链接控件LinkLabel无法触发Alt快捷键

C# 超链接控件LinkLabel无法触发Alt快捷键

在C#中&#xff0c;为控件添加快捷键的方式有两种&#xff0c;其中一种就是Windows中较为常见的Alt快捷键&#xff0c;比如运行对话框&#xff0c;记事本菜单等。只需要按下 Alt 框号中带下划线的字母即可触发该控件的点击操作。如图所示 在C#开发中&#xff0c;实现类似的操作…
阅读更多...
赛氪媒体支持“2024科普中国青年之星创作交流活动”医学专场落幕

赛氪媒体支持“2024科普中国青年之星创作交流活动”医学专场落幕

2024年11月15日下午&#xff0c;由中国科普作家协会、科普中国发展服务中心主办&#xff0c;什刹海文化展示中心承办&#xff0c;并携手国内产学研一体融合领域的领军者——赛氪网共同支持的“2024科普中国青年之星创作交流活动”医学科普专场&#xff0c;在什刹海文化展示中心…
阅读更多...
《现代制造技术与装备》是什么级别的期刊？是正规期刊吗？能评职称吗？

《现代制造技术与装备》是什么级别的期刊？是正规期刊吗？能评职称吗？

​问题解答 问&#xff1a;《现代制造技术与装备》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的第二批认定学术期刊。 问&#xff1a;《现代制造技术与装备》级别&#xff1f; 答&#xff1a;省级。主管单位&#xff1a;齐鲁工业大学&#xff0…
阅读更多...
（十一）Python字符串常用操作

（十一）Python字符串常用操作

一、访问字符串值 Python访问子字符串变量&#xff0c;可以使用方括号来截取字符串。与列表的索引一样&#xff0c;字符串索引从0开始。 hh"LaoTie 666" hh[2] mm"床前明月光" mm[3] 字符串的索引值可以为负值。若索引值为负数&#xff0c;则表示由字符…
阅读更多...
数据结构(初阶6)---二叉树(遍历——递归的艺术)(详解)

数据结构(初阶6)---二叉树(遍历——递归的艺术)(详解)

二叉树的遍历与练习 一.二叉树的基本遍历形式1.前序遍历(深度优先遍历)2.中序遍历(深度优先遍历)3.后序遍历(深度优先遍历)4.层序遍历&#xff01;&#xff01;(广度优先遍历) 二.二叉树的leetcode小练习1.判断平衡二叉树1&#xff09;正常解法2&#xff09;优化解法 2.对称二叉…
阅读更多...
20.100ASK_T113-PRO 开发板开机自动QT程序简单的方法一

20.100ASK_T113-PRO 开发板开机自动QT程序简单的方法一

本文详细介绍了在嵌入式系统中实现程序开机自启动的多种方法&#xff0c;包括通过修改/etc/profile、/etc/rc.local文件&#xff0c;以及在/etc/init.d目录下创建启动脚本等方式。文章还解释了不同配置文件的作用及它们之间的区别。 开机自动启动QT应用程序 用户模式下的启动 …
阅读更多...
Android蓝牙架构，源文件目录/编译方式学习

Android蓝牙架构，源文件目录/编译方式学习

Android 版本 发布时间 代号&#xff08;Codename&#xff09; Android 1.0 2008年9月23日 无 Android 1.1 2009年2月9日 Petit Four Android 1.5 2009年4月27日 Cupcake Android 1.6 2009年9月15日 Donut Android 2.0 2009年10月26日 Eclair Android 2.1 2…
阅读更多...
LeetCode 145.二叉树的后序遍历

LeetCode 145.二叉树的后序遍历

题目&#xff1a;给你一棵二叉树的根节点 root &#xff0c;返回其节点值的 后序遍历 。 思路&#xff1a;左 右 根 代码&#xff1a; /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* Tre…
阅读更多...
GitLab｜数据迁移

GitLab｜数据迁移

注意&#xff1a;新服务器GitLab版本需和旧版本一致 在旧服务器执行命令进行数据备份 gitlab-rake gitlab:backup:create 备份数据存储在 /var/opt/gitlab/backups/ 将备份数据传输到新服务器的/var/opt/gitlab/backups/下&#xff0c;并修改文件权限&#xff08;下载前和上传…
阅读更多...
实验四：构建园区网（OSPF 动态路由）

实验四：构建园区网（OSPF 动态路由）

目录 一、实验简介 二、实验目的 三、实验需求 四、实验拓扑 五、实验步骤 1、在 eNSP 中部署网络 2、设计全网 IP 地址 3、配置二层交换机 4、配置路由交换机并测试通信 5、配置路由接口地址 6、配置 OSPF 动态路由&#xff0c;实现全网互通 一、实验简介 使用路由…
阅读更多...
外卖系统开发实战：从架构设计到代码实现

外卖系统开发实战：从架构设计到代码实现

开发一套外卖系统&#xff0c;需要在架构设计、技术选型以及核心功能开发等方面下功夫。这篇文章将通过代码实例&#xff0c;展示如何构建一个基础的外卖系统&#xff0c;从需求梳理到核心模块的实现&#xff0c;帮助你快速掌握开发要点。 一、系统架构设计 一个完整的外卖系…
阅读更多...
“AI玩手机”原理揭秘：大模型驱动的移动端GUI智能体

“AI玩手机”原理揭秘：大模型驱动的移动端GUI智能体

作者&#xff5c;郭源 前言 在后LLM时代&#xff0c;随着大语言模型和多模态大模型技术的日益成熟&#xff0c;AI技术的实际应用及其社会价值愈发受到重视。AI智能体&#xff08;AI Agent&#xff09;技术通过集成行为规划、记忆存储、工具调用等机制&#xff0c;为大模型装上…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023