์๊ฐ
โ๋น์ ์ ๊ทธ ์๋ฆฌ์ ๋จธ๋ฌผ๊ธฐ ์ํด ๊ฐ๋ฅํ ํ ๋นจ๋ฆฌ ๋ฌ๋ ค์ผ ํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ ์ด๋๊ฐ์ ๋์ฐฉํ๋ ค๋ฉด ์ ์ด๋ ๋ ๋ฐฐ๋ ๋นจ๋ฆฌ ๋ฌ๋ ค์ผ ํด์!"
(c) ์ด์ํ ๋๋ผ์ ์จ๋ฆฌ์ค
์ผ๋ง ์ ๊ฐ์๋ฅผ ํด๋ฌ๋ผ๋ ์์ฒญ์ ๋ฐ์์ต๋๋ค. ๋ถ์๊ฐ๋ค ์ ํฌ ํ์ฌ์์๋ ๋ฐ์ดํฐ ๋ชจ๋ธ ์ค๊ณ๋ผ๋ ์ฃผ์ ์ ๋ํด ์ด์ผ๊ธฐํ์ต๋๋ค. ์ค๋ ์๊ฐ (๋๋ก๋ ๋ช ๋ ์ฉ) ํ๋ก์ ํธ์ ๋ชฐ๋ํ๋ค ๋ณด๋ฉด IT ๊ธฐ์ ์ธ๊ณ์์ ์ด๋ค ์ผ์ด ๋ฒ์ด์ง๊ณ ์๋์ง ์ ๋๋ก ํ์ ํ์ง ๋ชปํ๊ธฐ ๋๋ฌธ์ ๋๋ค. ์ ํฌ ํ์ฌ์์๋ (๋ง์นจ๋ด ๊ทธ๋ ๊ฒ ๋์๋ค์) ๋ง์ ํ๋ก์ ํธ์์ NoSQL ๋ฐ์ดํฐ๋ฒ ์ด์ค๋ฅผ ์ฌ์ฉํ์ง ์์ต๋๋ค (์ ์ด๋ ์์ง์). ๊ทธ๋์ ์ ๋ ๊ฐ์์์ HBase๋ฅผ ์๋ก ๋ค์ด NoSQL ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ํนํ ์ง์คํ๊ณ , NoSQL์ ์ฌ์ฉํด ๋ณธ ์ ์ด ์๋ ๋ถ๋ค์ ์ํด ๊ฐ์ ๋ด์ฉ์ ์ง์ค์ ์ผ๋ก ์ ๋ฌํ๋ ค๊ณ ๋ ธ๋ ฅํ์ต๋๋ค. ํนํ ๋ช ๋ ์ ์ ์ฝ์๋ ์ฌ๋ก๋ฅผ ํ์ฉํ์ฌ ๋ฐ์ดํฐ ๋ชจ๋ธ ์ค๊ณ์ ๋ช ๊ฐ์ง ํน์ง์ ์ค๋ช ํ์ต๋๋ค. ์๋ฅผ ๋ถ์ํ ๋, ์ ๋ ๊ฐ์ ๋ฌธ์ ์ ๋ํ ์ฌ๋ฌ ๊ฐ์ง ํด๊ฒฐ์ฑ ์ ๋น๊ตํ์ฌ ์ฒญ์ค์๊ฒ ์ฃผ์ ์์ด๋์ด๋ฅผ ๋ ์ ์ ๋ฌํ๊ณ ์ ํ์ต๋๋ค.
์ต๊ทผ "์ง๋ฃจํด์" (5์์ ๊ธด ๊ฒฉ๋ฆฌ ๊ธฐ๊ฐ์ด ํนํ๋ ์ด๋ฐ ์ํฉ์ ๋์์ด ๋ฉ๋๋ค) ์ค์ค๋ก์๊ฒ ๋ฌผ์์ต๋๋ค. ์ด๋ก ์ ๊ณ์ฐ์ด ์ค์ ์ํฉ์ ์ผ๋ง๋ ๋ถํฉํ ์ ์์๊น์? ์ฌ์ค, ์ด ๊ธ์ ์์ด๋์ด๋ ๋ฐ๋ก ์ด๋ ๊ฒ ํ์ํ์ต๋๋ค. ์ค๋ซ๋์ NoSQL์ ์ฌ์ฉํด ์จ ๊ฐ๋ฐ์๋ผ๋ฉด NoSQL์์ ์๋ก์ด ๊ฒ์ ๋ฐฐ์ฐ์ง ๋ชปํ ์๋ ์์ต๋๋ค(๋ฐ๋ผ์ ๊ธ์ ์ ๋ฐ์ ๋ฐ๋ก ๊ฑด๋๋ธ ์๋ ์์ต๋๋ค). ํ์ง๋ง ๋ถ์๊ฐ์์ง NoSQL์ ๊ธด๋ฐํ๊ฒ ๋ค๋ฃจ์ด ๋ณธ ์ ์ด ์๋ ์ฌ๋๋ค์๊ฒ๋ HBase๋ฅผ ์ํ ๋ฐ์ดํฐ ๋ชจ๋ธ์ ์ค๊ณํ๋ ๋ฐ ํ์ํ ๊ธฐ๋ณธ์ ์ธ ์ฌํญ์ ์ดํดํ๋ ๋ฐ ์ ์ฉํ ๊ฒ์ด๋ผ๊ณ ์๊ฐํฉ๋๋ค.
์์ ๋ถ์
์ ์๊ฐ์๋ NoSQL ๋ฐ์ดํฐ๋ฒ ์ด์ค๋ฅผ ์ฌ์ฉํ๊ธฐ ์ ์ ์ฅ๋จ์ ์ ์ ์คํ๊ฒ ๊ณ ๋ คํด์ผ ํฉ๋๋ค. ๋๋ถ๋ถ์ ๊ฒฝ์ฐ ๊ธฐ์กด ๊ด๊ณํ DBMS๋ฅผ ์ฌ์ฉํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ํน๋ณํ ์ด์ ๊ฐ ์๋ค๋ฉด NoSQL์ ์ฌ์ฉํ์ง ์๋ ๊ฒ์ด ์ข์ต๋๋ค. ๊ทธ๋๋ NoSQL ๋ฐ์ดํฐ๋ฒ ์ด์ค๋ฅผ ์ฌ์ฉํ๊ธฐ๋ก ๊ฒฐ์ ํ๋ค๋ฉด, NoSQL์ ์ค๊ณ ๋ฐฉ์์ด ๋ค์ ๋ค๋ฅด๋ค๋ ์ ์ ๊ณ ๋ คํด์ผ ํฉ๋๋ค. ํนํ ์ด์ ์ ๊ด๊ณํ DBMS๋ง ์ฌ์ฉํด ๋ณธ ์ฌ๋๋ค์๊ฒ๋ ์ผ๋ถ ๋ฐฉ์์ด ์์ํ๊ฒ ๋๊ปด์ง ์ ์์ต๋๋ค(์ ๊ฒฝํ์ ๋ฐ๋ฅด๋ฉด). ๋ฐ๋ผ์ "๊ด๊ณํ" ํ๊ฒฝ์์๋ ์ผ๋ฐ์ ์ผ๋ก ์ฃผ์ ์์ญ์ ๋ชจ๋ธ๋งํ๋ ๊ฒ๋ถํฐ ์์ํ์ฌ, ํ์ํ ๊ฒฝ์ฐ์๋ง ๋ชจ๋ธ์ ๋น์ ๊ทํํฉ๋๋ค. NoSQL์์๋ ๋ฐ์ดํฐ ์์ ์ ๋ํ ์์ ์๋๋ฆฌ์ค๋ฅผ ์ฆ์ ๊ณ ๋ คํด์ผ ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ์ฒ์์๋ ๋ฐ์ดํฐ๋ฅผ ๋น์ ๊ทํํฉ๋๋ค. ์ด ์ธ์๋ ์ฌ๋ฌ ๊ฐ์ง ์ฐจ์ด์ ์ด ์์ผ๋ฉฐ, ์๋์์ ์ค๋ช ํ๊ฒ ์ต๋๋ค.
์ฐ๋ฆฌ๊ฐ ๊ณ์ํด์ ์ฐ๊ตฌํ ๋ค์์ "ํฉ์ฑ" ๋ฌธ์ ๋ฅผ ๊ณ ๋ คํด ๋ณด๊ฒ ์ต๋๋ค.
์ด๋ค ์ถ์์ ์ธ ์์ ๋คํธ์ํฌ ์ฌ์ฉ์์ ์น๊ตฌ ๋ชฉ๋ก์ ์ ์ฅํ๋ ๊ตฌ์กฐ๋ฅผ ์ค๊ณํด์ผ ํฉ๋๋ค. ๋จ์ํ๋ฅผ ์ํด ๋ชจ๋ ์ฐ๊ฒฐ์ด (๋งํฌ๋์ธ์ด ์๋ ์ธ์คํ๊ทธ๋จ์ฒ๋ผ) ์ง์ ์ฐ๊ฒฐ๋๋ค๊ณ ๊ฐ์ ํ๊ฒ ์ต๋๋ค. ์ด ๊ตฌ์กฐ๋ ํจ์จ์ ์ธ ๋ค์์ ํ์ฉํด์ผ ํฉ๋๋ค.
- ์ฌ์ฉ์ A๊ฐ ์ฌ์ฉ์ B๋ฅผ ์ฝ๊ณ ์๋์ง(์ฝ๊ธฐ ํจํด)์ ๋ํ ์ง๋ฌธ์ ๋ตํ์ธ์.
- ์ฌ์ฉ์ A๊ฐ ์ฌ์ฉ์ B๋ฅผ ๊ตฌ๋ /๊ตฌ๋ ์ทจ์ํ ๋ ๋งํฌ ์ถ๊ฐ/์ ๊ฑฐ ํ์ฉ(๋ฐ์ดํฐ ๋ณ๊ฒฝ ํ ํ๋ฆฟ)
๋ฌผ๋ก , ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ์๋ ์ฌ๋ฌ ๊ฐ์ง ์ต์ ์ด ์์ต๋๋ค. ์ผ๋ฐ์ ์ธ ๊ด๊ณํ DB์์๋ ๋งํฌ ํ ์ด๋ธ(์๋ฅผ ๋ค์ด, ์ด "์น๊ตฌ"๋ฅผ ํฌํจํ๋ ๊ฐ์กฑ, ์ง์ฅ ๋ฑ์ ์ฌ์ฉ์ ๊ทธ๋ฃน์ ์ ์ฅํด์ผ ํ๋ ๊ฒฝ์ฐ ํ์ดํ ๊ฐ๋ฅ)์ ๋ง๋ค๊ณ , ์ก์ธ์ค ์๋๋ฅผ ์ต์ ํํ๊ธฐ ์ํด ์ธ๋ฑ์ค/ํํฐ์ ๋์ ์ถ๊ฐํ ๊ฐ๋ฅ์ฑ์ด ๋์ต๋๋ค. ๊ฒฐ๊ณผ ํ ์ด๋ธ์ ๋ค์๊ณผ ๊ฐ์ ๊ฒ์ ๋๋ค.
USER_ID
์น๊ตฌ_์์ด๋
Vasya
ํํฐ
Vasya
ะะปั
๋ช ํ์ฑ๊ณผ ๋ ๋์ ์ดํด๋ฅผ ์ํด ์ฌ๊ธฐ์ ๋ ๋์๊ฐ ID ๋์ ์ด๋ฆ์ ํ์ํ๊ฒ ์ต๋๋ค.
HBase์ ๊ฒฝ์ฐ ๋ค์ ์ฌํญ์ ์ ์ ์์ต๋๋ค.
- ์ ์ฒด ํ
์ด๋ธ ์ค์บ์ผ๋ก ์ด์ด์ง์ง ์๋ ํจ์จ์ ์ธ ๊ฒ์์ด ๊ฐ๋ฅํฉ๋๋ค. ํค๋ก๋ง ๋
์ ์ ์ผ๋ก
- ์ฌ์ค, ๋ง์ ์ฌ๋์ด ์ต์ํ ๊ทธ๋ฐ ๋ฐ์ดํฐ๋ฒ ์ด์ค์ SQL ์ฟผ๋ฆฌ๋ฅผ ์์ฑํ๋ ๊ฒ์ ๋์ ์๊ฐ์ ๋๋ค. ๊ธฐ์ ์ ์ผ๋ก๋ ๊ฐ์ Impala์์ HBase๋ก ์กฐ์ธ ๋ฐ ๊ธฐํ ๋ ผ๋ฆฌ๋ฅผ ํฌํจํ SQL ์ฟผ๋ฆฌ๋ฅผ ๋ณด๋ผ ์ ์์ง๋ง ์ผ๋ง๋ ํจ๊ณผ์ ์ผ๊น์...
๋ฐ๋ผ์ ์ฌ์ฉ์ ID๋ฅผ ํค๋ก ์ฌ์ฉํด์ผ ํฉ๋๋ค. "์น๊ตฌ ID๋ฅผ ์ด๋์ ์ด๋ป๊ฒ ์ ์ฅํ ๊ฒ์ธ๊ฐ?"๋ผ๋ ์ฃผ์ ์์ ๊ฐ์ฅ ๋จผ์ ๋ ์ค๋ฅด๋ ์๊ฐ์ ์ด์ ์ ์ฅํ๋ ๊ฒ์ ๋๋ค. ์ด ๊ฐ์ฅ ๋ช ํํ๊ณ "์์งํ" ์ต์ ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค(์ด๋ฆ์ ๋ค์๊ณผ ๊ฐ์ด ์ง์ ํ๊ฒ ์ต๋๋ค). ์ต์ 1(๊ธฐ๋ณธ๊ฐ), ์ถํ ์ฐธ๊ณ ์ฉ์ผ๋ก):
๋ก์ฐํค
์ฐ์ฌ
Vasya
1: ํํฐ์ผ
2: ์ฌ๋ฆฌ์ผ
3: ๋ค์ค
ํํฐ
1: ๋ง์ค
2: ๋ฐ์ค
์ฌ๊ธฐ์ ๊ฐ ํ์ ๋คํธ์ํฌ์ ํ ์ฌ์ฉ์์ ํด๋นํฉ๋๋ค. ์ด์๋ ์น๊ตฌ ์์ ๋ฐ๋ผ 1, 2, โฆ๋ผ๋ ์ด๋ฆ์ด ์ง์ ๋๊ณ , ๊ฐ ์ด์๋ ์น๊ตฌ์ ID๊ฐ ์ ์ฅ๋ฉ๋๋ค. ๊ฐ ํ์ ์ด ๊ฐ์๋ ์๋ก ๋ค๋ฅด๋ค๋ ์ ์ ์ ์ํด์ผ ํฉ๋๋ค. ์ ๊ทธ๋ฆผ์ ์์์ ํ ํ์๋ ์ธ ๊ฐ์ ์ด(1, 2, 3)์ด ์๊ณ , ๋ ๋ฒ์งธ ํ์๋ ๋ ๊ฐ์ ์ด(1๊ณผ 2)๋ง ์์ต๋๋ค. ์ฌ๊ธฐ์๋ ๊ด๊ณํ ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ์๋ HBase์ ๋ ๊ฐ์ง ์์ฑ์ ์ง์ ์ฌ์ฉํ์ต๋๋ค.
- ์ด ๊ตฌ์ฑ์ ๋์ ์ผ๋ก ๋ณ๊ฒฝํ๋ ๊ธฐ๋ฅ(์น๊ตฌ ์ถ๊ฐ -> ์ด ์ถ๊ฐ, ์น๊ตฌ ์ ๊ฑฐ -> ์ด ์ ๊ฑฐ)
- ๋ค๋ฅธ ํ์๋ ๋ค๋ฅธ ์ด ๊ตฌ์ฑ์ด ์์ ์ ์์ต๋๋ค.
์์ ์๊ตฌ ์ฌํญ์ ์ค์ํ๋์ง ๊ตฌ์กฐ๋ฅผ ํ์ธํด ๋ณด๊ฒ ์ต๋๋ค.
- ๋ฐ์ดํฐ ์ฝ๊ธฐ: Vasya๊ฐ Olya์ ๊ฐ์ ํ๋์ง ์ดํดํ๋ ค๋ฉด ๋ค์์ ์ฝ์ด์ผ ํฉ๋๋ค. ์ ์ฒด ๋ผ์ธ RowKey = "Vasya" ํค๋ฅผ ์ฌ์ฉํ์ฌ Olya๋ฅผ ๋ง๋ ๋๊น์ง ์ด ๊ฐ์ ๋ฐ๋ณตํฉ๋๋ค. ๋๋ Olya๋ฅผ ๋ง๋์ง ์๋ ๋ชจ๋ ์ด ๊ฐ์ ๋ฐ๋ณตํ์ฌ False๋ฅผ ๋ฐํํฉ๋๋ค.
- ์ธ๋ถ ์ ๋ณด ํธ์ง: ์น๊ตฌ ์ถ๊ฐ: ๋น์ทํ ๋ฌธ์ ์ ๋ํด์๋ ๋นผ์ผ ํฉ๋๋ค. ์ ์ฒด ๋ผ์ธ RowKey = "Vasya" ํค๋ฅผ ์ฌ์ฉํ์ฌ ์น๊ตฌ์ ์ด ์๋ฅผ ๊ณ์ฐํฉ๋๋ค. ์ ์น๊ตฌ์ ID๋ฅผ ์ ๋ ฅํ ์ด ๋ฒํธ๋ฅผ ๊ฒฐ์ ํ๋ ค๋ฉด ์ด ์ด ์น๊ตฌ ์๊ฐ ํ์ํฉ๋๋ค.
- ๋ณ๊ฒฝ ์ฌํญ: ์น๊ตฌ ์ญ์ :
- ๋นผ์ผ ํฉ๋๋ค ์ ์ฒด ๋ผ์ธ RowKey = "Vasya" ํค๋ฅผ ์ฌ์ฉํ์ฌ ์ญ์ ๋๋ ์น๊ตฌ๊ฐ ๊ธฐ๋ก๋ ์ด์ ์ฐพ์ต๋๋ค.
- ๋ค์์ผ๋ก, ์น๊ตฌ๋ฅผ ์ญ์ ํ ํ์๋ ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ ํ ์ด๋ก "์ด๋"ํ์ฌ ๋ฒํธ ๋งค๊ธฐ๊ธฐ์ "๊ฐ๊ฒฉ"์ด ์๊ธฐ์ง ์๋๋ก ํด์ผ ํฉ๋๋ค.
์ด์ "์กฐ๊ฑด๋ถ ์์ฉ ํ๋ก๊ทธ๋จ" ์ธก๋ฉด์์ ๊ตฌํํด์ผ ํ ์ด๋ฌํ ์๊ณ ๋ฆฌ์ฆ์ด ์ผ๋ง๋ ์์ฐ์ ์ผ์ง ํ๊ฐํด ๋ณด๊ฒ ์ต๋๋ค. ๊ฐ์์ ์์ ๋คํธ์ํฌ์ ํฌ๊ธฐ๋ฅผ n์ด๋ผ๊ณ ํฉ์๋ค. ๊ทธ๋ฌ๋ฉด ํ ์ฌ์ฉ์๊ฐ ๊ฐ์ง ์ ์๋ ์ต๋ ์น๊ตฌ ์๋ (n-1)์ ๋๋ค. O-๊ธฐํธ๋ฅผ ์ฌ์ฉํ๋ ํ์์ ์ด ๊ฐ์ ์ค์ํ์ง ์์ผ๋ฏ๋ก, ์ด ๋ชฉ์ ์์๋ (-1)๋ก ๋ฌด์ํด๋ ๋ฉ๋๋ค.
- ๋ฐ์ดํฐ ์ฝ๊ธฐ: ์ ์ฒด ํ์ ๋นผ๊ณ ๊ทนํ๊ฐ ๋ด์ ๋ชจ๋ ์ด์ ์ ๋ ฌํด์ผ ํฉ๋๋ค. ์ฆ, ๋น์ฉ์ ์ํ ์ถ์ ๊ฐ์ ์ฝ O(n)์ด ๋ฉ๋๋ค.
- ์ธ๋ถ ์ ๋ณด ํธ์ง: ์น๊ตฌ ์ถ๊ฐ: ์น๊ตฌ์ ์๋ฅผ ๊ฒฐ์ ํ๋ ค๋ฉด ํ์ ๋ชจ๋ โโ์ด์ ๋ฐ๋ณตํ ๋ค์ ์ ์ด์ ์ฝ์ ํด์ผ ํฉ๋๋ค => O(n)
- ๋ณ๊ฒฝ ์ฌํญ: ์น๊ตฌ ์ญ์ :
- ์ถ๊ฐํ๋ ๊ฒ๊ณผ ์ ์ฌํฉ๋๋ค. ํ๊ณ ๋ด์ ๋ชจ๋ ์ด์ ์ดํด๋ด์ผ ํฉ๋๋ค => O(n)
- ์ด์ ์ญ์ ํ ํ์๋ "์ด๋"ํด์ผ ํฉ๋๋ค. ์ด๋ฅผ "์ ๋ฉด"์ผ๋ก ๊ตฌํํ๋ฉด ํ๊ณ์ ๋๋ฌํ์ ๋ ์ต๋ (n-1)๊ฐ์ ์ฐ์ฐ์ด ๋ ํ์ํฉ๋๋ค. ํ์ง๋ง ์ด ๋ถ๋ถ๊ณผ ์ค์ ์ ์ธ ๋ถ๋ถ์์๋ ๋ค๋ฅธ ์ ๊ทผ๋ฒ์ ์ ์ฉํ์ฌ "์์ฌ ์ด๋"์ ๊ณ ์ ๋ ์ฐ์ฐ ํ์๋ก ๊ตฌํํ ๊ฒ์
๋๋ค. ์ฆ, n์ ๊ด๊ณ์์ด ์์ ์๊ฐ์ด ๊ฑธ๋ฆฝ๋๋ค. ์ด ์์ ์๊ฐ(์ ํํ O(2))์ O(n)์ ๋นํด ๋ฌด์ํ ์ ์์ต๋๋ค. ์ด ์ ๊ทผ๋ฒ์ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ต๋๋ค. "๋ง์ง๋ง" ์ด์ ๋ฐ์ดํฐ๋ฅผ ์ญ์ ํ๋ ค๋ ์ด๋ก ๋ณต์ฌํ ๋ค์ ๋ง์ง๋ง ์ด์ ์ญ์ ํฉ๋๋ค.

