주된 개발 환경은 Python(Django)이며 필요한 곳에서는 Golang과 TypeScript를 활용하고 있습니다.
오늘은 쏘카일레클에서 가장 처음 유저들에게 사용 가능한 전기자전거들의 모습을 보여주는 클러스터링 기능에 대해서 간략하게 설명하고 이를 구현하고 있는 Golang(이하 Go언어)에 대해서 살펴보겠습니다.
최초 사용자가 바라보고 있는 화면에서 나타나는 기기들의 정보는 Django 모노리틱 서버에서 담당했습니다.
시간이 지남에 따라 가용 기기 대수가 늘어났고 실시간으로 사용자에게 사용 가능한 기기를 노출시켜야 했습니다. 유저가 화면을 움직이고 줌 레벨을 변경할 때 마다 서버를 조회했고, 그 결과 트래픽이 모노리틱 서버의 특정 엔드포인트에 몰리게 되어 서버 스케일아웃이 필요 이상으로 자주 발동하는 부작용이 생겼습니다. 고민 끝에 Python 만큼이나 간결한 문법을 가졌으면서도 강타입 컴파일 언어로 성능이 매우 뛰어난 Golang 서버로 기기 목록 조회 기능을 이관하게 되었습니다.
그렇게 쏘카일레클의 기기 목록을 담당하는 랜드 마커 서버가 탄생했습니다.
클라이언트 사이드 클러스터링
최초 Go언어로 변경된 기기 목록 서버(랜드 마커)에서는 클러스터링을 하지 않고 단순히 기기 목록을 전달해 주는 역할만 했습니다. 클라이언트 사이드(iOS, Android)에서는 각자의 언어로 기기들을 클러스터링하여 보여주는 로직을 구현하였습니다. 여기에는 다음과 같은 문제점이 존재했습니다.
- 불필요한 데이터의 전달: 단순히 기기의 위치 뿐만이 아니라 기기의 기타 정보가 포함된 데이터를 네트워크를 통해 전달하게 되면서 사용자의 데이터 사용량이 증가합니다.
- 기기의 자원 소모 증가: 전달 받은 기기들의 목록을 클라이언트 모바일에서 연산을 통해 클러스터링 하면서 사용자 기기의 배터리를 더 많이 소모하게 됩니다.
- 유지보수의 어려움: 줌 레벨에 따른 클러스터링 정도, 화면에서 보여주고자 하는 데이터가 변경되면 두 가지 모바일 플랫폼에서 모두 수정이 필요하며 이는 즉각적으로 변경이 가능한 서버에 비해서 여러가지 허들이 존재합니다.
이러한 문제점을 해결하고자 클러스터링을 서버사이드로 이관하는 작업을 시작하게 됩니다.
서버사이드 클러스터링
그런데… 어떻게 하지…?
클러스터링이란 개념과 지리 데이터라는 개념을 일레클에서 처음으로 접한 상태에서 개발을 시작하면서 여러가지 난관이 있었습니다.
- PostGIS의 클러스터링 함수 활용
쏘카일레클에서는 반납구역, 서비스 운영 구역, 기기들의 위치, 일레클 존, 거치대 등의 데이터를 유저들에게 전달하고 데이터 분석을 위해 PostGIS와 GeoDjango를 적극 활용하고 있습니다.
그리고 PostGIS에서는 기본적인 geospatial data의 연산을 지원하고 애플케이션 서버의 연산 속도 보다 DB에서의 연산이 훨씬 더 빠르기 때문에 처음 클러스터링 기능을 구현하기 위해서 생각했던 방식은 이러한 함수를 잘 활용해보자 였습니다. 실제로도도 클러스터링을 위한 기능을 제공하고 있습니다.
위의 내용을 참고하여 쿼리를 이용해 더미 데이터를 sql로 생성해서 위의 함수들을 실행해 보아도 원하는 대로 결과가 나오지 않았고 실행 시간 또한 5초 이상으로 매우 느렸습니다.
또한, DB의 쿼리를 이용해 클러스터링을 구현할 경우에 DB에 부하를 줄 여지가 있고 해당 쿼리와 GIS함수에 대한 이해 없이는 해당 기능에 대한 수정과 트러블 슈팅에서 병목으로 작용할 여지가 존재한다고 생각했습니다.
애플리케이션 클러스터링
위와 같은 문제를 겪으면서 애플리케이션 단에서 클러스터링을 구현하기로 하였고, 밀도 기반의 클러스터링이 사용자 화면에서의 클러스터링 문제를 해결하기에 더 적합하다고 판단하여 Go언어로 DBSCAN 알고리즘을 구현하기로 결정합니다.
DBSCAN 알고리즘이란?
- https://en.wikipedia.org/wiki/DBSCAN
- Density-based spatial clustering of applications with noise
- 밀도 기반으로 클러스터를 식별하고 노이즈(이상값)을 효과적으로 처리하는 알고리즘입니다. 다양한 모양과 크기의 클러스터를 찾는데 유용합니다.
DBSCAN 알고리즘은 2가지 요소(minPts, eps)에 따라서 서로 다른 클러스터링 결과를 반환하게 됩니다.
주요 용어
- eps: 두 포인트를 하나의 클러스터로 볼 기준이 되는 거리. 즉 두개의 포인트 사이의 거리가 eps보다 작을 경우 두 포인트는 하나의 클러스터에 포함할 수 있습니다.(minPts가 2이상일 경우에)
- minPts: eps안에 최소 몇 개의 포인트를 포함할지 여부.(만일 eps가 10이고 minPts가 5일 때, 4개의 포인트가 서로의 간격이 10보다 작더라도 이는 클러스터로 취급하지 않습니다.)
- 노이즈: 어떤 클러스터에도 포함되지 않는 데이터입니다.
알고리즘 수행 단계
- 모든 데이터는 방문하지 않은 상태로 시작
- 주어진 데이터(포인트) 중 하나를 선택하여 방문
- 선택한 포인트의 반경 eps안에 minPts 이상이면 클러스터를 확장, 이하라면 노이즈로 간주합니다.
- 모든 포인트를 방문할 때 까지 위의 과정을 반복합니다.
클러스터링에 대해서 알아보기 전에 쏘카일레클에서 왜 기존 언어 스택인 Python이 아닌 Go언어를 선택했을까요?
우선 쏘카일레클 백엔드 팀원들은 모두 Python에는 익숙하지만, 다른 언어에 대한 경험과 숙련도는 저마다 차이가 있는 상태라는 것을 고려해야 했습니다.
또한 Python은 현재 GIL로 인해 멀티 쓰레드의 장점을 활용하기 어렵고 추후 랜드 마커의 기능과 성능에서 더 많은 가능성을 열어두기 위해서 멀티 쓰레드를 지원하는 언어를 고민하고 있었습니다.
결국 jvm계열 언어나 Go언어를 두고 고민이 시작되었는데요. 성능과 개발 편의성, 유지 보수등을 고려했을 때, 문법이 간단하고 암시적 인터페이스를 지원하는 Go언어를 최종 선택하게 되었습니다.
Go언어
Go언어를 사용하면서 느낀점은 Go 언어는 불필요한 라이브러리의 사용을 지양하고 스탠다드 라이브러리를 이용하여 구현하는 방식을 지향하고 있다는 것입니다.
또한 문법이 간단하고 인터페이스가 암시적으로 구현되어져 있어 인터페이스를 이용한 약결합 상태를 유지하기 쉽게 되어 있습니다.
package main
import "fmt"
type I interface {
M()
}
type T struct {
S string
}
// This method means type T implements the interface I,
// but we don't need to explicitly declare that it does so.
func (t T) M() {
fmt.Println(t.S)
}
func main() {
var i I = T{"hello"}
i.M()
}또한, 강타입 컴파일 언어이고 Python으로 개발할 때는 추가적으로 설치하고 설정해 주어야 했던 린팅, 포매팅, 정적 타입체킹 들등의 기능을 컴파일러가 제공하기 때문에 개발자는 Go 개발 환경을 구축하기가 매우 쉽고, 일관된 환경에서 작업할 수 있습니다.
언어 자체에서 테스트 코드와 벤치마킹 기능을 제공하기 때문에 pytest와 같은 추가적인 라이브러리의 설치가 불필요한 점도 큰 장점이라고 생각합니다.
이제는 Go언어를 처음으로 사용하면서 느꼈던 어려움에 대해서도 얘기해 보겠습니다.
간결하지만 이상해 보이는 문법
처음 Go언어의 문법을 보았을 때 느꼈던 점은, “뭔가 이상한데…” 였습니다.
Go언어는 소위 클래스와 같은 개념을 구조체(struct)로 표현하는데 Java, Python등의 기타 언어와는 달리 구조체에 대해 선언하는 함수를 리시버 함수라고 부르며, 구조체 코드블록의 밖에서 표현하게 됩니다.
type Bike struct {
ID int64
}
func (b Bike) startRiding() {
fmt.Println("start riding")
}- 개인적인 의견으로는 인터페이스가 암시적 이기 때문에 구조체가 인터페이스를 구현하더라도 struct 의 {} 범위 안에서 수정이 이루어질 필요가 없게 하기 위함이 아닐까 싶습니다.
type Bike interface {
startRiding()
}
type FranchiseBike struct {
}
// 아래의 함수를 선언함으로써 FranchiseBike는 Bike 인터페이스의 구현하게 됩니다.
// 이제 Bike를 사용하는 모든 곳에서 FranchiseBike는 동일하게 사용할 수 있습니다.
func (f FranchiseBike) startRiding() {
//TODO implement me
panic("implement me")
}
// 만일 FranchiseBike가 또 다른 인터페이스를 구현하려면 어떻게 해야 할까요?포인터와 Value
포인터는 값이 저장된 메모리의 위치 값을 가지고 있는 변수입니다.
Go에서는 메서드에 기본적으로 포인터를 넘겨주지 않는다면 모든 값을 복사하여 넘겨주게 됩니다.
그렇다면 어떨 때 포인터를 사용해야 할까요? https://google.github.io/styleguide/go/decisions#receiver-type
간략하게는 아래의 규칙을 적용할 수 있습니다.
포인터
- 구조체가 담고있는 데이터가 매우 크다.
- 구조체가 가지고 있는 값의 복사가 안전하지 않다.(sync.Mutex)
- 구조체의 값을 변경해주어야 할 경우.
Value
- 단순히 plain data를 사용할 경우
랜드 마커에서는 DB 커넥션들을 관리하는 repository의 경우 포인터를 활용하고 있습니다.
명시적인 에러의 반환
Go에서는 try-catch가 존재하지 않습니다.
빌트인 라이브러리에서 부터 명시적으로 에러를 반환해주고 있고 자연스럽게 강제적으로 모든 에러를 명시적으로 핸들링 하도록 합니다.
if err != nil {
...
}스택 트레이스의 부재
기본적으로 Go에서 에러 타입은 아래와 같이 단순히 Error 메서드를 구현하기만 하면 됩니다.
// The error built-in interface type is the conventional interface for
// representing an error condition, with the nil value representing no error.
type error interface {
Error() string
}그러다 보니 자연스럽게 에러가 반환되어도 호출 스택에 대한 정보가 누락되어 있습니다.
이는 Go의 설계 철학과 언어의 간결함에 기인하여 코드의 가독성을 높이고 디버깅을 쉽게 만들기 위함입니다.
그럼에도 불구하고 스택트레이스의 정보를 포함하고 싶을 경우에는 https://github.com/pkg/errors 를 이용하여 스택 정보를 추가할 수 있습니다. 쏘카일레클에서는 해당 패키지를 이용하여 Sentry와 Datadog에 리포트 시에 스택 정보를 볼 수 있도록 하고 있습니다.
테스트 코드와 벤치 마킹
Go 언어에서는 아래와 같이 테스트 코드와 벤치마크 코드를 작성할 수 있습니다.
xxx_test.go: xxx파일을 테스트 하는 코드를 작성하게 되고 해당 파일은 테스트 파일로 인식하게 됩니다.
func TestAFunc(t *testing.T) {} // 테스트 코드를 작성합니다.
func BenchmarkAFunc(b *testing.B) {} // 성능 테스트를 위한 벤치마킹 코드를 작성합니다.쏘카일레클에서는 클러스터링 기능을 테스트하고 벤치마킹하는 코드를 다음과 같이 작성하여 사용하고 있습니다.
// 전체 클러스터링 로직을 간략하게 표현하면 다음과 같습니다.
// 하나의 클러스터에는 바이크 데이터가 slice형태로 담겨있게 됩니다.
type Cluster []model.ClusterBikeModel
// 클러스터링에 마커 위치, 클러스터링 유무, 클러스터링 개수, 담겨있는 바이크들의 정보를 담고 있는 구조체
type MarkerCluster struct {
Location types.Vec2 `json:"marker_location" swaggertype:"array,integer"`
IsCluster bool `json:"is_cluster"`
Count int `json:"count"`
Cluster []model.ClusterBikeModel `json:"cluster" swaggertype:"array,object"`
}
// 주어진 바이크를 minPts와 eps를 기준으로 하여 클러스터링합니다.
func Clusterize(bikes []model.ClusterBikeModel, minPts int, eps float64) []Cluster {
// 클러스터링 로직
// 주어진 바이크들을 순차적으로 탐색하면서 eps 범위안에 바이크가 minPts개 이상이 존재한다면 클러스터링합니다.
}
// 클러스터링에는 바이크들만 담겨 있기 때문에 지도에 표현할 마커의 위치와 바이크 정보를 정렬합니다.
func AddMarkerOnCluster(clusters []Cluster) []MarkerCluster {
var sumX, sumY float64
markerClusters := make([]MarkerCluster, 0)
for _, cluster := range clusters {
sumX = 0
sumY = 0
mc := MarkerCluster{}
mc.Count = len(cluster)
if len(cluster) == 1 { // noise
mc.IsCluster = false
mc.Location = cluster[0].GetVectorPoint()
mc.Cluster = cluster } else {
for _, bike := range cluster {
sumX += bike.GetVectorPoint().X
sumY += bike.GetVectorPoint().Y
}
avgX := sumX / float64(len(cluster))
avgY := sumY / float64(len(cluster))
mc.Location = types.Vec2{X: avgX, Y: avgY}
mc.IsCluster = true
mc.Cluster = cluster
} markerClusters = append(markerClusters, mc)
}
return markerClusters위의 코드를 Go언어에서 기본적으로 제공하는 테스트와 벤치마킹으로 확인해 보겠습니다.
package service
import (
"fmt"
"landmarker-api/domain/model"
"landmarker-api/domain/types"
"math/rand"
"testing"
"time"
)
// 테스트 시에 랜덤으로 생성할 바이크의 위경도 범위를 지정합니다.
const (
seoulLatMin = 37.426190 // 서울 위도 최소값
seoulLatMax = 37.701046 // 서울 위도 최대값
seoulLngMin = 126.764503 // 서울 경도 최소값
seoulLngMax = 127.183701 // 서울 경도 최대값
maxPoint = 200000 // 최대로 만들어낼 바이크 구조체의 개수
start = 0.1 // 100 미터
end = 10.0 // 10 km
)
// 주어진 max 개수만큼 바이크 포인터를 생성합니다.
func makeBikePoints(max int) []model.ClusterBikeModel {
rand.Seed(42)
bikes := make([]model.ClusterBikeModel, 0)
for i := 0; i < max; i++ {
lat := rand.Float64()*(seoulLatMax-seoulLatMin) + seoulLatMin
lng := rand.Float64()*(seoulLngMax-seoulLngMin) + seoulLngMin
location := types.Point{
P: types.Vec2{X: lng, Y: lat},
} bikes = append(bikes, model.ServiceBike{Bike: model.Bike{ID: uint(i), Location: location}})
} return bikes
}
// 사용자가 줌 레벨을 변경함에 따라서 eps값이(클러스터링의 기준을 판단하는 값, 두 포인터의 거리 차가 해당 값 이하일 경우 클러스터링의 대상으로 판단) 변경되기 때문에 이를 테스트 하기 위해 랜덤으로 eps를 생성합니다.
func makeRandomEps(start, end float64) float64 {
rand.Seed(time.Now().UnixNano())
return rand.Float64()*(end-start) + start
}
// 랜덤으로 생성한 바이크를 클러스터링합니다.
func makeCluster() []Cluster {
bikes := makeBikePoints(maxPoint)
return Clusterize(bikes, 2, makeRandomEps(start, end))
}
// 1개의 클러스터링에 바이크가 유일하게 존재하는지 확인합니다.
func isBikeUnique(bikes []model.ClusterBikeModel) bool {
seen := make(map[uint]bool)
for _, bike := range bikes {
if seen[bike.GetID()] {
return false
}
seen[bike.GetID()] = true
}
return true
}
// Test코드를 작성합니다.
func TestClusterize(t *testing.T) {
// 테이블 드리븐 테스트 방식을 사용하기 위해서 원하는 테스트 결과와 테스트 시에 사용할 데이터를 선언합니다.
tests := []struct {
want int
bikes []model.ClusterBikeModel
}{
{100, makeBikePoints(100)},
{1_000, makeBikePoints(1_000)},
{3_000, makeBikePoints(3_000)},
{5_000, makeBikePoints(5_000)},
{7_000, makeBikePoints(7_000)},
{10_000, makeBikePoints(10_000)},
{15_000, makeBikePoints(15_000)},
{20_000, makeBikePoints(20_000)},
{50_000, makeBikePoints(50_000)},
{100_000, makeBikePoints(100_000)},
{200_000, makeBikePoints(200_000)},
}
for _, tt := range tests {
randomEps := makeRandomEps(start, end)
testName := fmt.Sprintf("eps %f, before cluster bike count %d, after cluster bike count %d", randomEps, tt.want, len(tt.bikes))
t.Run(testName, func(t *testing.T) {
clusters := Clusterize(tt.bikes, 2, randomEps)
afterBikeCount := 0
for _, cluster := range clusters {
afterBikeCount += len(cluster)
isUnique := isBikeUnique(cluster)
if !isUnique {
t.Errorf("cluster에 중복 데이터가 존재합니다.")
} } if tt.want != afterBikeCount {
t.Errorf("got %d, want %d", afterBikeCount, tt.want)
}
}) }}
func BenchmarkClusterize(b *testing.B) {
for i := 0; i < b.N; i++ {
bikes := makeBikePoints(maxPoint)
Clusterize(bikes, 2, makeRandomEps(start, end))
}}
func BenchmarkAddMarkerOnCluster(b *testing.B) {
cluster := makeCluster()
for i := 0; i < b.N; i++ {
AddMarkerOnCluster(cluster)
}}위의 테스트 코드를 이용해 1차적으로 테스트를 하여 클러스터링 이전과 이후에 데이터의 손실이 없고 중복된 데이터가 클러스터되지 않음을 확인했습니다.
실제로는 클라이언트의 줌 레벨에 따른 eps의 적절한 값을 찾기 위해 실제 앱 화면을 살펴보면서 적절한 값을 찾아 나갔습니다.
// GetDynamicEPS 줌 레벨에 따른 적절한 eps를 반환한다. (Km)
func GetDynamicEPS(mapZoomLevel float64) float64 {
if (X값) < mapZoomLevel && mapZoomLevel <= (Y값) {
return (EPS값)
} else if (X값) < mapZoomLevel && mapZoomLevel < (Y값) {
return (EPS값)
} else if (X값) <= mapZoomLevel && mapZoomLevel < (Y값) {
return (EPS값)
} else if (X값) <= mapZoomLevel && mapZoomLevel < (Y값) {
return (EPS값)
} else if (X값) <= mapZoomLevel && mapZoomLevel < (Y값) {
return (EPS값)
}
return (EPS값)
}결과는 다음과 같습니다.
끝으로
아직 많은 개선점을 가지고 있어 지속적으로 개선해 나아가야 하겠지만, 해당 프로젝트를 진행하면서 Go언어에 대해서 조금 더 알게 되어서 뜻깊고 즐거운 시간이었습니다.
나인투원의 백엔드 개발팀은 쏘카일레클과 쏘카의 전기자전거, 그리고 티머니GO와 같은 제휴채널측에 안정적인 성능 기반의 서비스를 제공하기 위해 다양한 기술을 사용하고 있고, 또 사용할 준비가 되어 있는 도전적인 팀입니다.
쏘카일레클의 백엔드에 관심이 있으시다면 아래 링크를 참고해주세요.
- 채용 공고는 추후 추가될 예정입니다.
감사합니다.
