Categories
Offsites

Quantified Self Part 6 – 생산적인 하루에 대한 정량적인 표현과 4년간의 데이터 이야기

이번 포스트에서는 그 동안 모아온 데이터에 대한 이야기를 집중적으로 해보려고 합니다. 왜 이 데이터들을 모았는지, 그리고 그 동안 모아온 데이터가 무엇을 말하고 있는지에 대한 이야기 입니다.

images

출처 : http://quantifiedself.com/

지금까지의 시리즈

Github: https://github.com/DongjunLee/quantified-self

‘오늘 하루 알차게 보냈다!’ 이 말을 숫자로 표현할 수 있을까요?

Quantified Self 를 주제로 사이드 프로젝트를 진행하면서, 정량적으로 정의하고 싶던 것이 있습니다.
‘오늘 하루 알차게 보냈다!, 뿌듯하다!’ 혹은 ‘아.. 오늘은 아무것도 한 것이 없네..’ 이러한 하루하루에 대한 느낌들 입니다. 느낌이라는 것 자체가 주관적이라는 것을 알고 계실 것입니다. 하루에 대한 평가는 주관이 기본이 되며, 특히 개개인이 가지는 가치관 이라던가, 선호에 따라서 각각 다르게 평가할 수 있습니다. 그래서 실 데이터를 보면서 오늘 하루를 제가 어떤 식으로 평가를 할 것인지 이야기하기 전에, 제가 중요하게 여기는 것을 먼저 이야기 해보고자 합니다.

저는 ‘습관’을 굉장히 중요시 여기고, 하루하루 무언가 꾸준히 하면서 쌓아올린 것이 결국에 나중에 결과를 만들어 낸다고 믿고 있습니다. 이 칼럼(습관은 자신의 참 모습을 보여주는 창이다)에서, 제가 생각하는 습관의 중요성을 잘 말해주고 있습니다.

계몽주의 철학자 데이비드 흄은 이런 습관에 대한 고대와 중세의 해석을 더욱 확장했습니다. 흄은 습관이 바로 인간을 인간으로 만든다고 생각했습니다. 그는 습관을 모든 ‘정신이 그 작동을 의지’하는, ’우주의 접착제(cement)’라 불렀습니다. 예를 들어, 우리는 공을 높이 던지고 떨어지는 것을 볼 수 있습니다. 그는 습관에 의해 우리가 몸을 움직여 공을 던지고 그 공의 궤적을 바라볼 수 있으며, 이를 통해 원인과 결과의 관계를 파악할 수 있다고 생각했습니다. 흄에게 인과론은 바로 습관에 의한 연상작용이었습니다. 그는 언어, 음악, 인간관계 등 경험을 유용한 무언가로 바꾸는 모든 기술이 습관에 의해 만들어진다고 믿었습니다. 곧, 습관은 우리가 세상을 살아가고 이 세상의 원리를 이해하기 위해 반드시 필요한 도구였습니다. 흄에게 습관은 ‘인간 삶의 거대한 안내자’였습니다.

습관에서 ‘무엇을 할 것인가’ 역시 굉장히 중요한 주제입니다. 여기에는 당장 해야 하는 일 보다는 자기 계발에 해당하는 일들이 해당됩니다.

image.png

스티븐 코비의 시간관리 매트릭스

작업에는 몇가지 종류가 있습니다. <성공하는 사람들의 7가지 습관> 에서 나오는 시간관리 매트릭스가 그 중의 하나 일 것 입니다. ‘긴급함’ 과 ‘중요함’ 2가지 척도로서 작업들을 나누는 것입니다. 여기서 제 2사분면은 중장기 계획, 인간관계 유지, 자기계발 등 당장 급하지는 않지만 미래에 큰 보상을 주는 일들이 포함됩니다.

목표는 이렇게 정리할 수 있겠네요.

  1. 자신이 발전할 수 있는 일들에 시간을 많이 사용하고,
  2. 이 활동들을 꾸준히 지속하는 것

이제 제가 어떠한 하루들을 목표로 하는 지 이해 하셨을 것이라 생각이 됩니다. 그 동안의 포스트에서는 데이터를 수집하기 위한 준비와, 그 과정에서 몇가지 자동화도 작업 해보았습니다. 최근 포스트에서는 데이터 시각화도 하면서 대쉬보드도 만들어보았지요. 이 일련의 작업들의 궁극적인 목적은 실제 데이터들을 보면서, ‘생산적인 하루’를 보내고 있는지, 이런 하루를 보내려면 앞으로 어떻게 하면 좋을지 데이터를 보면서 저 자신을 더 깊게 이해하기 위함이였습니다.

생산적인 하루에 대한 Metric 을 정해보자.

생산적인 하루를 정량적인 숫자로 표현하기 위해서는 몇가지 단계를 거칠 필요가 있습니다. ‘오늘 하루 알차게 보냈다!’ 이 문장을 분해를 하는 것입니다. 먼저 이 느낌에 포함이 되는 요소들은 무엇이 있을까요? 예를 들어, 이런 요소들이 있을 것 입니다. 잠은 잘 잤는지, 하려고 했던 To do list 는 다 완료 했는지, 또 그 작업들을 할때 집중해서 했는지, 하루를 기분 좋게 보냈는지, 크게는 이러한 요소들이 있을 것 입니다.

제가 뽑은 요소는 다음의 5가지 입니다. Attention, Happy, Productive, Sleep, Habit. 이제 각각의 요소들을 어떻게 정량적으로 평가할 수 있을지 한번 더 단계를 들어가서 보시죠.

Attention, 작업에 대한 집중

  • 진행한 작업들에 대해서 얼마나 집중했는지는 의미합니다.
  • 기본적으로 40분 이상 진행한 작업에 대해서 집중도를 물어보게 만들어 놓았습니다.
  • 집중도에 대한 점수는 1~5점 척도로 되어있습니다.

image.png

Happy, 그 당시의 기분

  • 하루를 기준으로 200분 마다 그 당시의 기분에 대해서 물어봅니다.
  • 행복도에 대한 점수 역시 1~5점이 기준입니다.

image.png

Productive, 각종 Tool을 활용한 생산성 점수

  • RescueTime 는 PC/모바일을 사용한 기록을 가지고 Productive Pulse 라는 점수를 계산하여 제공해주고 있습니다. (이 값이 어떻게 구해지는 지는 이 링크에서 확인하실 수 있습니다.)

image.png

  • Toggl 에서는 오늘 하루 기록된 작업시간이 8시간 이상부터 100점, 그 아래로는 시간에 비례해서 점수를 차감합니다.
    (예를 들어, 7시간 작업 시 → 87.5점, 6시간 작업 시 → 75점)

image.png

  • Github 에서 오늘을 기준으로 10일 동안의 Commit의 합이 10개 이상부터 100점, 그 아래로는 커밋 수에 비례해서 측정됩니다. 아래 contributions 의 수를 의미합니다.

image.png

  • Todoist 에서는 100점을 기준으로, 완료하지 못한 일들 (+ 기한이 지난 경우 포함)을 우선순위에 따라 차감을 하게 됩니다.
    우선순위는 아래와 같이 4가지가 있고, 높은 우선 순위부터 5, 4, 3, 2 점씩 차감이 됩니다.

image.png

  • 위의 각각의 항목들은 모두 100점 만점이 기준이 됩니다. 여기서 종합 생산성 점수는 다음과 같습니다

Productive = Github (10) + Toggl (30) + Todoist (50) + RescueTime (10)

Sleep, 수면 시간

  • 7시간을 이상은 전부 100점, 그 아래로는 시간과 비례해서 점수를 측정합니다.
  • 수면에 대해서는 약간 관대하게 점수를 재고 있었습니다. (너무 잠을 많이 자는 것이 오히려 피곤함을 초래하는 경우도 있기 때문이죠)

Habit, 매일하는 습관에 해당하는 활동들

  • 개별 항목 하나하나가 5점의 점수를 가집니다.
  • 매일 하려고 하는 습관에 해당하는 일로서 다음의 일들이 습관에 해당합니다.
    • 운동
    • 공부한 것 정리
    • 일기

이제 각각의 항목들을 정리했으니, 마지막으로 이 각각의 점수를 종합해서 오늘 하루를 점수를 매겨보겠습니다.

오늘 하루에 대한 점수 = Attention(20) + Happy(10) + Productive(30) + Sleep(20) + RepeatTask(10) + Habit(15)

이 기준을 모두 만족하면서, 100점을 얻으려면 다음과 같은 일들이 필요합니다. 모든 진행한 작업들에 대해서 집중을 해야하고, 기분도 좋아야 하며, 일일커밋 역시 꾸준히 해주고, 8시간 이상 생산적인 작업을 하고, 등록했던 모든 To do list는 완료를 하고, 컴퓨터를 생산적인 소스 위주로 작업을 하면서, 잠은 7시간 이상 자고, 운동, 공부한 것 정리, 일기 모두 완료를 해야겠네요….😱

이렇게 제가 바라보는 오늘 하루에 대한 점수를 정량화 할 수 있는 식을 만들어 보았습니다. 처음 말한 것처럼, 무엇을 중요시하는 지에 따라서 점수에 대한 비중은 조절할 수 있을 것이고 자신의 생활 패턴에 따라서 기록할 수 있는 수단 또한 달라 질 수 있을 것 입니다.

4년 간의 데이터가 말해주는 것들

사이드 프로젝트를 시작하고, 데이터를 수집하기 시작한 것은 2017-01-30 부터 입니다. 대략 4년째 이렇게 계속해서 Kino를 사용하고 있습니다. 특별히 문제가 없는 이상, 앞으로도 이렇게 사용을 하게 될 것 같네요. 🙂

그럼 그 동안의 데이터의 변화를 보면서 제가 생산적인 하루들을 보냈는지 이야기 해보려고 합니다.

image.png

그림 1 – 월간 종합점수의 변화

위의 도표는 월간 평균 total_score(종합 점수) 를 기준으로 만들어진 라인 차트입니다. 사이드 프로젝트를 시작하는 초반에 열심히 하면서 점수가 올라가다가.. 2018년 상반기부터 떨어지기 시작하는 것이 보입니다. 이 시기가 네이버로 이직을 했던 시기인데, 이직을 하고 나서는 사이드 프로젝트 및 따로 진행했던 ML/DL 논문 구현 들은 하지 않고 회사 일에 더 집중했던 시기입니다. 그리고 2020년부터는 다시 이 QS 프로젝트에 신경을 쓰면서 점수가 올라간 시기입니다. 회사 일도 좋지만, 그 외의 시간을 잘 활용하는 것이 중요한 것 같다는 생각이 드네요. 조금 더 자세히 데이터들을 살펴보려고 합니다.

사이드 프로젝트의 재미 그리고 연구/개발에서 미팅/관리 작업으로

image.png

그림 2 – 각각의 월을 기준으로 각 작업들의 작업시간을 카테고리에 따라 누적한 누적막대차트

이 도표는 월을 기준으로, 각 작업들의 시간을 누적막대로 구성하였습니다. 주요한 작업들인 연구/개발과 미팅/관리만을 표시해보았습니다. 위에서 언급한 것처럼, 2017년에는 이 QS 사이드 프로젝트를 정말 재미있게 개발을 하던 시기이기도 하고, Deep Learning 공부를 하면서 논문 재구현에 힘을 쓰던 시기이기도 합니다. 실제로 작업 시간의 차이가 유의미하게 크기 때문에.. 종합 점수의 차이 또한 이해가 되네요.
2019년도에는 미팅/관리의 작업들이 확 늘어나게 되는데, 커리어의 변화가 이렇게 보이기도 합니다. 관련해서 커리에 대한 이야기는 2019 회고에서 더 자세히 확인할 수 있습니다.

생산적인 하루에 대한 상관관계

이제 다음 데이터를 조금 더 자세히 살펴볼까요? 먼저 보고자 하는 것은 잠 입니다.
‘잠을 더 자면, 그 날의 기분이 더 좋을 것인가?’ 라는 직관적인 생각을 확인해보고자 합니다.

image.png

그림 3- 수면시간에 따른 행복도 점수의 산점도 차트

위 도표를 보면 2017년도의 점들이 2020년에 비해서 왼쪽에 위치한 경향성을 확인할 수 있습니다. 2017년에는 평일에는 보통 5~6시간을 잤고, 2020년에 7~8시간을 자는 것을 확인할 수 있습니다. 이것은 사실 통근 시간에 따른 삶의 질을 확연하게 보여주는 것이기도 합니다. 각각의 연도에 집에서 회사까지 출근하는 시간이 각각 1시간 30분, 30분 이 걸리기 때문이죠. (이렇게 통근 시간이 중요합니다..)

수면 시간은 여러가지로 생활에 영향을 미칠 것 입니다. 예전에 왕복 3시간 통근 하던 때를 추억해보면, 아주 큰 영향이라고 느껴집니다. 데이터는 어떻게 말을 해줄까요? 수면시간과 하루의 행복도 점수 평균에 대한 상관 계수 (0.252) 로 약한 상관관계가 있다는 것을 알 수가 있습니다. 제가 느끼는 느낌의 정도와 상관계수는 차이가 있어보이나, 수면시간의 중요성은 똑같이 말을 해주고 있습니다.

다음으로 종합 점수에 대해서 전체 상관관계를 한번 봐볼까요?

image.png

그림 4 – 수면시간, 작업 수와 작업시간, 그리고 각종 점수들의 상관계수

종합점수에 대해서 가장 강한 상관관계를 가지고 있는 것은 ‘생산성 점수’ (0.62) 입니다. 종합 점수에서 30%으로 가장 큰 비율을 차지하고 있기도 하고, 생산성 점수와 작업의 집중도는 연결되어 있기 때문에 어쩌면 당연한 결과일 것 입니다. 그 다음으로는 점수의 변동이 큰 반복작업 점수 (0.54), 작업시간 (0.42) 으로 작업에 관한 것들이 또한 강한 상관관계를 보여주고 있습니다. 수면 점수(0.20) 와 행복도 점수(0.22) 그리고 집중도 점수(0.27) 는 상대적으로 약한 상관 관계를 보여주고 있네요. 지금의 Metric에서의 생산성은 일정한 기준을 통과하면 만점을 주고 있기 때문에, 질보다는 기본적인 양이 더 중요하게 고려되고 있음을 말해주고 있습니다.

상관계수를 보다 보니, 막연하게 알고 있던 것을 데이터를 통해 확인할 수 있었습니다. 바로 잠을 포기하고 작업을 하는 경우 입니다. 수면시간과 작업시간 간의 상관계수는 (-0.37)으로 음의 상관관계를 보여주고 있습니다. 그에 비해서 수면시간과 집중도 간의 상관계수는 (0.11)으로 아주 약한 상관관계를 보이고 있습니다. 직관적으로는 수면시간이 작업 집중도에 중요한 요소일 것이라고 생각하였는데, 생각과는 약간 다른 결과를 보여주고 있네요. 오히려 수면 시간 보다는 그날의 기분 (0.25) 가 더 상관계수가 높았습니다. 위에서 수면시간과 행복도에 대한 약한 상관관계가 있음을 확인했었기 때문에, 같이 연결해서 봐야할 것입니다.

여기서 지금 Metric의 한계점이 보이기도 합니다. 잠을 줄이면서 공부를 더 한다면, 평소보다 점수는 더 높게 나올 것 입니다. 하지만 ‘꾸준함’을 생각해보면 잠 또한 더 중요하게 생각해야 할 것입니다. 이런 한계점들에 대해서는 아래에서 더 나은 Metric 에서 이야기를 해보고자 합니다.

다음으로는 종합점수와 가장 높은 상관 관계를 보이는 작업에 대해서 조금 더 디테일하게 살펴보겠습니다.

작업의 종류에 따른 집중도와 각 변수들과의 상관계수

어떠한 작업에 대해서 집중도에 관여하는 요소들은 무엇이 있을까요? (Category) 어떠한 작업을 하는지, (When) 언제 하는지, (Mood) 그 당시의 기분은 어떠한지, 조금 더 세부적으로 들어가면 방해요소는 없었는지, 난이도는 적절한지 등의 다양한 요소가 있을 것 입니다. 여기서 데이터를 보려고 하는 것은 작업의 종류, 시간대, 기분을 가지고 살펴보려고 합니다.

