django/django — pull request #3008 by dw (2014-08-02 17:54:24+00:00)
Title: Improve file upload performance when many duplicate names exist.

Storage.get_available_name() previously handled naming conflicts by
exhaustively testing each possible alternative, starting at zero until a
free name was found.

In some scenarios this would lead to pathological performance due to
stat()ing a huge number of existent files, potentially causing I/O and
reducing cache effectiveness by warming the metadata of previously cold
files.

This patch preserves the existing naming scheme (incrementing integers),
but introduces a binary search to find the first free name. Given a
filename that is duplicated 10,000 times, the number of stat() calls
required to find the first free name drops from 10,000 to just 24.

['highest', None, 'got', 0, 'num stats', 1]
['highest', 0, 'got', 1, 'num stats', 6]
['highest', 1, 'got', 2, 'num stats', 6]
['highest', 2, 'got', 3, 'num stats', 6]
['highest', 3, 'got', 4, 'num stats', 6]
['highest', 4, 'got', 5, 'num stats', 6]
['highest', 5, 'got', 6, 'num stats', 6]
['highest', 6, 'got', 7, 'num stats', 6]
['highest', 7, 'got', 8, 'num stats', 6]
['highest', 8, 'got', 9, 'num stats', 6]
['highest', 9, 'got', 10, 'num stats', 6]
['highest', 10, 'got', 11, 'num stats', 7]
['highest', 100, 'got', 101, 'num stats', 12]
['highest', 1000, 'got', 1001, 'num stats', 18]
['highest', 10000, 'got', 10001, 'num stats', 24]
['highest', 100000, 'got', 100001, 'num stats', 32]
['highest', 1000000, 'got', 1000001, 'num stats', 38]
['highest', 10000000, 'got', 10000001, 'num stats', 44]

By default Django should ideally use some randomized naming scheme,
although this might be a surprising change for existing installations
(especially since e.g. intuitive directory sorting is broken).

Time-based names are another option, but are likely to break for high
traffic / multi-server installations.