Столкновение хеш-таблицы в наборе Python?

Как можно иметь в наборе Python 2 одинаковых элемента? Это ошибка Python?

type(data_chunks)
<class 'set'>

len(data_chunks)
43130

same = [x for x in data_chunks if x.md5==chunk.md5]
[<Model.Chunk.Chunk o...x0DB40870>, <Model.Chunk.Chunk o...x0DB40870>]

len(same)
2

same[0] is same[1]
True

same[0] == same[1]
True

len(set(same))
1

Но когда я строю из него словарь, дублирование удаляется!

len({k:k.product_id for k in data_chunks})
43129

Почему это работает для словаря, а не для набора? Я думал, что это была коллизия в хеш-таблице, но на самом деле дублированный объект - это тот же объект, поэтому он не был найден в поиске набора, когда был добавлен следующий элемент (?)

Дополнительная информация:

  • Chunk определил методы __hash__ и __eq__
  • Python 3.7.2
  • Я понял, что у Chunk есть некоторые свойства, которые вызывают ошибку - это не должно быть важно, поскольку они не вызываются
  • текущая строка кода: data_chunks = data_chunks | another_set
  • интерактивная подсказка во время сеанса отладки в vscode
  • при запуске кода это случается иногда
  • но во время этого сеанса отладки создание новых наборов из data_chunks всегда имеет одинаковую длину

РЕДАКТИРОВАТЬ

Реализация чанка

class Chunk(object):
    def __init__(self,
                 md5,
                 size=None,
                 compressedMd5=None,
                 # ... (more elements)
                 product_id=None):
       self.md5 = md5
       self.product_id = product_id
       # (etc.)

    def __eq__(self, other):
        if self.compressedMd5:
            return self.compressedMd5 == other.compressedMd5 and self.product_id == other.product_id
        return self.md5 == other.md5 and self.product_id == other.product_id

    def __hash__(self):
        return self.name.__hash__()

    @property
    def name(self):
        return self.compressedMd5 if self.compressedMd5 is not None else self.md5

==================

ИЗМЕНИТЬ Хорошо, поэтому код выглядит следующим образом:

repository - дескриптор json

chunking_strategy = ... - в основном класс, который хранит настройки, например, что блоки будут сжиматься.

result_handler = Strategy.DefaultResultHandler(repository) Создает уникальные хэши объектов чанков в репозитории: чанков и сопоставление соответствующих файлов. Позже он вызовет задания сжатия, а затем установит compressedMd5 и другие свойства существующих фрагментов.

generation_strategy = Strategy.CachingGenerationStrategy(
            result_handler,
            Settings().extra_io_threads,
        )

data_chunks = Strategy.DepotChunker(repository, chunking_strategy, generation_strategy)()

при инициализации DeputChunker: задания на фрагменты задач подготавливаются на основе настроек chunking_strategy. Затем generation_strategy.__call__ метод обрабатывает все задания: файлы, которые нужно разделить на небольшие части на основе ранее определенных объектов Chunk. Это сделано в multiprocessing.Pool. После создания физических блоков они проверяют md5, и объект Chunk обновляется на compressedMd5, compressedSize и product_id. Затем (сразу после изменения объекта Chunk) в набор добавляются объекты chunk. Этот набор возвращен из DepotChunker

Затем сжатые фрагменты сохраняются в кеше.


Затем все data_chunks - это поиск небольших объектов с небольшим размером, из которых создаются физические фрагменты (в буфере памяти), состоящие из объединенных небольших файлов. Назовем их smallFilesChunks. Они добавлены к data_chunks:

     sfChunk = Chunk(
                sfCompressedContentMD5,  # yes I see that this is compressed md5 - it was intended for some reason I don't know
                size=sfSize,
                compressedMd5=sfCompressedContentMD5,
                compressedSize=sfCompressedSize,
                product_id=productId
            )
        if not sfChunk in data_chunks:  # purly sanity check
            data_chunks.add(sfcChunk)

В конце создаются мета-файлы, которые также разбиваются на части и добавляются в data_chunks

Тогда мета-файлы - это дампы, и они тоже разбиты на части.

for depot in manifest_depots:
        data_chunks = data_chunks | simpleChunker(depot)

В этот момент сеанс отладчика с самого начала был записан


person Mesco    schedule 23.07.2019    source источник
comment
Вероятно, необходимо также увидеть реализацию Chunk, чтобы выявить какие-либо проблемы с хешированием.   -  person Rach Sharp    schedule 23.07.2019
comment
Да, давайте посмотрим на хеш-функцию и методы сравнения.   -  person NPE    schedule 23.07.2019
comment
Кроме того, Chunk изменчив?   -  person NPE    schedule 23.07.2019
comment
@Mesco, пожалуйста, отредактируйте свое сообщение, включив в него правильный минимально воспроизводимый пример (stackoverflow.com/help/minimal-reproducible-example)   -  person bruno desthuilliers    schedule 23.07.2019
comment
Кажется, что __hash__ использует метод __hash__ на compressedMd5 или md5 - они реализуют __hash__ одинаково? Вы составляете список same на основе равенства только атрибута md5, тогда как __hash__ is и __eq__ также проверяют другие атрибуты.   -  person Jeff    schedule 23.07.2019
comment
md5 - это строка. CompressedMd5 не является обязательным [str, None]   -  person Mesco    schedule 23.07.2019
comment
@brunodesthuilliers Я хочу это сделать ... Я пытаюсь исправить странные ошибки в нашем приложении, которые возникают иногда даже на том же компьютере, всего лишь с одной попытки   -  person Mesco    schedule 23.07.2019
comment
@Chris_Rands см. Результаты: len (data_chunks) и len ({k: k.product_id for k in data_chunks})   -  person Mesco    schedule 23.07.2019


