HTTP高效解析的方法之哈希加速

╰半夏微凉° 2022-11-30 12:50 319阅读 0赞

# 哈希加速 #

在我们获取到HTTP的外部请求的时候，第一步去识别它所对应的请求类型，然后再去获取它后面所对的URL,最后在对URL做进一步的解析。

在我们获取到了URL之后，我们需要在数据库中或者文件系统中获取对应的文件（也就是字符串匹配），但是解析过程中字符串的比较很慢，达不到我们的需求，那么我们就需要加快URL的解析，那么如何操作呢？我们可以使用哈希加速

哈希加速：把服务器自己所对应的url全部通过哈希算法，把每一个路径都算成一个数，然后把输入的URL也进行哈希算法，算成一个数，和服务器的进行比较，如果在服务器的哈希范围内并且有匹配的值，就打开对应的路径所对应的文件，如果哈希值匹配不上，就认为此URL是错误的URL。

这样通过哈希来比较，比字符串的比较快的多。

*  HASH解析URL链接实现

/*管理URL的对象*/
    typedef struct { 
        char    url[MAX_URL_LEN];	//URL
        size_t  len;				//长度
        int     all;				//个数
        UT_hash_handle hh;  		//HASH表
    } url_t;
    
    
    /*HASH表的一个节点*/
    typedef struct UT_hash_handle { 
       struct UT_hash_table *tbl;
       void *prev;                       /* prev element in app order */
       void *next;                       /* next element in app order */
       struct UT_hash_handle *hh_prev;   /* previous hh in bucket order */
       struct UT_hash_handle *hh_next;   /* next hh in bucket order */
       void *key;                        /* ptr to enclosing struct's key */
       unsigned keylen;                  /* enclosing struct's key len */
       unsigned hashv;                   /* result of hash-fcn(key) */
    } UT_hash_handle;
    
    
    /*HASH表*/
    typedef struct UT_hash_table
    { 
       UT_hash_bucket *buckets;
       unsigned num_buckets, log2_num_buckets;
       unsigned num_items;
       struct UT_hash_handle *tail; /* tail hh in app order, for fast append */
       ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */
    
       /* in an ideal situation (all buckets used equally), no bucket would have * more than ceil(#items/#buckets) items. that's the ideal chain length. */
       unsigned ideal_chain_maxlen;
    
       /* nonideal_items is the number of items in the hash whose chain position * exceeds the ideal chain maxlen. these items pay the penalty for an uneven * hash distribution; reaching them in a chain traversal takes >ideal steps */
       unsigned nonideal_items;
    
       /* ineffective expands occur when a bucket doubling was performed, but * afterward, more than half the items in the hash had nonideal chain * positions. If this happens on two consecutive expansions we inhibit any * further expansion, as it's not helping; this happens when the hash * function isn't a good fit for the key domain. When expansion is inhibited * the hash will still work, albeit no longer in constant time. */
       unsigned ineff_expands, noexpand;
    
       uint32_t signature; /* used only to find hash tables in external analysis */
    #ifdef HASH_BLOOM
       uint32_t bloom_sig; /* used only to test bloom exists in external analysis */
       uint8_t *bloom_bv;
       uint8_t bloom_nbits;
    #endif
    }
    
    
    /*HASH算法*/
    HASH_FIND_STR(urls, url, u);
    
    #define HASH_FIND_STR(head,findstr,out) \ HASH_FIND(hh,head,findstr,(unsigned)uthash_strlen(findstr),out)
    
    
    #define HASH_FIND(hh,head,keyptr,keylen,out) \ do { \ unsigned _hf_hashv; \ HASH_VALUE(keyptr, keylen, _hf_hashv); \ HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ } while (0
    
    
    #define HASH_VALUE(keyptr,keylen,hashv) \ do { \ HASH_FCN(keyptr, keylen, hashv); \ } while (0)
    
    
    #ifdef HASH_FUNCTION
    #define HASH_FCN HASH_FUNCTION
    #else
    #define HASH_FCN HASH_JEN
    #endif
    
    #define HASH_JEN(key,keylen,hashv) \ do { \ unsigned _hj_i,_hj_j,_hj_k; \ unsigned const char *_hj_key=(unsigned const char*)(key); \ hashv = 0xfeedbeefu; \ _hj_i = _hj_j = 0x9e3779b9u; \ _hj_k = (unsigned)(keylen); \ while (_hj_k >= 12U) { \ _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + ( (unsigned)_hj_key[2] << 16 ) \ + ( (unsigned)_hj_key[3] << 24 ) ); \ _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + ( (unsigned)_hj_key[6] << 16 ) \ + ( (unsigned)_hj_key[7] << 24 ) ); \ hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + ( (unsigned)_hj_key[10] << 16 ) \ + ( (unsigned)_hj_key[11] << 24 ) ); \ \ HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ \ _hj_key += 12; \ _hj_k -= 12U; \ } \ hashv += (unsigned)(keylen); \ switch ( _hj_k ) { \ case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */         \
        case 10: hashv += ( (unsigned)_hj_key[9] << 16 );  /* FALLTHROUGH */         \
        case 9:  hashv += ( (unsigned)_hj_key[8] << 8 );   /* FALLTHROUGH */         \
        case 8:  _hj_j += ( (unsigned)_hj_key[7] << 24 );  /* FALLTHROUGH */         \
        case 7:  _hj_j += ( (unsigned)_hj_key[6] << 16 );  /* FALLTHROUGH */         \
        case 6:  _hj_j += ( (unsigned)_hj_key[5] << 8 );   /* FALLTHROUGH */         \
        case 5:  _hj_j += _hj_key[4];                      /* FALLTHROUGH */         \
        case 4:  _hj_i += ( (unsigned)_hj_key[3] << 24 );  /* FALLTHROUGH */         \
        case 3:  _hj_i += ( (unsigned)_hj_key[2] << 16 );  /* FALLTHROUGH */         \
        case 2:  _hj_i += ( (unsigned)_hj_key[1] << 8 );   /* FALLTHROUGH */         \
        case 1:  _hj_i += _hj_key[0];                                                \
      }                                                                              \
      HASH_JEN_MIX(_hj_i, _hj_j, hashv);                                             \
    } while (0)
    
    #define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ do { \ (out) = NULL; \ if (head) { \ unsigned _hf_bkt; \ HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ } \ } \ } while (0)
    
    
     HASH_ADD_STR(urls, url, u);

