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

Году в 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разрядное целое число, умноженный на юниксовское время в часах, по модулю большого простого числа. Теперь предложения с одинаковой ценой перетасовывались каждый час. Перетасовка хорошо работала по той же причине, по какой если у планеты есть несколько спутников, обращающихся в плоскости эклиптики, периоды обращения которых соотносятся, как иррациональные числа, то вероятность того, что в определенный момент у данного спутника будет минимальная эклиптическая долгота, вторая по величине, третья по величине и т. д. одинакова, и равняется единице, деленной на число спутников. Я тогда читал книжку про статистическую механику, узнал о существовании эргодической теоремы, и вывел из нее этот факт в пределе, когда и размер хэшированного идентификатора в битах, и большое простое число стремятся к бесконечности (подробностей я теперь уже не помню).

Если у меня будут внуки, и они будут уметь программировать, то я им буду рассказывать эту историю.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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:59 am
Powered by Dreamwidth Studios