Скорость поиска: состояние или база данных?

Question

У меня есть куча списков слов на моем сервере, и я планировал создать простой API JSON с открытым исходным кодом, который возвращает, если пароль находится в списке , как метод проверки. Я делаю это в Python с Flask и буквально просто возвращаюсь, если присутствует вход.

Одна небольшая проблема: список слов составляет около 150 миллионов записей и 1,1 ГБ текста.

Мой API (минимальный) находится ниже. Является ли более эффективным хранить каждую строку в MongoDB и многократно искать или хранить всю вещь в памяти с помощью синглета, и заполнять ее при запуске, когда я вызываю app.run? Или различия являются субъективными?
Кроме того, это даже хорошая практика, чтобы сделать последнее? Я думаю, что поиски могут начать обходить налогом, если я открою это для публики. Я также предложил кому-то предложить Trie для эффективного поиска.

Обновление: Я проделал немного тестирования, и поиск документов очень медленный с таким большим количеством записей. Можно ли использовать базу данных с надлежащими индексами для одного столбца данных, который необходимо эффективно искать?

from flask import Flask 
from flask.views import MethodView 
from flask.ext.pymongo import PyMongo 
import json 

app = Flask(__name__) 
mongo = PyMongo(app) 

class HashCheck(MethodView): 

    def post(self): 
    return json.dumps({'result' : 
     not mongo.db.passwords.find({'pass' : request.form["password"])}) 
    # Error-handling + test cases to come. Negate is for bool. 

    def get(self): 
    return redirect('/') 

if __name__ == "__main__": 
    app.add_url_rule('/api/', view_func=HashCheck.as_view('api')) 
    app.run(host="0.0.0.0", debug=True) 

_{1: Я - гайка безопасности. Я использую его в своих регистрационных формах и отклоняю общий ввод. Одним из списков слов является UNIQPASS.}

Answer 1

Что я хотел бы предложить, это гибридный подход. По мере выполнения запросов выполняются две проверки. Первый в локальном кеше и второй в магазине MongoDB. Если первый сбой, но второй успешно завершен, добавьте его в кеш памяти. Со временем приложение будет «виновато» в наиболее распространенных «плохих паролях»/записях.

Это имеет два преимущества:
1) Общие слова отбрасываются очень быстро изнутри памяти.
2) Стоимость запуска близка к нулю и амортизирована по многим запросам.

При хранении списка слов в MongoDB я бы сделал поле _id удержанием каждого слова. По умолчанию вы получите ObjectId, который является полным отходом в этом случае. Затем мы также можем использовать автоматический индекс на _id. Я подозреваю, что плохая производительность, которую вы видели, была связана с тем, что в поле «pass» не было указателя.Вы также можете попробовать добавить один на поле 'проход' с:

mongo.db.passwords.create_index("pass") 

Для завершения сценария _id: вставить слово:

mongo.db.passwords.insert({ "_id" : "password" }); 

Запросы затем выглядеть:

mongo.db.passwords.find({ "_id" : request.form["password"] }) 

Как упоминалось в @Madarco, вы также можете сбрить другой бит времени запроса, гарантируя, что результаты возвращаются из индекса путем ограничения возвращаемых полей только в поле _id ({ "_id" : 1}).

mongo.db.passwords.find({ "_id" : request.form["password"] }, { "_id" : 1}) 

НТН - Роб

P.S. Я не эксперт Python/Pymongo, поэтому может не иметь правильного синтаксиса на 100%. Надеюсь, это по-прежнему полезно.

Answer 2

Учитывая, что ваш список полностью статичен и помещается в память, я не вижу убедительной причины использовать базу данных.

Я согласен с тем, что Trie будет эффективен для вашей цели. Также будет работать хэш-таблица.

PS: Слишком плохо о глобальном блокировщике Python. Если вы использовали язык с реальной многопотоковой обработкой, вы можете воспользоваться неизменной структурой данных и запустить сервер через несколько ядер с разделяемой памятью.

Answer 3

Я бы предложил проверить и попробовать redis как вариант. Быстро, очень быстро и имеет хорошие привязки python. Я попытался бы создать набор в redis списка слов, а затем использовать функцию SISMEMBER, чтобы проверить, находится ли слово в наборе. SISMEMBER - операция O (1), поэтому она должна быть быстрее, чем запрос mongo.

Thats предполагается, что вы хотите, чтобы весь список в памяти, конечно, и что вы готовы покончить с монго. , ,

Вот больше информации о Redis-х SISMEMBER, и в python bindings для Redis

Answer 4

Я бы рекомендовал kyotocabinet, это очень быстро. Я использовал его в аналогичных обстоятельствах:

import kyotocabinet as kyc 

from flask import Flask 
from flask.views import MethodView 
import json 

app = Flask(__name__) 


dbTree = kyc.DB() 

if not dbTree.open('./passwords.kct', DB.OREADER): 
    print >>sys.stderr, "open error: " + str(dbTree.error()) 
    raise SystemExit 


app = Flask(__name__) 


class HashCheck(MethodView): 

    def post(self): 
    return json.dumps({'result' : 
     dbTree.check(request.form["password"]) > 0 }) 
    # Error-handling + test cases to come. Negate is for bool. 

    def get(self): 
    return redirect('/') 

if __name__ == "__main__": 
    app.add_url_rule('/api/', view_func=HashCheck.as_view('api')) 
    app.run(host="0.0.0.0", debug=True)