Lock free caching

All developers writing multi-threaded, real-time mission critical systems has encountered the problem of reading from a cache and updating it at the same time. This is something that should be avoided as it will generally lead to exceptions, but how do you get your cache updated without introducing concurrency problems in your code?

The following will address this problem and give a (well known) design to solve it. The small code samples are in C++, but any language will do. I will also show a way to check for updates without reading all values (we here assume, that the values are stored in a database), hence keeping the load on the database to a minimum.

Please add the usual disclaimers about not being production coded, that you have to add error checking, &c. I must also apologize for the layout; when I have more time, I will create a template/style to accommodate code snippets.

Assume that you have a map of some sort.

typedef std::map<key,value> CMapCollection;
CMapCollection m_colMyMap[2];
long m_lMapCacheIdx;

As can be seen we declare an array of two maps. This is to hold the active and passive map. The m_lMapCacheIdx will hold the index of the active cache, so when we wish to look up a key in the map, we do the following:

CMapCollection::iterator it = m_colMyMap[m_lMapCacheIdx].find(theKey);

We can now do our lookups in the active map, and update the passive map without introducing concurrency problems in the form of locks.

My UpdateCache() function will connect to a database, retrieve a recordset and update the cache accordingly.

bool CMyClass::UpdateCache( void )
{
bool bRet = m_pConnection->AccessDatabase(...);

// Find the passive cache
const long lPassiveIdx = m_lMapCacheIdx ? 0 : 1;

// Clear the passive cache
m_colMyMap[lPassiveIdx].clear();

// Loop around the recordset returned by the call to AccessDatabase(...) and
// update the, just cleared, passive cache.

// Switch active cache
if ( bUpdateOk )
{
m_lMapCacheIdx = lPassiveIdx;
}

return true;
}

We periodically want to check for new values, so we have a worker thread timing out with a given interval, here 1000 ms.

unsigned long CMyClass::_WorkerThread ( CMyClass *pThis )
{
HRESULT hRes = CoInitializeEx(NULL, COINIT_MULTITHREADED);
if (hRes != S_OK) ErrorExit( _T("CoInitializeEx failed"), hRes );

unsigned long ulRes = pThis->WorkerThread();

CoUninitialize(); // Closes the COM library on the current thread, unloads all DLLs loaded by the thread, frees any other resources that the thread maintains, and forces all RPC connections on the thread to close

return ulRes;
}

unsigned long CMyClass::WorkerThread()
{
while ( true )
{
unsigned long ulEvent = WaitForSingleObject(m_hEvent, 1000); // Timeout every sec
switch (ulEvent)
{
case WAIT_TIMEOUT:
UpdateCache();
break;
case WAIT_OBJECT_0: // Something in queue or stop flag set
if (m_bStopFlag)
{
return ThreadExitCleanUp(0);
}
break;
default:
return ThreadExitCleanUp(-1);
break;
} // end switch on ulEvent
} // end while true
}

To ease readability I will reduce my UpdateCache function to the following:

bool CMyClass::UpdateCache( void )
{
bool bRet = m_pConnection->AccessDatabase(...);
// Do the update stuff
return true;
}

I've declared my UpdateCahce function as a bool; old habit as we do not yet use the return value; it might as well have been declared as void.

So every second we call our UpdateCache() function. However, we may not want to actually check for updates this frequently.

We will add some more code to UpdateCache. Assume the following:

m_llUpdateTime is declared as __int64. This is the time stamp for the last update.
UtcTimeNow() is a helper function that sets the UTC time (always use UTC when doing anything with time and you want to ensure it is working over different time zones).

bool CMyClass::UpdateCache( void )
{
__int64 tNow;
UtcTimeNow(&tNow);

if ( (tNow < m_llUpdateTime ¦¦
(tNow - m_ llUpdateTime)/TSW_SECONDS_TO_NANOSEC >= 900))
{
m_pConnection->AccessDatabase(...);
// Do the update stuff
m_ llUpdateTime = tNow;
}
return true;
}

We now only access the database every 15 minutes (900 seconds), but we still do it regardless of whether any rows in the database has been updated or not. If we are reading in large amounts of data this is really a waste of resources.

To accommodate this last requirement, I will use a design pattern of first checking a timestamp in another (small) table and only if this timestamp is more recent than when I last read my data, I will access the data base. The database schema for the TableUpdates table is: TableName (varchar), Timestamp (datetime).

The member variable m_TableUpdate is a pointer to a class maintaining a connection to the database. It also has two helper functions: CheckForTableUpdate() and AcceptTableUpdate(). CheckForTableUpdate() takes a table name as input and returns a bool if the time stamp for that table has been updated since last time we checked. AcceptTableUpdate() sets an internal timer for when the last update was read. This design allows us to use the same class for checking multiple tables for updates.

Update our UpdateCache() function to the following:

bool CMyClass::UpdateCache( void )
{
LPTSTR TableUpdateTag = _T("Exchanges");
__int64 tNow;
UtcTimeNow(&tNow);

if ( (tNow < m_llUpdateTime ¦¦
(tNow - m_ llUpdateTime)/TSW_SECONDS_TO_NANOSEC >= 900))
{
bool bIsUpdated = false;
if ( !m_TableUpdate.CheckForTableUpdate(TableUpdateTag, &bIsUpdated) )
{
bIsUpdated = true; // We force a read if the check failed
// Some error logging
}

if ( bIsUpdated )
{
if ( !m_TableUpdate.AcceptTableUpdate(TableUpdateTag) )
{
// Some more error logging
}
m_pConnection->AccessDatabase(...);
// Do the update stuff
m_ llUpdateTime = tNow;
}
}
return true;
}

We have now achieved what we wanted, namely to only read the (map)values from the database when they have been updated.