[REDIS] 숫자가 범위 내에 여부를 결정하는 레디 스 또는 MongoDB를?

숫자가 범위 내에 여부를 결정하는 레디 스 또는 MongoDB를?

IP 주소는 많은 금지 IP 범위의 하나에 해당하는 경우 신속하게 확인에 나는 방법이 필요합니다.

저는 현재 IP가 지정된 범위에 속하는 경우 확인의 iptables를 사용합니다. 이것은 수천 범위에 대한 벌금을 작동하지만 그 수는 수십만에 크게 증가하고, 성장을 계속에 관한 것입니다.

단순히 iptables에 새로운 규칙을 추가 내 현재의 방법으로 다른 문제는 중복의 증가이다.

나는 그것이 룰 세트에 추가되는 전에 IP 또는 범위가 기존의 (큰) 범위에 속하는 경우 확인하기위한 효율적인 방법이 필요합니다.

루비는 내가 가장 익숙한 오전 언어이지만, 어떤 데이터 구조는 범위의 적 증가를위한 최고의 선택이 될 것입니다?

내가 생각 해낸 하나 개의 솔루션은 IP가 설정에있는 경우 단순히 확인, 정수로 개별 IP를 저장하기 위해 아마도 MongoDB의를 레디 스 세트를 사용하거나하는 것입니다 ...하지만 내 직감이 나를 똑똑한 방법이 있어야한다 알려줍니다.

내가 정수로 IP를 변환하고 범위를 저장한다면, 어떤 새로운 IP 또는 범위가 이미 기존의 더 큰 범위에 포함 될 수 있는지 확인하기 위해 범위를 통해 실행할 수있는 최적의 방법이 될 것이다?

최종 주 : 속도는 메모리 비용보다 더 중요하다.

해결법

