[Varnish] #210: The binary heap implementation does not scale

[Varnish]

#210: The binary heap implementation does not scale
-------------------------+--------------------------------------------------
 Reporter:  phk          |        Owner:  phk  
     Type:  enhancement  |       Status:  new  
 Priority:  normal       |    Milestone:       
Component:  varnishd     |      Version:  trunk
 Severity:  normal       |   Resolution:       
 Keywords:               |  
-------------------------+--------------------------------------------------
Old description:

> The binary heap implementation does not scale well to multiple millions
> of objects.
>
> There are two different approaches that can be persued:
>
> Either keep one (gigantic) binary heap, but fragment the array for
> holding it, so that we don't have to realloc(3) it as one huge slap of
> memory.
>
> Or keep only the next couple of hours worth of data in the binary heap,
> and relegate objects further in the future to a (number of) somewhat
> unsorted lists, which are examined at regular intervals for objects that
> need to move into the binary heap.
>
> Think real hard...

New description:

 The binary heap implementation does not scale well to multiple millions of
 objects.

 There are two different approaches that can be persued:

 Either keep one (gigantic) binary heap, but fragment the array for holding
 it, so that we don't have to realloc(3) it as one huge slab of memory.

 Or keep only the next couple of hours worth of data in the binary heap,
 and relegate objects further in the future to a (number of) somewhat
 unsorted lists, which are examined at regular intervals for objects that
 need to move into the binary heap.

 Think real hard...

-- 
Ticket URL: <http://varnish.projects.linpro.no/ticket/210#comment:1>
Varnish <http://varnish.projects.linpro.no/>
The Varnish HTTP Accelerator