Riak VClock

简介:

Riak VClock

关于向量时钟的概念。在这里就多讲了,大家能够參照一下Dynamo的论文了解一下,向量时钟在分布式主要用于解决一致性性问题。能够和CRDTs一起看。

以下的源码是參照riak中的,就是把它翻译为elixir格式而已。基本不变。

时钟主要出现的情况有网络分区和并行更新。

这样仅仅会丢掉一些向量时钟的信息,即数据更新过程的信息,可是不会丢掉实实在在的数据。仅仅有当一种情况会有问题,就是一个client保持了一个非常久之前的向量时钟,然后继承于这个向量时钟提交了一个数据,此时就会有冲突。由于服务器这边已经没有这个非常久之前的向量时钟信息了,已经被剪枝掉了可能,所以client提交的此次数据,在服务端无法找到一个祖先。此时就会创建一个sibling。

所以这个剪枝的策略是一个权衡tradeoff,一方面是无限增长的向量时钟的空间。还有一方面是偶尔的会有"false merge"。对,但肯定的是,不会悄无声息的丢数据。综上。为了防止向量时钟空间的无限增长,剪枝还是比用server标识向量时钟工作的更好。

  • 结构:

主要有3个元祖{node, {opCount, TS}},分布为节点(协调器)。操作数和操作时间。

  • 基本的方法:

merge(合并):

合并的规则是,opCount>TS:当节同样时,谁的opCount大,谁赢;假设opCount一样时,谁的时间大谁赢。

@doc """
  Combine all VClock in the input list into their least possible common descendant
  """
  @spec merge(list, list) :: list
  def merge([]), do: []
  def merge([singevclock]), do: singevclock
  ## first is a list, eg [:a, {1, 1234}]
  # rest is list of list, eg [[{:a, {1, 233}}, {:b, {3, 124}}]]
  def merge([first|rest])  do
    merge(rest, :lists.keysort(1, first))
  end
  def merge([], nclock), do: nclock
  def merge([aclock|vclocks], nclock)  do
    merge(vclocks, merge(:lists.keysort(1, aclock), nclock, []))
  end
  def merge([], [], accclock), do: :lists.reverse(accclock)
  def merge([], left, accclock), do: :lists.reverse(accclock, left)
  def merge(left, [], accclock), do: :lists.reverse(accclock, left)
  def merge(v = [{node1, {ctr1, ts1} = ct1} = nct1 | vclock],
            n = [{node2, {ctr2, ts2} = ct2} = nct2 | nclock], accclock) do
    cond do
      node1 < node2 ->
        merge(vclock, n, [nct1|accclock]);
      node1 > node2 ->
        merge(v, nclock, [nct2|accclock]);
      true ->
        ({_ctr, _ts} = ct) = cond do
                            ctr1 > ctr2 ->
                              ct1;
                            ctr1 < ctr2 ->
                              ct2;
                            true ->
                              {ctr1, :erlang.max(ts1, ts2)}
                          end
        merge(vclock, nclock, [{node1, ct}|accclock])
    end
  end


prune(裁剪):

裁剪的法则主要是空间时间双方面.
!()[../pic/riak_4.png]

终于的裁剪函数prune_vclock1(v, now, bprops, headtime).

@doc """
  Possibly shrink the size of a vclock, depending on current age and size
  """
  @spec prune(v :: list, now :: integer, bucketprops :: any) :: list
  def prune(v, now, bucketprops) do
    ## This sort need to be deterministic, to avoid spurious merge conflicts later,
    # We achieve this by using the node ID as secondary key
    sortv = :lists.sort(fn({n1, {_, t1}}, {n2, {_, t2}}) -> {t1, n1} < {t2, n2} end, v)
    prune_vclock1(sortv, now, bucketprops)
  end

  def prune_vclock1(v, now, bprops) do
    case get_property(:small_vclock, bprops) >= :erlang.length(v) do
      true -> v;
      false ->
        {_, {_, headtime}} = hd(v)
        case (now - headtime) < get_property(:young_vclock, bprops) do
          true -> v;
          false -> prune_vclock1(v, now, bprops, headtime)
        end
    end
  end

  def prune_vclock1(v, now, bprops, headtime) do
    # has a precondition that v is longer than small and older than young
    case (:erlang.length(v) > get_property(:big_vclock, bprops)) or ((now - headtime) > get_property(:old_vclock, bprops)) do
        true -> prune_vclock1(tl(v), now, bprops);
        false -> v
    end
  end

  def get_property(key, pairlist) do
    case :lists.keyfind(key, 1, pairlist) do
      {_key, value} ->
        value;
      false ->
        :undefined
    end
  end


  • source
