How to shuffle songs?
http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/
요약:
random이란? 정말로 랜덤하게 음악을 섞어서 보여주는것
Fisher-Yates shuffle
그러나 실 사용자들은 랜덤을 그렇게 받아들이지 않는다. 예를 들어 같은 가수의 음악이 연속으로 들린다면 사용자들은 랜덤이 아니라고 여긴다.
사용자가 랜덤이라고 느낄 수 있도록 알고리즘을 수정할 필요가 있다.
Martin Fiedler 라는 사람의 The art of shuffling music 라는 블로그 내용이 있다. 앞에서 말한 문제를 해결해주는 알고리즘이지만 너무 복잡하다.
이에 따라 여기에 Floyd-Steinberg dithering 같은 알고리즘을 써서 같은 종류로 구분되는(예를 들면 같은 작곡가 또는 같은 가수) 음악을 흐트려 놓는 수정을 가하였다.
2014년 3월 11일 화요일
2014년 3월 2일 일요일
Pinterest에서의 ZooKeeper의 SPOF문제 해결하기
ZooKeeper Resilience at Pinterest
http://engineering.pinterest.com/post/77933733851/zookeeper-resilience-at-pinterest
=> 위 내용에의 요약
* ZooKeeper도 fail 할 수 있다.
Too many connections
Too many transactions
Protocol bugs
Human errors
Network partitions
* ZooKeeper의 SPOF를 해결하기 위한 초기 방법
- Add capacity
- Add observers: vote에는 관여하지 않는 ZooKeeper host를 두는 것. vote는 하지 않지만 watch등 다른 것은 가능하게 한다(proxy).
- Use multiple ZooKeeper clusters for isolation
- Fallback to static files: ZooKeeper가 죽으면 static host file과 configuration file을 사용한다.
* Decouple out applications from ZooKeeper
개개의 머신에 있는 daemon이 ZooKeeper에 접속하여 watch하고 data를 받아와서 로컬에 저장한다. 각가의 application들은 로컬에 있는 data를 사용한다.
http://engineering.pinterest.com/post/77933733851/zookeeper-resilience-at-pinterest
=> 위 내용에의 요약
* ZooKeeper도 fail 할 수 있다.
Too many connections
Too many transactions
Protocol bugs
Human errors
Network partitions
* ZooKeeper의 SPOF를 해결하기 위한 초기 방법
- Add capacity
- Add observers: vote에는 관여하지 않는 ZooKeeper host를 두는 것. vote는 하지 않지만 watch등 다른 것은 가능하게 한다(proxy).
- Use multiple ZooKeeper clusters for isolation
- Fallback to static files: ZooKeeper가 죽으면 static host file과 configuration file을 사용한다.
* Decouple out applications from ZooKeeper
개개의 머신에 있는 daemon이 ZooKeeper에 접속하여 watch하고 data를 받아와서 로컬에 저장한다. 각가의 application들은 로컬에 있는 data를 사용한다.
2014년 3월 1일 토요일
애플 iMessage의 보안 설명
Apple Explains Exactly How Secure iMessage Really Is
http://techcrunch.com/2014/02/27/apple-explains-exactly-how-secure-imessage-really-is/
=> 간단 요약
iMessage의 동작 방식
1. iMessage를 처음 사용하면 두개의 private/public key 셋을 만든다.
2. private key는 디바이스에 놔두고(나중에 decrypt에 사용) public key는 애플의 서버에 보낸다.
3. 내 친구가 나와 채팅하고자 하면 친구의 장비는 내 public key를 애플 서버로부터 받아온다. 친구가 메시지를 작정하고 send를 하면 받아온 public key로 encrypt를 한 후 내보낸다.
4. 각각의 메시지별로 암호화가 된다. 예를 들어 내가 아이폰과 아이패드를 가지고 있다면 나는 아이폰용 pri/pub key 셋, 아이패드용 pri/pub key 셋을 가지고 있을 것이므로 각각의 장비별로 암호화된 후 보내진다.
5. timestamp나 APN routing data같은 일부분의 데이타는 암호화하지 안는다.
6. 암호화된것과 암호화되지 않은 전체를 모아 또 암호화를 한다.
7. 사진이나 긴 메시지같은 양이 큰 경우: 랜덤 키를 만들어 사진을 이것으로 암호화한다. 그리고 암호화된 사진을 애플의 서버에 저장한다(URI). 키와 사진의 URI를 암호화하여 보내고자 하는 쪽에 전달한다. 받은 쪽은 URI에서 사진을 받아온 후 키로 복호화하여 사진을 볼 수 있게 된다.
8. 사용자가 메시지를 받으면 애플을 서버에서 메시지를 지운다. 받아가지 않는 경우 최대 7일동안 저장한다.
http://techcrunch.com/2014/02/27/apple-explains-exactly-how-secure-imessage-really-is/
=> 간단 요약
iMessage의 동작 방식
1. iMessage를 처음 사용하면 두개의 private/public key 셋을 만든다.
2. private key는 디바이스에 놔두고(나중에 decrypt에 사용) public key는 애플의 서버에 보낸다.
3. 내 친구가 나와 채팅하고자 하면 친구의 장비는 내 public key를 애플 서버로부터 받아온다. 친구가 메시지를 작정하고 send를 하면 받아온 public key로 encrypt를 한 후 내보낸다.
4. 각각의 메시지별로 암호화가 된다. 예를 들어 내가 아이폰과 아이패드를 가지고 있다면 나는 아이폰용 pri/pub key 셋, 아이패드용 pri/pub key 셋을 가지고 있을 것이므로 각각의 장비별로 암호화된 후 보내진다.
5. timestamp나 APN routing data같은 일부분의 데이타는 암호화하지 안는다.
6. 암호화된것과 암호화되지 않은 전체를 모아 또 암호화를 한다.
7. 사진이나 긴 메시지같은 양이 큰 경우: 랜덤 키를 만들어 사진을 이것으로 암호화한다. 그리고 암호화된 사진을 애플의 서버에 저장한다(URI). 키와 사진의 URI를 암호화하여 보내고자 하는 쪽에 전달한다. 받은 쪽은 URI에서 사진을 받아온 후 키로 복호화하여 사진을 볼 수 있게 된다.
8. 사용자가 메시지를 받으면 애플을 서버에서 메시지를 지운다. 받아가지 않는 경우 최대 7일동안 저장한다.
페이스북에서의 사진 캐싱에 대하여
An analysis of Facebook photo caching
https://code.facebook.com/posts/220956754772273/an-analysis-of-facebook-photo-caching
=> 위 내용에의 요약
사진의 사용에는 네부분의 캐싱이 있다.
Browser cache -> Edge cache -> Origin cache -> Haystack(Backend)
Browser cache: 사용자가 사진을 봤다면 브라우저의 캐시(로컬)에 저장될 것이다.
Edge cache: 브라우저의 캐시에 사진이 없다면 CDN이나 edge cache로 사진을 요청한다. edge cache는 internet points of presence(PoPs)에 위치해 있다.
Origin cache: 여러 data center에 위치해 있는 하나의 캐시이다. 사진의 id 기준으로 캐시하고 있기 때문에 같은 사진을 요청하는 경우에는 항상 같은 서버에 요청하게 된다.
Haystack: 실제 사진을 저장하고 있는 backend store. origin cache는 같은 data center에 있는 haystack에게 사진을 요청한다(만약 같은 data center에 있는 haystack이 죽었다면 다른 data center에 있는 haystack에게 요청한다.).
사진에 대한 hit ratio를 확인해 보니 haystack으로 가는 request는 9.9%정도 밖에 되지 않았다.
그래도 이걸 또 향상시켜 보자.
1. 캐시의 양을 증가시킨다.
=> 인기가 많은 사진의 경우 brower cache와 edge cache에서 중요한 역할을 하고 인기가 적은 사진의 경우 origin이나 backend에서 중요하다.
2. 캐싱 알고리즘의 변경
많이 사용되는 캐싱 알고리즘으로 FIFO, LRU, LFU, S4LRU가 있다. 우리의 테스트에서 S4LRU가 가장 성능이 좋게 나왔다.
papger: http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf
https://code.facebook.com/posts/220956754772273/an-analysis-of-facebook-photo-caching
=> 위 내용에의 요약
사진의 사용에는 네부분의 캐싱이 있다.
Browser cache -> Edge cache -> Origin cache -> Haystack(Backend)
Browser cache: 사용자가 사진을 봤다면 브라우저의 캐시(로컬)에 저장될 것이다.
Edge cache: 브라우저의 캐시에 사진이 없다면 CDN이나 edge cache로 사진을 요청한다. edge cache는 internet points of presence(PoPs)에 위치해 있다.
Origin cache: 여러 data center에 위치해 있는 하나의 캐시이다. 사진의 id 기준으로 캐시하고 있기 때문에 같은 사진을 요청하는 경우에는 항상 같은 서버에 요청하게 된다.
Haystack: 실제 사진을 저장하고 있는 backend store. origin cache는 같은 data center에 있는 haystack에게 사진을 요청한다(만약 같은 data center에 있는 haystack이 죽었다면 다른 data center에 있는 haystack에게 요청한다.).
사진에 대한 hit ratio를 확인해 보니 haystack으로 가는 request는 9.9%정도 밖에 되지 않았다.
그래도 이걸 또 향상시켜 보자.
1. 캐시의 양을 증가시킨다.
=> 인기가 많은 사진의 경우 brower cache와 edge cache에서 중요한 역할을 하고 인기가 적은 사진의 경우 origin이나 backend에서 중요하다.
2. 캐싱 알고리즘의 변경
많이 사용되는 캐싱 알고리즘으로 FIFO, LRU, LFU, S4LRU가 있다. 우리의 테스트에서 S4LRU가 가장 성능이 좋게 나왔다.
papger: http://www.cs.cornell.edu/~qhuang/papers/sosp_fbanalysis.pdf
2014년 2월 28일 금요일
Mozilla에서 차세대 브라우저로 개발중인 Servo에 대한 소개
Servo: Inside Mozilla's mission to reinvent the web browser for the nulti-core age
http://www.zdnet.com/servo-inside-mozillas-mission-to-reinvent-the-web-browser-for-the-multi-core-age-7000026606/
=> 위 내용에 대한 요약
Servo는 기존의 브라우저들의 단점을 극복하기 위해 완전히 밑바닥부터 개발되고 있는 차세대 브라우저이다. 모질라와 삼성에 의해 개발되고 있다.
현재 주 브라우저들은 쓰레드나 멀티프로세싱을 하긴 하지만 많은 작업을 sequential하게 진행한다. 주로 layout -> rendering -> javascript 의 순이라고 보면 된다. Servo는 이 세작업을 각각의 task로 분리하여 동시에 동작시킨다.
물론 serialisation을 피할 수 없는 것도 있기 때문에 이러한 것들은 sequential하게 동작할 수 밖에 없다. 하지만, 독립적으로 할 수 있는 많은 것들(윈도우를 resize한다던지 또는 iframe의 경우라던지)이 있다. layout의 경우도 tree형태로 동작함으로서 순차적으로 진행해야 하지만 이것을 벗어나 독립적으로 동작시킬 수 있는 것도 있다. Servo는 이것을 기존의 브라우저들보더 더 강하게 parallel layout을 시도한다.
Servo는 Rust를 개발언어로 사용하기 때문에 C/C++에서와 같은 메모리 문제를 발생시키지 않는다. 이것은 보안에 매우 큰 이점을 가진다. Rust는 task 사이에 메모리를 공유하지 않고 서로간에 메시지로 통신하기 때문에 data 공유의 문제가 발생하지 않는다.
http://www.zdnet.com/servo-inside-mozillas-mission-to-reinvent-the-web-browser-for-the-multi-core-age-7000026606/
=> 위 내용에 대한 요약
Servo는 기존의 브라우저들의 단점을 극복하기 위해 완전히 밑바닥부터 개발되고 있는 차세대 브라우저이다. 모질라와 삼성에 의해 개발되고 있다.
현재 주 브라우저들은 쓰레드나 멀티프로세싱을 하긴 하지만 많은 작업을 sequential하게 진행한다. 주로 layout -> rendering -> javascript 의 순이라고 보면 된다. Servo는 이 세작업을 각각의 task로 분리하여 동시에 동작시킨다.
물론 serialisation을 피할 수 없는 것도 있기 때문에 이러한 것들은 sequential하게 동작할 수 밖에 없다. 하지만, 독립적으로 할 수 있는 많은 것들(윈도우를 resize한다던지 또는 iframe의 경우라던지)이 있다. layout의 경우도 tree형태로 동작함으로서 순차적으로 진행해야 하지만 이것을 벗어나 독립적으로 동작시킬 수 있는 것도 있다. Servo는 이것을 기존의 브라우저들보더 더 강하게 parallel layout을 시도한다.
Servo는 Rust를 개발언어로 사용하기 때문에 C/C++에서와 같은 메모리 문제를 발생시키지 않는다. 이것은 보안에 매우 큰 이점을 가진다. Rust는 task 사이에 메모리를 공유하지 않고 서로간에 메시지로 통신하기 때문에 data 공유의 문제가 발생하지 않는다.
2014년 2월 20일 목요일
드랍 박스에서의 비디오 변환
Video Processing at Dropbox
https://tech.dropbox.com/2014/02/video-processing-at-dropbox/
* 비디오 관련 문제점
1. 다양한 종류의 코덱이 있다.
2. 네트워크 상태가 사용자에 따라 다르다.
3. 사용자가 사용는 장비의 성능이 제각각이다.
=> 위 문제 해결을 위해 소스 비디오를 사용자의 장비에 맞는 형태로 변경(transcode)한다.
초기에는 사용자가 비디오를 올리면 올리자마자 바로 모든 장비에서 볼 수 있도록 변경을 해주었는데 이것은 적합하지 않았다. 그래서 사용자의 요청이 있을 때 변경해서 보여주는 형태로 바꾸었다.
* 구현
HTTP Live Streaming 사용: 사용자의 환경에 맞는 다른 bit rate의 비디오를 선택하여 재생할 수 있도록 해주는 장점이 있다.
한번 transcoding되고 나면 cache를 사용 한다.-> 물론 사용자의 패턴에 따른 적당한 retention 정책으로 유지한다.
transcoding중에는 사용자가 transcoding worker에서 비디오를 받아올 수 있도록 한다.
transcoding에 ffmpeg를 사용: fast start도 사용
비디오를 쪼개는 데(segment)에는 애플에서 제공하는 것과 ffmpeg에 있는 것이 있는데 모두 우리에게 맞지 않아서 직접 개발했다.
segment의 크기는 latency(round trip과 transmission time을 고려)를 줄이기 위해 작은 사이즈로부터 5초까지 증가시킨다. 실제로 segment는 처음에 2s, 2s, 3s, 3s, 4s, 4s, 5s ... 의 형태로 증가한다.
그래도 latency가 불만족스러워 이를 더 줄이기 위해 비디오의 처음 몇초는 아예 미리 transcoding하였다.
https://tech.dropbox.com/2014/02/video-processing-at-dropbox/
* 비디오 관련 문제점
1. 다양한 종류의 코덱이 있다.
2. 네트워크 상태가 사용자에 따라 다르다.
3. 사용자가 사용는 장비의 성능이 제각각이다.
=> 위 문제 해결을 위해 소스 비디오를 사용자의 장비에 맞는 형태로 변경(transcode)한다.
초기에는 사용자가 비디오를 올리면 올리자마자 바로 모든 장비에서 볼 수 있도록 변경을 해주었는데 이것은 적합하지 않았다. 그래서 사용자의 요청이 있을 때 변경해서 보여주는 형태로 바꾸었다.
* 구현
HTTP Live Streaming 사용: 사용자의 환경에 맞는 다른 bit rate의 비디오를 선택하여 재생할 수 있도록 해주는 장점이 있다.
한번 transcoding되고 나면 cache를 사용 한다.-> 물론 사용자의 패턴에 따른 적당한 retention 정책으로 유지한다.
transcoding중에는 사용자가 transcoding worker에서 비디오를 받아올 수 있도록 한다.
transcoding에 ffmpeg를 사용: fast start도 사용
비디오를 쪼개는 데(segment)에는 애플에서 제공하는 것과 ffmpeg에 있는 것이 있는데 모두 우리에게 맞지 않아서 직접 개발했다.
segment의 크기는 latency(round trip과 transmission time을 고려)를 줄이기 위해 작은 사이즈로부터 5초까지 증가시킨다. 실제로 segment는 처음에 2s, 2s, 3s, 3s, 4s, 4s, 5s ... 의 형태로 증가한다.
그래도 latency가 불만족스러워 이를 더 줄이기 위해 비디오의 처음 몇초는 아예 미리 transcoding하였다.
2014년 2월 18일 화요일
페이스북 로그인 연동하기 - web
여기서는 웹 서비스 개발시 로그인을 할 때 페이스북 로그인과의 연동을 어떻게 할 수 있는지를 알아보자.
(참조: https://developers.facebook.com/docs/facebook-login/manually-build-a-login-flow/)
1. 페이스북에서 app을 만들어서 App ID(=Client ID)와 App secret(=Client Secret)을 발급받는다.
2. Authorization을 위해 "https://graph.facebook.com/oauth/authorize" 로 redirect한다.
이 때 get을 사용하며 parameter로 아래의 값을 넣어준다.
client_id: 페이스북에 app을 만들면 생성되는 값
redirect_uri: 페이스북으부터 되돌아오기 위한 url 이자 두번째 단계를 실행하기 위한 url
scope: 사용자에게 요청할 퍼미션 리스트
response_type: response data를 어디에 넣을 것인지 선택
state: CSRF를 방지하기 위해 생성한 unique string. 다음번 access token 단계에서 여기에서 넣어준 state값과 같은 state가 넘어왔는지를 보고 제대로 된 단계를 진행하고 있는 것인지 확인한다.
예를 들면 아래와 같은 URL이 될 것이다.
https://graph.facebook.com/oauth/authorize?client_id=1234567890&redirect_uri=http://yoursite.com/authenticate/&scope=email&response_type=code&state=djkfgj3kfjg-23jfjgjg-32jfjgj4--djfjgkf
위의 예 URL에 한 내용은 아래와 같다.
client_id는 페이스북에서 app을 만들면 생성되는 값을 넣어주고 redirect_uri는 페이스북에서 authorize가 처리되고 나면 redirect줄 url을 넣어준 것이다. scope는 간단하게 email로 설정해 주었고 response_type은 url에 parameter로 넘어오도록 code로 해준 것이고 state는 UUID.randomUUID() 을 사용해서 random number를 만들어낸 것이다.
로컬에서의 테스트를 위해 redirect_uri에 localhost를 넣어주면 redirect관련 에러가 발생한다. 이 경우는 페이스북 앱의 설정(Settings)에서 App Domains에 localhost 를 넣어주고 Site URL에 사용할 주소를 넣어준다(내 경우는 다음과 같이 넣어주었다: http://localhost:9000).
3. 2에서 사용자가 정상적으로 access를 허락하면 페이스북에서는 내가 넣어준 redirect uri로 redirect시켜준다. 여기서 access token을 가져오기 위한 작업을 한다.(서버에서 바로 http로 페이스북 access token url에 접속한다.)
정상적이라면 redirect시 파라메터에 state와 code 값이 넘어온다. state값이 정상적인 값(2에서 넣어준 값)인지 확인한다.
이제 access token을 얻어오기 위해 "https://graph.facebook.com/oauth/access_token" 에 요청을 한다. 이때 넘겨주는 parameter는 다음과 같다.
client_id: 페이스북 앱 생성시 생성되는 값
redirect_uri: OAuth 프로세스를 시작한 request_uri
client_secret: 페이스북 앱 생성시 생성되는 값
code: redirect시 받은 값
위의 요청을 하면 accesss_token 과 expires를 response로 준다. 여기까지 에러 없이 진행되었으면 인증 완료된 것이다.
에러의 경우 error 파라메터로 에러를 넘겨주므로 이 파라메터가 있는지 항상 확인해야 한다.
"access_denied"와 "redirect_uri_mismatch"등의 에러 내용이 있다.
4. 이제 사용자 정보를 요청한다. url은 "https://graph.facebook.com/me" 이다.
요청할 때 parameter로 access_token과 fields를 넣어준다.
fields는 요청할 사용자 정보이다:(예: id,name,last_name,username,,email,)
페이스북 api를 참조하여 다른 url로 다른 정보를 추가로 요청할 수도 있다.
(참조: https://developers.facebook.com/docs/facebook-login/manually-build-a-login-flow/)
1. 페이스북에서 app을 만들어서 App ID(=Client ID)와 App secret(=Client Secret)을 발급받는다.
2. Authorization을 위해 "https://graph.facebook.com/oauth/authorize" 로 redirect한다.
이 때 get을 사용하며 parameter로 아래의 값을 넣어준다.
client_id: 페이스북에 app을 만들면 생성되는 값
redirect_uri: 페이스북으부터 되돌아오기 위한 url 이자 두번째 단계를 실행하기 위한 url
scope: 사용자에게 요청할 퍼미션 리스트
response_type: response data를 어디에 넣을 것인지 선택
state: CSRF를 방지하기 위해 생성한 unique string. 다음번 access token 단계에서 여기에서 넣어준 state값과 같은 state가 넘어왔는지를 보고 제대로 된 단계를 진행하고 있는 것인지 확인한다.
예를 들면 아래와 같은 URL이 될 것이다.
https://graph.facebook.com/oauth/authorize?client_id=1234567890&redirect_uri=http://yoursite.com/authenticate/&scope=email&response_type=code&state=djkfgj3kfjg-23jfjgjg-32jfjgj4--djfjgkf
위의 예 URL에 한 내용은 아래와 같다.
client_id는 페이스북에서 app을 만들면 생성되는 값을 넣어주고 redirect_uri는 페이스북에서 authorize가 처리되고 나면 redirect줄 url을 넣어준 것이다. scope는 간단하게 email로 설정해 주었고 response_type은 url에 parameter로 넘어오도록 code로 해준 것이고 state는 UUID.randomUUID() 을 사용해서 random number를 만들어낸 것이다.
로컬에서의 테스트를 위해 redirect_uri에 localhost를 넣어주면 redirect관련 에러가 발생한다. 이 경우는 페이스북 앱의 설정(Settings)에서 App Domains에 localhost 를 넣어주고 Site URL에 사용할 주소를 넣어준다(내 경우는 다음과 같이 넣어주었다: http://localhost:9000).
3. 2에서 사용자가 정상적으로 access를 허락하면 페이스북에서는 내가 넣어준 redirect uri로 redirect시켜준다. 여기서 access token을 가져오기 위한 작업을 한다.(서버에서 바로 http로 페이스북 access token url에 접속한다.)
정상적이라면 redirect시 파라메터에 state와 code 값이 넘어온다. state값이 정상적인 값(2에서 넣어준 값)인지 확인한다.
이제 access token을 얻어오기 위해 "https://graph.facebook.com/oauth/access_token" 에 요청을 한다. 이때 넘겨주는 parameter는 다음과 같다.
client_id: 페이스북 앱 생성시 생성되는 값
redirect_uri: OAuth 프로세스를 시작한 request_uri
client_secret: 페이스북 앱 생성시 생성되는 값
code: redirect시 받은 값
위의 요청을 하면 accesss_token 과 expires를 response로 준다. 여기까지 에러 없이 진행되었으면 인증 완료된 것이다.
에러의 경우 error 파라메터로 에러를 넘겨주므로 이 파라메터가 있는지 항상 확인해야 한다.
"access_denied"와 "redirect_uri_mismatch"등의 에러 내용이 있다.
4. 이제 사용자 정보를 요청한다. url은 "https://graph.facebook.com/me" 이다.
요청할 때 parameter로 access_token과 fields를 넣어준다.
fields는 요청할 사용자 정보이다:(예: id,name,last_name,username,,email,)
페이스북 api를 참조하여 다른 url로 다른 정보를 추가로 요청할 수도 있다.
피드 구독하기:
글 (Atom)