Ну пишут далеко не везде, но в части добавления вы правы, сложность у put/get/remove одинаковая.
В статье же содержится ошибка, так как вставка в начало цепочки сама по себе хоть и гарантирует время O(1), но в java перед вставкой сразу проходим по всей длинне цепочки, чтобы удостовериться что такого элемента нету, в результате O(1) у нас только в идеальном случае будет когда отсутвуют коллизии.
Будет, именно проверки наличия ключа даёт проблему, что вставка никогда не будет быстрее get.
Другой вопрос что в теории длинна цепочки не может быть больше (int)(capacity * loadFactor), и для небольших мэпов это проходит. Проблемы могут случиться когда вы заполнили хеш, он разросся и это значение стало достаточно большим, потом удалили большинство и опять заполняете, может оказаться так, что все данные попадают в одну ооооочень длинную цепочку, вероятность конечно низкая, но всё может случится в этом мире.
Отдельно хотелось бы заметить нюанс, что размер таблицы для кранения цепочек всегда кратен степени двойки и при расширении удваивается, на этапе инициализации любое ваше значение округляется до ближайшей степени в большую сторону:
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity) capacity <<= 1;
Данное условие следует из оптимизации при получении текущего индекса в таблице цепочек:
static int indexFor(int h, int length) {
return h & (length-1);
}
Вот такой вот оригинальный способ получения остатка от деления =) (код эквивалентен: h % length)
да, походу поняли =)
у каждой системы своя ниша и свой случай использования, знаю случаи когда решения в пределах одной системы сосуществуют не мешая друг другу (быстрый mq на самописной ситеме поверх Hazelcast и передача/хранения собщений пользователей в системе поверх hbase).
Про что конкретно вы хотите услышать?
Ту же теракоту давно не пинал, а про hbase и её возможности могу, только хотелось бы узнать что вам интересно.
по поводу удобства когда имеется интерфейс map я с вами спорить не буду, но следом возникают вопросы:
«IMDG умеет писать в БД, файл или любое другое хранилище данных, таким образом тоже может обеспечивать долговременное хранение данных.» — насколько я помню та же теракота умеет хранить данные только в памяти, и если с ehcache ещё возможно использовать отдельно с дампом на диск, то при переводе её в кластерный вариант остаётся возможность только держать в памяти, да и чем большинство плюсов по скорости сразу пропадают когда начинается вытеснение данных на диск.
«IMDG — это скорее NoSQL + кластерный кэш + возможность обработки данных.» — что вы подразумеваете под «возможность обработки данных», большинство nosql решений имеют встроенные средства для обработки данных, в основном на парадигме MR (mongodb — внутри, hbase,cassandra — легко подключаются к hadoop).
Чтобы внести ясность: я не говорю что IMDG ненужен или ещё что-то, на нём действительно можно строить распределённый кеш для RDBMS, быстрые очереди сообщений, согласен что использовать nosql для кеширования тоже совсем правильно, НО в некоторых местах лучше бы подошла nosql база данных, вместо связки реляционной db + кластерный кеш.
p.s. с теракотой работал год назад, в данный момент активно занимаюсь hadoop/hbase, так что уж если и писать, то по ним.
1. Не совсем понял почему не подходит вариант с кешом, якобы данные там могут устареть, ведь по своей сути IMDG ничем от него не отличается, кроме того что добавился слой распределения по кластеру. К тому же даже IMDG не снимает проблему когда к db имеется несколько точек доступа, то есть не только наше приложение, но и кто-то для оптимизации полез ручками напрямую, данные в распределённый IMDG не попадут, так как о них он не узнает.
2. Сравнение с nosql считаю не совсем корректным, если уж и сравнивать, то с тем же кластером memcache.
2.1. NoSQL — это полноценные решения которые гарантируют, что если у вас во всех dc резко погас свет (а такое даже у амазона бывает), то данные не пропадут.
2.2. Имеются объёмы данных которые все в кеш запихивать нецелесообразно(есть горячие, а есть очень редко используемые, в итоге иногда и можно подождать пока они подтянуться) или невозможно (большие объёмы). А уж если действительно нужна скорость ставьте памяти побольше, в итоге что у IMDG всё будет в памяти, что у NoSQL всё в памяти и выдача моментом.
3. «NoSQL — это отдельное приложение, доступ к которому осуществляется снаружи. IMDG — это часть вашего приложения. » — различие не совсем понятно, что IMDG может работать в той же jvm, что и само приложение (лично имел опыт работы с ehcache + terracotta) ясно, но вот дальше как-то смазано. И IMDG в основе своём требует сервера для поддержания кеша в памяти, и NoSQL отдельных серверов для хранения данных, отличие сводится к разным реализациям backend для слоя данных, интерфейс у них будет одинаков get/put/delete.
4. Может я и ошибаюсь, но если у нас имеется db для хранения финансов, то использовать там прослойку в виде IMDG рискованно, только явные транзакции в db.
p.s. по поводу использовать nosql как промежуточный кеш для снижения нагрузки к db встречал только если это memcache в кластере, в противном случае полностью согласен, что распределённый кеш в памяти более предпочтителен. На практике использовал архитектуру: распределённый кеш на terracotta + вся запись в бд через очередь сообщений на изменение данных, после изменения данные сразу обновляются в кеше, но в базу попадают с задержкой.
Эх убунтоводы-убунтоводы, перед тем как писать хотя бы сорцы пошерстили =)
«Новое ядро тянет за собой поддержку нескольких старых, редко используемых функций, таких как файловую систему Reiser4,» (сходил по ссылке и сам увидел, что автор оригинальной новости этот бред написал)
4й райзер никогда не был в ядре, и в этом его тоже нету, Шишкин до сих пор его не допилил для ключения в ядро, всегда был только 3й reiserfs, причём в своё время это была революцией, так как это первая журналируемая фс под linux.
возможно ошибаюсь когда говорю что именно как кешер используют, им больше нужно было для инкрементальных счётчиков + высокая скорость доступа, а у memcache проблемы с атомарностью операций присутвуют.
По поводу базы данных: тут стоит учитывать, что это key-value база данных, поэтому выборка по ключу достаточно быстро происходит, а вот попытки писать всё в стиле реляционных бд вызывают ооочень большие тормоза.
С MongoDB сильно не сталкивался, а вот с hbase (из того же поколения nosql) приходилось, нормальные показатели если использовать нативный java протокол, да и не зря же facebook перешёл с memcache на hbase, но там согласен его дополнительно ещё интересовали моменты о скорости работы с холодным кешем + единый для всех серверов, а отнють не локальный.
основной вопрос заключается в том что:
тестирование в 1 поток не дают никакой информации по поводу того, как всё это всё поведёт себя под большой нагрузкой, не упрётесь ли вы в один момент на неприятную ситуацию когда имеется 1000 запросов на обработку, и каждому надо из кеша по 1 записи:
1. выполняем их последовательно в 1 поток, выигрывает база1, база2 сливает в 2 раза.
2. выполняем их в 10 потоков, база1 сливает в 5 раз, база2 вырывается вперёд.
Так что, как было замечено выше, вы тестировали отнють не поведение системы под нагрузкой. Да я и не могу себе представить какую можно создать нагрузку в 1 поток.
По поводу установки соединения (сам java разработчик): неужели в php нет никакого пулинга соединения, чтобы не проводить эту тяжёлую операцию для каждого запроса?
Каждый раз инициировать новый коннект и говорить про высокие нагрузки в моём понимании неуместно, даже для рест сервисов в этом случае зачастую открывается один физ коннект и в него последовательно долбятся запросы, а вы тут вообще про кешер разговор ведёте.
рассматривая hadoop мы имеем thrift интерфейс, а следовательно:
1. доступ на hdfs
2. доступ к состоянию джобов и их управление
3. доступ к hive и как следсвие sql-подобному языку для выполнения запросов на mr
А учитывая, что thrift может скомпилить схему и под php, то получаем доступ к кластеру хоть из пыха, хоть из си, хоть с питона.
Не путайте возможность подключения и отправку запросов на выполнение и сами вычисления.
не стоит думать что я имею что-то против него, но каждый следующий фреймворк кичится что я быстрее hadoop, забывая что hadoop это не только MapReduce, а целый стек технологий.
основная фишка в том, что часто используемые данные кешируются в
памяти, у хадупа как таковое главный тормоз это hdfs, в качестве постоянного хранилища у этого sparky используется… упс hdfs или s3 от amazon, в итоге стоит данным не влезть в память и сразу же мы в какашке.
В данный момент hadoop уже достаточно имеет поддержки на уровне больших кампаний, а фреймворков которые превосходят по тестам hadoop более чем достаточно.
очередной пример — piccolo.news.cs.nyu.edu/ (извиняюсь ссылку на хабр найти не могу, точно знаю что уже проскакивала она где-то здесь)
правда там таже проблема — все данные в памяти и мы рады, а вот что делать если данные в память не влазят?
Конечно можно и так, но из опыта использования наиболее просто разворачивается hadoop от cloudera под linux, достаточно прописать репозитории и пару командами у вас стоят все компоненты.
Вопросы остаются только с конфиг файлами.
С амазоном дел не имел, разворачивал внутренний сервис на hadoop.
По поводу кому нужен hadoop под win, то случаи разные бывают, да и в 0.22 патчи уже смержены, основная функциональность от cygwin это, как не смешно бы звучало: выдача свободного места на диске и сколько уже занято. Да, ява до сих пор не умеет этого, поэтому для lin используются вызовы через шел скрипты и bash (для этого если захочешь развернуть под фрёй надо ставишь на машины дополнительно баш, или патчить хадуп), а под виндой раньше был cygwin, сейчас всё это обернули внутрь jni.
но в любом случае разворачивание под linux намного проще «этого».
Переход с простоем на перезагрузку:
1. ставим PartiotionMagic и VirtualBox
2. выделяем раздел
3. привызываем раздел к виртуальному диску для vbox
4. ставим систему вплоть до иксов и делаем настройку под себя
5. перегружаемся в рабочую и почти настроенную систему
время отказа — 1 перезагрузка =)
Сам делал установку подобным образом, конечно путь не совсем тривиальный, до этого линух был не один год, но времени на настройку не было, поэтому приходилось всё делать в фоне с основными задачами. Новый ноут уже шёл с виндой, а так как по работе уже подкопились долги, то выделить время на простую установку не получалось (старый ноут сгорел, да и стояла там на тот момент федора)
Я использую СПО и в качестве помощи помогаю развивать проект.
Одно дело когда я разрабатываю на компанию и она получает неплохой доход с этого, тут работаю за ЗП. И совсем другое дело, что наработки сделанные отправляю обратно в проект, этим я не только себя избавляю от накладывания патчей с каждой новой версией, но и надеюсь, что другие поступают также, избавляя от багов на которые я ещё не наткнулся.
Оригинальный автор статьи тоже начинал путь в СПО с корыстной целью улучшить свои знания в perl, он мог бы оставить наработки у себя, но выложил в открытый доступ и избавил других людей от повторения этих же операций по портированию и отладке, НО первоначальный стимул был «надеялся, что смогу улучшить свое знание языка».
Не понимаю многих которые считают, что помощь это:
1. нужно обязятельно помогать деньгами
2. нужно сидеть и кодить, кодить, кодить просив работу, семью.
Зачем?
Если у вас есть свободная монетка, можно и скинуть автору на пиво, ведь с помощью его программы вы сэкономили себе больше времени чем вам стоит заработать эту монетку. Если же нашли багу, но что вам стоит вместо того чтобы из версии в версии ругать программу и говорить какая она бажная зайти на сайт и ОДИН раз повесить баг, и его пофиксят, или разработчик программы, или вольный программер который вообще взглянул на эту программу только для того, чтобы улучшить свои знания в этом языке программирования.
Допустим у нас активно используется hadoop, я занимаюсь разработкой под него, можно сказать зарабатываю на еду с помощью свободного ПО. В процессе разработки уже пофиксил 3 бага (тикет в их жиру + прикладывание патча, уже внедрены в ветку). hadoop не первый проект с которым приходилось работать и слать патчи.
Могли зажать эти патчи у себя, типо мы пофиксили себе, а на остальных плевать. Но ведь на том и стоит СПО, что даже если каждый поправит или хотя бы сообщит по багу, то всем будет лучше, продукт развивается, стабилизируется и возвращаются в виде более цельных и рабочих решений нам же самим.
Так что прежде чем говорить про покушать, нужно сразу осмотреться вокруг и задуматься с помощью каких инструментов это покушать зарабатывается.
size entry table: 65536
null: 65535
not null: 1
имею одну большую цепочку из 30к элементов
Вопрос: какая скорость работы получится?
p.s. да я знаю что это придуманный пример, но он наглядно илюстрирует падение якобы O(1), можете поставить 1кк и идти курить
В статье же содержится ошибка, так как вставка в начало цепочки сама по себе хоть и гарантирует время O(1), но в java перед вставкой сразу проходим по всей длинне цепочки, чтобы удостовериться что такого элемента нету, в результате O(1) у нас только в идеальном случае будет когда отсутвуют коллизии.
Другой вопрос что в теории длинна цепочки не может быть больше (int)(capacity * loadFactor), и для небольших мэпов это проходит. Проблемы могут случиться когда вы заполнили хеш, он разросся и это значение стало достаточно большим, потом удалили большинство и опять заполняете, может оказаться так, что все данные попадают в одну ооооочень длинную цепочку, вероятность конечно низкая, но всё может случится в этом мире.
Отдельно хотелось бы заметить нюанс, что размер таблицы для кранения цепочек всегда кратен степени двойки и при расширении удваивается, на этапе инициализации любое ваше значение округляется до ближайшей степени в большую сторону:
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity) capacity <<= 1;
Данное условие следует из оптимизации при получении текущего индекса в таблице цепочек:
static int indexFor(int h, int length) {
return h & (length-1);
}
Вот такой вот оригинальный способ получения остатка от деления =) (код эквивалентен: h % length)
у каждой системы своя ниша и свой случай использования, знаю случаи когда решения в пределах одной системы сосуществуют не мешая друг другу (быстрый mq на самописной ситеме поверх Hazelcast и передача/хранения собщений пользователей в системе поверх hbase).
Про что конкретно вы хотите услышать?
Ту же теракоту давно не пинал, а про hbase и её возможности могу, только хотелось бы узнать что вам интересно.
«IMDG умеет писать в БД, файл или любое другое хранилище данных, таким образом тоже может обеспечивать долговременное хранение данных.» — насколько я помню та же теракота умеет хранить данные только в памяти, и если с ehcache ещё возможно использовать отдельно с дампом на диск, то при переводе её в кластерный вариант остаётся возможность только держать в памяти, да и чем большинство плюсов по скорости сразу пропадают когда начинается вытеснение данных на диск.
«IMDG — это скорее NoSQL + кластерный кэш + возможность обработки данных.» — что вы подразумеваете под «возможность обработки данных», большинство nosql решений имеют встроенные средства для обработки данных, в основном на парадигме MR (mongodb — внутри, hbase,cassandra — легко подключаются к hadoop).
Чтобы внести ясность: я не говорю что IMDG ненужен или ещё что-то, на нём действительно можно строить распределённый кеш для RDBMS, быстрые очереди сообщений, согласен что использовать nosql для кеширования тоже совсем правильно, НО в некоторых местах лучше бы подошла nosql база данных, вместо связки реляционной db + кластерный кеш.
p.s. с теракотой работал год назад, в данный момент активно занимаюсь hadoop/hbase, так что уж если и писать, то по ним.
1. Не совсем понял почему не подходит вариант с кешом, якобы данные там могут устареть, ведь по своей сути IMDG ничем от него не отличается, кроме того что добавился слой распределения по кластеру. К тому же даже IMDG не снимает проблему когда к db имеется несколько точек доступа, то есть не только наше приложение, но и кто-то для оптимизации полез ручками напрямую, данные в распределённый IMDG не попадут, так как о них он не узнает.
2. Сравнение с nosql считаю не совсем корректным, если уж и сравнивать, то с тем же кластером memcache.
2.1. NoSQL — это полноценные решения которые гарантируют, что если у вас во всех dc резко погас свет (а такое даже у амазона бывает), то данные не пропадут.
2.2. Имеются объёмы данных которые все в кеш запихивать нецелесообразно(есть горячие, а есть очень редко используемые, в итоге иногда и можно подождать пока они подтянуться) или невозможно (большие объёмы). А уж если действительно нужна скорость ставьте памяти побольше, в итоге что у IMDG всё будет в памяти, что у NoSQL всё в памяти и выдача моментом.
3. «NoSQL — это отдельное приложение, доступ к которому осуществляется снаружи. IMDG — это часть вашего приложения. » — различие не совсем понятно, что IMDG может работать в той же jvm, что и само приложение (лично имел опыт работы с ehcache + terracotta) ясно, но вот дальше как-то смазано. И IMDG в основе своём требует сервера для поддержания кеша в памяти, и NoSQL отдельных серверов для хранения данных, отличие сводится к разным реализациям backend для слоя данных, интерфейс у них будет одинаков get/put/delete.
4. Может я и ошибаюсь, но если у нас имеется db для хранения финансов, то использовать там прослойку в виде IMDG рискованно, только явные транзакции в db.
p.s. по поводу использовать nosql как промежуточный кеш для снижения нагрузки к db встречал только если это memcache в кластере, в противном случае полностью согласен, что распределённый кеш в памяти более предпочтителен. На практике использовал архитектуру: распределённый кеш на terracotta + вся запись в бд через очередь сообщений на изменение данных, после изменения данные сразу обновляются в кеше, но в базу попадают с задержкой.
«Новое ядро тянет за собой поддержку нескольких старых, редко используемых функций, таких как файловую систему Reiser4,» (сходил по ссылке и сам увидел, что автор оригинальной новости этот бред написал)
4й райзер никогда не был в ядре, и в этом его тоже нету, Шишкин до сих пор его не допилил для ключения в ядро, всегда был только 3й reiserfs, причём в своё время это была революцией, так как это первая журналируемая фс под linux.
glennas.wordpress.com/2011/03/09/hbase-in-production-at-facebook-jonathan-gray-at-hadoop-world-2010/
возможно ошибаюсь когда говорю что именно как кешер используют, им больше нужно было для инкрементальных счётчиков + высокая скорость доступа, а у memcache проблемы с атомарностью операций присутвуют.
По поводу базы данных: тут стоит учитывать, что это key-value база данных, поэтому выборка по ключу достаточно быстро происходит, а вот попытки писать всё в стиле реляционных бд вызывают ооочень большие тормоза.
тестирование в 1 поток не дают никакой информации по поводу того, как всё это всё поведёт себя под большой нагрузкой, не упрётесь ли вы в один момент на неприятную ситуацию когда имеется 1000 запросов на обработку, и каждому надо из кеша по 1 записи:
1. выполняем их последовательно в 1 поток, выигрывает база1, база2 сливает в 2 раза.
2. выполняем их в 10 потоков, база1 сливает в 5 раз, база2 вырывается вперёд.
Так что, как было замечено выше, вы тестировали отнють не поведение системы под нагрузкой. Да я и не могу себе представить какую можно создать нагрузку в 1 поток.
По поводу установки соединения (сам java разработчик): неужели в php нет никакого пулинга соединения, чтобы не проводить эту тяжёлую операцию для каждого запроса?
Каждый раз инициировать новый коннект и говорить про высокие нагрузки в моём понимании неуместно, даже для рест сервисов в этом случае зачастую открывается один физ коннект и в него последовательно долбятся запросы, а вы тут вообще про кешер разговор ведёте.
1. hive — отправка sql запросов,
2. hdfs — выгрузка, загрузка фалов.
Если будете собираться расширять статью и описывать работу со всем стеком hadop могу помочь.
P.S. сам java разработчик, так что занимался в основном настройкой этой всей связки.
1. доступ на hdfs
2. доступ к состоянию джобов и их управление
3. доступ к hive и как следсвие sql-подобному языку для выполнения запросов на mr
А учитывая, что thrift может скомпилить схему и под php, то получаем доступ к кластеру хоть из пыха, хоть из си, хоть с питона.
Не путайте возможность подключения и отправку запросов на выполнение и сами вычисления.
памяти, у хадупа как таковое главный тормоз это hdfs, в качестве постоянного хранилища у этого sparky используется… упс hdfs или s3 от amazon, в итоге стоит данным не влезть в память и сразу же мы в какашке.
В данный момент hadoop уже достаточно имеет поддержки на уровне больших кампаний, а фреймворков которые превосходят по тестам hadoop более чем достаточно.
очередной пример — piccolo.news.cs.nyu.edu/ (извиняюсь ссылку на хабр найти не могу, точно знаю что уже проскакивала она где-то здесь)
правда там таже проблема — все данные в памяти и мы рады, а вот что делать если данные в память не влазят?
Вопросы остаются только с конфиг файлами.
С амазоном дел не имел, разворачивал внутренний сервис на hadoop.
По поводу кому нужен hadoop под win, то случаи разные бывают, да и в 0.22 патчи уже смержены, основная функциональность от cygwin это, как не смешно бы звучало: выдача свободного места на диске и сколько уже занято. Да, ява до сих пор не умеет этого, поэтому для lin используются вызовы через шел скрипты и bash (для этого если захочешь развернуть под фрёй надо ставишь на машины дополнительно баш, или патчить хадуп), а под виндой раньше был cygwin, сейчас всё это обернули внутрь jni.
но в любом случае разворачивание под linux намного проще «этого».
1. ставим PartiotionMagic и VirtualBox
2. выделяем раздел
3. привызываем раздел к виртуальному диску для vbox
4. ставим систему вплоть до иксов и делаем настройку под себя
5. перегружаемся в рабочую и почти настроенную систему
время отказа — 1 перезагрузка =)
Сам делал установку подобным образом, конечно путь не совсем тривиальный, до этого линух был не один год, но времени на настройку не было, поэтому приходилось всё делать в фоне с основными задачами. Новый ноут уже шёл с виндой, а так как по работе уже подкопились долги, то выделить время на простую установку не получалось (старый ноут сгорел, да и стояла там на тот момент федора)
Я использую СПО и в качестве помощи помогаю развивать проект.
Одно дело когда я разрабатываю на компанию и она получает неплохой доход с этого, тут работаю за ЗП. И совсем другое дело, что наработки сделанные отправляю обратно в проект, этим я не только себя избавляю от накладывания патчей с каждой новой версией, но и надеюсь, что другие поступают также, избавляя от багов на которые я ещё не наткнулся.
Оригинальный автор статьи тоже начинал путь в СПО с корыстной целью улучшить свои знания в perl, он мог бы оставить наработки у себя, но выложил в открытый доступ и избавил других людей от повторения этих же операций по портированию и отладке, НО первоначальный стимул был «надеялся, что смогу улучшить свое знание языка».
Не понимаю многих которые считают, что помощь это:
1. нужно обязятельно помогать деньгами
2. нужно сидеть и кодить, кодить, кодить просив работу, семью.
Зачем?
Если у вас есть свободная монетка, можно и скинуть автору на пиво, ведь с помощью его программы вы сэкономили себе больше времени чем вам стоит заработать эту монетку. Если же нашли багу, но что вам стоит вместо того чтобы из версии в версии ругать программу и говорить какая она бажная зайти на сайт и ОДИН раз повесить баг, и его пофиксят, или разработчик программы, или вольный программер который вообще взглянул на эту программу только для того, чтобы улучшить свои знания в этом языке программирования.
Могли зажать эти патчи у себя, типо мы пофиксили себе, а на остальных плевать. Но ведь на том и стоит СПО, что даже если каждый поправит или хотя бы сообщит по багу, то всем будет лучше, продукт развивается, стабилизируется и возвращаются в виде более цельных и рабочих решений нам же самим.
Так что прежде чем говорить про покушать, нужно сразу осмотреться вокруг и задуматься с помощью каких инструментов это покушать зарабатывается.