在去年的软件开发2.0技术大会上，我讲了一个支持动态负载均衡的多核查找设计方法。基本思想是采用数据结构分拆的方法，使用了多级的数据结构设计。下面先简要介绍一下这种多级数据结构的设计思路，然后给出一个采用数组顺序查找作为查找表实现的多级数据结构类CDHashArray。 在CDHashArray中，对数组的插入和删除都是顺序化的操作，查找也是近似于顺序化的操作，看起来似乎会很慢。实际上对于小数组，比如只有几个或十来个数组，其效率并不慢，这使得以前在单核时代无法用于大型查找的数组顺序查找，在多核时代却可以得到很好应用前景。 二级查找结构基本思想 二级查找结构就是在第1级查找时找到二级子表的位置，然后在找到的二级子表中进行第二次查找来找到对应的目标数据。 二级查找结构由一级查找表和二级子表构成，一个查找表中的每个节点指向一个二级查找子表。查找时，先将关键词映射成一级查找表的位置，然后将对应位置的二级子表取出，在子表中找到对应的查找目标数据。 Intel Threading Building Blocks(TBB)开源项目中，其中的concurrent_hash_map使用的就是一种最简单的二级查找结构。它使用了哈希表式的数据结构，并给哈希表的每个桶设一把锁。 对于普通的查找，这种简单的二级查找结构也许够用了，但是对于一些大型的查找，这种简单的二级查找结构并不能满足。首先的问题是如果子表数量过多，则锁的数量也非常多，锁本身需要占用大量的内存开销。 如果子表数量过少，那么又会引起另外一个重要的问题，那就是负载平衡问题。因为这种情况中有可能各个二级子表中的数据数量相差非常大，这将导致某些子表的访问量很少，而某些子表的访问量很大。这些访问量大的表很容易发生多个线程同时访问的情况，从而导致集中式锁竞争情况的发生。 为了解决二级查找结构中的不足，下面来看看多级查找结构的设计思想。 多级查找结构设计思想 如果拆分后的子表内插入的数据过多时，可以继续将其分拆，这样一直分拆下去，将形成一个多级的查找数据结构， 在多级查找结构中进行操作时，所有索引表的操作都是不用锁的，只有访问查找表时才用锁，这使得它的查找效率并不会比二级查找结构降低。并且由于它是负载均衡的，每个查找子表的数量都是小于设定值的，这样每个查找表中查找的时间都是有保证的。而二级查找结构中并不能给出这种保证，比如链式的哈希表，如果哈希函数设计不好，某个桶中的元素个数过多，在这个桶中的查找将变慢。
在这种多级查找结构的设计中，查找表必须是可以分拆的，一般来说，比较易于分拆的查找数据结构有AVL树、数组等。 下面以数组为例来实现一个多级查找结构。由于基本算法思想在去年的软件开发大会上讲过，这里就不再详述了。如果没有听过讲座的也可以从下面的代码中去体会算法的基本思想。 使用数组作为查找表，可能很多人会认为速度很慢，因为数组的插入和删除速度看起来似乎很慢。但是实际上，如果数组设置得很小，比如只有几个或十几个数据，那么其插入和删除的速度并不慢，另外使用数组还有一个好处是容易进行CACHE行对齐，以避免伪共享问题（即多个线程操作的不同数据却位于同一Cache行的问题）。 对于这种小数组的查找，并不需要用到二分查找，可以采用近似于顺序查找的方法来进行查找，其查找效率也非常高效。 CDHashArray源代码 template <class T> struct INDEXNODE { FASTLOCK lock; T Key; LONG volatile lType; //FIND_TABLE or INDEX_TABLE; void *pSubTable; //sub table pointer，if lType is // DARRAYSEARCH_FIND_TABLE, pSubTable is a Search Array, // if lType is DARRAYSEARCH_INDEX_TABLE, // then pSubTable pointer to a INDEXNODE array . };
template <class T, class SearchArray> class CDHashArray { PRIVATE: INDEXNODE<T> * m_pIndexNode; int m_nBucketCount; int m_nSplitCount;
HASHFUNC m_HashFunc;
void SubTableInsert(INDEXNODE<T> *pNode, T &Data); void SubTableDelete(INDEXNODE<T> *pNode, T &Data); void SubTableFind(INDEXNODE<T> *pNode, T &Data, T &OutData); public:
CDHashArray(int nBucketCount, HASHFUNC HashFunc); virtual ~CDHashArray();
void Insert(T &Data); void Delete(T &Data); void Find(T &Data, T &OutData); };
/** 子表插入函数
@param INDEXNODE<T> *pNode - 要查找的索引节点 @param T &Data - 要查找的数据 @return void - 无 */ template <class T, class SearchArray> void CDHashArray<T, SearchArray>::SubTableInsert( INDEXNODE<T> *pNode, T &Data) { FastLockAcquire(&(pNode->lock));
LONG lType = pNode->lType; if ( lType == CDHASHARRAY_FIND_TABLE ) { //将子表地址转换成一个索引表指针; SearchArray *pArray = (SearchArray *)pNode->pSubTable;
pArray->Insert(Data);
if ( pArray->m_nCount == pArray->m_nSize ) { CIndexTable<T, SearchArray> *pTable = new CIndexTable<T, SearchArray>;
pTable->Split(pArray);
pNode->pSubTable = pTable;
//查找表的子表类型= 索引表(原子操作); AtomicIncrement(&(pNode->lType)); } } else { //将查找表指针转换为索引表指针; CIndexTable<T, SearchArray> *pTable = (CIndexTable<T, SearchArray> *)pNode->pSubTable;
//在索引表中找到对应的子表; INDEXNODE<T> *pTempNode = pTable->UpperBound(Data);
//由于在获取锁前，其他线程将表的类型又查找表改为了索引表 //这种情况下有可能有很多其他线程访问这个索引表时是不需要使用锁的 //因此这里需要递归调用,防止找到的查找子表又发生大量插入而变为索引表 //这样会发生多级加锁解锁操作，不过发生这种情况的概率是非常低的 SubTableInsert(pTempNode, Data); } FastLockRelease(&(pNode->lock)); return ; }
/** 分布式搜索数组的插入数据函数
@param T &Data - 要插入的数据 @return void - 无 */ template <class T, class SearchArray> void CDHashArray<T, SearchArray>::Insert(T &Data) { int nPos = (*m_HashFunc)((void *)Data, m_nBucketCount); INDEXNODE<T> *pNode = &(m_pIndexNode[nPos]);
LONG lType = pNode->lType; while ( lType == CDHASHARRAY_INDEX_TABLE ) { //将子表地址转换成一个索引表指针; CIndexTable<T, SearchArray> *pIndexTable = (CIndexTable<T, SearchArray> *)pNode->pSubTable;
//最终子表＝在索引表中进行二分查找到对应的索引节点; pNode = pIndexTable->UpperBound(Data);
//子表类型＝索引节点的子表类型; lType = pNode->lType; }
SubTableInsert(pNode, Data); return; }
/** 分布式搜索数组的子表查找数据函数
@param INDEXNODE<T> *pNode - 要删除数据的索引节点 @param T &Data - 要查找的数据 @param T &OutData - 存放找到的数据 @return void - 无 */ template <class T, class SearchArray> void CDHashArray<T, SearchArray>::SubTableFind( INDEXNODE<T> *pNode, T &Data, T &OutData) { FastLockAcquire(&(pNode->lock));
if (pNode->lType == CDHASHARRAY_FIND_TABLE) { SearchArray *pArray = (SearchArray *)pNode->pSubTable;
//在查找表中查找包含Data的节点; pArray->Find(Data, OutData); } else { //将查找表指针转换为索引表指针; CIndexTable<T, SearchArray> *pTable = (CIndexTable<T, SearchArray> *)pNode->pSubTable;
//在索引表中进行二分查找到对应的子表; pNode = pTable->UpperBound(Data);
//由于在获取锁前，其他线程将表的类型又查找表改为了索引表 //这种情况下有可能有很多其他线程访问这个索引表时是不需要使用锁的 //因此递归调用,防止找到的查找子表又发生大量插入而变为索引表 //不过这样会发生多级加锁解锁操作，不过发生这种情况的概率是非常低的 SubTableFind(pNode, Data, OutData); } FastLockRelease(&(pNode->lock));
return; }
/** 分布式搜索数组的查找数据函数
@param T &Data - 要查找的数据 @param T &OutData - 存放找到的数据 @return void - 无 */ template <class T, class SearchArray> void CDHashArray<T, SearchArray>::Find(T &Data, T &OutData) { int nPos = (*m_HashFunc)((void *)Data, m_nBucketCount); INDEXNODE<T> *pNode = &(m_pIndexNode[nPos]);
LONG lType = pNode->lType; while ( lType == CDHASHARRAY_INDEX_TABLE ) { //将子表地址转换成一个索引表指针; CIndexTable<T, SearchArray> *pIndexTable = (CIndexTable<T, SearchArray> *)pNode->pSubTable;
//最终子表＝在索引表中进行二分查找到对应的索引节点; pNode = pIndexTable->UpperBound(Data);
//子表类型＝索引节点的子表类型; lType = pNode->lType; }
SubTableFind(pNode, Data, OutData); return; }
|