여기에는 아래와 같은 가정을 가지고 살펴보려고 합니다.

  • 일에 더 집중하게 될 수록, 그에 따라서 기분도 좋다.
    (몰입, 집중도 점수와 행복도 점수의 상관관계가 높은 경우)
  • 작업을 오래 할수록, 해당 작업에 집중할 수도 있고 집중이 안 될 수도 있다.
    (집중도 점수와 작업시간의 상관관계)
  • 작업은 언제 시작하느냐에 따라서 집중도에 영향을 줄 수 있다.
    (집중도 점수와 시작시간의 상관관계)
    예) 12시에 점심식사 시간인데, 11시 반에 개발을 시작하는 경우

지금처럼 고려되는 범주의 수가 3개 이상일 때는 산점도 매트릭스가 범주 간의 관계를 확인할 수 있어서 적합한 방식입니다.

image.png

그림 5-1 평일 오전 시간대(오전 10시 ~ 오후 1시)의 ‘개발’, ‘미팅’ 에 대한 산점도 매트릭스

작업은 굉장히 다양한 조건들이 있기 때문에, 세부적으로 조건을 가지고 살펴볼 필요가 있습니다. 위 도표는 오전시간을 대상으로 ‘개발’, ‘미팅’ 에 대한 산점도 매트릭스 입니다. 눈으로 확인할 수 있는 작업의 특성은 다음과 같습니다. 미팅은 보통 1시간 단위로 진행이 되므로 10, 11, 12 시에 몰려있는 것을 알 수가 있습니다. 그리고 개발에 대한 작업은 최소 1시간 정도의 집중을 위한 시간을 필요로 하기 때문에, 10시~11시 사이에 밀집되어 있는 것을 확인할 수 있습니다. 이러한 현상을 상관계수로도 확인을 할 수가 있습니다.

image.png

그림 5-2 평일 오전 시간의 ‘개발’, ‘미팅’ 에 대한 상관계수

위의 상관계수 도표를 통해서, 집중도와 각 변수들간의 관계가 차이가 있음이 눈에 확인히 보입니다. 눈에 띄는 차이는 1) 행복도점수와 2) 작업 시간 입니다.

먼저 행복점수 입니다. 개발을 하면서 일에 집중하면 할수록, 그에 따라서 기분이 좋음(0.44)을 보이고 있습니다. 그에 비해서 미팅의 경우에는 작업과 행복도 간에는 상관관계가 없다(-0.07)고 볼 수 있습니다. 오전에는 미팅보다는 개발 작업을 하는 것이 더욱 집중하면서 진행한다는 것을 말해주고 있지 않나 싶습니다.

다음은 작업 시간입니다. 위에서 말한 것과 비슷한 경향으로서, 오전에 진행하는 미팅의 경우 시간이 길수록 집중력이 떨어지는 경향(-0.39)이 보이는 반면 개발은 작업시간이 길수록 더 집중력이 높았던 경향(0.29)을 보이고 있습니다.

image.png

그림 6-1 평일 오후 시간대 (오후 1~8시)의 ‘개발’, ‘미팅’ 에 대한 산점도 매트릭스

위의 도표는 오후 시간대에 대한 같은 조건의 산점도 매트릭스입니다. 오전보다는 오후 시간을 더 길게 활용하고 있기 때문에 점들이 확실히 더 많아 보이네요. 여기에서도 오전에서와 비슷하게, 미팅작업은 대부분 정시에 몰려있는 모습이 보이고, 미팅은 보통 1시간, 개발은 1~2시 사이에 몰려있는 것을 확인할 수 있습니다. 그리고 개발에서는 대부분 행복도 점수가 3~5 점이나, 미팅 작업에서 행복도 점수가 2점으로 떨어진 경우들도 보입니다. 이것은 개발에 비해서 상대적으로 컨트롤이 어려운, 미팅이 가지는 특성이 아닐까 싶습니다.

image.png

그림 6-2 평일 오후 시간의 ‘개발’, ‘미팅’ 에 대한 상관계수

오전과 마찬가지로 상관계수를 살펴보겠습니다. 위와 마찬가지로 1) 행복도 점수 2) 작업 시간으로 집중도의 상관 관계를 비교해보려고 합니다.

가장 큰 차이는 오후에 진행한 미팅은 집중도와 행복도 간의 상관관계가 높다는 것(0.41) 이였습니다. 개별 케이스마다 차이점이 있겠지만, 점들을 보면 행복도 점수 2~5점에 많이 흩어져 있는 것이 보입니다. 미팅은 불필요하게 초대를 받거나 때로는 참관을 하기도 하고, 제대로 된 진전이 없는 경우도 있습니다. 이러한 상황에 따라서 집중도 점수도 차이가 날 것이고 그때의 기분 또한 자연스럽게 연결이 될 것이기 때문입니다.

그에 비해서 오후에는 미팅의 작업시간이 길어도 별로 문제가 되지 않았습니다. 상관계수 0.01 으로 아무런 상관관계가 없다고 보이고 있었습니다. 개발의 경우에는 오전보다는 조금 낮지만 (0.21), 여전히 오래 개발을 할수록 집중을 했었다라는 것을 말해주고 있습니다.

image.png

그림 6-3 개발/미팅/관리 작업들의 몰입 점수에 대한 오전/오후 별 히스토그램

위의 상관관계들을 보았을 때, 아침 혹은 오후에 따라서 작업에 몰입하는 경향에 차이가 있음을 알 수가 있습니다. 집중도가 높으면서 기분이 좋은 경우를 몰입하는 상황(집중도 점수 + 행복도 점수)이라고 가정하고 작업들의 분포를 살펴보았습니다. 미팅/관리 쪽의 일들은 오전보다는 오후에 높은 점수 쪽으로 분포가 되어있고, 개발은 거의 비슷한 분포를 보이고 있네요.

이렇게 시간대에 따라서 영향을 받는 작업들이 있는 반면에, 아무런 상관관계가 없는 것도 있을 것입니다.
바로 ‘운동’ 입니다.

image.png

그림 7-1 평일 모든 시간대의 ‘운동’ 대한 상관계수

운동의 특성상, 언제 시작을 하던 (0.08), 혹은 얼마나 하던 (-0.02), 집중해서 하게 되고, 하고 나면 상쾌하기 때문이 아닐까 싶습니다. 실제로 운동에 대한 작업들은 거의 대부분이 5점에 있습니다. 이 조커와 같은 운동에 대한 효과는 운동을 한 날과 하지 않은 날을 비교해보면 더 그 차이를 체감할 수 있습니다.

image.png

그림 7-2 운동 여부에 따른 바이올린 차트

운동을 한 경우인, 빨간색 바이올린 도표가 조금 더 위로 위치해 있는 것을 볼 수 있습니다. 운동을 한 날이 하지 않는 날보다 조금 더 집중하는 편이고, 작업을 더 많이한다는 것을 말해주고 있습니다.

지금까지의 정보들을 종합해보면 다음과 같은 전략으로 하루의 작업들을 배치할 수 있을 것 입니다.

  • 오전에는 일찍 연구/개발을 시작해서 점심 먹기 전까지 쭉 집중
  • 연구/개발 작업은 오래할 수 있는 시간을 충분히 확보하고 진행
  • 미팅/관리 작업들은 오전보다는 오후에 진행
  • 운동은 아무때나 일정에 맞춰서 하되, 꼭 해주기

자기계발에 해당하는 우선 순위 2 의 작업들

image.png

그림 8 – 우선순위 2에 해당하는 작업 카테고리의 월간 작업시간 막대 그래프

흔히 자기계발에 해당하는 시간들로 카테고리를 정리하였습니다. 여기에는 책을 읽고, 운동을 꾸준히 해주며, 각종 세미나와 강의를 듣고, 공부한 것을 정리하기도 하고, 일기를 쓰고, 명상을 하는 등의 다양한 활동들이 포함됩니다. 2018년 1월에 이상하게 데이터가 틔는 부분이 있지만, 전체적으로는 조금씩 시간을 늘려나가는 모습을 볼 수 있습니다. 명확한 목표 수치가 있는 것은 아니지만, 계속해서 공부를 하면서 꾸준히 월마다 80~100 시간은 쓰고자 하고 있습니다.

Metric은 고정이 아니라, 목표에 맞춰서 계속 변화합니다.

그 동안의 데이터를 분석해보니, 지금은 처음에 목표로 잡고 있던 Metric에는 근접한 생활을 하고 있다고 생각이 들었습니다. 이렇게 습관을 만드는 것이 어렵네요.

살면서 목표는 계속해서 변화하게 됩니다. 그에 따라서 Metric 또한 달라져야 할 것 입니다. 그리고 목표가 바뀌는 것 외에도 새로운 데이터를 수집할 수 있게 되거나, 기존의 데이터를 다른 방식으로 수집하게 된다면 이에 따른 목표 설정이 새로 필요할 것입니다. 현재 몇가지 변화를 주고 있는데, 가장 큰 변화는 아래 3가지 입니다.

image.png

출처: https://blog.fitbit.com/sleep-stages-explained/
  1. 수면 : 현재는 Fitbit Versa 를 통해서 조금 더 정확한 수면에 대한 정보를 얻고 있습니다. 개인적으로 잠에 대한 관심도 많고, 가끔 밤에 잠이 안 와서 밤잠을 설친 날에는 그날 하루가 피곤해지는 것을 경험하다보니.. 자연스럽게 수면에 대해서 점수도 더 올리고 엄격한 기준을 적용해보려고 하고 있습니다.
    위의 그래프에서 보는 것처럼, 잠은 REB, Light, Deep 의 단계를 순환하고 그것을 잡아주고 있기 때문에 더 정확한 진단이 가능할 것입니다. 그 동안은 단순히 잠을 자기 시작한 시간, 일어난 시간을 기준으로 했기 때문에 수면시간과의 상관관계도 더 정확히 알아볼 수 있을 것입니다.
  2. 블로그 작성 : 많은 개발자분들에게 블로그는 꾸준히 해보려고 하지만 정말 잘 안되는 것 중의 하나일 것이라고 생각합니다. 저에게는 특히 그랬네요. 최근에는 글로 자신의 생각을 정리해보는 것이 정말 중요하고, 저만의 컨텐츠를 만들어보고 싶다는 생각으로 노력을 해보고 있습니다.
    블로그는 특별히 습관으로 만들기 위해 신경 쓰는 부분이라 habit 에 포함시켜서 진행 시, 5점을 주도록 설정하였네요. (다른 습관들은 자리를 잡아서 점수를 줄였습니다. 5→3점)
  3. 작업의 질 : 지금까지 집중했던 것은 ‘일단 하자’ 였습니다. 어느정도는 습관으로 자리를 잡은 지금은 ‘더 잘하자’ 에 포커스를 맞춰보고자 합니다. 작업의 질에 집중하는 이유는 의 한 구절을 인용해 보고자 합니다. 이제야 A작업을 어느정도는 해냈고, B 작업을 할 수 있는 단계가 되었다고 생각하기 때문입니다.함께>

    더글러스는 작업을 세 가지 수준으로 구분합니다. A, B, C 작업입니다.
    A 작업은 원래 그 조직이 하기로 되어 있는 일을 하는 걸 말합니다.
    B 작업은 A 작업을 개선하는 걸 말합니다. 제품을 만드는 사이클에서 시간과 품질을 개선하는 것이죠
    C 작업은 B 작업을 개선하는 것 입니다. 개선 사이클 자체의 시간과 품질을 개선하는 것입니다. … 한마디로 개선하는 능력을 개선하는 걸 말합니다.
    더글러스는 “우리가 더 잘하는 것을 더 잘하게 될수록 우리는 더 잘하는 걸 더 잘 그리고 더 빨리 하게 될 것이다” – 복리의 비밀, 34 페이지 중

끝으로

이번 포스트에서는 ‘생산적인 하루’ 를 정량적으로 수치화해보고, 직접 정의를 해본 Metric으로 점수를 산정해보았습니다. 그 동안의 데이터를 살펴보면서, 예전에는 더 열심해 했었는데.. 라는 생각도 하고 조금 더 자세히 데이터들을 분석해보면 하루를 조금 더 효율적으로 보낼 수 있는 방향도 알아보았습니다. 무엇보다도 저 자신을 더 이해할 수 있었습니다. 또한 2020년이 되어서야 데이터를 모으는 것에 그치지 않고, 한 걸음 더 나아갈 수 있었습니다. 가장 중요한 것은 액션 즉, 행동이기에, 이렇게 자신에 대한 데이터들을 통해 현실을 제대로 인지하고 그에 따라서 조금 더 나은 방향으로 행동에 변화를 이끌어 낼 수 있으면 좋겠습니다.
여러분의 하루는 어떤 식으로 수치화를 할 수 있을까요? 또 데이터에서 어떤 것들은 얻고 있으신가요?

Categories
Offsites

클린 아키텍처: 아름다운 코드에서 아키텍처까지

이번 포스트에서는 로버트 마틴의 ‘Clean Architecture’ 을 읽고서 느꼈던 점들을 기반으로, 책에 대한 소개와 추천을 드리고자 합니다.

‘아름다운 코드’ 스터디

이 책은 오랜만에 예전에 했던 스터디를 떠올리게 해주었습니다. 바로 ‘아름다운 코드란 무엇인가?’ 를 주제로 진행했던 스터디 입니다. 이때 다뤘던 책 중의 하나가 로버트 마틴의 ≪클린코드≫ 입니다. 이 책에서는 코드를 어떻게 짜야하는지, 변수와 함수의 네이밍과 함수 간의 순서 등 주로 코드의 가독성을 기본으로 다양한 주제들을 다루고 있기 때문에, 흥미롭게 이야기할 수 있는 주제들이 많습니다. 다만 저자의 스타일이 자신의 주장을 명확하게 밝히는 편이기 때문에 무조건 이렇게 하는게 맞다 라는 관점 보다는 ‘A라는 상황에서는 이런 장점들이 있기 때문에 이렇게 해야 한다고 생각한다’ 에 가깝습니다. 그래서 저자가 제시하는 다양한 상황과 주장에 대해서 서로 어떻게 생각하는지 이야기 해보고 토론해보면서 많은 것들을 배웠던 기억이 납니다.

클린 아키텍처≫ 역시, 스타일은 ≪클린코드≫ 와 비슷합니다. 다만 뷰가 조금 다릅니다. 아주 가까이, 코드란 무엇인가 에서 부터 조금씩 Zoom-out을 하면서 프로그래밍 패러다임, 코드 설계 원칙, 컴포넌트, 아키텍처 까지 전반적인 내용들을 다루고 있습니다. 이번에는 혼자서 책을 보았는데, 같이 보면서 의견 나누면서 스터디 진행하면 좋겠다는 생각이 자연스럽게 들었습니다.

예전에 스터디 했을 때와는 다르게, 이제는 어느 정도 현업에서 개발하고 있기 때문에, 이 책을 볼때는 자연스럽게 그 동안의 경험들에 근거해서 바라보게 됩니다. 특히 아래의 말은 공감이 가는 말이기도 합니다.

소프트웨어 개발의 단순한 진리, 빨리 가는 유일한 방법은 제대로 가는 것이다.

  • 1장 설계와 아키텍처란? 중에서

그렇다면 아름다운 아키텍처란 무엇일까?

아키텍처가 가지는 의미는 무엇일까요? 건축에서 아키텍처는 다음과 같은 의미로 쓰입니다.

건물이나 다른 구조물을 계획하고 설계하고 건설하는 과정과 그 결과물

images

브루넬레스키가 설계하고 건축한 플로렌스 대성당, 출처: 건축 위키백과

CS 에서의 아키텍처 역시, 시스템을 계획하고 설계하는 전반을 포함하고 있다고 생각합니다. 조금 더 분리해서 들여다보면, 시스템을 튼튼하게 받쳐주는 구조를 의미한다고 생각을 합니다. 이 구조가 튼튼할 수록, 쉽게 변경할 수 있을수록 시스템은 무궁무진한 방향으로 발전할 수 있을 것 입니다. 그리고 계획과 설계는 한번에 끝나는 일이 아닌, 계속해서 상황에 따라서 변화해야하는 것이기도 합니다.

