Jun. 24th, 2017

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

Году в 2004-2005 я работал в Амазоне, и унаследовал код, передающий данные о предложениях товаров для создания страницы с этими предложениями (например). Данные о предложении состояли из идентификатора, состояния (новое, б/у, коллекционное, отремонтированное); регулярной цены; цены на распродаже и сроков распродажи, если таковые были; доступности; наценок и увеличения сроков доставки на Гавайи, Пуэрто-Рико и т. п.; и т. д. Эти данные поступали из трех источников: склады самого Амазона; большие поставщики, которые регулярно посылали нам информацию о своем инвентаре; и мелкие продавцы, которые продавали свои книжки и т. п. на сайте Амазона. Данные из разных источников хранилась в разных независимо разработанных системах, основанных на разных технологиях; данные от мелких продавцов - в объектно-ориентированной базе данных.

Код, который я унаследовал, брал списки предложений, отсортированные по цене в порядке возрастания, и сливал их в один список (для первой страницы со списком - первые 25 предложений, для второй - брал первые 50 и отбрасывал первые 25, и т. д.; каждый из исходных списков был того же размера, что и результат). Предложение было классом в C++, а список был дважды связанным списком (std::list) умных указателей на этот класс, но не STL-овских, которых тогда еще не было, а внутренних амазоновских, написанных одним разработчиком, нынче главным архитектором одной известной компании; алгоритм слияния был реализован вручную.

Я подумал: зачем нужна эта ручная реализация алгоритма слияния, если можно класть списки предложений в std::vector, вызывать функцию std::inplace_merge, и после каждого слияния отбрасывать все элементы после первых 25 (50 и т. д.)? Однако, как оказалось, в умном указателе есть баг: если его присвоить самому себе, то он обнуляется, а STL-овская реализация алгоритма слияния иногда присваивает разыменованные итераторы самим себе. Я дал знать об этом баге автору указателя, но библиотека с умным указателем была настолько корневая, что исправить его означало перекомпилировать значительную часть всего амазоновского кода, что занимало чуть ли не сутки, и вызывало множество случайных ошибок. Поэтому баг остался неисправленным. Слияние же я реализовал, используя кучу: создать вектор, пройтись по всем предложениям из всех источников, и класть их в этот вектор, используя функцию std::push_heap, и если размер вектора превышает 25 (50 и т. д.), удалить из вектора максимальный элемент, используя функцию std::pop_heap. В конце вектор будет состоять из самое большее 25 (50 и т. д.) минимальных предложений из всех источников в кучевом порядке; их можно вынуть оттуда от самого большого до самого маленького, используя функцию std::pop_heap, и положить в вектор результата в обратном порядке.

Проблема заключалась в том, что как старый, вручную реализованный код, так и функция std::inplace_merge устойчивые, а мой алгоритм - нет. Если все предложения поступали из одного источника - объектно-ориентированной базы данных с предложениями от мелких продавцов с одной и той же ценой, то старый код сохранял их порядок, а новый - перетасовывал.

Если покупатель видит список предложений с одной и той же ценой на веб-странице, то в подавляющем большинстве случаев он покупает первое предложение из списка. Код, обновлявший объектно-ориентированную базу данных, держал список предложений отсортированным по цене в порядке возрастания. Если же у двух предложений была одинаковая цена, то этот код ставил последнее обновленное предложение первым в список, и до того, как я унаследовал код слияния, оно продолжало стоять первым после слияния с другими источниками данных. Поэтому продавцы бомбардировали амазоновские сервера пустыми обновлениями, чтобы их предложения стояли первыми в списке. Особенно это было заметно в Германии, где по закону новые книги нельзя продавать дешевле цены на обложке (например); из-за пустых обновлений европейские серверы Амазона были перегружены. Мое изменение это сломало; теперь последнее обновленное предложение вставало посреди списка.

Весной 2005 года прошла Amazon Seller Conference, на которой послышались жалобы от продавцов: мы уволили четверых человек (кажется; я эти цифры помню очень смутно); мы уволили двоих человек. Отдел Амазона в Германии написал, что два продавца объявили банкротство. Все эти люди построили свою бизнес-модель на баге в коде Амазона, и исправление этого бага ее сломало.

Но это еще не конец истории. Через несколько месяцев один продавец написал Джеффу Безосу: почему мое предложение для такого-то товара стоит на втором месте уже четыре месяца? От Безоса это письмо спустилось по корпоративной иерархии ко мне, но вместо того, чтобы случайным образом перетасовывать предложения с одинаковой ценой, я добавил вторичный ключ для сравнения: хэшированный идентификатор, интерпретированный как 64разрядное целое число, умноженный на юниксовское время в часах, по модулю большого простого числа. Теперь предложения с одинаковой ценой перетасовывались каждый час. Перетасовка хорошо работала по той же причине, по какой если у планеты есть несколько спутников, обращающихся в плоскости эклиптики, периоды обращения которых соотносятся, как иррациональные числа, то вероятность того, что в определенный момент у данного спутника будет минимальная эклиптическая долгота, вторая по величине, третья по величине и т. д. одинакова, и равняется единице, деленной на число спутников. Я тогда читал книжку про статистическую механику, узнал о существовании эргодической теоремы, и вывел из нее этот факт в пределе, когда и размер хэшированного идентификатора в битах, и большое простое число стремятся к бесконечности (подробностей я теперь уже не помню).

Если у меня будут внуки, и они будут уметь программировать, то я им буду рассказывать эту историю.

Profile

ygam: (Default)
Илья

August 2017

S M T W T F S
  12345
6 789 101112
13 141516171819
20212223242526
2728293031  

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 18th, 2017 04:54 am
Powered by Dreamwidth Studios