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

Varnish varnish-bugs at projects.linpro.no
Thu Feb 5 12:02:45 CET 2009

#210: The binary heap implementation does not scale
 Reporter:  phk          |        Owner:  phk   
     Type:  enhancement  |       Status:  closed
 Priority:  lowest       |    Milestone:  Later 
Component:  varnishd     |      Version:  trunk 
 Severity:  normal       |   Resolution:  fixed 
 Keywords:               |  
Comment (by tfheen):

 (In [3606]) Merge r3390: Rework the binary heap we use for expiry

 Rework the binary heap, we use for expiry processing, to deal more
 gracefully with large number of objects.

 Previously we kept all objects in a single array which resultined
 in increasingly infrequent but increasingly demanding calls to
 calloc(3) with the consequent massive memory copies.  We also did
 not release memory again if unused.

 Now we stripe the array into rows of 64k objects each.

 This number is a compromise between space wastage, max 1MB on a
 64bit machine, and the desire to not add and delete rows all the
 time.  With 64k objects in a row, even on a very busy server would
 only add a new row every 5...10 seconds during ramp up.

 Delete unused rows, but keep a hysteresis of an entire empty row
 to avoid silly add-delete-add-delete-add-delete behaviour at row

 Streamline some of the functions a bit.

 Fixes #210

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

More information about the varnish-bugs mailing list