๊ฒฐ๊ณผ์ ์ผ๋ก ๋ชจ๋ ์๋๋ฆฌ์ค์์ ์ฐ๋ฆฌ๋ O(n)์ ์ ๊ทผ์ ๊ณ์ฐ ๋ณต์ก๋๋ฅผ ์ป์์ต๋๋ค.
๋ฐ์ดํฐ๋ฒ ์ด์ค์์ ๊ฑฐ์ ํญ์ ์ ์ฒด ์ค์ ์ฝ์ด์ผ ํ๊ณ , ์ธ ๊ฐ์ง ๊ฒฝ์ฐ ์ค ๋ ๊ฐ์ง๋ ๋ชจ๋ ์ด์ ๊ฒํ ํ์ฌ ์ด ์น๊ตฌ ์๋ฅผ ์ธ๋ ๋ฐ๋ง ์ฌ์ฉ๋๋ค๋ ๊ฒ์ ์ด๋ฏธ ์๊ณ ๊ณ์ค ๊ฒ์
๋๋ค. ๋ฐ๋ผ์ ์ต์ ํ๋ฅผ ์ํด ๊ฐ ๋คํธ์ํฌ ์ฌ์ฉ์์ ์ด ์น๊ตฌ ์๋ฅผ ์ ์ฅํ๋ "count" ์ด์ ์ถ๊ฐํ ์ ์์ต๋๋ค. ์ด ๊ฒฝ์ฐ, ์ด ์น๊ตฌ ์๋ฅผ ์ธ๋ ๋ฐ ์ ์ฒด ์ค์ ์ฝ์ ํ์๊ฐ ์๊ณ , "count" ์ด ํ๋๋ง ์ฝ์ผ๋ฉด ๋ฉ๋๋ค. ์ค์ํ ๊ฒ์ ๋ฐ์ดํฐ๋ฅผ ์กฐ์ํ ๋ "count" ์ด์ ์
๋ฐ์ดํธํ๋ ๊ฒ์ ์์ง ์๋ ๊ฒ์
๋๋ค. ์ด๋ ๊ฒ ํ๋ฉด ๊ฐ์ ๋ ๊ฒฐ๊ณผ๋ฅผ ์ป์ ์ ์์ต๋๋ค. ์ต์
2(๊ฐ์):
๋ก์ฐํค
์ฐ์ฌ
Vasya
1: ํํฐ์ผ
2: ์ฌ๋ฆฌ์ผ
3: ๋ค์ค
์นด์ดํธ: 3
ํํฐ
1: ๋ง์ค
2: ๋ฐ์ค
์นด์ดํธ: 2
์ฒซ ๋ฒ์งธ ์ต์ ๊ณผ ๋น๊ตํ์ ๋:
- ๋ฐ์ดํฐ ์ฝ๊ธฐ: "Vasya๊ฐ Olya๋ฅผ ์ฝ๋์?"๋ผ๋ ์ง๋ฌธ์ ๋ํ ๋ต์ ์ป์ผ๋ ค๋ฉด ์๋ฌด๊ฒ๋ ๋ณํ์ง ์์์ต๋๋ค => O(n)
- ์ธ๋ถ ์ ๋ณด ํธ์ง: ์น๊ตฌ ์ถ๊ฐ: ์ ์น๊ตฌ ์ถ๊ฐ ์์ ์ ๊ฐ์ํํ์ต๋๋ค. ์ด์ ์ ์ฒด ํ์ ์ฝ๊ณ ํด๋น ์ด์ ๋ฐ๋ณตํ ํ์๊ฐ ์๊ณ , "count" ์ด์ ๊ฐ๋ง ๊ฐ์ ธ์ ์ ์น๊ตฌ๋ฅผ ์ถ๊ฐํ ์ด ๋ฒํธ๋ฅผ ์ฆ์ ๊ฒฐ์ ํ ์ ์์ต๋๋ค. ์ด๋ฅผ ํตํด ๊ณ์ฐ ๋ณต์ก๋๊ฐ O(1)๋ก ๊ฐ์ํฉ๋๋ค.
- ๋ณ๊ฒฝ ์ฌํญ: ์น๊ตฌ ์ญ์ : ์น๊ตฌ๋ฅผ ์ญ์ ํ ๋ ์ด ์ด์ ์ฌ์ฉํ๋ฉด ๋ฐ์ดํฐ๋ฅผ ํ ์ ์ผ์ชฝ์ผ๋ก "์ด๋"ํ ๋ ๋ฐ์ํ๋ I/O ์์ ์๋ฅผ ์ค์ผ ์ ์์ต๋๋ค. ํ์ง๋ง ์ญ์ ํด์ผ ํ ์ด์ ์ฐพ๊ธฐ ์ํด ์ด์ ๋ฐ๋ณตํด์ผ ํ๋ฏ๋ก => O(n)
- ๋ฐ๋ฉด์, ์ด์ ๋ฐ์ดํฐ๋ฅผ ์ ๋ฐ์ดํธํ ๋๋ง๋ค "count" ์ด์ ์ ๋ฐ์ดํธํด์ผ ํ์ง๋ง ์ด ์์ ์๋ ์ผ์ ํ ์๊ฐ์ด ์์๋๋ฉฐ, ์ด๋ O-์ฌ๋ณผ๋ฆญ ํ๋ ์์ํฌ ๋ด์์ ๋ฌด์๋ ์ ์์ต๋๋ค.
์ ๋ฐ์ ์ผ๋ก ์ต์
2๊ฐ ์กฐ๊ธ ๋ ์ต์ ์ฒ๋ผ ๋ณด์ด์ง๋ง "ํ๋ช
๋์ ์งํ"์ ๋ ๊ฐ๊น์ต๋๋ค. "ํ๋ช
"์ ์ผ์ผํค๋ ค๋ฉด ๋ค์์ด ํ์ํฉ๋๋ค. ์ต์
3(์ด).
๋ชจ๋ ๊ฒ์ ๋ค์ง์ด ๋ณด์: ์๋ช
ํ์ ์ด ์ด๋ฆ ์ฌ์ฉ์ ID! ์นผ๋ผ์ ์ฐ์ผ ๋ด์ฉ์ ์ค์ํ์ง ์์ต๋๋ค. 1๋ฒ์ผ๋ก ํ๊ฒ ์ต๋๋ค(์ผ๋ฐ์ ์ผ๋ก ์ ์ฉํ ์ ๋ณด, ์๋ฅผ ๋ค์ด "๊ฐ์กฑ/์น๊ตฌ/๊ธฐํ" ๊ทธ๋ฃน). ์ด๋ฌํ ์ ๊ทผ ๋ฐฉ์์ NoSQL ๋ฐ์ดํฐ๋ฒ ์ด์ค ์ฌ์ฉ ๊ฒฝํ์ด ์๋ "์ผ๋ฐ์ธ"์๊ฒ๋ ๋๋ผ์ธ ์ ์์ง๋ง, HBase์ ์ ์ฌ๋ ฅ์ ์ด ์์
์์ ํจ์ฌ ๋ ํจ๊ณผ์ ์ผ๋ก ํ์ฉํ ์ ์๊ฒ ํด ์ค๋๋ค.
๋ก์ฐํค
์ฐ์ฌ
Vasya
ํํฐ์ผ: 1
์ฌ๋ฆฌ์ผ: 1
๋ค์ค: 1
ํํฐ
๋ง์ค: 1
๋ฐ์ค: 1
์ฌ๊ธฐ์ ์ฐ๋ฆฌ๋ ์ฌ๋ฌ ๊ฐ์ง ์ด์ ์ ๋์์ ์ป์ ์ ์์ต๋๋ค. ์ด๋ฅผ ์ดํดํ๊ธฐ ์ํด ์๋ก์ด ๊ตฌ์กฐ๋ฅผ ๋ถ์ํ๊ณ ๊ณ์ฐ ๋ณต์ก๋๋ฅผ ์ถ์ ํด ๋ณด๊ฒ ์ต๋๋ค.
- ๋ฐ์ดํฐ ์ฝ๊ธฐ: Vasya๊ฐ Olya์ ๊ฐ์ ํ๋์ง ์ฌ๋ถ์ ๋ํ ์ง๋ฌธ์ ๋ตํ๋ ค๋ฉด "Olya" ์ด ํ๋๋ง ์ฝ์ผ๋ฉด ๋ฉ๋๋ค. ๊ฐ์ ํ๋ค๋ฉด ๋ต์ True์ด๊ณ , ๊ฐ์ ํ์ง ์์๋ค๋ฉด False์ ๋๋ค => O(1)
- ์ธ๋ถ ์ ๋ณด ํธ์ง: ์น๊ตฌ ์ถ๊ฐ: ์น๊ตฌ ์ถ๊ฐ: ์๋ก์ด ์ด "์น๊ตฌ ID"๋ฅผ ์ถ๊ฐํ๊ธฐ๋ง ํ๋ฉด ๋ฉ๋๋ค => O(1)
- ๋ณ๊ฒฝ ์ฌํญ: ์น๊ตฌ ์ญ์ : "์น๊ตฌ ID" ์ด๋ง ์ ๊ฑฐํ๋ฉด ๋ฉ๋๋ค => O(1)
๋ณด์๋ค์ํผ, ์ด๋ฌํ ์ ์ฅ ๋ชจ๋ธ์ ์ค์ํ ์ฅ์ ์ ํ์ํ ๋ชจ๋ ์๋๋ฆฌ์ค์์ ๋จ ํ๋์ ์ด๋ง ์ฌ์ฉํ์ฌ ์์ ํ ์ ์๋ค๋ ๊ฒ์ ๋๋ค. ์ฆ, ๋ฐ์ดํฐ๋ฒ ์ด์ค์์ ์ ์ฒด ํ์ ์ฝ์ง ์์๋ ๋๊ณ , ๋ ๋์๊ฐ ํด๋น ํ์ ๋ชจ๋ โโ์ด์ ๊ฒํ ํ์ง ์์๋ ๋ฉ๋๋ค. ์ฌ๊ธฐ์ ๋ฉ์ถ ์๋ ์์ง๋ง...
์ด ๋ถ๋ถ์ ๊ณ ๋ฏผํด ๋ณด๋ฉด ๋ฐ์ดํฐ๋ฒ ์ด์ค ์ ๊ทผ ์ ์ฑ๋ฅ์ ์ต์ ํํ๊ณ I/O ์์ ์ ์ค์ด๋ ๋ฐฉํฅ์ผ๋ก ํ ๊ฑธ์ ๋ ๋์๊ฐ ์ ์์ต๋๋ค. ์ฐ๊ฒฐ์ ๋ํ ์ ์ฒด ์ ๋ณด๋ฅผ ํ ํค์ ์ง์ ์ ์ฅํ๋ฉด ์ด๋จ๊น์? ์ฆ, ํค๋ฅผ userID.friendID์ฒ๋ผ ๋ณตํฉ ํค๋ก ๋ง๋๋ ๊ฒ์ ๋๋ค. ์ด ๊ฒฝ์ฐ ํ ์ด์ ์ฝ์ ํ์๋ ์์ต๋๋ค(์ต์ 4(ํ)):
๋ก์ฐํค
์ฐ์ฌ
๋ฐ์ค.ํํฐ์
ํํฐ์ผ: 1
๋ฐ์ค.์ฌ์ผ
์ฌ๋ฆฌ์ผ: 1
๋ฐ์ค.๋ค์ค
๋ค์ค: 1
ํํฐ์.๋ง์ค
๋ง์ค: 1
ํํฐ์ผ.๋ฐ์ค
๋ฐ์ค: 1
์ด๋ฌํ ๊ตฌ์กฐ์์ ๋ชจ๋ ๋ฐ์ดํฐ ์กฐ์ ์๋๋ฆฌ์ค์ ํ๊ฐ๋ ์ด์ ๋ณํ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก O(1)์ด ๋ ๊ฒ์ ๋๋ค. ๋ณํ 3๊ณผ์ ์ฐจ์ด์ ์ ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ์ ์ถ๋ ฅ ์์ ํจ์จ์ฑ์๋ง ์์ต๋๋ค.
์, ๋ง์ง๋ง "๋๋น๋ฅํ์ด"์ ๋๋ค. ์ต์ 4์์ ํ ํค์ ๊ธธ์ด๊ฐ ๊ฐ๋ณ์ ์ด์ด์ ์ฑ๋ฅ์ ์ํฅ์ ๋ฏธ์น ์ ์๋ค๋ ๊ฒ์ ์ฝ๊ฒ ์ ์ ์์ต๋๋ค(HBase๋ ๋ฐ์ดํฐ๋ฅผ ๋ฐ์ดํธ ์งํฉ์ผ๋ก ์ ์ฅํ๊ณ ํ ์ด๋ธ์ ํ์ ํค ๊ธฐ์ค์ผ๋ก ์ ๋ ฌ๋๋ค๋ ์ ์ ๊ธฐ์ตํ์ธ์). ๋ํ, ๊ตฌ๋ถ ๊ธฐํธ๊ฐ ์๋๋ฐ, ๊ฒฝ์ฐ์ ๋ฐ๋ผ ์ฒ๋ฆฌํด์ผ ํ ์๋ ์์ต๋๋ค. ์ด๋ฌํ ์ํฅ์ ์์ ๋ ค๋ฉด userID์ friendID์ ํด์๋ฅผ ์ฌ์ฉํ ์ ์์ต๋๋ค. ๋ ํด์ ๋ชจ๋ ๊ธธ์ด๊ฐ ๊ณ ์ ๋์ด ์์ผ๋ฏ๋ก ๊ตฌ๋ถ ๊ธฐํธ ์์ด ๊ฐ๋จํ ์ฐ๊ฒฐํ ์ ์์ต๋๋ค. ๊ทธ๋ฌ๋ฉด ํ ์ด๋ธ์ ๋ฐ์ดํฐ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค(์ต์ 5(ํด์)):
๋ก์ฐํค
์ฐ์ฌ
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
ํํฐ์ผ: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
์ฌ๋ฆฌ์ผ: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
๋ค์ค: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
๋ง์ค: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
๋ฐ์ค: 1
๋ถ๋ช
ํ, ์ฐ๋ฆฌ๊ฐ ๊ณ ๋ คํ๊ณ ์๋ ์๋๋ฆฌ์ค์ ๋ฐ๋ผ ์ด๋ฌํ ๊ตฌ์กฐ๋ก ์์
ํ๋ ์๊ณ ๋ฆฌ์ฆ ๋ณต์ก๋๋ ์ต์
4์ ๋์ผํ ๊ฒ์
๋๋ค. ์ฆ, O(1)์
๋๋ค.
๊ทธ๋ฌ๋ฉด ๋ชจ๋ ๊ณ์ฐ ๋ณต์ก๋ ์ถ์ ์น๋ฅผ ํ๋์ ํ์ ๋ฃ์ด ๋ณด๊ฒ ์ต๋๋ค.
์น๊ตฌ ์ถ๊ฐ
์น๊ตฌ๋ฅผ ์ฒดํฌํ๋ค
์น๊ตฌ ์ญ์ ํ๊ธฐ
์ต์
1(๊ธฐ๋ณธ๊ฐ)
O (N)
O (N)
O (N)
์ต์
2(๊ฐ์)
O (1)
O (N)
O (N)
์ต์
3(์ด)
O (1)
O (1)
O (1)
์ต์
4(ํ)
O (1)
O (1)
O (1)
์ต์
5(ํด์)
O (1)
O (1)
O (1)
๋ณด์๋ค์ํผ, ์ต์ 3~5๊ฐ ๊ฐ์ฅ ์ ํธ๋๋ ๊ฒ์ผ๋ก ๋ณด์ด๋ฉฐ, ์ด๋ก ์ ์ผ๋ก ๋ชจ๋ ํ์ ๋ฐ์ดํฐ ์กฐ์ ์๋๋ฆฌ์ค๋ฅผ ์์ ์๊ฐ ๋ด์ ์คํํ ์ ์์ต๋๋ค. ๋ฌธ์ ์ ์กฐ๊ฑด์ด ๋ชจ๋ ์ฌ์ฉ์์ ์น๊ตฌ ๋ชฉ๋ก์ ํ๋ณดํ๋ ๊ฒ์ ๋ช ์์ ์ผ๋ก ์๊ตฌํ๋ ๊ฒ์ ์๋์ง๋ง, ์ค์ ํ๋ก์ ํธ ํ๋์์ ์ ๋ฅํ ๋ถ์๊ฐ๋ก์ ๊ทธ๋ฌํ ์์ ์ด ๋ฐ์ํ ๊ฐ๋ฅ์ฑ์ "์์ธก"ํ๊ณ "๋ฏธ๋ฆฌ ๋๋นํ๋" ๊ฒ์ด ์ข์ต๋๋ค. ๋ฐ๋ผ์ ์ ๋ ์ต์ 3์ ๊ณต๊ฐํฉ๋๋ค. ํ์ง๋ง ์ค์ ํ๋ก์ ํธ์์๋ ์ด ์์ฒญ์ด ์ด๋ฏธ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก ํด๊ฒฐ๋์์ ๊ฐ๋ฅ์ฑ์ด ๋งค์ฐ ๋์ผ๋ฏ๋ก, ์ ์ฒด ์์ ์ ๋ํ ์ ๋ฐ์ ์ธ ์ดํด๊ฐ ์๋ค๋ฉด ์ต์ข ๊ฒฐ๋ก ์ ๋ด๋ฆฌ์ง ์๋ ๊ฒ์ด ์ข์ต๋๋ค.
์คํ ์ค๋น
์์ ์ด๋ก ์ ์ถ๋ก ์ ์ค์ ๋ก ํ ์คํธํด ๋ณด๊ณ ์ถ์ต๋๋ค. ์ด๊ฒ์ด ๋ฐ๋ก ๊ธด ์ฃผ๋ง ๋์ ๋ ์ค๋ฅธ ์์ด๋์ด์ ๋ชฉํ์์ต๋๋ค. ์ด๋ฅผ ์ํด์๋ ์์ ์ค๋ช ํ ๋ชจ๋ ๋ฐ์ดํฐ๋ฒ ์ด์ค ์ฌ์ฉ ์๋๋ฆฌ์ค์์ "์กฐ๊ฑด๋ถ ์ ์ฉ"์ ์๋์ ์์ ๋คํธ์ํฌ ๊ท๋ชจ(n)์ ์ฆ๊ฐ์ ๋ฐ๋ฅธ ์ด ์๊ฐ์ ์ฆ๊ฐ๋ฅผ ํ๊ฐํด์ผ ํฉ๋๋ค. ์คํ ๊ณผ์ ์์ ์ธก์ ํ ๋ชฉํ ๋งค๊ฐ๋ณ์๋ "์กฐ๊ฑด๋ถ ์ ์ฉ"์ด ํ๋์ "๋น์ฆ๋์ค ์ฐ์ฐ"์ ์ํํ๋ ๋ฐ ์์๋๋ ์๊ฐ์ ๋๋ค. "๋น์ฆ๋์ค ์ฐ์ฐ"์ด๋ ๋ค์ ์ค ํ๋๋ฅผ ์๋ฏธํฉ๋๋ค.
- ์๋ก์ด ์น๊ตฌ ํ ๋ช ์ถ๊ฐํ๊ธฐ
- ์ฌ์ฉ์ A๊ฐ ์ฌ์ฉ์ B์ ์น๊ตฌ์ธ์ง ํ์ธํ์ธ์
- ์น๊ตฌ ํ ๋ช ์ญ์
๋ฐ๋ผ์ ์ด๊ธฐ ๋ช ์ธ์์ ๋ช ์๋ ์๊ตฌ ์ฌํญ์ ๊ณ ๋ คํ ๋ ๊ฒ์ฆ ์๋๋ฆฌ์ค๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ๋ฐ์ดํฐ ๊ธฐ๋กํฌ๊ธฐ๊ฐ n์ธ ๋ฌด์์ ์ด๊ธฐ ๋คํธ์ํฌ๋ฅผ ์์ฑํฉ๋๋ค. "์ค์ ์ธ๊ณ"์ ๋ ๊ฐ๊น๊ฒ ๋ง๋ค๊ธฐ ์ํด ๊ฐ ์ฌ์ฉ์์ ์น๊ตฌ ์ ๋ํ ํ๋ฅ ๋ณ์๋ก ์ง์ ํฉ๋๋ค. "์กฐ๊ฑด๋ถ ์ ํ๋ฆฌ์ผ์ด์ "์ด ์์ฑ๋ ๋ชจ๋ ๋ฐ์ดํฐ๋ฅผ HBase์ ์ฐ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ธก์ ํฉ๋๋ค. ๊ทธ๋ฐ ๋ค์ ๊ฒฐ๊ณผ ์๊ฐ์ ์ถ๊ฐ๋ ์น๊ตฌ ์๋ก ๋๋๋๋ค. ์ด๋ ๊ฒ ํ๋ฉด ํ "๋น์ฆ๋์ค ์์ "์ ๊ฑธ๋ฆฌ๋ ํ๊ท ์๊ฐ์ ๊ตฌํ ์ ์์ต๋๋ค.
- ๋ฐ์ดํฐ ์ฝ๊ธฐ๊ฐ ์ฌ์ฉ์์ ๋ํด, ์ฌ์ฉ์๊ฐ ๊ตฌ๋ ํ๋์ง ์ฌ๋ถ์ ๊ด๊ณ์์ด ๋ต๋ณ์ ์ป์ด์ผ ํ๋ "์ฑ๊ฒฉ" ๋ชฉ๋ก์ ์์ฑํ์ญ์์ค. ๋ชฉ๋ก์ ๊ธธ์ด๋ ๋๋ต ์ฌ์ฉ์์ ์น๊ตฌ ์์ ๊ฐ์ผ๋ฉฐ, ์ ํ๋ ์น๊ตฌ์ ์ ๋ฐ์ "์", ๋๋จธ์ง ์ ๋ฐ์ "์๋์"๋ก ๋ตํด์ผ ํฉ๋๋ค. ํ์ธ์ "์"์ "์๋์"๊ฐ ๋ฒ๊ฐ์ ๋ํ๋๋ ์์๋ก ์ํ๋ฉ๋๋ค(์ฆ, ๋งค ์ด๋ง๋ค ์ต์ 1๊ณผ 2์ ๋ํ ํ์ ๋ชจ๋ โโ์ด์ ๊ฒํ ํด์ผ ํฉ๋๋ค). ๊ทธ๋ฐ ๋ค์ ์ด ํ์ธ ์๊ฐ์ ์ ํ๋ ์น๊ตฌ ์๋ก ๋๋์ด ํ ์ฃผ์ ๋ฅผ ํ์ธํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ํ๊ท ์๊ฐ์ ๊ตฌํฉ๋๋ค.
- ๋ฐ์ดํฐ ์ญ์ ์ฌ์ฉ์์ ๋ชจ๋ ์น๊ตฌ๋ฅผ ์ญ์ ํฉ๋๋ค. ์ญ์ ์์๋ ๋ฌด์์์ ๋๋ค(์ฆ, ๋ฐ์ดํฐ ๊ธฐ๋ก์ ์ฌ์ฉ๋ ์๋ ๋ชฉ๋ก์ "์์ต๋๋ค"). ์ด ํ์ธ ์๊ฐ์ ์ญ์ ๋๋ ์น๊ตฌ ์๋ก ๋๋์ด ํ ๋ฒ์ ํ์ธ์ ๊ฑธ๋ฆฌ๋ ํ๊ท ์๊ฐ์ ๊ตฌํฉ๋๋ค.
5๊ฐ์ง ๋ฐ์ดํฐ ๋ชจ๋ธ ๋ณํ ๊ฐ๊ฐ๊ณผ ๋ค์ํ ๊ท๋ชจ์ ์์
๋คํธ์ํฌ์ ๋ํด ์๋๋ฆฌ์ค๋ฅผ ์คํํ์ฌ ๋คํธ์ํฌ๊ฐ ์ฑ์ฅํจ์ ๋ฐ๋ผ ์๊ฐ์ด ์ด๋ป๊ฒ ๋ณํ๋์ง ํ์ธํด์ผ ํฉ๋๋ค. 5n ๋ด์์ ๋คํธ์ํฌ์ ์ฐ๊ฒฐ๊ณผ ํ์ธํ ์ฌ์ฉ์ ๋ชฉ๋ก์ XNUMX๊ฐ์ง ๋ณํ ๋ชจ๋์์ ๋น์ฐํ ๋์ผํด์ผ ํฉ๋๋ค.
๋ ๋์ ์ดํด๋ฅผ ์ํด, n=5์ ๋ํด ์์ฑ๋ ๋ฐ์ดํฐ์ ์๋ฅผ ์๋์ ์ ์ํฉ๋๋ค. ์์ฑ๋ "์์ฑ๊ธฐ"๋ ์ถ๋ ฅ์์ โโ์ธ ๊ฐ์ ID ์ฌ์ ์ ์์ฑํฉ๋๋ค.
- ์ฒซ ๋ฒ์งธ๋ ์ฝ์ ์ฉ์ ๋๋ค
- ๋ ๋ฒ์งธ๋ ํ์ธ์ฉ์ ๋๋ค
- ์ธ ๋ฒ์งธ๋ ์ ๊ฑฐ์ฉ์ ๋๋ค
{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # ะฒัะตะณะพ 15 ะดััะทะตะน
{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # ะฒัะตะณะพ 18 ะฟัะพะฒะตััะตะผัั
ััะฑัะตะบัะพะฒ
{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # ะฒัะตะณะพ 15 ะดััะทะตะน
๋ณด์๋ค์ํผ, ๊ฒ์ฆ์ ์ํด ์ฌ์ ์ ์๋ 10๋ณด๋ค ํฐ ๋ชจ๋ ID๋ ๋ช ๋ฐฑํ False ๊ฒฐ๊ณผ๋ฅผ ๋ผ ๊ฒ์ ๋๋ค. "์น๊ตฌ"์ ์ฝ์ , ๊ฒ์ฆ ๋ฐ ์ญ์ ๋ ์ฌ์ ์ ์ง์ ๋ ์ ํํ ์์์ ๋ฐ๋ผ ์ํ๋ฉ๋๋ค.
์ด ์คํ์ ๋ ธํธ๋ถ์์ ์คํ๋์์ต๋๋ค. Windows 10HBase๋ ํ๋์ Docker ์ปจํ ์ด๋์์ ์คํ๋๊ณ , Python๊ณผ Jupyter Notebook์ ๋ค๋ฅธ ์ปจํ ์ด๋์์ ์คํ๋์์ต๋๋ค. Docker์๋ 2๊ฐ์ CPU ์ฝ์ด์ 2GB์ RAM์ด ํ ๋น๋์์ต๋๋ค. "๋๋ฏธ ์ ํ๋ฆฌ์ผ์ด์ " ์๋ฎฌ๋ ์ด์ ๊ณผ ํ ์คํธ ๋ฐ์ดํฐ ์์ฑ ๋ฐ ์๊ฐ ์ธก์ ํ๋ ์์ํฌ๋ฅผ ํฌํจํ ๋ชจ๋ ๋ก์ง์ Python์ผ๋ก ์์ฑ๋์์ต๋๋ค. ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค. , ์ต์ 5์ ๋ํ ํด์(MD5)๋ฅผ ๊ณ์ฐํ๋ ค๋ฉด - hashlib
ํน์ ๋ ธํธ๋ถ์ ์ปดํจํ ์ฑ๋ฅ์ ๊ณ ๋ คํ์ฌ ์ ์ฒด ํ ์คํธ ์ฃผ๊ธฐ(๋ชจ๋ n์ ๋ํ ๋ชจ๋ ์ต์ ์ ๋ํ ๋ชจ๋ ์๋๋ฆฌ์ค)์ ์ด ์คํ ์๊ฐ์ด ํ ๋ฒ์ ํฐํํฐ(ํ๊ท 10๋ถ) ๋์ ์ฌ์ ํ ์ด๋ ์ ๋ ํฉ๋ฆฌ์ ์ด๊ณ ์ ํฉํ ๊ฒฝ์ฐ n = 30, 170, โฆ 15์ ๋ํด ์คํ์ ์ผ๋ก ์ถ์๋ฅผ ์ ํํ์ต๋๋ค.
์ฌ๊ธฐ์ ์ด ์คํ์ ์ ๋์ ์ธ ์ฑ๋ฅ ์์น๋ฅผ ํ๊ฐํ๋ ๊ฒ์ด ์๋๋ผ๋ ์ ์ ๊ฐ์กฐํด์ผ ํฉ๋๋ค. ๋ ๊ฐ์ง ๋ค๋ฅธ ์ต์ ์ ์๋์ ์ผ๋ก ๋น๊ตํ๋ ๊ฒ์กฐ์ฐจ ์์ ํ ์ ํํ์ง ์์ ์ ์์ต๋๋ค. ์ด์ n์ ๋ฐ๋ฅธ ์๊ฐ ๋ณํ์ ํน์ฑ์ ๊ด์ฌ์ ๊ฐ๊ฒ ๋๋๋ฐ, ์์ ์ธ๊ธํ "ํ ์คํธ ์คํ ๋"์ ๊ตฌ์ฑ์ ๊ณ ๋ คํ ๋, ๋ฌด์์ ์์ธ ๋ฐ ๊ธฐํ ์์ธ์ ์ํฅ์ "์ ๊ฑฐ"ํ ์๊ฐ ์ถ์ ์น๋ฅผ ์ป๋ ๊ฒ์ ๋งค์ฐ ์ด๋ ต๊ธฐ ๋๋ฌธ์ ๋๋ค(๊ทธ๋ฆฌ๊ณ ๊ทธ๋ฌํ ์์ ์ ์ค์ ๋์ง ์์์ต๋๋ค).
์คํ ๊ฒฐ๊ณผ
์ฒซ ๋ฒ์งธ ์คํ์ ์น๊ตฌ ๋ชฉ๋ก์ ์ฑ์ฐ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ด ์ด๋ป๊ฒ ๋ณํ๋์ง ์ดํด๋ณด๋ ๊ฒ์
๋๋ค. ๊ฒฐ๊ณผ๋ ์๋ ๊ทธ๋ํ์ ๊ฐ์ต๋๋ค.

์ต์
3~5๋ ๋คํธ์ํฌ ๊ท๋ชจ์ ์ฑ์ฅ์ ์์กดํ์ง ์๋ ์ฌ์ค์ ์ผ์ ํ "๋น์ฆ๋์ค ์ด์" ์๊ฐ๊ณผ ๋์ ๋๋ ์ฑ๋ฅ ์ฐจ์ด๋ฅผ ๋ณด์ผ ๊ฒ์ผ๋ก ์์๋ฉ๋๋ค.
์ต์
2๋ ์ผ์ ํ์ง๋ง ์ฝ๊ฐ ๋ ๋ฎ์ ์ฑ๋ฅ์ ๋ณด์ด๋ฉฐ, ์ต์
2~3์ ๋นํด ๊ฑฐ์ ์ ํํ ๋ ๋ฐฐ ๋ ๋์ต๋๋ค. ์ด๋ ์ด๋ก ๊ณผ ์ผ์นํ๊ธฐ ๋๋ฌธ์ ๋ง์กฑ์ค๋ฝ์ง ์์ ์ ์์ต๋๋ค. ์ด ์ต์
์์๋ HBase์์ ์
์ถ๋ ฅ ์์
์๊ฐ ์ ํํ ๋ ๋ฐฐ ๋ ๋ง์ต๋๋ค. ์ด๋ ๋ณธ ํ
์คํธ๊ฐ ์ด๋ก ์ ์ผ๋ก ์ฐ์ํ ์ ํ๋๋ฅผ ์ ๊ณตํ๋ค๋ ๊ฐ์ ์ ์ธ ์ฆ๊ฑฐ๊ฐ ๋ ์ ์์ต๋๋ค.
์ต์
1์ ๊ฐ์ฅ ๋๋ฆด ๊ฒ์ผ๋ก ์์๋๋ฉฐ, ๋คํธ์ํฌ ํฌ๊ธฐ์ ๋ฐ๋ผ ์น๊ตฌ ํ ๋ช
์ ์ถ๊ฐํ๋ ๋ฐ ์์๋๋ ์๊ฐ์ด ์ ํ์ ์ผ๋ก ์ฆ๊ฐํ๋ ๋ชจ์ต์ ๋ณด์
๋๋ค.
์ด์ ๋ ๋ฒ์งธ ํ
์คํธ์ ๊ฒฐ๊ณผ๋ฅผ ์ดํด๋ณด๊ฒ ์ต๋๋ค.

๋ณํ 3~5๋ ์์๋๋ก ๋คํธ์ํฌ ํฌ๊ธฐ์ ๊ด๊ณ์์ด ์์ ์๊ฐ์ผ๋ก ๋์ํฉ๋๋ค. ๋ณํ 1๊ณผ 2๋ ๋คํธ์ํฌ ํฌ๊ธฐ ์ฆ๊ฐ์ ๋ฐ๋ผ ์๊ฐ์ด ์ ํ์ ์ผ๋ก ์ฆ๊ฐํ๋ฉฐ ์ ์ฌํ ์ฑ๋ฅ์ ๋ณด์
๋๋ค. ๋์ฑ์ด ๋ณํ 2๋ ์ฝ๊ฐ ๋ ๋๋ฆฐ ๊ฒ์ผ๋ก ๋ํ๋ฌ์ต๋๋ค. ์ด๋ ์ถ๊ฐ ์ด "count"๋ฅผ ์ฝ๊ณ ์ฒ๋ฆฌํด์ผ ํ๊ธฐ ๋๋ฌธ์ธ ๊ฒ์ผ๋ก ๋ณด์ด๋ฉฐ, ์ด๋ n์ด ์ฆ๊ฐํจ์ ๋ฐ๋ผ ๋์ฑ ๋๋๋ฌ์ง๋๋ค. ํ์ง๋ง ์ด ๋น๊ต์ ์ ํ๋๊ฐ ์๋์ ์ผ๋ก ๋ฎ๊ธฐ ๋๋ฌธ์ ๊ฒฐ๋ก ์ ๋ด๋ฆฌ์ง๋ ์๊ฒ ์ต๋๋ค. ๋ํ, ์ด๋ฌํ ๋น์จ(๋ณํ 1๊ณผ 2 ์ค ์ด๋ ๊ฒ์ด ๋ ๋น ๋ฅธ์ง)์ ์ถ์ ์์ ๋ง๋ค (์ข
์์ฑ์ ๋ณธ์ง์ ์ ์งํ๋ฉด์๋) ๋ณ๊ฒฝ๋์์ต๋๋ค.
๋ง์ง๋ง ๊ทธ๋ํ๋ ์ ๊ฑฐ ํ ์คํธ์ ๊ฒฐ๊ณผ์ ๋๋ค.

์ฌ๊ธฐ์๋ ๋๋ ์ผ์ ์์ต๋๋ค. ์ต์
3~5๋ ์ ๊ฑฐ ์์
์ ์ผ์ ํ ์๊ฐ ์์ ์ํํฉ๋๋ค.
๊ฒ๋ค๊ฐ ํฅ๋ฏธ๋ก์ด ์ ์ ์ด์ ์๋๋ฆฌ์ค์ ๋ฌ๋ฆฌ ์ต์
4์ 5๋ ์ต์
3๋ณด๋ค ๋์ ๋๊ฒ ์ฑ๋ฅ์ด ์ฝ๊ฐ ๋จ์ด์ง๋ค๋ ๊ฒ์
๋๋ค. ํ ์ญ์ ์์
์ ์ผ๋ฐ์ ์ผ๋ก ๋
ผ๋ฆฌ์ ์ธ ์ด ์ญ์ ์์
๋ณด๋ค ๋น์ฉ์ด ๋ ๋ง์ด ๋๋ ๊ฒ์ผ๋ก ๋ณด์
๋๋ค.
์์๋๋ก ์ต์ 1๊ณผ 2๋ ์๊ฐ์ด ์ ํ์ ์ผ๋ก ์ฆ๊ฐํฉ๋๋ค. ๊ทธ๋ฌ๋ ์ต์ 2๋ ์นด์ดํธ ์ด์ "์ฒ๋ฆฌ"ํ๊ธฐ ์ํ ์ถ๊ฐ์ ์ธ ์ ์ถ๋ ฅ ์์ ์ผ๋ก ์ธํด ์ต์ 1๋ณด๋ค ์ง์์ ์ผ๋ก ๋๋ฆฝ๋๋ค.
์คํ์ ์ผ๋ฐ์ ์ธ ๊ฒฐ๋ก :
- ์ต์ 3~5๋ HBase๋ฅผ ํ์ฉํ๋ฏ๋ก ํจ์จ์ฑ์ด ๋ ๋์ต๋๋ค. ๊ทธ๋ฌ๋ ์ฑ๋ฅ์ ์ผ์ ํ๊ฒ ๋ค๋ฅด๋ฉฐ ๋คํธ์ํฌ ํฌ๊ธฐ์ ๋ฐ๋ผ ๋ฌ๋ผ์ง์ง ์์ต๋๋ค.
- ๋ณํ 4์ 5์ ์ฐจ์ด๋ ๊ธฐ๋ก๋์ง ์์์ต๋๋ค. ํ์ง๋ง ์ด๊ฒ์ด ๋ณํ 5๋ฅผ ์ฌ์ฉํด์๋ ์ ๋๋ค๋ ๊ฒ์ ์๋ฏธํ์ง๋ ์์ต๋๋ค. ํ ์คํธ ์คํ ๋์ ์ฑ๋ฅ ํน์ฑ์ ๊ณ ๋ คํ์ ๋, ์ฌ์ฉ๋ ์คํ ์๋๋ฆฌ์ค๊ฐ ์ฐจ์ด๋ฅผ ๋๋ฌ๋ด์ง ๋ชปํ์ ๊ฐ๋ฅ์ฑ์ด ๋งค์ฐ ๋์ต๋๋ค.
- ๋ฐ์ดํฐ๋ฅผ ์ฌ์ฉํ์ฌ "๋น์ฆ๋์ค ์ด์"์ ์ํํ๋ ๋ฐ ํ์ํ ์๊ฐ์ด ์ฆ๊ฐํ๋ค๋ ์ฌ์ค์ ์ด์ ์ ์ป์ ๋ชจ๋ ์ต์ ์ ๋ํ ์ด๋ก ์ ๊ณ์ฐ์ ์ ๋ฐ์ ์ผ๋ก ํ์ธ์์ผ ์ฃผ์์ต๋๋ค.
์ปคํผ์ฝ
์ด๋ฌํ ๋๋ต์ ์ธ ์คํ ๊ฒฐ๊ณผ๋ ์ ๋์ ์ธ ์ง๋ฆฌ๋ก ๋ฐ์๋ค์ฌ์๋ ์ ๋ฉ๋๋ค. ๊ณ ๋ ค๋์ง ์์ ์ฌ๋ฌ ์์ธ๋ค์ด ๊ฒฐ๊ณผ์ ์ํฅ์ ๋ฏธ์ณค์ผ๋ฉฐ, ํนํ ๋คํธ์ํฌ ๊ท๋ชจ๊ฐ ์์ ๊ทธ๋ํ์์ ์ด๋ฌํ ๋ณ๋์ด ๋๋๋ฌ์ง๊ฒ ๋ํ๋ฉ๋๋ค. ์๋ฅผ ๋ค์ด, happybase์์ ์ฌ์ฉํ๋ Thrift์ ์๋, ์ ๊ฐ ์์ฑํ Python ๋ก์ง์ ๊ตฌํ ๋ฐฉ์๊ณผ ์ฉ๋(์ฝ๋๊ฐ ์ต์ ์ผ๋ก ์์ฑ๋์๊ฑฐ๋ ๋ชจ๋ ๊ตฌ์ฑ ์์๋ฅผ ํจ์จ์ ์ผ๋ก ํ์ฉํ๋ค๊ณ ๋ ๋ณด์ฅํ ์ ์์ต๋๋ค), HBase ์บ์ฑ ๊ธฐ๋ฅ, ๊ทธ๋ฆฌ๊ณ ๋ฐฑ๊ทธ๋ผ์ด๋ ํ๋ ๋ฑ์ด ์ํฅ์ ๋ฏธ์ณค์ ์ ์์ต๋๋ค. Windows 10 ์ ๋ ธํธ๋ถ ๋ฑ์์ ํ์ธํ ๊ฒฐ๊ณผ, ์ ๋ฐ์ ์ผ๋ก ๋ชจ๋ ์ด๋ก ์ ๊ฐ์ ์ด ์คํ์ ์ผ๋ก ํ๋น์ฑ์ด ์ ์ฆ๋์๋ค๊ณ ๊ฒฐ๋ก ์ง์ ์ ์์ต๋๋ค. ์ ์ด๋, ์ด๋ฌํ ์ ๋ฉด ๊ณต๊ฒฉ์ผ๋ก๋ ๊ฐ์ ์ ๋ฐ๋ฐํ ์ ์์์ต๋๋ค.
๊ฒฐ๋ก ์ ์ผ๋ก HBase์์ ๋ฐ์ดํฐ ๋ชจ๋ธ์ ์ค๊ณํ๊ธฐ ์์ํ๋ ๋ชจ๋ ์ฌ๋์ ์ํ ๋ช ๊ฐ์ง ๊ถ์ฅ ์ฌํญ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค. ๊ด๊ณํ ๋ฐ์ดํฐ๋ฒ ์ด์ค ์์ ๊ฒฝํ์ ์ ์ด๋๊ณ "๊ณ๋ช "์ ๊ธฐ์ตํ์ธ์.
- ์ค๊ณ ์ ์ฃผ์ ์์ญ ๋ชจ๋ธ์ด ์๋ ์์ ๋ฐ ๋ฐ์ดํฐ ์กฐ์ ํจํด์์ ์งํํฉ๋๋ค.
- ํจ์จ์ ์ธ ์ก์ธ์ค(์ ์ฒด ํ ์ด๋ธ ์ค์บ ์์) - ํค๋ก๋ง ๊ฐ๋ฅ
- ๋น์ ๊ทํ
- ๊ฐ ํ์๋ ๊ฐ๊ธฐ ๋ค๋ฅธ ์ด์ด ํฌํจ๋ ์ ์์ต๋๋ค.
- ์ด์ ๋์ ๊ตฌ์ฑ
์ถ์ฒ : habr.com