아키텍처는 종착지가 아니라 여정에 더 가까우며, 고정된 산출물이 아니라 계속된 탐구 과정에 더 가까움을 이해해야 좋은 아키텍처가 만들어진다.

  • 추천사 중에서

좋은 소프트웨어 설계의 목표는?
소프트웨어 아키텍처의 목표는 필요한 시스템을 만들고 유지보수하는 데 투입되는 인력을 최소화하는 데 있다.

  • 1장 설계와 아키텍처란? 중에서

저자는 아키텍처의 목표에 대해서 명확한 방향을 제시하고 있다고 생각을 합니다.

‘필요한 시스템을 만들 수 있으면서, 가장 적은 인원으로 대응할 수 있는 것.’

필요한 시스템에는 확장성과 속도, 견고함과 같은 측면들이 포함되어 있다고 보이기 때문에 그 외에 한가지 요소를 더 추가하면 조금 더 명확한 방향이라고 할 수 있을 것 같습니다. 바로 시간입니다.

‘요구되는 기간 안에 필요한 시스템을 만들 수 있으면서, 가장 적은 인원으로 대응할 수 있는 것.’

코드에서 패러다임, 컴포넌트, 아키텍처까지

아래에서는 저자가 이 책에서 이야기하는 다양한 주제에 대해서 다뤄보고자 합니다. 저자가 이 책을 쓴 것에는 다음과 같은 전제가 기본으로 들어가 있습니다.

코드는 여전히 순차 sequence, 분기 selection, 반복 iteration 의 집합체일 뿐이다. … 언어는 조금 발전했다. 도구는 환상적으로 좋아졌다. 하지만 컴퓨터 프로그래밍을 이루는 기본 구성요소는 조금도 바뀌지 않았다.

  • 서문 중에서

이를 가장 잘 표현하는 것은 추천사에도 있는 이 말이라고 생각합니다. ‘소프트웨어는 본질적으로 재귀적이고 프랙털구조로 되어 있으며…’ 아래 그림처럼, 일부 작은 조각(기본 구성요소)이 전체(소프트웨어)와 비슷한 형태를 지니는 것.

이제 기본 구성요소를 넘어서 패러다임 부터 간단하게 이야기 해보려고 합니다.

images