Ответы (2)


Одна проблема заключается в том, что __eq__ не коммутативен для пар объектов, у одного из которых есть compressedMd5, а у другого нет (т.е. его compressedMd5 установлен в None). Это означает, что можно построить два объекта a и b так, чтобы a == b и одновременно b != a.

Связанная проблема заключается в том, что __eq__ и __hash__ несовместимы друг с другом в схожих обстоятельствах (__eq__ отказался бы смотреть на other.compressedMd5, если self.compressedMd5 равно None.)

Изменчивость также может быть проблемой, как показано в следующем примере:

class Chunk(object):
  def __init__(self, md5):
    self.md5 = md5

  def __hash__(self):
    return hash(self.md5)

s = set()
chunk = Chunk('42')
s.add(chunk)
chunk.md5 = '123'
s.add(chunk)
print(s)

На моем компьютере это дает set([<__main__.Chunk object at 0x106d03390>, <__main__.Chunk object at 0x106d03390>]), т.е. один и тот же объект появляется в наборе дважды.

Нечто подобное может произойти в вашем коде, если вы измените md5 или установите / отключите / измените compressedMd5.

person NPE    schedule 23.07.2019
comment
Спасибо, я вижу проблему. Но в настоящее время len([x for x in data_chunks if x.compressedMd5 is None]) == 0 и фактически - same массивы состоят из двух одинаковых элементов object at 0x0DB40870 - person Mesco; 23.07.2019
comment
@Mesco: Chunk объекты изменяемы? - person NPE; 23.07.2019
comment
Я понимаю разницу - нет, ее нет. Но похоже, что кроме времени создания ничего не изменилось. - person Mesco; 23.07.2019
comment
Фактически, md5 и compressedMd5 - это свойства, а фактические значения классов - дураки (я упростил код вставки) - person Mesco; 23.07.2019
comment
@Mesco: Очень сложно отладить такую ​​тонкую проблему с помощью прокси / догадок. :( - person NPE; 23.07.2019
comment
Какие операции вы выполняли с фрагментом между его первым и повторным добавлением? Похоже, что некоторые операции могут изменить хеш, скорее всего, в этом проблема. - person Hans-Martin Mosner; 23.07.2019
comment
Но разве мы тогда не ожидали бы len(set(same)) - ›2? Также AFAIK set и dict используют хеш-таблицу для создания ключей, поэтому я не уверен, почему у set(data_chunks) есть дубли, а у {k:k.product_id for k in data_chunks} нет. Если бы мне пришлось угадывать, я бы сказал, что согласен с NPE, что __eq__ и __hash__ не выполняют здесь одинаковых сравнений, но это вообще странно. Мы кое-что не знаем об операциях на Chunks здесь. - person Jeff; 23.07.2019
comment
Я установил отладчик в каждом сеттере чанков. Я обновлю вопрос для более подробной информации. @ Hans-MartinMosner выглядит так, будто готовит больше кусков из кеша, а затем добавляет их к основному набору кусков. Но проверим глубже (это займет некоторое время, так как в этом случае один сеанс фрагментации длится около 1 часа) - person Mesco; 23.07.2019
comment
@Jeff именно так! Я знаю, что проблемы с изменчивостью имеют значение ... но как это можно сделать в точке останова, когда все, скажем, заморожено? Это 1) set(same) не имеет дубликатов, но set(data_chunks) имеет 2) dict build из data_chunks меньше - person Mesco; 23.07.2019
comment
@Mesco: Для меня эти симптомы сильно намекают на изменчивость Chunk (в частности, на то, что хеш чанка изменяется в течение его жизни). - person NPE; 23.07.2019
comment
@Mesco: Пока мы изучаем различные способы, по которым что-то может пойти не так, есть ли параллелизм в какой-либо части этого кода? - person NPE; 23.07.2019
comment
@NPE Есть больше потоков, используемых для генерации чанков, а затем загрузки на сервер. После того, как чанки физически сгенерированы на основе объектов чанка, они сжимаются. Затем объекты Chunks обновляются с помощью compressMd5. Затем блоки добавляются в data_chunks набор. (подробности см. в моем обновлении) - person Mesco; 23.07.2019

Хорошо, я понимаю, что такое поведение трудно воспроизвести надежно, поэтому все, что мы можем предложить с банкоматом, - это предложения о том, что может вызвать такие проблемы ...

В дополнение к тому, что уже упоминал NPE, у вас действительно есть потенциальная проблема с изменяемым Chunk: атрибуты md5 и compressedMd5 могут быть изменены в любое время, поэтому результат hash(chunk) не гарантированно будет стабильным. Вы можете проверить свою кодовую базу на предмет возможных гремлинов здесь. Если вы обнаружите, что какой-либо код обновляет один из этих атрибутов после добавления chunk в набор, то, вероятно, виноват в этом. FWIW помните, что Python никогда ничего не копирует косвенно, поэтому что-то вроде этого:

chunks = set()

def make_chunk(md5, ...)
   c = Chunk(md5, ...)
   chunks.add(c)
   return c

def do_something_bad(chunk):
    chunk.md5 = something_else

def main():
   c = make_chunk()
   # ... lots of code here
   do_something_bad(c)

БУДУТ отражать изменение в chunks и все испортить (примечание: да, вы, вероятно, уже знаете это, но это очень распространенная ошибка для людей, переходящих из более распространенных языков)

NB: это проблема, конечно, только в том случае, если что-то меняет один из этих атрибутов, но сделать их доступными только для чтения все равно будет безопаснее (ну, по крайней мере, согласно определениям Python для «только для чтения» и «безопасный», то есть xD).

person bruno desthuilliers    schedule 23.07.2019