400 줄 코드 는 로 컬 키 - Value 캐 시 를 실현 합 니 다. 성능 은 초당 수백 만 번 이 고 프로 세 스 재 부팅 이 유효 합 니 다. LRU 탈락 - HashTable
Key - Value 캐 시 는 매우 많 습 니 다. memcache, redis 를 많이 사용 합 니 다. 그들 은 모두 독립 된 서비스 형식 으로 실 행 됩 니 다. 작업 중 에 로 컬 key - value 캐 시 를 삽입 해 야 할 때 가 있 습 니 다. 물론 LevelDb 등 이 있 지만 너무 무 거 운 것 같 습 니 다.
본 고 는 매우 가 벼 운 캐 시 를 실현 하 였 다.
1. 실현 코드 는 400 줄 만 필요 합 니 다.
2. 성능 이 효율 적 이 고 value 길이 가 1K 일 때 테스트 속도 가 초당 200 만 정도 입 니 다.
3. 캐 시 는 파일 에 매 핑 되 기 때문에 malloc, free 의 비용, 그리고 가 져 온 메모리 유출, 메모리 조각 등 이 없습니다.
4. 서비스 가 끊 기 면 다시 시작 한 후에 캐 시 내용 이 계속 존재 합 니 다.
5. 캐 시 를 디스크 파일 에 비 추 면 기계 가 끊 어도 캐 시 에 내용 이 존재 합 니 다. 물론 데이터 가 손 상 될 수 있 습 니 다.
6. 어느 정도 에 LRU 도태 알고리즘 을 실 현 했 고 이 루어 진 LRU 는 전체적인 것 이 아니 라 하나의 체인 에 불과 하기 때문에 일정한 절차 에서 이 루어 졌 다 고 할 수 있다.
7. 안정 적 이 고 여러 프로젝트 에서 활용 되 었 으 며 온라인 에 배 치 된 기 계 는 몇 십 대 이 고 반년 동안 운행 되 었 으 며 문제 가 없 었 습 니 다.
8. 일반적인 캐 시 키, value 는 모두 문자열 형식 입 니 다. 이 캐 시 키, value 는 모두 class, struct 대상 구조 로 사용 하기에 더욱 편리 합 니 다.
오래된 규칙 은 코드 에 직접 올 립 니 다.
template<typename K, typename V>
class HashTable
{
public:
HashTable(const char *tablename, uint32_t tableLen, uint32_t nodeTotal);
virtual ~HashTable();
bool Add(K &key, V &value)
{
AutoLock autoLock(m_MutexLock);
//check is exist
uint32_t nodeId = GetIdByKey(key);
if(nodeId != m_InvalidId) return false;
nodeId = GetFreeNode();
if(nodeId == m_InvalidId) return false;
uint32_t hashCode = key.HashCode();
Entry *tmpNode = m_EntryAddr + nodeId;
tmpNode->m_Key = key;
tmpNode->m_Code = hashCode;
tmpNode->m_Value = value;
uint32_t index = hashCode % m_HeadAddr->m_TableLen;
AddNodeToHead(index, nodeId);
return true;
}
bool Del(K &key)
{
AutoLock autoLock(m_MutexLock);
uint32_t nodeId = GetIdByKey(key);
if(nodeId == m_InvalidId) return false;
uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;
return RecycleNode(index, nodeId);
}
bool Set(K &key, V &value)
{
AutoLock autoLock(m_MutexLock);
uint32_t nodeId = GetIdByKey(key);
if(nodeId == m_InvalidId) return false;
(m_EntryAddr + nodeId)->m_Value = value;
return true;
}
bool Get(K &key, V &value)
{
AutoLock autoLock(m_MutexLock);
uint32_t nodeId = GetIdByKey(key);
if(nodeId == m_InvalidId) return false;
value = (m_EntryAddr + nodeId)->m_Value;
return true;
}
bool Exist(K &key)
{
AutoLock autoLock(m_MutexLock);
uint32_t nodeId = GetIdByKey(key);
if(nodeId == m_InvalidId) return false;
return true;
}
uint32_t Count()
{
AutoLock autoLock(m_MutexLock);
return m_HeadAddr->m_UsedCount;
}
//if exist set else add
bool Replace(K &key, V &value)
{
AutoLock autoLock(m_MutexLock);
if(Exist(key)) return Set(key, value);
else return Add(key, value);
}
/***********************************************
****LRU: when visit a node, move it to head ****
************************************************/
//if no empty place,recycle tail
bool LruAdd(K &key, V &value, K &recyKey, V &recyValue, bool &recycled)
{
AutoLock autoLock(m_MutexLock);
if(Exist(key)) return false;
if(Add(key, value)) return true;
uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;
uint32_t tailId = GetTailNodeId(index);
if(tailId == m_InvalidId) return false;
Entry *tmpNode = m_EntryAddr + tailId;
recyKey = tmpNode->m_Key;
recyValue = tmpNode->m_Value;
recycled = true;
RecycleNode(index, tailId);
return Add(key, value);
}
bool LruSet(K &key, V &value)
{
AutoLock autoLock(m_MutexLock);
if(Set(key, value)) return MoveToHead(key);
else return false;
}
bool LruGet(K &key, V &value)
{
AutoLock autoLock(m_MutexLock);
if(Get(key, value)) return MoveToHead(key);
else return false;
}
//if exist set else add; if add failed recycle tail than add
bool LruReplace(K &key, V &value, K &recyKey, V &recyValue, bool &recycled)
{
AutoLock autoLock(m_MutexLock);
recycled = false;
if(Exist(key)) return LruSet(key, value);
else return LruAdd(key, value, recyKey, recyValue, recycled);
}
void Clear()
{
AutoLock autoLock(m_MutexLock);
m_HeadAddr->m_FreeBase = 0;
m_HeadAddr->m_RecycleHead = 0;
m_HeadAddr->m_UsedCount = 0;
for(uint32_t i = 0; i < m_HeadAddr->m_TableLen; ++i)
{
(m_ArrayAddr+i)->m_Head = m_InvalidId;
(m_ArrayAddr+i)->m_Tail = m_InvalidId;
}
}
int GetRowKeys(vector<K> &keys, uint32_t index)
{
AutoLock autoLock(m_MutexLock);
if(index >= m_HeadAddr->m_TableLen) return -1;
keys.clear();
keys.reserve(16);
int count = 0;
Array *tmpArray = m_ArrayAddr + index;
uint32_t nodeId = tmpArray->m_Head;
while(nodeId != m_InvalidId)
{
Entry *tmpNode = m_EntryAddr + nodeId;
keys.push_back(tmpNode->m_Key);
nodeId = tmpNode->m_Next;
++count;
}
return count;
}
void *Padding(uint32_t size)
{
AutoLock autoLock(m_MutexLock);
if(size > m_HeadSize - sizeof(TableHead)) return NULL;
else return m_HeadAddr->m_Padding;
}
private:
static const uint32_t m_InvalidId = 0xffffffff;
static const uint32_t m_HeadSize = 1024;
struct TableHead
{
uint32_t m_TableLen;
uint32_t m_NodeTotal;
uint32_t m_FreeBase;
uint32_t m_RecycleHead;
uint32_t m_UsedCount;
char m_TableName[256];
uint32_t m_Padding[0];
};
struct Array
{
uint32_t m_Head;
uint32_t m_Tail;
};
struct Entry
{
V m_Value;
K m_Key;
uint32_t m_Code;
uint32_t m_Next;
uint32_t m_Prev;
};
size_t m_MemSize;
uint8_t *m_MemAddr;
TableHead *m_HeadAddr;
Array *m_ArrayAddr;
Entry *m_EntryAddr;
ThreadMutex m_MutexLock;
bool MoveToHead(K &key);
uint32_t GetIdByKey(K &key);
void AddNodeToHead(uint32_t index, uint32_t nodeId);
bool MoveNodeToHead(uint32_t index, uint32_t nodeId);
bool RecycleNode(uint32_t index, uint32_t nodeId);
uint32_t GetTailNodeId(uint32_t index);
uint32_t GetFreeNode();
DISABLE_COPY_AND_ASSIGN(HashTable);
};
template<typename K, typename V>
HashTable<K, V>::HashTable(const char *tablename, uint32_t tableLen, uint32_t nodeTotal)
{
AbortAssert(tablename != NULL);
m_MemSize = m_HeadSize + tableLen*sizeof(Array) + nodeTotal*sizeof(Entry);
m_MemAddr = (uint8_t*)MemFile::Realloc(tablename, m_MemSize);
AbortAssert(m_MemAddr != NULL);
m_HeadAddr = (TableHead*)(m_MemAddr);
m_ArrayAddr = (Array*)(m_MemAddr + m_HeadSize);
m_EntryAddr = (Entry*)(m_MemAddr + m_HeadSize + tableLen*sizeof(Array));
m_HeadAddr->m_TableLen = tableLen;
m_HeadAddr->m_NodeTotal = nodeTotal;
strncpy(m_HeadAddr->m_TableName, tablename, sizeof(m_HeadAddr->m_TableName));
if(m_HeadAddr->m_UsedCount == 0)//if first use init array to invalid id
{
for(uint32_t i = 0; i < tableLen; ++i)
{
(m_ArrayAddr+i)->m_Head = m_InvalidId;
(m_ArrayAddr+i)->m_Tail = m_InvalidId;
}
m_HeadAddr->m_FreeBase = 0;
m_HeadAddr->m_RecycleHead = 0;
}
}
template<typename K, typename V>
HashTable<K, V>::~HashTable()
{
MemFile::Release(m_MemAddr, m_MemSize);
}
template<typename K, typename V>
bool HashTable<K, V>::MoveToHead(K &key)
{
uint32_t nodeId = GetIdByKey(key);
uint32_t index = key.HashCode() % m_HeadAddr->m_TableLen;
return MoveNodeToHead(index, nodeId);
}
template<typename K, typename V>
uint32_t HashTable<K, V>::GetIdByKey(K &key)
{
uint32_t hashCode = key.HashCode();
uint32_t index = hashCode % m_HeadAddr->m_TableLen;
Array *tmpArray = m_ArrayAddr + index;
uint32_t nodeId = tmpArray->m_Head;
while(nodeId != m_InvalidId)
{
Entry *tmpNode = m_EntryAddr + nodeId;
if(tmpNode->m_Code == hashCode && key.Equals(tmpNode->m_Key)) break;
nodeId = tmpNode->m_Next;
}
return nodeId;
}
template<typename K, typename V>
void HashTable<K, V>::AddNodeToHead(uint32_t index, uint32_t nodeId)
{
if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return;
Array *tmpArray = m_ArrayAddr + index;
Entry *tmpNode = m_EntryAddr + nodeId;
if(m_InvalidId == tmpArray->m_Head)
{
tmpArray->m_Head = nodeId;
tmpArray->m_Tail = nodeId;
}
else
{
tmpNode->m_Next = tmpArray->m_Head;
(m_EntryAddr + tmpArray->m_Head)->m_Prev = nodeId;
tmpArray->m_Head = nodeId;
}
}
template<typename K, typename V>
bool HashTable<K, V>::MoveNodeToHead(uint32_t index, uint32_t nodeId)
{
if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return false;
Array *tmpArray = m_ArrayAddr + index;
Entry *tmpNode = m_EntryAddr + nodeId;
//already head
if(tmpArray->m_Head == nodeId)
{
return true;
}
uint32_t nodePrev = tmpNode->m_Prev;
uint32_t nodeNext = tmpNode->m_Next;
(m_EntryAddr+nodePrev)->m_Next = nodeNext;
if(nodeNext != m_InvalidId)
{
(m_EntryAddr+nodeNext)->m_Prev = nodePrev;
}
else
{
tmpArray->m_Tail = nodePrev;
}
tmpNode->m_Prev = m_InvalidId;
tmpNode->m_Next = tmpArray->m_Head;
(m_EntryAddr + tmpArray->m_Head)->m_Prev = nodeId;
tmpArray->m_Head = nodeId;
return true;
}
template<typename K, typename V>
bool HashTable<K, V>::RecycleNode(uint32_t index, uint32_t nodeId)
{
if(index >= m_HeadAddr->m_TableLen || nodeId >= m_HeadAddr->m_NodeTotal) return false;
Array *tmpArray = m_ArrayAddr + index;
Entry *tmpNode = m_EntryAddr + nodeId;
uint32_t nodePrev = tmpNode->m_Prev;
uint32_t nodeNext = tmpNode->m_Next;
if(nodePrev != m_InvalidId)
{
(m_EntryAddr + nodePrev)->m_Next = nodeNext;
}
else
{
tmpArray->m_Head = nodeNext;
}
if(nodeNext != m_InvalidId)
{
(m_EntryAddr + nodeNext)->m_Prev = nodePrev;
}
else
{
tmpArray->m_Tail = nodePrev;
}
(m_EntryAddr+nodeId)->m_Next = m_HeadAddr->m_RecycleHead;
m_HeadAddr->m_RecycleHead = nodeId;
--(m_HeadAddr->m_UsedCount);
return true;
}
template<typename K, typename V>
uint32_t HashTable<K, V>::GetTailNodeId(uint32_t index)
{
if(index >= m_HeadAddr->m_TableLen) return m_InvalidId;
Array *tmpArray = m_ArrayAddr + index;
return tmpArray->m_Tail;
}
template<typename K, typename V>
uint32_t HashTable<K, V>::GetFreeNode()
{
uint32_t nodeId = m_InvalidId;
if(m_HeadAddr->m_UsedCount < m_HeadAddr->m_FreeBase)//get from recycle list
{
nodeId = m_HeadAddr->m_RecycleHead;
m_HeadAddr->m_RecycleHead = (m_EntryAddr+nodeId)->m_Next;
++(m_HeadAddr->m_UsedCount);
}
else if(m_HeadAddr->m_UsedCount < m_HeadAddr->m_NodeTotal)//get from free mem
{
nodeId = m_HeadAddr->m_FreeBase;
++(m_HeadAddr->m_FreeBase);
++(m_HeadAddr->m_UsedCount);
}
else
{
nodeId = m_InvalidId;
}
//init node
if(nodeId < m_HeadAddr->m_NodeTotal)
{
Entry *tmpNode = m_EntryAddr + nodeId;
memset(tmpNode, 0, sizeof(Entry));
tmpNode->m_Next = m_InvalidId;
tmpNode->m_Prev = m_InvalidId;
}
return nodeId;
}
저자: gdutliuyun 827 발표 2013 - 12 - 10 17: 11: 37 원문 링크
댓 글
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vue 단일 페이지에 여러 개의 echarts 도표가 있을 때의 공용 코드 쓰기html에서: 데이터 처리는 말할 필요가 없다.응, 직접 그림을 그려: 공통 섹션: 이 페이지를 떠날 때 파괴: 추가 정보: Vue + Echarts 차트 표시 및 동적 렌더링 준비 작업 echarts 의존 설치 n...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.