defmodule VClock do
  @moduledoc """
    this is !!!!!!!!
  """
  @vsn 0.1

  @spec fresh() :: []
  def fresh do
    []
  end

  # return true if va is a direct descendant of vb, else false -- remember, a vclock is its own descendant!
  @spec descends(any, []) :: (true|false)
  def descends(_, []) do
    true
  end

  @type va :: list()
  @spec descends(any, any) :: (false|true)
  def descends(va, vb) do
    [{nodeb, {ctrb, _}} | resetb] = vb
    case :lists.keyfind(nodeb, 1, va) do
      false ->
        false;
      {_, {ctra, _tsa}} ->
        (ctra >= ctrb) && descends(va, resetb)
    end
  end

  @doc """
  Combine all VClock in the input list into their least possible common descendant
  """
  @spec merge(list, list) :: list
  def merge([]), do: []
  def merge([singevclock]), do: singevclock
  ## first is a list, eg [:a, {1, 1234}]
  # rest is list of list, eg [[{:a, {1, 233}}, {:b, {3, 124}}]]
  def merge([first|rest])  do
    merge(rest, :lists.keysort(1, first))
  end
  def merge([], nclock), do: nclock
  def merge([aclock|vclocks], nclock)  do
    merge(vclocks, merge(:lists.keysort(1, aclock), nclock, []))
  end
  def merge([], [], accclock), do: :lists.reverse(accclock)
  def merge([], left, accclock), do: :lists.reverse(accclock, left)
  def merge(left, [], accclock), do: :lists.reverse(accclock, left)
  def merge(v = [{node1, {ctr1, ts1} = ct1} = nct1 | vclock],
            n = [{node2, {ctr2, ts2} = ct2} = nct2 | nclock], accclock) do
    cond do
      node1 < node2 ->
        merge(vclock, n, [nct1|accclock]);
      node1 > node2 ->
        merge(v, nclock, [nct2|accclock]);
      true ->
        ({_ctr, _ts} = ct) = cond do
                            ctr1 > ctr2 ->
                              ct1;
                            ctr1 < ctr2 ->
                              ct2;
                            true ->
                              {ctr1, :erlang.max(ts1, ts2)}
                          end
        merge(vclock, nclock, [{node1, ct}|accclock])
    end
  end

  @doc """
  get the counter value in vclock set from node
  """
  @spec get_counter(node :: atom, vclock::list) :: (integer|:undefined)
  def get_counter(node, vclock) do
    case :lists.keytake(node, 1, vclock) do
      {_, {c, _}} -> c;
      false -> :undefined
    end
  end

  @doc """
  Get the timestamp value in a VClock set from node
  """
  @spec get_timestamp(node :: atom, vclock :: list) :: (integer | :undefined)
  def get_timestamp(node, vclock) do
    case :lists.keytake(node, 1, vclock) do
      {_, {_, ts}} -> ts;
      false -> :undefined
    end
  end
  @doc """
    increment VClock at node
  """
  @spec increment(atom, list) :: integer
  def increment(node, vclock) do
    increment(node, timestamp(), vclock)
  end
  @spec increment(atom, integer, list) :: list
  def increment(node, incts, vclock) do
    IO.puts "#{inspect node}, #{inspect incts}, #{inspect vclock}"
    {{_ctr, _ts} = c1, newv} = case :lists.keytake(node, 1, vclock) do
                                  false ->
                                    {{1, incts}, vclock};
                                  {:value, {_n, {c, _t}}, modv} ->
                                    {{c + 1, incts}, modv}
                               end
    [{node, c1} | newv]
  end

  # retrun the list of all nodes that have ever incremented VClock
  @spec all_nodes(vclock :: list) :: (list)
  def all_nodes(vclock) do
    vclock |> Enum.map(fn({x, {_, _}}) -> x end)
  end
  @days_from_gergorian_base_to_epoch (1978 * 365 + 478)
  @seconds_from_gergorian_base_to_epoch (@days_from_gergorian_base_to_epoch * 24 * 60 * 60)
  @spec timestamp() :: integer
  def timestamp do
    {megaseconds, seconds, _} = :os.timestamp()
    @days_from_gergorian_base_to_epoch + megaseconds * 1000000 + seconds
  end

  @doc """
   Compares two VClock for equality
  """
  @spec equal(va :: list, vb :: list) :: (true | false)
  def equal(va, vb) do
    Enum.sort(va) === Enum.sort(vb)
  end

  @doc """
  Possibly shrink the size of a vclock, depending on current age and size
  """
  @spec prune(v :: list, now :: integer, bucketprops :: any) :: list
  def prune(v, now, bucketprops) do
    ## This sort need to be deterministic, to avoid spurious merge conflicts later,
    # We achieve this by using the node ID as secondary key
    sortv = :lists.sort(fn({n1, {_, t1}}, {n2, {_, t2}}) -> {t1, n1} < {t2, n2} end, v)
    prune_vclock1(sortv, now, bucketprops)
  end

  def prune_vclock1(v, now, bprops) do
    case get_property(:small_vclock, bprops) >= :erlang.length(v) do
      true -> v;
      false ->
        {_, {_, headtime}} = hd(v)
        case (now - headtime) < get_property(:young_vclock, bprops) do
          true -> v;
          false -> prune_vclock1(v, now, bprops, headtime)
        end
    end
  end

  def prune_vclock1(v, now, bprops, headtime) do
    # has a precondition that v is longer than small and older than young
    case (:erlang.length(v) > get_property(:big_vclock, bprops)) or ((now - headtime) > get_property(:old_vclock, bprops)) do
        true -> prune_vclock1(tl(v), now, bprops);
        false -> v
    end
  end

  def get_property(key, pairlist) do
    case :lists.keyfind(key, 1, pairlist) do
      {_key, value} ->
        value;
      false ->
        :undefined
    end
  end

