Tuesday, January 22, 2013

NetflixGraph Memory Optimization

Drew Koszewnik:

The relationships between objects in our directed graph were generally represented with HashMaps, where HashSets of “to” objects were keyed by “from” objects.

This was a lot of objects and a lot of 64-bit pointers. In the new design:

Our data structure maintains two arrays. One is an integer array, and the other is a byte array. Each object’s connections are encoded into the byte array as delta-encoded variable-byte integers (more on this in the next paragraph). The integer array contains offsets into the byte array, such that the connections for the object represented by some ordinal are encoded starting at the byte indicated by offsetArray[ordinal].

This reduced the memory footprint by 90%.

Comments RSS · Twitter

Leave a Comment