1. ==============================

   1.이전 포스터는 달리, 나는 당신이 순진 색인을 사용하여 O (로그 n)의 복잡도를 얻을 수 있다고 생각하지 않습니다. 이제 예를 들어 MongoDB를 살펴 보겠습니다. 당신은 (범위의 시작과 끝 속성)이 인덱스를 정의 할 수 있지만, MongoDB를 만 주어진 쿼리를 해결하기 위해 하나를 사용합니다. 그것은 작동하지 않습니다 그래서. 당신이 범위를 모두 시작과 끝 속성을 포함하는 단일 복합 인덱스를 사용하는 경우 이제 복잡성 확인하는 최초의 범위를 찾을 수 로그 수 있지만 다음 쿼리와 일치하는 마지막 범위를 찾기 위해 선형 얻을 것이다. 최악의 복잡도는 O (N), 모든 저장된 범위는 입력 내용을 중복 할 때 당신은 그것이있다.

   이전 포스터는 달리, 나는 당신이 순진 색인을 사용하여 O (로그 n)의 복잡도를 얻을 수 있다고 생각하지 않습니다. 이제 예를 들어 MongoDB를 살펴 보겠습니다. 당신은 (범위의 시작과 끝 속성)이 인덱스를 정의 할 수 있지만, MongoDB를 만 주어진 쿼리를 해결하기 위해 하나를 사용합니다. 그것은 작동하지 않습니다 그래서. 당신이 범위를 모두 시작과 끝 속성을 포함하는 단일 복합 인덱스를 사용하는 경우 이제 복잡성 확인하는 최초의 범위를 찾을 수 로그 수 있지만 다음 쿼리와 일치하는 마지막 범위를 찾기 위해 선형 얻을 것이다. 최악의 복잡도는 O (N), 모든 저장된 범위는 입력 내용을 중복 할 때 당신은 그것이있다.

   보조 노트에 사용 레디 스 당신이 무엇을 알고있는 경우에 당신이 (O (로그 n)의 복잡도) 정렬 된 인덱스를 에뮬레이션 할 수 있습니다 소트 세트. 레디 스 간단한 키 - 값 저장소보다 조금 더 많은 것이다. 레디 스는 세트 스킵 목록을 사용하여 구현 분류하고, 점수와 값을 모두 항목을 비교하는 데 사용됩니다.

   이러한 문제를 해결하기 위해, 전용 색인 구조가 필요하다. 당신은 좀보고 할 수 있습니다 :

   http://en.wikipedia.org/wiki/Segment_tree 또는 http://en.wikipedia.org/wiki/Interval_tree

   관심이 공간을 통해 속도 인 경우,이 인덱스를 평평하게 흥미로운 일이 될 수 있습니다. 예를 들어, (논의를 단순화하기 위해 정수만을 사용하여) 다음과 같은 범위를 살펴 보자 :

   A 2-8
   B 4-6
   C 2-9
   D 7-10
   

   비 중복 세그먼트 색인 희소 구조가 구축 될 수있다.

   0  []
   2  [A C]
   4  [A C B]
   7  [A C D]
   9  [C D]
   10 [D]
   11 []
   

   각 항목은 낮은 값으로 키와 매칭리스트 또는 범위 세트로 세그먼트 겹치는 비 구속 포함한다. 항목이 정렬 된 용기 사용하여 색인한다 (목록, BTREE, 건너 뛰기, 나무 등)

   5와 일치하는 범위를 발견하기 위해, 우리는 5보다 낮거나 동일한 제 항목 (이 예에서 4 것) 및 광범위의 목록을 찾아 제공된다 ([A B C])

   이 데이터 구조로, 질의의 복잡성이 O (로그 N) 정말. 그러나 구축하고 유지하는 사소한 (비싼) 없습니다. 그것은 모두 MongoDB를하고 레디 스로 구현 될 수있다.

   여기 레디 스와 예이다 :

   > rpush range:2 2-8 2-9
   (integer) 2
   > rpush range:4 2-8 2-9 4-6
   (integer) 3
   > rpush range:7 2-8 2-9 7-10
   (integer) 3
   > rpush range:9 2-9 7-10
   (integer) 2
   > rpush range:10 7-10
   (integer) 1
   > zadd range_index 0 range:0 2 range:2 4 range:4 7 range:7 9 range:9 10 range:10
   (integer) 6
   > zrevrangebyscore range_index 5 0 LIMIT 0 1
   1) "range:4"
   > lrange range:4 0 -1
   1) "2-8"
   2) "2-9"
   3) "4-6"
   

2. ==============================

   2.당신이 범위를 처리하는 경우, MongoDB를 그에 대한 레디 스보다 더 나은 될 것입니다. 특정 IP 주소를 처리하는 경우, 레디 스 최선의 선택이 될 것입니다.

   당신이 범위를 처리하는 경우, MongoDB를 그에 대한 레디 스보다 더 나은 될 것입니다. 특정 IP 주소를 처리하는 경우, 레디 스 최선의 선택이 될 것입니다.

   왜?

   MongoDB를 사용하면 O (로그 n)이 단순히 키 값 저장소입니다 레디 스 반면에 시간을 조회 할 수있는 IP 주소의 시작과 끝 범위에 인덱스를 구축 할 수 있습니다.

   당신은 당신에 대해 확인하고 싶어하는 모든 단일 IP가 해시 테이블에 있던 경우 레디 스 해시를 사용하고 O (1) 시간을 그들을 보이지만 당신이 범위를 사용하고 있기 때문에 나는 몽고는 가장 좋은 건 말할 것입니다 수 있습니다. 난 당신이 레디 스 툴킷의 데이터 구조의보다 나은 로그 N 시간보다 얻을려고 생각하지 않습니다. O 어쩌면하지만 O (로그 n)이 소트 세트 또는 목록 (N).

3. ==============================

   3.오늘 우리는 레디 스에서 블룸 필터를 사용할 수 있습니다.

   오늘 우리는 레디 스에서 블룸 필터를 사용할 수 있습니다.

from https://stackoverflow.com/questions/8622816/redis-or-mongo-for-determining-if-a-number-falls-within-ranges by cc-by-sa and MIT license