那么我们如何维护一个HASH表呢？

**添加一个HASH**

int add_url(const char *url)
    { 
        url_t  *u;
    
        if (!url || strlen(url) >= MAX_URL_LEN) return 0;
    
        pthread_rwlock_wrlock(&rwlock);
    
        HASH_FIND_STR(urls, url, u);
        if (u) { 
            pthread_rwlock_unlock(&rwlock);
            return 0;
        }
    
        u = (url_t *)calloc(1, sizeof(url_t));
    
        strncpy(u->url, url, MAX_URL_LEN - 1);
        u->len = strlen(u->url);
    
        if (u->url[u->len - 1] == URL_SPLIT) { 
            //u->url[u->len - 1] = 0;
            u->all = 1;
        }
    
        HASH_ADD_STR(urls, url, u);
    
        pthread_rwlock_unlock(&rwlock);
    
        return 1;
    }

**判断URL在不在HASH表中**

int has_url(const char *url)
    { 
        char    tmp[MAX_URL_LEN];
        char   *start, *end, *pos;
        size_t  ul;
        url_t  *u;
    
        if (!url) { 
            return 0;
        }
        
        ul = strlen(url); 
        if (ul >= MAX_URL_LEN) { 
            return 0;
        }
    
        memset(tmp, 0x00, sizeof(tmp));
    
        pos   = tmp;
        start = (char *)url;
    
        pthread_rwlock_rdlock(&rwlock);
    
        HASH_FIND_STR(urls, url, u);
        if (u) { 
            pthread_rwlock_unlock(&rwlock);
            return 1;
        }
    
        end = strchr(start, URL_SPLIT);
        for (; end; end = strchr(start, URL_SPLIT)) { 
            memcpy(pos, start, end - start + 1);
    
            HASH_FIND_STR(urls, tmp, u);
            if (u && u->all) { 
                pthread_rwlock_unlock(&rwlock);
                return 1;
            }
    
            pos += (end - start + 1);
            start = end + 1;
        }
    
        pthread_rwlock_unlock(&rwlock);
    
        return 0;
    }

删除一个URL

int del_url(const char *url)
    { 
        url_t  *u;
    
        if (!url || strlen(url) >= MAX_URL_LEN) { 
            return 0;
        }
    
        pthread_rwlock_wrlock(&rwlock);
        
        HASH_FIND_STR(urls, url, u);
        if (u) { 
            HASH_DEL(urls, u);
            pthread_rwlock_unlock(&rwlock);
            return 1;
        }
    
        pthread_rwlock_unlock(&rwlock);
    
        return 0;
    }