출처:[https://www.scienceall.com/프랙털fractal/)

프로그래밍 패러다임

패러다임이란 해당 문제에 접근하는 관점 혹은 방법론을 의미합니다. 프로그래밍 패러다임에는 크게 3가지가 존재합니다. 저자는 이 대표적인 3가지 패러다임을 ‘규제’의 관점으로 바라보고 있습니다. 우리에게 자유를 뺏어 가기 때문이죠.

  1. 구조적 프로그래밍 : 제어흐름의 직접적인 전환에 부과되는 규율이다. (goto문)
  2. 객체지향 프로그래밍 : 제어흐름의 간접적인 전환에 부과되는 규율이다. (함수포인터)
  3. 함수형 프로그래밍 : 변수 할당에 부과되는 규율이다. (할당문)

이렇게 규율을 부과하는 것은 해당 문제를 풀어감에 있어서, 규율이 도움이 되기 때문입니다. 그래서 위의 패러다임들은 배타적인 관계가 아닌, 상호 보완적인 관계에 가깝다고 볼 수 있습니다. 각각의 패러다임이 가지는 가장 큰 강점을 아래와 같이 추려 보았습니다.

구조적 프로그래밍

모든 프로그램을 순차(sequence), 분기(selection), 반복(iteration) 이라는 세 가지 구조만으로 표현할 수 있다는 사실을 증명했다.
(중략)
모듈을 증명 가능한 더 작은 단위로 재귀적으로 분해할 수 있게 되었고, 이는 결국 모듈을 기능적으로 분해할 수 있음을 뜻했다.

  • 4장 구조적 프로그래밍 중에서

객체지향 프로그래밍

images

구현체와 인터페이스 사이의 소스 코드 의존성(상속 관계)이 제어흐름과는 반대인 점을 주목하자. 이는 의존성 역전(dependency inversion)이라고 부르며, 소프트웨어 아키텍처 관점에서 이러한 현상은 심오한 의미를 갖는다.
OO 언어가 다형성을 안전하고 편리하게 제공한다는 사실은 소스 코드 의존성을 어디에서든 역전시킬 수 있다는 뜻이기도 하다.
(중략)
이것이 힘이다! 이것이 바로 OO가 제공하는 힘이다. 그리고 이것이 바로 OO가 지향하는 것이다(최소한 아키텍트의 관점에서는).

  • 5장 객체 지향 프로그래밍 중에서

함수형 프로그래밍

아키텍트는 왜 변수의 가변성을 염려하는가? 터무니없게도 대답은 단순하다. 경합(race) 조건, 교착상태(deadlock) 조건, 동시 업데이트(concurrent update) 문제가 모두 가변 변수로 인해 발생하기 때문이다. 만약 어떠한 변수도 갱신되지 않는다면 경합 조건이나 동시 업데이트 문제가 일어나지 않는다. 락(lock)이 가변적이지 않다면 교착상태도 일어나지 않는다.
다시 말해 우리가 동시성 애플리케이션에서 마주치는 모든 문제, 즉 다수의 스레드와 프로세스를 사용하는 애플리케이션에서 마주치는 모든 문제는 가변 변수가 없다면 절대로 생기지 않는다.
아키텍트라면 동시성(concurrency) 문제에 지대한 관심을 가져야만 한다. … 이 질문에 대한 대답은 대체로 긍정적이다. 단, 저장 공간이 무한하고 프로세서의 속도가 무한히 빠르다고 전제한다면 말이다.

  • 6장 함수형 프로그래밍 중에서

설계 원칙과 컴포넌트

다음으로는 코드의 설계 원칙을 이야기합니다. 다음과 같은 SOLID를 각 항목 별로 살펴보게 됩니다.

  • SRP: 단일 책임 원칙 Single Responsibility Principle
  • OCP: 개방-폐쇄 원칙 Open-Closed Priciple
  • LSP: 리스코프 치환 원칙 Liskov Substitution Principle
  • ISP: 인터페이스 분리 원칙 Interface Segregation Principle
  • DIP: 의존성 역전 원칙 Dependency Inversion Principle

각각의 원칙 마다도 이야기하는 것들이 많이 있습니다만, 이정도로 소개만 하고 컴포넌트에 대해서 이야기를 해보려고 합니다.

SOLID 원칙이 벽과 방에 벽돌을 배치하는 방법을 알려준다면, 컴포넌트 원칙은 빌딩에 방을 배치하는 방법을 설명해준다. 큰 빌딩과 마찬가지로 대규모 소프트웨어 시스템은 작은 컴포넌트들로 만들어진다.

  • 4부 컴포넌트 원칙 중에서

컴포넌트 역시 SOLID 와 비슷하게 몇가지 원칙들을 소개합니다. 다만 컴포넌트가 가지는 속성을 기반으로 설계 원칙들을 이야기 합니다. 코드가 로직의 구성체라면, 컴포넌트는 코드들의 구성체이면서 아래와 같은 특징들을 가지고 있습니다. 가장 중요하게 이야기되는 특징이 ‘배포’ 와 ‘독립성’ 이라는 것을 아실 수 있을 것 입니다.

컴포넌트는 배포 단위다. 컴포넌트는 시스템의 구성 요소로 배포할 수 있는 가장 작은 단위다. … 컴파일형 언어에서 컴포넌트는 바이너리 파일의 결합체다. 인터프리티형 언어의 경우는 소스 파일의 결합체다. 모든 언어에서 컴포넌트는 배포할 수 있는 단위 입자다. … 컴포넌트가 마지막에 어떤 형태로 배포되든, 잘 설계된 컴포넌트라면 반드시 독립적으로 배포 가능한, 따라서 독립적으로 개발 가능한 능력을 갖춰야 한다.

  • 12 장 컴포넌트 중에서

images

컴포넌트 응집도에 대한 균형 다이어그램
  • REP: 재사용/릴리즈 등가 원칙
  • CCP: 공통 폐쇄 원칙
  • CRP: 공통 재사용 원칙

컴포넌트 결합

  • ADP: 의존성 비순환 원칙
  • SDP: 안정된 의존성 원칙
  • SAP: 안정된 추상화 원칙

아키텍처

마지막으로 전체를 아우르는 아키텍처 입니다. 여기에서도 다양한 사례들을 기반으로 이야기하고, 또 저자가 주장하는 구조가 있습니다. 아마 이 책에서 가장 유명한 다이어그램이 아닐까 싶습니다.

images

https://blog.insightbook.co.kr/2019/08/08/클린-아키텍처/

코어인 업무 규칙이 담겨있는 ‘엔티티’, 사용자에 대한 입력과 출력을 기반으로 구성되는 ‘유스케이스’, 그 바깥으로는 컨트롤러와 프레젠터가 있고 마지막 외부 인터페이스들인 (세부사항이라고 표현하기도 하는) 웹, UI, DB 이 있습니다. 의존성은 안쪽을 향해 있으며, 제어흐름 역전을 위해서 DIP가 안에서 사용되는 모습들도 보이고 있습니다.

여기에는 다음과 같은 특징들이 담고 있다고 이야기하고 있습니다.

  • 프레임워크 독립성
  • 테스트 용이성
  • UI 독립성
  • 데이터베이스 독립성
  • 모든 외부 에이전시에 대한 독립성

위의 클린 아키텍처에 대한 조금 더 자세한 설명을 포함해서 경계와 험블 객체, 등 다양한 주제에 대해서 많은 이야기를 하고 있으니 자세히 읽어보시는 것을 추천드립니다.

정리를 하기 전에 마지막으로 ‘아키텍처’ 에 대한 저자의 생각을 인용하고자 합니다. 저 역시 해당 시스템의 아키텍트는 계속해서 코드를 다뤄야 한다는 점에 동의하기 때문입니다.

무엇보다도 소프트웨어 아키텍트는 프로그래머이며, 앞으로도 계속 프로그래머로 남는다. 소프트웨어 아키텍트라면 코드에서 탈피하여 고수준의 문제에 집중해야 한다는 거짓말에 절대로 속아 넘어가서는 안 된다. 소프트웨어 아키텍트는 코드와 동떨어져서는 안 된다. 소프트웨어 아키텍트는 최고의 프로그래머이며, 앞으로도 계속 프로그래밍 작업을 맡을 뿐만 아니라 동시에 나머지 팀원들이 생산성을 극대화할 수 있는 설계를 하도록 방향을 이끌어 준다. … 프로그래밍 작업을 계속하는 이유는, 발생하는 문제를 경험해보지 않는다면 다른 프로그래머를 지원하는 작업을 제대로 수행할 수 없기 때문이다.

  • 15장 아키텍처란? 중에서

끝으로

이 책은 정말 다양한 주제들을 다루고 있습니다. 엉클 밥의 다양한 인사이트 역시 확인하실 수 있을 것입니다. 그리고 서두에 이야기를 한 것처럼, 저자가 던지고 있는 다양한 화두를 살펴보면서 자신은 해당 상황에서 어떻게 생각하고 설계하고 있는지 비교해보면 더 많은 것들을 얻을 수 있을 것이라고 생각합니다. 이 책을 보시면서 설계에 대해서 더 깊이 고민하고, 아름다운 아키텍처를 만드는 아키텍트를 꿈꾸시는 분들에게 추천드리고 싶습니다.

부록

한가지 이야기하고 싶은 점은, 저자의 주 언어는 Java라고 알고 있습니다. 그런 만큼, 구체적인 예시로 들어가면 대부분 객체지향 언어가 많이 부각되기도 합니다. 마지막 장의 패키지를 보면 자바의 Spring에서 많이 보던 구조이기도 합니다. 하지만 처음에 저자가 이야기 한 것처럼 기본 구성요소는 변하지 않기 때문에 문제가 되지는 않을 것이라 생각합니다.

그 외 볼거리

Categories
Offsites

CodeReading – 1. PyTorch

Code Reading은 잘 작성되어 있는 프레임워크, 라이브러리, 툴킷 등의 다양한 프로젝트의 내부를 살펴보는 시리즈 입니다. 이번 포스트에서는 직관적인 사용이 가능한 PyTorch 에 대해서 다뤄보겠습니다.

Code Reading

글쓰기에는 이러한 말이 아주 널리 퍼져 있습니다. “글쓰기를 잘 하려면 먼저 글을 많이 읽어라.” 코드를 작성하는 것에도 적용될 수 있는 말이라고 생각을 합니다. 사실 우리는 이미 글을 많이 읽고 있습니다. 버그를 고치면서 혹은 다양한 코드 예제를 구글링해서 찾아보기도 하고, 동료가 짠 코드를 이해해야 하는 일 등.. 우리는 수많은 코드들을 읽고 있습니다. 하지만 이런 글들을 많이 본다고 해서 좋은 글을 쓸 수 있을까요? 위 글에 대한 전제에는 이부분이 포함되어 있을 것입니다. “글쓰기를 잘 하려면 먼저 (좋은) 글을 많이 읽어라.”

그래서 더 좋은 코드를 작성하기 위해 널리 사용되고 있고, 잘 작성된 코드들의 내부를 살펴보면서 하나하나 읽어보려고 합니다.

이번 포스트에서 코드를 바라보는 기준은 ‘프레임워크’ 로서 바라보려고 합니다. 즉, 일관된 협력을 위해서 어떻게 설계를 하였는지, 그리고 사용자들이 어떤 식으로 재사용을 할 수 있도록 정의했는지 등을 보려고 합니다. 프레임워크에 대해서, 객체지향 설계 책 ≪오브젝트≫에서는 아래와 같이 정의하고 있습니다.

프레임워크란 ‘추상 클래스나 인터페이스를 정의하고 인스턴스 사이의 상호작용을 통해 시스템 전체 혹은 일부를 구현해 놓은 재사용 가능한 설계’, 또는 ‘애플리케이션 개발자가 현재의 요구사항에 맞게 커스터마이징할 수 있는 애플리케이션의 골격(skeleton)’을 의미한다. 첫 번째 정의가 프레임워크의 구조적인 측면에 초점을 맞추고 있다면 두 번째 정의는 코드와 설계의 재사용이라는 프레임워크의 사용 목적에 초점을 맞춘다.

  • 15 Chapter 디자인패턴과 프레임워크 중에서

PyTorch

images

출처:https://github.com/pytorch/pytorch

처음 다뤄보고 하는 프로젝트는 현재 제가 가장 많이 사용하고 있는 프레임워크인 PyTorch 입니다. 딥러닝에서는 TensorFlow 와 같이 가장 널리 쓰이고 있는 프레임워크로서, Dynamic Graph 기반의 명령형 제어흐름과 모듈 구성 그리고 Python으로 손쉽게 사용할 수 있는 특징이 있습니다. 이 특징들로 인해서 직관적인 코드 작성이 가능하고, 디버깅도 편하게 할 수 있으며, 모듈화가 정말 잘 되어 있어서 코드를 사용하는 입장에서 아주 편한 장점이 있습니다. 이런 이유들로 인해서 첫 Code Reading의 사례로 선정하기도 하였습니다.

images

안타깝게도 코어는 C++ 으로 작성 되어있고, PyTorch는 이것을 python으로 사용할 수 있도록 wrapping 한 것입니다. 저의 내공이 부족하여 C++ 내부까지 자세히 살펴보지는 못하고 프레임워크로서 내부 구조와 Python 코드들을 위주로 살펴보려고 합니다. (그래서 살펴보는 코드의 반 이상은 빠져있지 않을까 싶네요..!)

프레임워크로서 살펴보는 것이기 때문에, 전체 코드를 살펴보는 것보다는 중심이 되는 코드들의 구조와 어떤 식으로 협력을 하는지, 또 사용자들이 쉽게 쓰기위한 특징 들은 무엇이 있는지 살펴보겠습니다.

먼저 전반적인 PyTorch의 특징은 다음과 같습니다.

  • Tensor computation (like NumPy) with strong GPU acceleration
  • Deep neural networks built on a tape-based autograd system

출처: https://github.com/pytorch/pytorch

간단하게 직역하면, Numpy 에서 사용하는 방식을 거의 그대로 Tensor 를 다룰 수 있고, 이 Tensor 연산들을 코드로 작성 하면 위에 그림처럼, 자동으로 미분이 가능한 그래프가 그려지면서 backward 호출만 하면 되는 강력한 프레임워크라고 말할 수 있습니다.

다음으로는 Github 에 있는 각 packages 에 대한 간단한 설명입니다.

Packages

  • torch : numpy 유사한 Tensor, GPU 지원
  • torch.autograd : 자동으로 backprop 이 가능하게 하는 패키지
  • torch.jit : Just-in-time compilation
  • torch.nn : neural network 용, 유연성을 최대의 목표로 디자인
  • torch.multiprocessing : data_loading, Hogwild training (without any locking)
  • torch.utils : DataSet, DataLoader 등의 유틸들

여러가지 Package 들이 있지만, 이번에 제가 다뤄보고자하는 것은 torch, torch.autograd , torch.nn 입니다. (코드는 v1.6.0 을 기준으로 살펴보았습니다.)

torch.tensor

여기에서는 Tensor에 대해서 간단하게만 살펴보려고 합니다. (대부분이 C++ 이 베이스이기 때문이죠..)
Tensor는 논리적인 View로서 실제 물리적인 저장소인 Storage 와 같이 이루어져 있습니다.

아래의 Tensor 를 복사하는 부분의 코드를 보시면 확인할 수 있습니다. 논리적인 뷰에서의 설정값들인 offset, size, stride 를 넣게 되어 있습니다.

(stride에 대해서는 이 Stride Visualizer에서 조금 더 자세히 이해할 수 있습니다.)

images

출처: http://blog.ezyang.com/2019/05/pytorch-internals/

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/tensor.py#L66

new_storage = self.storage().__deepcopy__(memo)
...

new_tensor = self.new()
new_tensor.set_(new_storage, self.storage_offset(), self.size(), self.stride())
new_tensor.requires_grad = self.requires_grad

단순하게 말하자면, Storage에는 물리적으로 매핑되는 값들이 관리되고 있고 storage_offset은 물리적인 주소에 대한 offset, strides 는 인덱스에 곱해지는 계수를 의미합니다. 이렇게 논리적 뷰/물리적 저장소가 나뉘어서 관리되고 있기 때문에, Tensor에 대한 단순 Transpose 등의 연산은 계산이 아주 단순하게 됩니다. 논리적인 뷰의 설정만 달라지면 되는 일이기 때문이죠.

Tensor에 대해서 조금 더 자세히 살펴보겠습니다. Tensor는 하나의 데이터 구조 입니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/tensor.py#L35

class Tensor(torch._C._TensorBase):
    ...
# https://github.com/pytorch/pytorch/blob/v1.6.0/torch/_C/__init__.pyi.in

# Defined in torch/csrc/autograd/python_variable.cpp
class _TensorBase(object):
    requires_grad: _bool
    shape: Size
    data: Tensor
    names: List[str]
    device: _device
    dtype: _dtype
    layout: _layout
    real: Tensor
    imag: Tensor
    T: Tensor
    ndim: _int
    _version: _int
    _base: Optional[Tensor]
    grad_fn: Any
    ${tensor_method_hints}

위와 같은 속성들을 가지고 있는 것을 알 수 있습니다. 주요하게는 각 Tensor 마다 requires_grad 을 가지고 있고, grad_fn 또한 가지고 있는데요, PyTorch를 v0.4.0 버전 전부터 사용하시던 분들은 이후에 업데이트 된 내용이 눈에 들어오실 것 입니다. 바로 torch.autograd.VariableTensor 로 합쳐진 것이죠. 주석의 파일 경로를 보면 그 이전에는 Tensor 대신에 Variable 을 사용했던 것을 짐작할 수 있습니다. (/autograd/)

이렇게 데이터에 대한 속성들을 설정하는 것 외에도 코드 상에는 backward 라는 매서드를 가지고 있습니다. 이 함수는 바로 autograd package 로 연결이 되어 있습니다. 이를 통해서, 각 Tensor는 backward 메서드를 가지고 있지만 실질적으로 해당 로직은 autograd 에서 처리됨을 알 수 있습니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/tensor.py#L155

def backward(self, gradient=None, retain_graph=None, create_graph=False, inputs=None):
    r"""Computes the gradient of current tensor w.r.t. graph leaves.
    
        The graph is differentiated using the chain rule.
    ...
    torch.autograd.backward(self, gradient, retain_graph, create_graph, inputs=inputs)

backward 메소드에 의해서 각 Tensor 에 누적되는 gradient → grad.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/tensor.py#L725

    @property
    def grad(self):
        """
        This attribute is ``None`` by default and becomes a Tensor the first time a call to
        :func:`backward` computes gradients for ``self``.
        The attribute will then contain the gradients computed and future calls to
        :func:`backward` will accumulate (add) gradients into it.
        """
        ...
        return self._grad

또 한가지 눈 여겨서 볼 매서드는 register_hook 입니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/tensor.py#L187

def register_hook(self, hook):
    r"""Registers a backward hook.

    The hook will be called every time a gradient with respect to the
    Tensor is computed. The hook should have the following signature::
      hook(grad) -> Tensor or None
    ...

    Example::
      >>> v = torch.tensor([0., 0., 0.], requires_grad=True)
      >>> h = v.register_hook(lambda grad: grad * 2)  # double the gradient
      >>> v.backward(torch.tensor([1., 2., 3.]))
      >>> v.grad
       2
       4
       6
      [torch.FloatTensor of size (3,)]
      >>> h.remove()  # removes the hook

Docstring 에 적혀있는 것처럼, hookbackward 가 호출 될때마다, 등록한 hook의 함수가 불러지는 것을 알 수 있습니다. 이는 각각의 상황에 맞춰서 gradient를 조절하는 hook이 등록될 수 있음을 의미합니다.

torch.autograd

다음으로는 이어서 autograd 팩키지를 살펴보겠습니다. 이 부분에 대한 소개는 다음과 같습니다.

Autograd is a hotspot for PyTorch performance, so most of the heavy lifting is implemented in C++. This implies that we have to do some shuffling between Python and C++; and in general, we want data to be in a form that is convenient to manipulate from C++.

성능에 주요한 부분으로서 C++ 으로 구현되어 있다는 것을 아실 수 있을 것 입니다. 여기에서 가장 중요한 컨셉은 Node, Function 이 2가지가 될 것입니다. Node 는 그래프에 대한 로직들, Function 은 forward, backward 에 대한 로직들을 담고 있다고 봐주시면 됩니다.

먼저 위의 Tenosrbackward 가 연결되는 autograd.backward 함수를 보시겠습니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/autograd/__init__.py#L57

def backward(
    tensors: _TensorOrTensors,
    grad_tensors: Optional[_TensorOrTensors] = None,
    retain_graph: Optional[bool] = None,
    create_graph: bool = False,
    grad_variables: Optional[_TensorOrTensors] = None,
) -> None:
    r"""Computes the sum of gradients of given tensors w.r.t. graph leaves.
    ...
    """

    ...
    Variable._execution_engine.run_backward(
        tensors, grad_tensors, retain_graph, create_graph,
        allow_unreachable=True)  # allow_unreachable flag

이 부분이 chain rule 에 따라서 계산된 gradient (grad_tensors ) 가 명령형 엔진에 의해서 계산되고, 각 텐서에 grad 값을 누적시키게 됩니다.

다음으로 PyTorch 문서에는 Custom Function을 구현할 수 있는, 확장에 대한 방법이 정리되어 있습니다. autograd 에 정의가 되어 있는 Function 을 상속하면서 필요한 메서드들을 구현하면 되는 것 입니다. 바로 forward와 backward 를 추가하는 것이죠. 아래 코드의 예제를 보면 이해가 갈 것이라 생각이 됩니다.

# Inherit from Function
class LinearFunction(Function):

    # Note that both forward and backward are @staticmethods
    @staticmethod
    # bias is an optional argument
    def forward(ctx, input, weight, bias=None):
        ctx.save_for_backward(input, weight, bias)
        output = input.mm(weight.t())
        if bias is not None:
            output += bias.unsqueeze(0).expand_as(output)
        return output

    # This function has only a single output, so it gets only one gradient
    @staticmethod
    def backward(ctx, grad_output):
        # This is a pattern that is very convenient - at the top of backward
        # unpack saved_tensors and initialize all gradients w.r.t. inputs to
        # None. Thanks to the fact that additional trailing Nones are
        # ignored, the return statement is simple even when the function has
        # optional inputs.
        input, weight, bias = ctx.saved_tensors
        grad_input = grad_weight = grad_bias = None

        # These needs_input_grad checks are optional and there only to
        # improve efficiency. If you want to make your code simpler, you can
        # skip them. Returning gradients for inputs that don't require it is
        # not an error.
        if ctx.needs_input_grad[0]:
            grad_input = grad_output.mm(weight)
        if ctx.needs_input_grad[1]:
            grad_weight = grad_output.t().mm(input)
        if bias is not None and ctx.needs_input_grad[2]:
            grad_bias = grad_output.sum(0)

        return grad_input, grad_weight, grad_bias

위에서 확인하신 것처럼 Function 은 필요한 메서드들을 미리 정의해놓은 추상 클래스라고 말할 수 있습니다. 이제 코드 내부로 가서 이 Function 이 어떻게 구현되어 있는지 살펴보겠습니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/autograd/function.py#L110

class Function(with_metaclass(FunctionMeta, _C._FunctionBase, _ContextMethodMixin, _HookMixin)):
    r"""Records operation history and defines formulas for differentiating ops.
    ...

Function 이라는 객체는 FunctionMeta 라는 Meta Class 로 만들어지며, _FunctionBase 를 상속하고, _ContextMethodMixin_HookMixin 를 통해 인터페이스로 확장이 되어 있다는 것을 알 수 있습니다. 조금 더 자세히 이해를 하려면, Python 이 지원하는 Meta Class와 Mixin에 대해서 간단히 이야기할 필요가 있을 것 같습니다.

Meta Class

메타 클래스에 대해서는 설명이 잘 되어있는 글을 참고해주시면 좋겠습니다. 메타 클래스에 대해서 알고 있다는 가정하에 글을 더 진행해보겠습니다. 메타클래스는 간단하게 아래와 같이 정의가 됩니다.

metaclass ——> (인스턴스) class ——> (인스턴스) object

메타클래스는 대부분 건드릴 일이 없으며, Python의 class를 수정하고 싶을 때 사용할 수 있습니다. 아래와 같이 __init__ , __new__ , __**prepare__** 등 클래스의 빌트인 매서드들을 수정할 수 있습니다.

# https://github.com/pytorch/pytorch/blob/v1.6.0/torch/_six.py#L39

def with_metaclass(meta, *bases):
    """Create a base class with a metaclass."""
    # This requires a bit of explanation: the basic idea is to make a dummy
    # metaclass for one level of class instantiation that replaces itself with
    # the actual metaclass.
    class metaclass(meta):

        def __new__(cls, name, this_bases, d):
            return meta(name, bases, d)
    return type.__new__(metaclass, 'temporary_class', (), {})

그럼 다시 Function 에서 사용되는 with_metaclass 는 어떤 역할을 하는지 살펴보겠습니다. 단순하게 이 코드는 정해진 Meta에 따라서, ‘temporay_class’ 라는 이름으로서 클래스들을 생성 하는 것입니다. Syntactic Sugar에 해당하는 경우라고 볼 수 있을 것 같습니다.

다음으로 넘어가서 여기 meta 에 연결되는 FunctionMeta 를 확인해볼까요?
FunctionMeta 는 생성자(__init__)에서 backward_fn 에 해당 Function 의 backward 메서드를 연결하는 역할을 합니다.

아래의 type 은 코드에 있는 것처럼, 동적으로 클래스를 생성하는 함수로 사용이 됩니다. BackwardCFunction 객체를 만들어서 _forward_clsbackward 메소드가 연결되는 것이죠.

# code : https://github.com/pytorch/pytorch/blob/v1.6.0/torch/autograd/function.py

class BackwardCFunction(_C._FunctionBase, _ContextMethodMixin, _HookMixin):
    _is_legacy = False

    def apply(self, *args):
        return self._forward_cls.backward(self, *args)

class FunctionMeta(type):
    """Function metaclass.
    ...
    """

    def __init__(cls, name, bases, attrs):
       ...

       backward_fn = type(name + 'Backward', (BackwardCFunction,), {'_forward_cls': cls})
       cls._backward_cls = backward_fn

여기서 FunctionBackwardCFunction 은 다중상속이 되어있는 것을 보셨을 것 입니다. 이렇게 구성된 두 클래스가 어떻게 동작하는지 이해하기 위해서는 Python의 상속구조를 이해하는 것이 필요합니다. 아래의 Class.mro() 를 통해서 객체의 매서드 실행 순서를 확인할 수가 있습니다. 호출되는 메서드를 찾을때 왼쪽부터 차례로 오른쪽으로 가는 것이죠.

class BackwardCFunction(_C._FunctionBase, _ContextMethodMixin, _HookMixin):
   ...

# BackwardCFunction.mro() : 해당 객체의 메서드 실행 순서를 표현합니다. (mro -> Method Resolution Order)
# [__main__.BackwardCFunction, __main__._C._FunctionBase, __main__._ContextMethodMixin, __main__._HookMixin, object]

Base가 두개가 되는 것은 흔히 알려져있는 다이아몬드 문제를 야기합니다. 대신 Mixin 이라는 방식을 통해서 다중상속을 하게 됩니다. 그래서 보통 Mixin 에는 attribute 보다는 method 확장이 주로 사용이 됩니다.

실제로 위 코드의 _ContextMethodMixin, _HookMixin 메서드 확장을 위해서 사용이 되고 있습니다.

믹스인에 대해서 보충 설명을 하자면, ≪오브젝트≫ 에서는 이렇게 정의를 하고 있습니다.

믹스인(mixin)은 객체를 생성할 때 코드 일부를 클래스 안에 섞어 넣어 재사용하는 기법을 가리키는 용어다. 합성이 실행 시점에 객체를 조합하는 재사용 방법이라면 믹스인은 컴파일 시점에 필요한 코드 조각을 조합하는 재사용방법이다.

  • 04 믹스인 중에서

다시 본론으로 돌아와서, Function 클래스의 내부를 살펴보겠습니다.

class Function(with_metaclass(FunctionMeta, _C._FunctionBase, _ContextMethodMixin, _HookMixin)):
    ...

    # for the tracer
    is_traceable = False

    @staticmethod
    def forward(ctx: Any, *args: Any, **kwargs: Any) -> Any:
        raise NotImplementedError("You must implement the forward function for custom"
                                  " autograd.Function.")

    @staticmethod
    def backward(ctx: Any, *grad_outputs: Any) -> Any:
        raise NotImplementedError("You must implement the backward function for custom"
                                  " autograd.Function.")

위와 같이 forward 그리고 backward 를 정의하도록 가이드하면서, 추상클래스로서의 역할을 하고 있는 것을 확인할 수 있습니다. 코드 내에는 공식적으로 InplaceFuction 그리고 NestedIOFunction 만 작성되어 있기는 하지만, 처음 예시로 봤던 LinearFunction 처럼 수 많은 연산로직들이 이 Function 의 정의된 규격을 따라가면 재사용이 가능함을 알 수 있습니다.

images

Module 에게 주어진 책임 예시 (GPU 할당 / 입력 계산)

일관된 객체들 간의 협력이 요구되는 프레임워크이기 때문에, 많은 연산의 기본이 되는 Function 클래스를 확인할 수 있었습니다. 다음으로는 PyTorch를 사용하신 분들은 친숙하게 느끼실 torch.nn 입니다.

torch.nn

여기부터는 순수 Python으로 코드가 구성되어 있습니다. 수 많은 코드들 중에서 살펴보려고 하는 것은 가장 기본이 되는 Module 클래스입니다. Python으로 전체가 구성되어 있는 것만큼, 여기에서는 모든 코드들이 typing 을 통해서 자료형이 모두 명시되어 있습니다.

images

Module 에게 주어진 책임 예시 (GPU 할당 / 입력 계산)

먼저 주어진 책임을 살펴보겠습니다.

  • 할당된 Tensor 관리 (Parameters, Buffer)
    • GPU 할당, 타입 변환, state_dict 저장 및 로드
  • Forward: 주어진 입력을 계산해서 반환
    • Forward 연산 및 Backward 등록

위의 책임에 따라서 필요한 속성들은 다음과 같이 확인할 수 있습니다.
(여기에서는 객체지향애 관련된 문법들이 포함되어 있기도 합니다. Python 에서 일반적으로 변수이름 은 public, _변수이름 은 private를 의미하게 되죠.)

  • training: (bool) 학습 모드 여부
  • _parameters : (OrderedDict) Learnable Parameters
  • _buffers : (OrderedDict) module 에서 사용은 되나, Parameter 는 아닌 경우 (persistent, non-persistent)
  • _non_persistent_buffers_set : (OrderedDict) persistent 의 여부를 관리하는 자료구조
  • _backward_hooks : (OrderedDict) Tensor에도 있었던 register_hook 과 같은 로직으로, backward 에 사용
  • _forward_hooks : (OrderedDict) Tensor에도 있었던 register_hook 과 같은 로직으로, forward 에 사용
  • _forward_pre_hooks : (OrderedDict)Tensor에도 있었던 register_hook 과 같은 로직으로, forward 전에 사용
  • _state_dict_hooks : (OrderedDict) 모듈의 state_dict를 만들 때, hook 로직 사용
  • _load_state_dict_pre_hooks : (OrderedDict) 모듈의 state_dict를 기반으로 load 할때, 로드 전 hook 로직 사용
  • _modules : (OrderedDict) 해당 Module 의 자식 Module들을 관리하기 위한 자료구조

위의 속성들을 보면 해당 Module 이 다양한 상황들을 커버하기 위해서 열어놓은 부분들이 눈에 보일 것 입니다. 가장 크게는 hook 이 모든 연산과 심지어는 저장(state_dict())과 로드(load_state_dict()) 에도 들어가고 있습니다. 다양한 세부적인 Module 들이 만들어질 수 있고, 무엇이 어떻게 추가될지 모르기 때문에 위와 같이 열어둔 것으로 이해가 되네요.

hook 에 대해서 코드를 자세히 살펴보기 전에, 먼저 Module의 기본 사용법에 대해서 잠시 이야기를 해보겠습니다. 일반적으로 Module을 새로 정의할 때는 아래와 같이 sub-module 들을 정의하고, 그에 따른 forward 메서드를 정의하면 됩니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/nn/modules/module.py#L169

import torch.nn as nn
import torch.nn.functional as F

class Model(nn.Module):
	  def __init__(self):
	      super(Model, self).__init__()
	      self.conv1 = nn.Conv2d(1, 20, 5)
	      self.conv2 = nn.Conv2d(20, 20, 5)

	  def forward(self, x):
	      x = F.relu(self.conv1(x))
	      return F.relu(self.conv2(x)

이렇게 self.conv1 로 정의를 하면 다음의 메서드가 자연스럽게 호출됩니다. 바로 __setattr__ 입니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/nn/modules/module.py#L774

def __setattr__(self, name: str, value: Union[Tensor, 'Module']) -> None:
    if isinstance(value, Parameter):
        ...
    elif params is not None and name in params:
        ...
    else:
        modules = self.__dict__.get('_modules')
        if isinstance(value, Module):
            ...
        elif modules is not None and name in modules:
            ...
        else:
            buffers = self.__dict__.get('_buffers')

위와 같이 Module 안에 정의된 속성이 어떤 객체 인가에 따라서, Parameter 로서 등록이 될 수도 있고, Module 혹은 Buffer 로도 등록이 될 수 있습니다. 이것 역시 Python의 빌트인(__builtlins__)로 미리 정의되어 있는 내장 함수입니다. Class 가 가지는 기본 속성들을 Module 이라는 Class에 맞는 직관적인 사용법으로 변환시킨 것이죠.

다음으로는 모델이 output 을 만드는 코드를 살펴보겠습니다. 바로 hook 이 연결되어 있는 부분이기도 하죠. 위의 Module은 다음과 같은 방식으로 사용하게 됩니다.

model = Model()
ouptuts = model(inputs)  # Model 의 __call__ 로 연결

위와 같이 model 이 넘겨 받는 부분은 __call__ 이라는 빌트인 함수로 연결이 됩니다.

# code: https://github.com/pytorch/pytorch/blob/v1.6.0/torch/nn/modules/module.py#L710

def _call_impl(self, *input, **kwargs):
    # 1. Forward Pre-hook
    for hook in itertools.chain(
            _global_forward_pre_hooks.values(),
            self._forward_pre_hooks.values()):
        result = hook(self, input)
        if result is not None:
            if not isinstance(result, tuple):
                result = (result,)
            input = result

    # 2. Forward
    if torch._C._get_tracing_state():
        result = self._slow_forward(*input, **kwargs)
    else:
        result = self.forward(*input, **kwargs)  # 우리가 정의하는 forward

    # 3. Forward Hook
    for hook in itertools.chain(
            _global_forward_hooks.values(),
            self._forward_hooks.values()):
        hook_result = hook(self, input, result)
        if hook_result is not None:
            result = hook_result

    # 4. Backward Hook 등록
    if (len(self._backward_hooks) > 0) or (len(_global_backward_hooks) > 0):
        var = result
        while not isinstance(var, torch.Tensor):
            if isinstance(var, dict):
                var = next((v for v in var.values() if isinstance(v, torch.Tensor)))
            else:
                var = var[0]
        grad_fn = var.grad_fn
        if grad_fn is not None:
            for hook in itertools.chain(
                    _global_backward_hooks.values(),
                    self._backward_hooks.values()):
                wrapper = functools.partial(hook, self)
                functools.update_wrapper(wrapper, hook)
                grad_fn.register_hook(wrapper)
    return result

__call__ : Callable[..., Any] = _call_impl

위의 코드를 보면 __call__ 에는 우리가 정의하는 forward 외에도 많은 로직들이 있음을 알 수 있습니다. 각 부분을 나누어서 주석을 추가하였습니다. 내부에서는 생각보다 많은 일들을 하고 있었네요!

Forward Pre-hook → Forward → Forward Hook → Backward Hook 등록 (grad_fn)

처음 예제에서 보신 것처럼, Module 안에는 Sub-Module 들이 정의되고 순차적으로 __call__ 이 호출되게 됩니다. 이때마다 위와 같은 로직이 실행되게 되는 것이죠.

그 외에 참고할 만한 직관적인 코드를 하나 더 살펴보고자 합니다.

    @overload
    def to(self: T, device: Optional[Union[int, device]] = ..., dtype: Optional[Union[dtype, str]] = ...,
           non_blocking: bool = ...) -> T:
        ...

    @overload
    def to(self: T, dtype: Union[dtype, str], non_blocking: bool = ...) -> T:
        ...

    @overload
    def to(self: T, tensor: Tensor, non_blocking: bool = ...) -> T:
        ...

    def to(self, *args, **kwargs):

        device, dtype, non_blocking, convert_to_format = torch._C._nn._parse_to(*args, **kwargs)

        if dtype is not None:
            if not dtype.is_floating_point:
                raise TypeError('nn.Module.to only accepts floating point '
                                'dtypes, but got desired dtype={}'.format(dtype))

        def convert(t):
            if convert_to_format is not None and t.dim() == 4:
                return t.to(device, dtype if t.is_floating_point() else None, non_blocking, memory_format=convert_to_format)
            return t.to(device, dtype if t.is_floating_point() else None, non_blocking)

        return self._apply(convert)

Java 혹은 다른 객체지향 언어들을 사용해봤다면, 위와 같은 overload 는 익숙할 것이라고 생각이 됩니다. 같은 메소드의 이름을 가지고 있으나, 요구하고 있는 파라미터가 다른 경우를 의미합니다. 시그니처가 다르다고 표현을 할 수 있죠.
typing 에서는 위와 같은 문법으로서 기능을 지원합니다. (참고로, typing 은 Python 3.5 부터 지원이 되고 있고, 그 이전 버전들을 위해서 [pip](https://pypi.org/project/typing/) 를 통해서 팩키지를 설치할 수 있습니다.)

다시 module.to(...) 라는 매서드로 돌아가서 보면, device(cpu/gpu), dtype 등의 연상장비 지정, 타입 변환 등을 한꺼번에 다룰 수 있는 모습을 보이고 있습니다. 사용을 하는 입장에서는 다른 것들을 신경쓰지 않고 to 라는 메소드에 원하는 것을 넣기만 하면 되는 것이죠.

끝으로

지금까지 이야기한 것을 간단하게 정리해보겠습니다. 가장 기본이 되는 Tensorautograd.Function 그리고 nn.Module 에 대해서 살펴보았습니다. 데이터 클래스로서 필요한 속성들이 명시되어 있고, 그것을 forward , backward 로 큰 틀을 잡아놓고 수 많은 연산들이 여기에 맞춰서 추가되고 있습니다. 그리고 이 연산들을 하나의 Module 로서 마음껏 조합해서 사용할 수 있도록 준비가 되어있죠.

PyTorch 는 객제치향의 여러가지 특징을 잘 살린 프레임워크라고 생각이 됩니다. 그와 동시에 Python 언어가 가지는 특징들 또한 잘 활용하여 사용자들이 직관적으로 코드를 작성할 수 있도록 돕고 있습니다.

References

Categories
Offsites

Orbital edge computing: nano satellite constellations as a new class of computer system

Orbital edge computing: nanosatellite constellations as a new class of computer system, Denby & Lucia, ASPLOS’20.

Last time out we looked at the real-world deployment of 5G networks and noted the affinity between 5G and edge computing. In true Crocodile Dundee style, Denby and Lucia are entitled to say “that’s not the edge, this is the edge!”. Today’s paper choice has it all: clusters of formation-flying autonomous nanosatellites working in tandem to overcome the physical limitations of space and the limited bandwidth to earth. The authors call this Orbital Edge Computing in contrast to the request-response style of satellite communications introduced with the previous generation of monolithic satellites. Only space system architects don’t call it request-response, they call it a ‘bent-pipe architecture.’

Momentum towards large constellations of nanosatellites requires a reimagining of space systems as distributed, edge-sensing and edge-computing systems.

Satellites are changing!

Satellites used to be large monolithic devices, e.g. the 500kg, $192M Earth Observing-1 (EO-1) satellite. Over the last couple of decades there’s been a big switch to /nanosatellite/ constellations. Nanosatellites are typically 10cm cubes (for the “CubeSat” standard), weigh just a few kilograms, and cost in the thousands of dollars.

The CubeSat form-factor limits what can be packed into the device and how much power is available. Without higher-risk deployable solar arrays, a cubesat relies on surface-mounted solar panels to harvest energy. This results in peak available power of about 7.1W.

A constellation is a collection of nanosatellites (the space segment) and a collection of on-the-ground transceivers (the ground segment). Constellations today are in the hundreds of nanosatellites, and reconfiguring such a constellation from the ground can take months. Constellations with thousands of nanosatellites are on their way. And it seems we can add satellites to the growing list of things that get finer-grained over time:

Looking forward, we expect deployments of satellites that are even smaller than nanosatellites. Chip-scale or gram-scale satellites (“chipsats”) can be deployed even more numerously and at even lower cost.

The old ground-initiated command-and-control style systems aren’t going to work for these finer-grained systems. To see why, we need to look at some of the physical constraints of computation and communication in space.

Physical constraints

We’ve already seen that nanosatellites have about 7W of power to play with, which they harvest from the environment and store in batteries or supercapacitors. Beyond power, volume is the second key limiting factor, in particular restricting the amount you can pack onboard, and best focal length achievable with cameras.

The Ground Sample Distance (GSD) is the distance on the ground between one pixel and the next in a camera image. It’s a function of orbit altitude, camera focal length, and pixel sensor size. Nanosatellite systems have a GSD of around 3.0m/px. When it comes to GSD, lower is better.

The satellite takes images of a path on the ground called the /ground track/. As it moves around the ground track, the ideal frequency at which to take images is one where each frame is perfectly adjacent to the one before, with no overlapping pixels. This is called the Ground Track Frame Rate (GTFR).

In order to achieve sufficient coverage of a ground track, a satellite or constellation must capture images individually or in aggregate at the GTFR.

In the bent pipe architecture a satellite gathers and stores data until it is near a ground station, and then transmits whatever it has. This results in delays of up to 5.5 hours from capture to receipt of data. A ground station with a 200 Mbit/s downlink datarate can retrieve up to to 15GB of data during a ten minute session. Even under ideal conditions, such a ground station can only support 9 satellites per revolution. It would take 112 ideally positioned stations to support a 1000-node constellation.

Downlink bandwidth increases with receiver gain, which increases with dish diameter on ground stations. Cubesats can’t increase receiver gain in this way due to their limited device size. So uplink data volume is on the order of kilobytes per pass.

That’s not enough bandwidth to download data from thousands of nano-satellites, nor enough to efficiently reconfigure a cluster via the uplink. Satellites are going to have to take responsibility for more decisions on their own, without waiting for commands from a ground station, and they’re going to have to do more onboard processing of data to make better use of the limited downlink bandwidth.

Introducing Orbital Edge Computing (OEC)

Orbital Edge Computing (OEC) is designed to do just that. Coverage of a ground track and processing of image tiles is divided up between members of a constellation in a computational nanosatellite pipeline (CNP).

A CNP leverages existing formation flying techniques to orbit in a fixed configuration, parallelizing data collection and processing across a constellation.

With onboard image processing to identify interesting data, it might be possible to reduce 15GB of raw data down to about 0.75GB that needs to be sent to the ground station. This would take just 30s at 200 Mbit/s. Rather than servicing only 9 satellites per revolution, a ground station could then service 185. The particular form of local processing depends on the application, but it could include for example CNN-based image classification, object detection, segmentation, or even federated machine learning. The general scheme of only sending the interesting parts of the data is known as intelligent early discard.

OEC nanosatellites also run local software for autonomous control, modelling the satellite’s position in time and space, and achievable bitrate, to determine when to communicate and what to communicate (raw data or processed images). This removes the dependence on command-and-control structures initiated at the ground station and sent over the precious uplink bandwidth.

The unique characteristics of OEC systems stem from the astrodynamics that govern them, giving rise to fundamental differences compared to terrestrial edge computing systems.

Formation flying, and formation processing

The authors explore two different options for nanosatellite formations with respect to ground track frames (GTFs), and two different options for parallel processing of images. Combined, this results in four different possible OEC configurations.

In a frame-spaced formation the nanosatellites are placed exactly one GTF apart in distance. (My mental model is a sliding window with an array of read heads, so that multiple GTFs can be read in parallel your mileage may vary!). An interesting variant of frame-spacing is orbit spacing which distributes satellites evenly across an orbit giving improved communication opportunities.

A close-spaced formation of nanosatellites packs the nanosatellites as close together as possible, such that the end-to-end pipeline distance between the satellites is less than the length of one GTF.

Whether frame-spaced or close-spaced, there are two options for how each satellite processes an image frame. Consider an image divided up into a set of tiles. With frame-parallel processing each nanosatellite processes all the tiles in each frame. With tile-parallel different tile segments are assigned to different satellites, which then process only their own tiles.

Computing on the edge with cote

These ideas are all packaged together in cote, “the first full-system model for orbital edge computing.” cote has two main components: a pre-mission simulation library, and an online autonomous control library ( cote-lib) to be included in nanosatellite software stacks.

cote-lib runs continuously in the background on an OEC device, explicitly modeling ground station available… [it] enables an OEC satellite to adapt to changing orbit and power conditions in real-time; such fine-grained adaptation is impossible with high-latency bent-pipe terrestrial control.

cote tracks time using Universal Time (UT1), which measure the rotation of the earth relative to distant astronomical objects. It supports three different coordinate frames: Earth-centered inertial (ECI), latitude, longitude and height (LLH), and south, east, z (SEZ). It’s important to model the true oblate nature of the Earth as it matters when establishing communication links via ground satellites with narrow high-gain antenna beams.

Given time and position, cote can use orbital mechanics to model the state of a satellite relative to the rotating earth. The simplified general perturbation model (SGP4) is used as the orbital mechanics engine. SPG4 is the GPS of space!

Understanding where it is relative to the Earth enables cote to model the maximum achievable bitrate for downlink, crosslink, and uplink channels at any given point in time. This can be used to plan when and what to communicate back to earth.

Evaluation

I’m running out of space to cover the evaluation section in any depth, so here are the highlights:

  • “Bent pipes are fundamentally unscalable using a constellation of 250 nanosatellites in a $97.3^o$ inclination orbit.”
  • Frame-spaced and orbit-spaced constellations downlink the most data, due to the reduction in downlink contention from their spacing.
  • Close-spaced constellation have much lower effective bandwidth, but also much lower latency. This is especially marked in the tile-parallel scheme, where the latency reduction for close-spacing is 617x!
  • Enabling intelligent early discard can reduce the number of required ground stations by 24x.

We show that an OEC architecture can reduce ground infrastructure over 24x compared to a bent-pipe architecture, and we show that pipelines can reduce system edge processing latency over 617x.

There’s loads of good stuff in this paper that I didn’t have the space to cover here, so if you’re at all interested in this topic I highly recommend checking it out.

Categories
Offsites

The case for a learned sorting algorithm

The case for a learned sorting algorithm, Kristo, Vaidya, et al., SIGMOD’20

We’ve watched machine learning thoroughly pervade the web giants, make serious headway in large consumer companies, and begin its push into the traditional enterprise. ML, then, is rapidly becoming an integral part of how we build applications of all shapes and sizes. But what about systems software? It’s earlier days there, but ‘The case for learned index structures’(Part 1 Part 2), SageDB and others are showing the way.

Today’s paper choice builds on the work done in SageDB, and focuses on a classic computer science problem: sorting. On a 1 billion item dataset, Learned Sort outperforms the next best competitor, RadixSort, by a factor of 1.49x. What really blew me away, is that this result includes the time taken to train the model used!

The big idea

Suppose you had a model that given a data item from a list, could predict its position in a sorted version of that list. 0.239806? That’s going to be at position 287! If the model had 100% accuracy, it would give us a completed sort just by running over the dataset and putting each item in its predicted position. There’s a problem though. A model with 100% accuracy would essentially have to see every item in the full dataset and memorise its position – there’s no way training and then using such a model can be faster than just sorting, as sorting is a part of its training! But maybe we can sample a subset of the data and get a model that is a useful approximation, by learning an approximation to the CDF (cumulative distribution function).

If we can build a useful enough version of such a model quickly (we can, we’ll discuss how later), then we can make a fast sort by first scanning the list and putting each item into its approximate position using the model’s predictions, and then using a sorting algorithm that works well with nearly-sorted arrays (Insertion Sort) to turn the almost-sorted list into a fully sorted list. This is the essence of Learned Sort.

A first try

The base version of Learned Sort is an out-of-place sort, meaning that it copies the sorted elements into a new destination array. It uses the model to predict the slot in the destination array for each item in the list. What should happen though if the model predicts (for example) slot 287, but there’s already an entry in the destination array in that slot? This is a collision. The candidate solutions are:

  1. Linear probing: scan the array for nearest vacant slot and put the element there
  2. Chaining: use a list or chain of elements for each position
  3. A Spill bucket: if the destination slot is already full, just put the item into a special spill bucket. At the end of the pass, sort and merge the spill bucket with the destination array.

The authors experimented with all three, and found that the spill bucket approach worked best for them.

The resulting performance depends on the quality of the model predictions, a higher quality model leads to fewer collisions, and fewer out-of-order items to be patched in the final Insertion Sort pass. Since we’re punting on the details of the model for the moment, an interesting question is what happens when you give this learned sort a perfect, zero-overhead oracle as the model? Say we want to sort all the numbers from zero to one billion. A perfect zero-overhead oracle can be built by just using the item value as the position prediction. 1456? That will go in position 1456…

And what did happen when the authors tried to sort the numbers using this perfect zero-overhead oracle?

To our astonishment, in this micro-experiment we observed that the time take to distributed the keys into their final sorted position, despite a zero-overhead oracle function, took 38.7 sec and RadixSort took 37.5 sec.

Why? If it’s high performance you’re after, you can’t ignore mechanical sympathy. Radix Sort is carefully designed to make effective use of the L2 cache and sequential memory accesses, whereas Learned Sort is making random accesses all over the destination array.

Sympathy for the machine

How can learned sort be adapted to make it cache-efficient? The solution is to change the first pass of Learned Sort into a cascading Bucket Sort. Instead of determining the final position in the destination array, the model prediction is used to ascertain which bucket (or bin) the element should go into.

  1. Let $f$ be the number of buckets ($f$ for fan-out). The first phase of learned sort is a cascading Bucket Sort. The initial pass uses the model predictions to place input elements into one of $f$ ordered buckets. Then each of these buckets is partitioned into a further $f$ buckets, and so on recursively until a threshold bucket size $t$ is reached. If at any stage a model prediction places in a item in a bucket that is already full, this item is just moved to a spill bucket instead.

  2. Once we’re down to buckets of size $t$, each of these is approximately sorted using the model predictions to place elements at an exact predicted position within the bucket.

  3. Concatenate the sorted buckets in order (some may have less than $t$ elements in them), and use Insertion Sort to patch up any discrepancies in ordering.

  4. Sort and merge the spill bucket.

    The secret to good performance with Learned Sort is choosing $f$ and $t$ so that at least one cache-line per bucket fits into the cache, making memory access patterns more sequential. The trade-off in setting $f$ is as follows: larger $f$ allows us to make more use of the predictive power of the model at each step, smaller $f$ increases the chances that we can append to a given bucket without causing a cache miss. For best performance, $f$ should be set so that all the hot memory locations fit in the L2 cache. For the evaluation set-up, this meant $f$ was around 1,000.

    The parameter $t$ influences the number of elements likely to end up in the spill bucket. Empirically the authors found that maximum performance is obtained when fewer than 5% of the elements end up in the spill bucket, which equates to a $t$ of around 100 for large datasets (see §3.1.2).

    With these changes in place, if the number of elements to sort is close to the key domain size (e.g. sorting $2^{32}$ elements with 32-bit keys), then Learned Sort performs almost identically to Radix Sort. But when the number of elements is much smaller than the key domain size, Learne Sort can significantly outperform Radix Sort.

Oh, yes – about the model!

All of this depends of course on being able to train a sufficiently accurate model that can make sufficiently fast predictions, so that the total runtime for Learned Sort, including the training time still beats Radix Sort. For this, the authors use the Recursive Model Index (RMI) architecture as first introduced in ‘The case for learned index structures‘. In brief, RMI uses layers of simple linear models arranged in a hierarchy a bit like a mixture of experts.

During inference, each layer of the model takes the key as an input and linearly transforms it to obtain a value, which is used as an index to pick a model in the next layer.

The main innovation the authors introduce here is the use of linear spline fitting for training (as opposed to e.g. linear regression with an MSE loss function). Spline fitting is cheaper to compute and gives better monotonicity (reducing the time spent in the Insertion Sort phase). Each individual spline model fits worse than its closed-form linear regression counterpart, but the hierarchy compensates. Linear splines result in 2.7x faster training, and up to 35% fewer key swaps during Insertion Sort.

Evaluation

On synthetic datasets containing double-precision keys following a standard normal distribution, the authors compared Learned Sort to a variety of cache-optimized and highly tuned C++ implementations of alternative sorting algorithms, presenting the most competitive alternatives in their results. The following chart shows sorting rates over input dataset sizes varying from one million to one billion items

Learned Sort outperforms the alternative at all sizes, but the advantage is most significant when the data no longer fits into the L3 cache – an average of 30% higher throughput than the next best algorithm.

The results show that our approach yields an average 3.38x performance improvement over C++ STL sort, which is an optimized Quick- sort hybrid, 1.49x improvement over sequential Radix Sort, and 5.54x improvement over a C++ implementation of Tim- sort, which is the default sorting function for Java and Python.

Learned Sort’s advantage holds over real datasets as well (§6.1 for datasets included in the test), and for different element types:

[Learned Sort] results in significant performance improvements as compared to the most competitive and widely used sorting algorithms, and marks an important step into building ML-enhanced algorithms and data structures.

Extensions

The paper also describes several extensions to Learned Sort including sorting in-place, sorting on other key types (strings initially), and improving performance for datasets with many duplicate items.

Categories
Offsites

Helios: hyperscale indexing for the cloud & edge – part 1

Helios: hyperscale indexing for the cloud & edge, Potharaju et al., PVLDB’20

On the surface this is a paper about fast data ingestion from high-volume streams, with indexing to support efficient querying. As a production system within Microsoft capturing around a quadrillion events and indexing 16 trillion search keys per day it would be interesting in its own right, but there’s a lot more to it than that. Helios also serves as a reference architecture for how Microsoft envisions its next generation of distributed big-data processing systems being built. These two narratives of reference architecture and ingestion/indexing system are interwoven throughout the paper. I’m going to tackle the paper in two parts, focusing today on the reference architecture, and in the next post on the details of Helios itself. What follows is a discussion of where big data systems might be heading, heavily inspired by the remarks in this paper, but with several of my own thoughts mixed in. If there’s something you disagree with, blame me first!

Why do we need a new reference architecture?

Cloud-native systems represent by far the largest, most distributed, computing systems in our history. And the established cloud-native architectural principles behind them aren’t changing here. But zoom out one level of abstraction, and you can also look at cloud platforms as the largest, most-centralised, computing systems in our history. We push as much data processing as possible onto warehouse-scale computers and systems software. It’s a planet-scale client-server architecture with an enormous number of mostly thin clients sharing the services of a few giant server systems. There are several pressures on such a design:

  • The volume of data continues to grow – by another 2 orders of magnitude this decade according to IDC – as does the velocity of data arrival and the variance in arrival rates. At the same time, end users want results faster – from batch to real-time.

We are observing significant demand from users in terms of avoiding batch telemetry pipelines altogether.

  • It makes heavy use of comparatively expensive data-center computing facilities
  • It’s limited by the laws of physics in terms of end-to-end latency
  • It’s more challenging to build privacy-respecting systems when all data needs to shipped remotely to be processed

The first two of these pressures combine to cause cloud systems to run into one of two limits as exemplified by this quote from the paper:

None of our existing systems could handle these requirements adequately; either the solution did not scale or it was too expensive to capture all the desired telemetry. (Emphasis mine)

Latency limits are one of the drivers pushing us towards more edge computing – a trend which began with static content distribution, then dynamic content (both of which sit on the response path), and now is extending to true edge computation (that can also help improve the request path, e.g. by local processing either eliminating or reducing the amount of data that needs to be sent on to central servers). Industrial IoT use cases are an example here.

The emergence of edge computing has raised new challenges for big data systems… In recent years a number of distributed streaming systems have been built via either open source or industry effort (e.g. Storm, Spark Streaming, MillWheel, Dataflow, Quill). These systems however adopt a cloud-based, centralised architecture that does not include any “edge computing” component – they typically assum an external, independent data ingestion pipeline that directs edge streams to cloud storage endpoints such as Kafka or Event Hubs.

On the privacy front, with increasing awareness and regulation (a good thing, imho!), it’s getting much more complex and expensive to process, store, and secure potentially sensitive data. The most cost-effective mechanism of all is not to store it centrally, and not to process it centrally. Securing data you don’t have and never saw is free! In this regard the machine learning community is ahead of the systems community, with a growing body of work on federated machine learning.

The GDPR directive requires that companies holding EU citizen data provide a reasonable level of protection for personal data… including erasing all personal data upon request… Finding the list of data streams that contain the user’s information requires a provenance graph (as the number of streams is in the order of 10s of billions) and an index (as each stream can span multiple peta-bytes) to avoid expensive linear scans.

What does the new reference architecture look like?

The central idea in the Helios architecture is ’embrace the edge’. Although the word federated doesn’t actually appear in the paper at all, federated big-data systems (c.f. federated machine learning and federated database management systems) seems a reasonable way of describing what’s going on here.

Helios is an effort towards building a new genre of big data systems that combine the cloud and edge as a single, holistic data processing platform.

(And by extension, we could envision end-user devices being part of that holistic platform too).

In the olden days we used to talk about function shipping and data shipping. Function shipping being the idea that you move the compute to the data, and data shipping being the idea that you move the data to the compute. Within todays cloud systems, a lot of function shipping takes place, but for the clients that interact with them, it’s very heavily skewed towards data shipping. In federated big-data systems perhaps the appropriate terms would be function spreading and data spreading. I.e. compute can take place at multiple different points along the path from end device to cloud (and back again), and data can be spread out across layers too. A good guiding principle for designing such a system is probably to minimise data movement – i.e. (1) do as much processing as possible as close to the point of data capture as possible, and only send the aggregated results downstream, and then (2) where pools of data do amass, do as much querying of that data as close to the point of data storage as possible and only send the query results back upstream.

In Helios, this translates to coming up with efficient techniques for splitting computation between end devices, edge, and cloud.

This split has another interesting consequence. We saw earlier that there is end-user pressure to replace batch systems with much lower latency online systems. I observe that computation split across end devices, edge, and cloud doesn’t really sit well with batch processing either. We do distributed batch processing within a layer (e.g. map-reduce) but across layers is different. My conclusion is that federated big-data systems are also online systems. One nice advantage of unifying batch and online processing is that we don’t need to duplicate logic:

This solves the problem of maintaining code that needs to produce the same result in two complex distributed systems.

Generally batch systems have higher throughput and higher latency, and as we reduce the batch size towards online systems, we lower the latency and also the throughput. It will be interesting to watch the throughput characteristics of federated big data systems, but it’s a challenge I think we have to take on. (Helios’ throughput is plenty good enough btw.)

Technically, what might it look like to build a system that works in this way?

Based on our production experience, we posit that a single engine model can (1) enable optimizations such as automatically converting recurring batch queries into streaming queries, dynamically mapping operators/computations to various layers (e.g., end device, edge, cloud), automated A/B testing for figuring out the best query execution plans, join query optimization in multi-tenant scenarios and automatic cost-based view materialisation, and (2) significantly reduce user and operational burden of having to learn and maintain multiple complex stacks.

I’m going to throw one more requirement into the mix for next-generation big data systems. You won’t find this in the Helios paper, but it is something that Microsoft have articulated well in other works, notably Cloudy with a high chance of DBMS: a 10-year prediction for enterprise-grade ML . From a data systems perspective, machine learning is just data processing over (usually) big data sets. We don’t really want completely separate systems for federated machine learning and federated big-data, especially as there are many data cycles between the two (ML both consuming and producing data) and ML is increasingly becoming a mainstream part of many systems and applications. See e.g. the introduction to ‘The case for a learned sorting algorithm.’

The picture that forms in my mind is of a federated differential dataflow style system that processes and materializes just what is needed at each layer. E.g. in the Helios case, “we can similarly distribute the task of data summarization – including filtering, projections, index generation, and online aggregation – to end devices.” One nice thing that falls out of extending such a system all the way out to the end devices is that it means the dataflow engine is effectively responsible for managing all of those pesky caches, and especially cache invalidation.

There might be many different layers of edge compute (e.g. 5G base stations, CDN POPs, …) between an end-(user) device and a warehouse scale computer (WSC, aka the cloud). You can think of these as concentric rings forming around WSCs, and conceptually a federated big data system can span all of them.

So far we’ve mostly been talking about spreading compute and data along a single path from an end device to the cloud and back again, leading to a picture like this.

But of course it’s entirely possible (and common) for a node at one layer to interact with multiple nodes at the layer below, leading to a picture more like this:

And furthermore it’s easy to imagine cases where peer-to-peer communication between nodes at the same level also makes sense:

In general we’re looking at a dynamic dataflow topology with very large numbers of nodes.

Helios is a successful production example of a subset of these ideas, and we’ll look at Helios itself in much more detail in the next post. For now I’ll close with this thought:

Helios provides one example for a specific type of computation, i.e. indexing of data. There are a number of related problems, such as resource allocation, query optimization, consistency, and fault tolerance. We believe that this is a fertile ground for future research.

Categories
Offsites

Helios: hyperscale indexing for the cloud & edge (part II)

Helios: hyperscale indexing for the cloud & edge, Potharaju et al., PVLDB’20

Last time out we looked at the motivations for a new reference blueprint for large-scale data processing, as embodied by Helios. Today we’re going to dive into the details of Helios itself. As a reminder:

Helios is a distributed, highly-scalable system used at Microsoft for flexible ingestion, indexing, and aggregation of large streams of real-time data that is designed to plug into relationals engines. The system collects close to a quadrillion events indexing approximately 16 trillion search keys per day from hundreds of thousands of machines across tens of data centres around the world.

As an ingestion and indexing system, Helios separates ingestion and indexing and introduces a novel bottoms-up index construction algorithm. It exposes tables and secondary indices for use by relational query engines through standard access path selection mechanisms during query optimisation. As a reference blueprint, Helios’ main feature is the ability to move computation to the edge.

Requirements

Helios is designed to ingest, index, and aggregate large streams of real-time data (tens of petabytes a day). For example, the log data generated by Azure Cosmos. It supports key use cases such as finding records relating to specific attributes (e.g. for incident support), impact and drill-down analysis, and performance monitoring and reporting. One interesting use case is in support of GDPR right to be forgotten requests, where it becomes necessary to search 10s of billions of streams to find those containing a user’s information.

Incoming streams can have data rates as high as 4TB/minute, with many columns to be indexed (7+ is common) and high cardinality.

System design

A stream table is defined by a loose schema which defines the sources to be monitored (as a SourceList) and indices to be created. For example:

Based on the CREATE STREAM statement, Helios generates an agent executable to be deployed on every machine producing a log that is part of the stream. It also generates an executable to be run on the server-side ingestion machines. The agent process accumulates and chunks incoming data into data blocks (with frequency determined by the CHUNK EVERY clause). Optionally, and central to how Helios handles high volume and velocity ingest at manageable scale and cost, the agent can also perform local processing (parsing, indexing, and aggregation) and send the resulting index entries to the ingestion clusters in a compact format.

Ingestion servers are stateless, running the user-defined dataflow (based on the CREATE SCHEMA statement) to process incoming blocks. Data blocks are stored in a distributed file system, and once acknowledged by the file system, an entry is written into Helio’s progress log. The progress log is used to track the progress of both data ingestion and index building. Secondary index generation (hydration) then happens asynchronously. The resulting index blocks are merged into a global index which maps (column, value) pairs to data block URIs.

The progress log is the only strongly synchronized component in Helios, and is deployed in quorum based rings of 5 servers. There are multiple replicated logs each governing a partition of the data set. In this manner Helios achieves a consistent rate of 55,000 writes/second for metadata persistence.

Indexing

A key factor in Helios’s success is asynchronous index mangement: Helios maintains eventually consistent indexes against the data, but exposes a strongly consistent queryable view of the underlaying data with best-effort index support.

Helios’ index is a multi-level (tree-based) structure that is built in a bottom-up manner. I.e., information is inserted at the leaves, and the index then ‘grows upwards’ through merge and add operations. The authors point out an interesting similarity to learned index structures here: “At the highest level, a learned index tries to learn a function that maps an index search key to the leaf nodes containing the search key. The Helios structure in its generic form performs exactly the same function, with the different that the mapping is not learned from data but composed from the (typically, hash) partitioning functions used by the different index levels.

Indexing begins by scanning the progress log from the latest checkpoint, with an initial leaf node at the bottom of the tree (level 0) constructed for each chunk. No global order is imposed here, indexed keys are simply packed into leaf nodes based on arrival order. Multiple nodes at the same level may be combined into one using the merge operator in accordance with a merge policy. Just as level 0 watches blocks arrive in the progress log and follows along creating leaf nodes, so the next level up, level 1 watches the progress of leaf nodes arriving at level 0, and creates a higher level index over the leaf nodes by applying the add operator. Level 2 follows the progress of level 1 in a similar manner, and so on for the desired number of levels. The result is an indexing frontier that moves forward across the levels through a per-level watermark.

An index node is a collection of (key, pointers) pairs. The merge operation combines two index nodes $N_1$ and $N_2$ by taking the union of their keys, and for each key the union of the pointers. E.g. if $N_1 = {K_1 mapsto {P_1, P_2}, K_2 mapsto {P_3}}$ and $N_2 = {K_2 mapsto {P_4}}$ then $N_1 oplus N_2 = { K_1 mapsto {P_1, P_2}, K_2 mapsto {P_3, P_4 }}$. Helios uses a size-based merge policy in which two nodes are merged if they are both below a given size threshold.

The add operation creates a new node at one level up containing the union of the keys in the blocks being added, and pointers to the nodes in the level below containing entries for those keys. E.g. $N_1 + N_2 = {K_1 mapsto {P_{N_1}}, K_2 mapsto {P_{N_1}, P_{N_2}}}$. Helios also uses a size-based add policy, in which nodes are added (at higher and higher levels) until the size of the resulting node reaches a configurable threshold.

Note that the resulting structure may contain orphan nodes (shown in grey in the figure above) that do not have any parent in the layer above. This has implications for query processing that we’ll look at shortly.

Index compaction, which also takes place bottom-up, is triggered when a configurable number of data blocks have been processed.

Federated indexing

Our initial approach towards data and index management focused towards bringing in data from all the sources into an ingestion cluster and performing the required post-processing operations (e.g. parsing, indexing, etc.). However, this approach incurs significant costs… The hierarchical/recursive indexing model gives the freedom of distributing our computation acress the agents and ingestion back-end servers, sharing the same intuition as the current trend of edge computation.

Pre-processing on agents reduces the size of the ingestion cluster required, at the cost of consuming processing power on the source machine. In Helios production deployments, the agent typically consumes 15%-65% of a single CPU core, and stays under an allocated memory budget of 1.6GB. The generated agent and ingestion code utilises a shared library called Quark which provides a selection of parsers, extractors, indexers, partitioners, serializers and compressors as well as query-processing operators with predicate push-down.

Querying

Helios indexes are represented and exposed as data in easily accessible formats, available for any query engine. This allows us to democratise index usage outside of Helios, e.g. query engines can perform their own cost-based index access path selection, and index reads can independently scale without being constrained by compute resources provided by Helios. In fact, we were able to integrate Apache Spark with no changes to its optimizer/compiler.

Due to the existence of orphan nodes, querying can’t proceed in a pure top-down manner. So Helios provides a hybrid index scan operator. Querying starts by moving down the tree from the root nodes (which are orphan nodes by definition), and then recursively repeating this process for each of the orphan nodes at the next level down moving right.

In Figure 6 above for example, we can search down the tree from $N_{21}$, but in doing so we miss any potential hits in the orphan node $N_{13}$ at the next level down. So after processing $N_{21}$ we start a new search from $N_{13}$. This in turn may miss hits in the orphan block $N_{08}$ so we then drop-down once more and move right…

Helios in production

Helios has multiple uses at Microsoft including supporting debugging and diagnostics, workload characterization, cluster health monitoring, deriving business insights, and performing impact analysis.

Helios clusters have been in production for the last five years, collecting close to a quadrillion log lines per day from hundreds of thousands of machines spread across tens of datacenters.

Categories
Offsites

Virtual consensus in Delos

Virtual consensus in Delos, Balakrishnan et al. (Facebook, Inc.), OSDI’2020

Before we dive into this paper, if you click on the link above and then download and open up the paper pdf you might notice the familiar red/orange splash of USENIX, and appreciate the fully open access. USENIX is a nonprofit organisation committed to making content and research freely available – both conference proceedings and the recorded presentations of their events. Without in-person conferences this year, income is down and events are under threat. If you want to help them, you have options to donate, become a member, or even talk to your organisation about becoming a partner, benefactor, or patron. Every little helps!

Back in 2017 the engineering team at Facebook had a problem. They needed a table store to power core control plane services, which meant strong guarantees on durability, consistency, and availability. They also needed it fast – the goal was to be in production within 6 to 9 months. While ultimately this new system should be able to take advantage of the latest advances in consensus for improved performance, that’s not realistic given a 6-9 month in-production target. So realistically all that could be done was to choose an existing consensus implementation and integrate it. Integrating an existing implementation brings problems of its own though:

Laying the system over an existing shared log such as LogDevice would allow us to reach production quickly, but also tie us for perpetuity to the fault-tolerance and performance properties of that consensus implementation.

What Facebook needed, literally, was a plan to throw one away. I.e., a plan that let them get into production quickly with an existing implementation, and then be able to upgrade it later without disturbing system operation (nobody wants to take down the central control plane for maintenance!). This calls for the oldest tool in the box: a level of indirection. In other words, an API based abstraction over consensus, together with a runtime that supports hot-swapping of those implementations. The standout candidate as the API for consensus is the shared log.

Recently, the shared log has gained traction as an API for consensus in research and industry. Applications can replicate state via this API by appending updates to the shared log, checking its tail, and reading back updates from it. The consensus protocol is hidden behind the shared log API, allowing applications to bind to any implementation at deployment time.

Behind the shared log API is a log abstraction that maps log positions to log entries. If you think of this a bit like mapping memory addresses to data in memory, then another parallel comes to mind: the virtual address space. One logical log, but with different portions of the log address space mapped to different backing shared log instances. This is the core idea in Delos, a VirtualLog that virtualises consensus.

We propose the novel abstraction of a virtual shared log (or VirtualLog). The VirtualLog exposes a conventional shared log API; applications above it are oblivious to its virtualized nature. Under the hood, the VirtualLog chains multiple shared log instances (called Loglets) into a single shared log.

It’s such a powerful idea that I can imagine distributed systems implementers everywhere adopting it from now on. What does the VirtualLog give us?

Firstly, it solves the upgrade problem. We have an existing Loglet writing log entries into the address space. To upgrade, the portion of the address space managed by this Loglet is sealed to prevent further writes, and then the Loglet chain is reconfigured to add the new Loglet at the tail. That’s not just theoretical, Facebook actually did this in production while Delos was processing over 1.8 billion transactions per day. The initial version of Delos went into production after eight months using a ZooKeeper-backed Loglet implementation, and then four months later it was swapped out for a new custom-built NativeLoglet that gave a 10x improvement in end-to-end latency.

Once you have a trusted reconfiguration protocol to move from one Loglet chain configuration to another, you can do lots of interesting things. For example, Loglets might be instances of the same ordering protocol, but with different parameters, or they could be entirely different log implementations (e.g. replacing Paxos with Raft), or they could be shims over external storage systems. If you have an existing implementation with its own leader elections, internal reconfiguration, and epochs that can sit happily under the Loglet abstraction. But critically, Loglets no longer need to handle all of that complexity:

While the VirtualLog’s reconfiguration mechanism can be used solely for migrating between entirely different Loglet implementations, it can also switch between different instances of the same Loglet protocol with changes to leadership, roles, parameters, and membership. As a result, the Loglet itself can be a statically configured protocol, without any internal support for reconfiguration. In fact, the Loglet does not even have to implement fault-tolerant consensus (i.e. be highly available for appends via leader election), as long as it provides a fault tolerant seal command, which is theoretically weaker and simpler to implement.

This separation of concerns moves reconfiguration into the VirtualLog control plane, leaving Loglets responsible for the data plane. It makes reconfiguration easier as well as simplifying the implementation of Loglets. If a Loglet fails for appends, it is simply sealed and the VirtualLog switches to a new Loglet.

Sealing

A minimal Loglet needs to provide totally ordered, durable storage via the shared log API. It can do this within a static configuration with no support for role or membership changes and no leader election. What it must provide however, is a highly available seal command that prevents any new appends from being acknowledged.

Once sealed, a Loglet can never be unsealed. So we have a couple of handy properties that make implementing seal much easier than a general purpose highly available append: only one value can ever be proposed, and that value is sticky. In Facebook’s implementation of NativeLoglet, seal simply sets a bit on a quorum of servers.

In addition to seal, a minimal Loglet is also responsible for its own failure detection, asking the VirtualLog to reconfigure when a failure is detected, and supplying a new Loglet configuration minus the failed servers.

Reconfiguration

Existing consensus systems often store the configuration and epoch information inline in the same totally ordered log as other commands. For VirtualLog, that would mean writing the configuration for the new Loglet inside the log address space of the outgoing Loglet before it is sealed. And that would put more complexity onto Loglets, requiring them to be highly available for appends, not just seal.

The VirtualLog uses a separate MetaStore instead, whose job is to manage the configuration of the VirtualLog over time. Because reconfiguration happens less frequently than regular command sequencing, the consensus protocol for reconfiguration can favour simplicity over out-and-out performance. For Facebook’s Delos, reconfiguration latencies of 10s of ms are ok.

The MetaStore exposes a single versioned register supporting a conditional write: writing requires supplying a new value and an expected existing version. Any client can initiate a reconfiguration, or complete a reconfiguration begun by another client. Reconfiguration has three steps:

  1. The client seals the current chain by sealing its active segment. A call to checkTail will now return the start of a new active segment. This is an idempotent operation.
  2. The reconfiguring client writes a new chain to the MetaStore. Because of the conditional write, if multiple clients are racing to reconfigure, at most one one can win.
  3. The reconfiguring client fetches the new chain from the MetaStore (in the case where its write failed in step 2).

Clients trying to write to the old active segment after step 1 will receive a ‘sealed’ error code, and can retry after fetching the latest chain from the MetaStore.

The NativeLoglet

Delos currently supports three disaggregated Loglets acting as shims over external services (ZooKeeper, a LogDevice service, and a Backup service used for cold storage). It also has two of its own Loglet implementations that can be run either converged or disaggregated: the NativeLoglet and the StripingLoglet.

In production, Facebook use the NativeLoglet in converged form. NativeLoglet implements seal by setting a bit on a quorum of servers. It uses a a central sequencer to assign positions to commands and forward requests to LogServers. An append is considered globally committed once a majority acknowledge. If the sequencer fails, NativeLoglet simply becomes unavailable for appends.

Practically, we found this protocol much easier to implement than fault-tolerant consensus: it took just under 4 months to implement and deploy a production-quality native Loglet.

Striping Loglets

The StripedLoglet is where things start to get even more interesting. A StripedLoglet is responsible for one portion of the global log address space, but internally it further maps (stripes) that portion over multiple nested Loglets.

This provides a simple way (about 300 loc) to scale throughput. For example, a shared sequencer bottleneck can be relieved by introducing a rotating sequencer – multiple sequencers dividing an address space between them and sharing the same underling LogServers. Alternatively, the address space can mapped to multiple underlying LogServer clusters to increase throughput.

Even though it is a composite, a StripedLoglet must still be sealed as a whole even if only one of its stripes needs to be reconfigured.

Delos in production

The evaluation section has lots of good information on experiences running Delos in production, as well as some synthetic benchmarks. The in-production switch from a ZK Loglet to NativeLoglet was done for the first time on April 2nd 2019, and gave a 10x improvement at p99 for gets, and a 5x improvement for writes.

My favourite example here is a really cool use case for reconfiguration. Most of the time Delos runs with a converged Loglet implementation, since this reduces the external dependencies of a very critical system. Under a log spike though, it can be reconfigured to run with a disaggregated Loglet, giving higher throughput. A related example is when Delos is running in converged mode and e.g. two of the five converged database replicas crash. Now the database and the shared log are fate-sharing and at risk if one more node is lost…

In this situation (which was not uncommon), we found it valuable to reconfigure the system to a disaggregated log, temporarily decoupling the fate of the database and the log. Once the database was restored to five replicas, we reconfigured back.

The overheads of virtualisation are pleasingly low: about 100-150µs at p99 latency, 10s of ms for reconfiguration, and no impact on peak throughput.

Limitations and future work

It all sounds pretty amazing doesn’t it! There are a couple of limitations: (1) consensus protocols that exploit speculation or commutativity don’t currently fit under the Loglet API. “In future work, we plan to extend virtual consensus to partially ordered shared logs.”, and (2) there’s a latency hit for VirtualLog-driven reconfiguration which may or may not be important in your scenario.

Categories
Offsites

Achieving 100Gbps intrusion prevention on a single server

Achieving 100 Gbps intrusion prevention on a single server, Zhao et al., OSDI’20

Papers-we-love is hosting a mini-event this Wednesday (18th) where I’ll be leading a panel discussion including one of the authors of today’s paper choice: Justine Sherry. Please do join us if you can.

We always want more! This stems from a combination of Jevon’s paradox and the interconnectedness of systems – doing more in one area often leads to a need for more elsewhere too. At the end of the day, there are three basic ways we can increase capacity:

  1. Increasing the number of units in a system (subject to Amdahl’s law).
  2. Improving the efficiency with which we can coordinate work across a collection of units (see the Universal Scalability Law)
  3. Increasing the amount of work we can do on a single unit

Options 1 and 2 are of course the ‘scale out’ options, whereas option 3 is ‘scale up’. With more nodes and more coordination comes more complexity, both in design and operation. So while scale out has seen the majority of attention in the cloud era, it’s good to remind ourselves periodically just what we really can do on a single box or even a single thread.

Today’s paper choice is a wonderful example of pushing the state of the art on a single server. We’ve been surrounding CPUs with accelerators for a long time, but at the heart of Pigasus‘ design is a really interesting inversion of control – the CPU isn’t coordinating and calling out to the accelerator, instead the FGPA is in charge, and the CPU is playing the support role.

IDS/IPS requirements

Pigasus is an Intrusion Detection / Prevention System (IDS/IPS). An IDS/IPS monitors network flows and matches incoming packets (or more strictly, Protocol Data Units, PDUs) against a set of rules. There can be tens of thousands of these rules, which are called signatures. A signature in turn is comprised of one or more patterns matching against either the header or the packet content, including both exact string matches and regular expressions. Patterns may span multiple packets. So before matching, the IDS/IPS has to reconstruct a TCP bytestream in the face of packet fragmentation, loss, and out-of-order delivery – a process known as reassembly.

When used in prevention mode (IPS), this all has to happen inline over incoming traffic to block any traffic with suspicious signatures. This makes the whole system latency sensitive.

So we need low latency, but we also need very high throughput:

A recurring theme in IDS/IPS literature is the gap between the workloads they need to handle and the capabilities of existing hardware/software implementations. Today, we are faced with the need to build IDS/IPSes that support line rates on the order of 100Gbps with hundreds of thousands of concurrent flows and capable of matching packets against tens of thousands of rules.

Moreover, Pigasus wants to do all this on a single server!

Back of the envelope

One of the joys of this paper is that you don’t just get to see the final design, you also get insight into the forces and trade-offs that led to it. Can you really do all this on a single server??

The traditional approach to integrating FPGAs in IDS/IPS processing is to have the CPU in charge, and offload specific tasks, such as regular expression parsing, to the FPGA. The baseline for comparison is Snort 3.0, “the most powerful IPS in the world” according to the Snort website. In particular, Pigasus is designed to be compatible with Snort rulesets and evaluated using the Snort Registered Ruleset (about 10K signatures). The biggest fraction of CPU time in Snort is spent in the Multi-String Pattern Matcher (MSPM) module, which is used for header and partial string matching.

Using Amdahl’s Law, we can see that even if MSPM were offloaded to an imaginary, infinitely fast accelerator, throughput would increase by only 85% to 600Mbps/core, still requiring 166 cores to reach 100Gpbs.

In fact, whatever module of Snort you try to offload to a hypothetical infinitely fast accelerator, you can never get close to the performance targets of Pigasus. That fixes Pigasus’ first design decision: the FPGA needs to be in charge as the primary compute platform, and the CPU will be secondary in service of it. (FPGAs are chosen because they are both energy efficient and available on SmartNICs).

Having settled on an FPGA-first design, this means that stateful packet processing for matching and reassembly needs to be performed on the FPGA. And that in turn means that the primary design constraint is the amount of FPGA memory available, especially Block RAM (BRAM). The target FPGA for Pigasus has 16MB of BRAM.

Of concern here is the regular expression matching performed by the Full Matcher. Regular expression matching is well studied, but state of the art hardware algorithms don’t reach the performance and memory targets needed for Pigasus. Performing RE matching on the FPGA would consume a lot of memory, and offer only marginal overall performance gains since most packets don’t touch the full matcher. This brings us to another major design decision: regular expression matching will be offloaded from the FPGA to the CPU.

Introducing Pigasus

Putting together everything we’ve learned so far, the overall architecture of Pigasus looks like this:

  • The reassembler is responsible for ordering TCP packets. It needs to do this at line rate while maintaining state for 100K flows.
  • The multi-string pattern matcher (MSPM) does header matching for all 10,000 rules, and exact string-match filtering to determine which further rules might possibly match.
  • If the MSPM indicates a possible match, the packet and rule IDs are sent to the DMA Engine, which farms work out to the CPU for full matching.
  • The Full Matcher runs on the CPU, polling a ring buffer populated by the DMA Engine.

To save the precious BRAM for the most performance sensitive tasks (reassembly and MSPM), the packet buffer and DMA Engine use the less powerful eSRAM and DRAM available on the FPGA.

Both the reassembler and MSPM modules required careful design to meet their performance and memory targets.

The reassembler: processing fast and slow

The key objective of our Reassemble is to perform this re-ordering for 100K’s of flows, while operating at 100Gbps, within the memory limitations of the FPGA.

The FPGA hardware really wants to operate in a highly parallel mode using fixed size data structures. This works well until we consider out of order packet arrival. To accomodate out-of-order packets though, a memory dense structure such as a linked list works better.

The solution is to divide the reassembly pipeline into a fast path handling in-order flows using fixed size buffers and constant time operations, and a slow path handling the remaining out of order flows. The constant time operations on the fast path guarantee a processing rate of 25 million packets-per-second, enough to reach the 100Gbps target at 500B+ packets. The slow path can’t take advantage of constant time operations, but fortunately is less often used as most packets arrive in order. It’s also used when inserting new flows.

The fast path, new flow insertion, and out-of-order processing all synchronise over shared flow state using a cuckoo-hashing based hash table design from FlowBlaze.

MPSM: First things first

There are challenges in the design of the MSPM too.

To the best of our knowledge, there are no other hardware or software projects reporting multi-string matching of tens of thousands of strings at 100Gpbs.

Snort 3.0 uses Intel’s Hyperscan library for MSPM. The Hyperscan string matching library is parallelisable and provides an 8x speedup over software state-machine based string matchers. But a simple translation to FPGA would blow the memory budget, requiring about 25MB of BRAM.

By carefully staging the work, Pigasus manages to fit everything into just 2MB of BRAM. This means it even has capacity to do more work in the MSPM stage than Snort itself does, reducing the amount of packets that need to be passed to the full matcher.

At the end of the day, a packet must match all the patterns in a signature for the rule to be triggered. The key insight in Pigasus is that some tests can be done very cheaply in terms of time and memory, while others are more memory intensive. Put this together with the realisation that most packets and most indices don’t match any rules at all and a plan emerges: make a filtering pipeline that progressively narrows. At the start of the pipeline we can afford to run lots of memory-cheap filters in parallel. Only a subset of incoming packets make it past these filters, so we need less of the more memory intensive filters running in parallel behind them to achieve the desired line rate.

Applying this filter first allows us to use fewer replicas of subsequent data structures (which are larger and more expensive), since most bytestream indices have already been filtered out by the string matcher. This enables high (effective) parallelism with a lower memory overhead.

This strategy is so effective that whereas Snort passes a packet to the full matcher if any filter matches, Pigasus is able to test for all string matches and further reduce the fraction of packets that head to the CPU for full-matching to just 5%. This testing is performed in parallel using a bloom-filter like representation, see §5.2 in the paper for details.

Headline results

Our experiments with a variety of traces show that Pigasus can support 100Gbps using an average of 5 cores and 1 FPGA, using 38x less power than a CPU-only approach.

There’s a full evaluation in §6 of the paper which I don’t have space to cover here. The headline is that Pigasus meets its design objectives using 23-200 fewer cores than Snort, and 18-62x less power!

The design of Pigasus is a singular proof point that a seemingly unattainable goal (…) on a single server is well within our grasp… Given the future hardware roadmaps of FPGAs and SmartNICs, we believe that our insights and successes can more broadly inform in-network acceleration beyond IDS/IPS as well.

Categories
Offsites

Elle: inferring isolation anomalies from experimental observations

Elle: inferring isolation anomalies from experimental observations, Kingsbury & Alvaro, VLDB’20

Is there anything more terrifying, and at the same time more useful, to a database vendor than Kyle Kingsbury’s Jepsen? As the abstract to today’s paper choice wryly puts it, “experience shows that many databases do not provide the isolation guarantees they claim.” Jepsen captures execution histories, and then examines them for evidence of isolation anomalies. General linearizability and serializability checking are NP-complete problems due to extreme state-space explosion with increasing concurrency, and Jepsen’s main checker, Knossos, taps out on the order of hundreds of transactions.

Databases are in for an ‘Ell(e) of a hard time with the new checker in the Jepsen family though, Elle. From the README:

Like a clever lawyer, Elle looks for a sequence of events in a story which couldn’t possibly have happened in that order, and uses that inference to prove the story can’t be consistent.

The paper describes how Elle works behind the scenes, and gives us a taste of Elle in action. Elle is able to check histories of hundreds of thousands of transactions in just tens of seconds. Which means whole new levels of stress for systems under test.

In the evaluation section we see Elle being used to test two SQL databases (TiDB, YugaByteDB), a document database (Fauna), and a graph database (Dgraph). By now I hardly consider it a plot-spoiler to tell you that it finds (unexpected) anomalies in all of them. You’ll find the details in §6 of the paper, and more information on the collaboration between Jepsen and the respective vendors to find and fix these issues on the Jepsen website.

What do we want from a transaction isolation checker?

An ideal transaction isolation checker would be able to…

  • Work with general patterns of transactions (not just specially chosen ones)
  • Detect many different types of anomalies, such that multiple isolation levels can be tested
  • Provide minimal reproducible bug reports when it does find a violation
  • Be efficient, so that large numbers of transactions at high levels of concurrency can be checked
  • Only report genuine anomalies (soundness)
  • Find all anomalies that exist in a history (completeness)

Elle ticks all the boxes, with the exception of completeness. In practice though, Elle typically does observe enough of a history to detect both cyclic and non-cyclic anomalies when they occur, with a guarantee holding under certain conditions.

Anomalies and the Direct Serialization Graph

Adya et al. gave portable definitions of isolation levels and anomalies in their 2000 paper “Generalized Isolation Level Definitions.” Central to the analysis is the notion of a Direct Serialization Graph (DSG). In a DSG nodes represent transactions, and edges between nodes are dependencies between transactions. There are three different types of edges possible between two transactions $T_i$ and $T_j$.

  • a write dependency occurs when $T_j$ overwrites a value previously written by $T_i$.
  • a read dependency occurs when $T_j$ reads a value previously written by $T_i$ (ignoring the complications of predicate reads for now)
  • an anti-dependency occurs when $T_j$ overwrites a value previously read by $T_i$.

The thing all these have in common is that they imply $T_j$ must follow $T_i$ in any serializable history. From this it follows that any cycle in the DSG means that there cannot be a valid serial history.

If only…

What Knossos does is identify write-read dependencies between transactions, translate these into an integer constraint problem, and feed it to a constraint solver to try and find a legitimate serial history. This works to a point but runs into the state-space explosion issues we touched on earlier with histories on the order of (small numbers of) hundreds of transactions. Moreover, when the constraint solver says “no”, we don’t have any insight into why the constraints couldn’t be solved.

This is all a lot more complex than the cycle checking needed in Adya’s model. For example, in a strongly connected component of a graph, every node in the component is reachable from every other node in the same component. If A is reachable from B, and B is reachable from A, we have a cycle! Tarjan’s strongly connected components algorithm can find the strongly connected components in a graph in linear time!

If only we actually had one of Adya’s Direct Serialization Graphs for a given run, then we’d have the triple benefit of anomaly detection exactly matching the definitions of the anomalies, explainability of the anomalies found in terms of those definitions (show the cycle), and linear runtime.

… there is one significant obstacle to working with an Adya history: we don’t have it. In fact, one may not even exist – the database system may not have any concept of a version order, or it might not expose that ordering information to clients.

Recoverability and traceability

So maybe we don’t have an Adya history out of the box. But can we recover one? That is, are there observations we could make of the running system, that are in our control, that would let us infer an Adya history? We know the nodes in the graph – that’s the set of transactions we submit – and we know the operations within those transactions (the reads and writes), as well as having visibility of commit and abort operations. What we need then, is some way of determining the edges.

If every written value is unique, and we have a scheme that enables mapping unique values back to transactions, then when we read a value (in $T_j$), we can always tell which transaction $T_i$ must have written it. This enables us to find the read dependency edges, a property the authors call recoverability.

For a write dependency though, we need to know the transaction $T_i$ that previously wrote the value $T_j$ is overwriting. Unfortunately that history is lost at the moment the old value is overwritten. Unless… we use a datatype that supports append operations (like a string, with concat, or an array), and we follow the convention that all writes must be appends of recoverable values. Now when we read the value, the full history is contained within it. E.g., we might read the list $[(T_i, 1), (T_j, 2)]$ and know that $T_i$ first wrote the value 1, and $T_j$ subsequently wrote the value 2. This is a property the authors call traceability.

If we’ve got recoverability and traceability then with a bit more work we can also find the anti-dependency edges – we have visibility into the return values of read operations, and we just have to look for traceable writes that append to that read value.

Because the model also includes commit and abort operations, this process additionally enables us to detect dirty updates where a transaction commits a version based on reading uncommitted state, as well as corruptions (garbage reads) where a transaction reads a value that no-one has written!

Inferring Direct Serialization Graphs

An inferred direct serialization graph is a DSG constructed from the inferred dependencies between transactions using the techniques just outlined. There’s one more piece of information we can use too, since we control the processes: if process $P$ performs $T_i$ and then $T_j$ then we know that $T_i$ must come before $T_j$ in the history. Adding in these per-process dependencies means that we can strengthen consistency checking in some cases (e.g. from snapshot isolation to strong session snapshot isolation).

Giving the database the benefit of the doubt

Things get a bit more complicated once we allow for the possibility of in-doubt transactions:

… when a client attempts to commit a transaction, but the result is unknown, e.g. due to a timeout or database crash, we leave the transaction with neither a commit nor abort operation.

Observations made in the presence of in-doubt transactions are said to be indeterminate. The problem then arises that there may be many possible histories compatible with the observation.

Elle provides soundness in the face of this complication by constructing a dependency graph which is a (maximal?) subgraph of every possible history compatible with that observation. If a cycle is detected in the subgraph, than it must exist in all compatible histories.

Putting it altogether

Putting this altogether, Elle can detect cycle-based dependencies (Adya’s G0, G1c, G-single, and G2 cycles), aborted reads, intermediate reads, and dirty updates.

In addition, there are phenomena which Adya et al.’s formalism does not admit, but which we believe (having observed them in real databases) warrant special verification.

These are the aforementioned garbage reads, as well as duplicate writes (the same argument written multiple times) and internal inconsistencies (where a transactions reads a value incompatible with its own prior reads and writes).

I’ve only been able to give a high level appreciation in this post, rest assured the paper itself is precise in its terminology and analysis, as befits the subject matter. If these ideas have caught your interest, it’s well worth reading in full.

The last word

Elle is effective. It has found anomalies in every database we’ve checked, ranging from internal inconsistency and aborted reads to anti-dependency cycles… Unlike solver-based checkers, Elle’s cycle-detection approach produces short witnesses of specific transactions and human-readable explanations of why each witness must be an instance of the claimed anomaly… We believe Elle will make the database industry safer.