end





本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5229840.html,如需转载请自行联系原作者
相关文章
|
数据可视化 Linux 网络安全
CentOS7.9下离线安装OctoMation编排自动化SOAR开源社区免费版
CentOS7.9下离线安装OctoMation编排自动化SOAR开源社区免费版
438 0
PCIe锁定事务(Locked Transactions)介绍
PCIe锁定事务(Locked Transactions)介绍
984 0
PCIe锁定事务(Locked Transactions)介绍
|
机器学习/深度学习 人工智能 搜索推荐
未来人工智能在后端开发中的应用前景
随着人工智能技术的不断发展,后端开发领域也迎来了新的机遇与挑战。本文探讨了人工智能在后端开发中的应用前景,分析了其对传统开发模式的影响和未来发展趋势。
|
8月前
|
人工智能 自然语言处理 数据可视化
AutoAgents:比LangChain更激进的AI开发神器!自然语言生成AI智能体军团,1句话搞定复杂任务
AutoAgents 是基于大型语言模型的自动智能体生成框架,能够根据用户设定的目标自动生成多个专家角色的智能体,通过协作完成复杂任务。支持动态生成智能体、任务规划与执行、多智能体协作等功能。
1439 91
|
9月前
|
机器学习/深度学习 供应链 搜索推荐
优化销售预测:6种模型适用的场景与实战案例
不同行业的销售预测采用什么模型比较好?3分钟了解6种销售预测模型,以及适用行业场景。
1703 2
优化销售预测:6种模型适用的场景与实战案例
|
11月前
|
机器学习/深度学习 人工智能 算法
从 OpenAI-o1 看大模型的复杂推理能力
深入解析OpenAI o1模型的复杂推理技术与发展历程
从 OpenAI-o1 看大模型的复杂推理能力
|
存储 数据可视化 数据挖掘
R语言在生物信息学中的应用
【4月更文挑战第25天】生物信息学是生物学、计算机科学和信息技术相结合的交叉学科,主要研究生物大分子信息的存储、处理、分析和解释。R语言作为一种强大的统计分析工具,被广泛应用于生物信息学领域。本文将介绍R语言在生物信息学中的应用,包括基因组学、转录组学、蛋白质组学、代谢组学等方面,帮助读者了解R语言在生物信息学中的重要性和应用前景。
545 2
|
机器学习/深度学习 数据可视化 数据挖掘
R语言包管理:如何使用CRAN与Bioconductor
【8月更文挑战第28天】CRAN和Bioconductor是R语言包的两个重要来源,分别覆盖了广泛的科学计算和生物信息学领域。通过掌握CRAN和Bioconductor的包管理技巧,用户可以更加高效地利用R语言进行数据分析、统计建模和生物信息学研究。在实际应用中,建议根据具体需求选择合适的包,并合理设置镜像站点以提高下载速度。同时,定期更新和卸载不再需要的包,有助于保持R环境的整洁和高效。
|
数据采集 SQL 关系型数据库
Python学习路线【对标大厂Python开发工程师的招聘要求,并推荐优质免费资源】打卡学习不迷茫
Python学习路线【对标大厂Python开发工程师的招聘要求,并推荐优质免费资源】打卡学习不迷茫
395 14
|
Web App开发 弹性计算 运维
快速部署1Panel运维面板
1Panel是一款Linux服务器管理面板,提供Web界面进行主机监控、文件、数据库和容器管理。本文介绍如何通过计算巢快速部署1Panel面板。
快速部署1Panel运维面板