[erlang-questions] Guidance to a cache mechanism

[Richard O'Keefe]

On 1/11/2012, at 7:47 PM, dmitry kolesnikov wrote:

> Hello Richard,
> 
> Somehow, I have missed your point here. It is obvious that two indexes
> are required: hash and b-tree. Unless we have a double linked list but
> we do not :-(

Let me quote the text I was replying to:

>> 
>> On 31/10/2012, at 6:55 PM, Maruthavanan Subbarayan wrote:
>>> I thought of keeping the time stamp as the key in the ets table and maintain that in state when a timeout event occurs. I hope this would help me to delete the entries in ets table with less burden.

> 
*THE* key.  That means one.  *THE* table.  That means one.

An ETS table can have only one key, only one index.

Now, let's think about this.
Sticking with Brekekek.example.com, suppose Xanthias sent a Croak
that is due to expire.  And suppose the structure is
	T1: {**Msg_Id, Time, User, Croak}
	T2: {**Time, [Msg_Id]}
	T3: {**User, [Msg_Id]}.
If Dionysus wants to see Croaks from Xanthias, he looks in T3,
and finds a list of Msg_Ids, which he then looks up in T1.

If Father Time wants to remove some messages, he looks in T2,
and finds a list of Msg_Ids, which he then removes from T1.
But what happens to T3?  T3 is not indexed by Time or Msg_Id.

One approach, which has been mentioned already, and I'm sorry for
forgetting by whom, is to make the lookup process a bit more
complicated.

When Dionysus wants to see Croaks from Xanthias, he looks in T3,
and finds a list of Msg_Ids.  But now he cannot be sure that those
Msg_Ids still exist.  So *while holding a lock on T3['Xanthias']*,
he picks up the messages from T1, and makes a new list of Msg_Ids,
the ones that still exist and have not expired.  Dionysus then
stores {'Xanthias', Filtered_Msg_Ids} back in T3.

Dealing with all the details gets a bit painful.  And when you've
done it, you have the problem that T3 can grow without limit:  an
entry in T3 shrinks only when someone looks at it.   Suppose, for
example, that Pluto Croaks frequently, but has no followers.  His
messages are regularly purged from T1,  but his entry in T3 keeps
on growing.

ETS certainly doesn't make any of this easy.

Mnesia is another matter.
Using (truncated) Time as primary key of a bag-structured table,
mnesia:add_table_index/2 to add an index on User,
mnesia:index_read/3 to find the Croaks of a User, and
mnesia:delete/3 to delete expired Croaks,
it all fits beautifully.